基于云计算的大数据挖掘平台
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于云计算的大数据挖掘平台范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：开发了一个基于云计算的并行分布式大数据挖掘平台——PDMiner。PDMiner实现了各种并行数据挖掘算法，如数据预处理、关联规则分析以及分类、聚类等算法。实验结果表明，并行分布式数据挖掘平台PDMiner中实现的并行算法，能够处理大规模数据集，达到太字节级；具有很好的加速比性能；实现的并行算法可以在商用机器构建的并行平台上稳定运行，整合了已有的计算资源，提高了计算资源的利用效率；可以有效地应用到实际海量数据挖掘中。在PDMiner中还开发了工作流子系统，提供友好统一的接口界面方便用户定义数据挖掘任务。
关键词： 云计算；分布式并行数据挖掘；海量数据
Abstract： In this paper， we develop a parallel and distributed data mining toolkit platform called PDMiner. This platform is based on cloud computing. PDMiner is used to preprocess data， analyze association rules， and parallel classification and clustering. Our experimental results show that the parallel algorithms in PDMiner can tackle data sets up to one terabyte. They are very efficient because they have good speedup， and they are easily extended so that they can be executed in a cluster of commodity machines. This means that full use is made of computing resources. The algorithms are also efficient for practical data mining. We also develop a knowledge flow subsystem that helps the user define a data mining task in PDMiner.
Key words： cloud computing； parallel and distributed data mining； big data
中图分类号：TN915.03； TP393.03 文献标志码：A 文章编号：1009-6868 （2013） 04-0032-007
随着物联网、移动通信、移动互联网和数据自动采集技术的飞速发展以及在各行各业的广泛应用，人类社会所拥有的数据面临着前所未有的爆炸式增长。美国互联网数据中心指出，互联网上的数据每年以50%的速度增长，每两年翻一番，而目前世界上90%以上的数据是最近几年才产生的，人类社会进入了“大数据”时代。因此，信息的获取非常重要，一定程度上，信息的拥有量已经成为决定和制约社会发展的重要因素。
数据挖掘作为信息获取的一门重要技术，得到了广泛的研究。数据挖掘[1]从大量的数据中挖掘出有用的信息，提供给决策者做决策支持，有着广阔的应用前景。由于要挖掘的信息源中的数据都是海量的，而且以指数级增长，传统的集中式串行数据挖掘方法不再是一种适当的信息获取方式。因此扩展数据挖掘算法处理大规模数据的能力，并提高运行速度和执行效率，已经成了一个不可忽视的问题。
为了解决海量数据的挖掘问题，一种简单的方式就是把所有的数据划分成若干份，也就是切分成若干个子任务，然后分布到各个计算资源上去进行计算，每个节点完成一个子任务，最后进行集成。分布式计算就是把一个计算问题分解成多个子问题并同时处理的计算模型。基于分布式计算模型，Luo等人[2-4]集成了很多数据挖掘算法到多主体系统。另外一种提高计算效率的方式是并行计算，并行计算也是把一个大的计算问题分割成小任务的形式。近年来，并行计算的体系结构和模型也引起了广泛的兴趣和研究[5-6]。
尽管分布式计算和并行计算有很相似的特点，但是它们之间各有侧重，分布式计算强调在所有异构计算资源上同时求解问题，而并行计算则更加强调同一台计算资源内部多线程并行。这两种计算方式可以对应到算法之间的并行以及算法内部并行这两种计算模式。文献[2-4]提出基于主体技术的算法之间并行的计算模式，他们利用主体技术中主体本身的自主性、智能性等特点，实现不同算法主体之间的并行计算，以消息传递的方式实现同步，大大提高了算法的执行效率，减少了运行时间。第二种计算模式，是粒度比较小的并行方式，主要研究的是算法内部的并行。通过把算法分解，尽可能地找出算法中可并行的部分进行并行计算。这种计算模型的最终效率取决于算法本身的可并行程度，如果并行程度非常高，那么就可以大大提高算法的运行效率。由于在很多应用中，只需要执行一种应用（算法），所以研究算法内部的并行实现非常重要。文献[7]实现了多种机器学习算法在多核计算机上的并行，本文主要针对第二种并行计算模式进行研究，而且可以在大规模计算机集群上运行。
近年来，云计算得到了学术界和业界的广泛关注，它是一种基于互联网的、大众参与的计算模式，其计算资源，包括计算能力、存储能力、交互能力，是动态、可伸缩、且被虚拟化的，以服务的方式提供给用户。基于大规模数据处理平台——Hadoop，我们研究开发了并行分布式数据挖掘平台——PDMiner，其目的是设计实现并行数据挖掘算法处理大数据集，且提高执行效率。在PDMiner中包含4个子系统，工作流子系统、用户接口子系统、数据预处理子系统和数据挖掘子系统。整个数据挖掘平台提供了一个从海量数据中挖掘有用知识的完整解决方案，而且提供了可扩展的灵活接口。
1 大规模数据处理平台
——Hadoop
Hadoop是一个软件计算平台，可以让程序员很容易地开发和运行处理海量数据的应用程序。其核心部分包括HDFS[8]和基于MapReduce[9-10]机制的并行算法实现。
1.1 HDFS
Hadoop分布式文件系统HDFS是受Google文件系统启发，建立在大型集群上可靠存储大数据集的文件系统。它和现有的分布式文件系统有着很多的相似性，然而和其他的分布式文件系统的区别也是很明显的。HDFS具有高容错性，可以部署在低成本的硬件之上。此外，HDFS提供高吞吐量地对应用程序数据的访问，适合大数据集的应用程序。
HDFS结构包含一个名字节点作为控制主节点，其他的服务器作为数据节点，存储数据。具体地说，HDFS具有如下几大特点：
（1）强容错性
HDFS通过在名字节点和数据节点之间维持心跳检测、检测文件块的完整性、保持集群负载均衡等手段使得系统具有高容错性，集群里个别机器故障将不会影响到数据的使用。
（2）流式数据访问与大数据集
运行在HDFS之上的应用程序必须流式地访问它们的数据集。HDFS适合批量处理数据，典型的HDFS文件是吉字节到太字节的大小，典型的块大小是64 MB。
（3）硬件和操作系统的异构性
HDFS的跨平台能力毋庸置疑，得益于Java平台已经封装好的文件IO系统，HDFS可以在不同的操作系统和计算机上实现同样的客户端和服务端程序。
1.2 MapReduce
MapReduce是Google实验室提出的一种简化的分布式程序设计模型，用于处理和生成大量数据集。通过该模型，程序自动分布到一个由普通机器组成的超大机群上并发执行。
Map和Reduce是该模型中的两大基本操作。其中，Map是把一组数据一对一的映射为另外的一组数据，Reduce是对数据进行规约，映射规则与规约规则可由用户通过函数来分别指定。现实生活中很多任务的实现都是可以基于类似这样的映射规约模式。
MapReduce通过把对数据集的大规模操作分发给网络上的每个节点来实现可靠性，每个节点会周期性地把完成的工作和状态信息返回给主节点。如果一个节点保持沉默超过一个预设的时间间隔，主节点就认为该节点失效了，并把分配给这个节点的数据发到别的节点，并且因此可以被其他节点所调度执行。
由于MapReduce运行系统已考虑到了输入数据划分、节点失效处理、节点之间所需通信等各个细节，使得程序员可以不需要有什么并发处理或者分布式系统的经验，就可以处理超大规模的分布式系统资源。
2 并行分布式大数据挖掘
平台体系架构
Hadoop提供了让程序员易于开发和运行处理海量数据应用程序的平台，其分布式文件系统HDFS是建立在大型集群上可靠存储大数据集的文件系统，具有可靠性，强容错性等特点；MapReduce提供了一种高效编写并行程序的编程模式。基于此，我们开发了并行数据挖掘平台——PDMiner，大规模数据存储在HDFS上，且通过MapReduce实现各种并行数据预处理和数据挖掘算法。
PDMiner是一个集成各种并行算法的数据挖掘平台，其中的并行计算模式不仅包括算法之间的并行，而且包括算法内部的并行。图1给出了并行数据挖掘平台PDMiner的总体系统架构，其中主要包括4个子系统：工作流子系统、用户接口子系统、并行抽取转换装载（ETL）子系统以及并行数据挖掘子系统。工作流子系统提供了友好的界面方便用户定义各种数据挖掘任务；用户接口可以对算法的参数进行设置以及通过结果展示模块分析挖掘结果并做出相应的决策；并行ETL算法子系统和并行数据挖掘算法子系统是PDMiner的核心部分，它们可以直接对存储在HDFS系统上的数据进行处理，ETL算法处理后的结果也可以作为数据挖掘算法的输入。
2.1 工作流子系统
工作流子系统提供了友好和统一的用户接口（UI），使得用户可以方便地建立数据挖掘任务。在创建挖掘任务过程中，可以选择ETL数据预处理算法、分类算法、聚类算法、以及关联规则算法等，右边下拉框可以选择服务单元的具体算法。工作流子系统通过图形化UI界面为用户提供服务，灵活建立符合业务应用工作流程的自定制挖掘任务。通过工作流界面，可以建立多个工作流任务，不仅每个挖掘任务内部并行，而且不同数据挖掘任务之间也并行。
2.2 用户接口子系统
用户接口子系统由2个模块组成：用户输入模块、结果展示模块。用户接口子系统负责与用户交互，读写参数设置，接受用户操作请求，根据接口实现结果展示。比如并行分类算法中并行朴素贝叶斯算法的参数设置界面如图2所示，从图中看到可以方便地设置算法的参数。这些参数包括训练数据、测试数据、输出结果以及模型文件的存储路径，而且还包括Map和Reduce任务个数的设置。结果展示部分实现了结果可视化理解，比如生成直方图、饼图等。
2.3 并行ETL算法子系统
数据预处理算法在数据挖掘中起着非常重要的作用，其输出通常是数据挖掘算法的输入。由于数据量的剧增，串行数据预处理过程需要消耗大量的时间来完成操作过程，因此为了提高预处理算法的执行效率，在并行ETL算法子系统中设计开发了19种预处理算法[11]，如图3所示，包括并行采样Sampling、并行数据预览PDPreview、并行数据添加标签PDAddLabel、并行离散化Discretize、并行增加样本ID、并行属换AttributeExchange、并行布尔型数据到系列数据的转换BoolToSerialNum、并行数据归一化Normalize、并行属性约简PCA、并行数据集成DataIntegration、并行统计Statistic、并行属性约简AttributeReduction、并行数据区间化Intervalize、并行冗余数据删除RedundancyRemove、并行属性添加AttributeAdd、并行属性修改AttributeModify、并行数据缺失值替换ReplaceMissingValues、并行属性删除AttributeDel，以及并行属性选择AttributeSelection等。
通常ETL操作都具有很高的并行化程度，比如属性的删除，可以把数据划分成很多块，算法对每个数据块的处理都是相对独立的，因此并行ETL子系统中实现的并行ETL算法具有很好的加速比，大大提高了算法的运行速度和执行效率。
2.4 并行数据挖掘子系统
并行数据挖掘子系统是并行数据挖掘平台PDMiner的核心部分，主要包括了三大类算法：并行关联规则算法、并行分类算法[12]以及并行聚类算法等。
目前该并行数据挖掘子系统中已经开发了很多经典的数据挖掘算法，各类并行算法模块包含的算法如图4、图5、图6所示，其中并行关联规则算法包括并行Apriori算法[13]，并行FP树FPgrowth以及并行Awfits算法；并行分类算法包括并行超曲面分类算法HSC、并行k近邻算法Knn、并行朴素贝叶斯算法NaiveBayes，并行决策树算法C4.5、并行基于范例推理算法CBR、并行基于类中心算法CBC以及并行极限向量机ESVM等；并行聚类算法包括并行DBScan算法，并行Clara算法[14]、并行k均值算法Kmeans[15-16]以及并行EM算法等。
执行数据挖掘算法的一般流程如图7所示。从算法流程来看，PDMiner是一个用户友好的系统，用户不用了解底层算法的设计和实现，就可以很容易使用系统。另外对于并行ETL子系统和并行数据挖掘子系统，还提供灵活的接口方便用户集成新的算法。
2.5 基于MapReduce实现的算法实例
下面以决策树为例描述基于MapReduce的并行算法的实现过程。决策树算法是利用已标记训练集建立决策树模型，然后利用生成的决策树对输入测试数据进行分类。在以前的很多工作，主要是把数据划分到多个计算节点上，然后各自建立决策树模型，最后采用集成的方式得到最终模型[17]。采用MapReduce机制可以很好地解决决策树算法内部的并行问题，提高算法的执行效率以及处理数据的规模。
图8给出了并行决策树算法的流程图。在该并行算法中，实现了同一层内节点之间、节点内的并行计算，提高算法的执行效率。更重要的是，实现的并行决策树算法以循环代替了递归，使得运行完程序所需要的最大作业（Job）个数可预测（最大数目为样本集中条件属性的数目 ），从而有利于控制程序的执行状态。而在递归中，无法预测还有多少节点要运算，这样就无法预测程序何时结束。由于层与层之间的运算是串行的，因此在基于MapReduce机制的并行决策树实现中，上一层都会传递前缀信息给下一层节点，这些前缀包括从根节点到当前分支的分裂属性信息等。
从流程图可以看到每一层只需要一个Job，而不关心有多少个节点。程序需要运行的最大层数由条件属性的个数决定，因此是可控制的。由于在并行的过程中主要是统计频率，因此的设计非常重要，设置如下：在训练过程中，训练数据被划分到各个节点中进行运算，Map函数输入的分别设计为样本ID和样本本身；输出的，key设计为训练样本对应的类别+条件属性的名字+条件属性的值，value为key出现的次数。Reduce函数的输入和输出的的设计均为Map函数输出的。
当还有前缀的情况下，需要删除训练集中包含生成决策规则的样本，该过程是一个读写的过程。对于包含新得到的决策规则的样本，不再写入训练集，这样在下一次迭代中就只计算那些没有包含生成决策规则的样本。
测试过程则非常简单，每个Map利用已生成的决策树模型对样本进行预测，直接样本的预测标记，不需要Reduce过程。
3 PDMiner的特点
3.1 可扩展性
PDMiner是一个可扩展的并行分布式数据挖掘平台，我们为系统提供了灵活的接口来扩展集成新的并行算法。通过工作流子系统可以很方便地添加一个新的算法，比如在并行ETL子系统中添加新的算法PDAlgorithm1，则只要添加如下代码：
通过加入最后一行代码以后就可以在选项卡PD-Filters下面加入一项PDAlgorithm1。生成空类PDAlgorithm1的代码如下：
其中在函数listOptions（ ）、getOptions（ ）、setOptions（ ）中编写配置算法参数的代码，在run（ ）函数中编写调用Map函数和Reduce函数的代码，用户可以根据具体的算法编写相应的Map函数和Reduce函数。并行数据挖掘算法的添加与ETL算法的添加类似。
3.2 支持多挖掘任务
在PDMiner中，不仅支持单个任务的创建和执行，而且支持同时创建和运行多个数据挖掘任务。这些任务可以是不同类别的挖掘任务，比如并行关联规则任务、并行分类和聚类任务等，当配置完参数，这些任务可以同时在并行分布式系统PDMiner中执行。
支持多挖掘任务功能，具有非常重要的作用。比如要对所有的分类算法进行比较，从而选择对已有数据集表现最佳的算法。一般的做法是串行测试完所有的算法，然后根据算法的效果进行选择。而在PDMiner中可以并行地解决该问题，所有的算法都面向同一个数据集（读取同一个头文件信息），最后结果通过系统进行展示，从而选择最合适的算法。从这个比较机制看到，所有的并行算法都是在并行系统中执行，因此可以处理大规模数据；另外，这些算法的执行过程是并行的，评价过程是自动的，因此可以减少算法执行时间和用户的干预。
3.3 创建复杂挖掘过程
通过工作流子系统，系统还支持创建复杂挖掘任务，可以把并行数据预处理操作和并行数据挖掘算法串联起来。系统提供并行属性删除操作、并行数据归一化以及并行分类算法朴素贝叶斯的串联。当配置完所有算法参数后，其执行过程如下：
·执行属性删除操作，对数据集进行属性删除操作，并且修改头文件，生成新的头文件信息。
·接收属性删除后更新后的头文件，进行数据归一化操作。
·进行分类算法任务。接收从第二步传递过来的头文件信息，然后启动分类算法任务。当任务执行完后，对分类结果进行展示。
4 实验分析
并行分布式数据挖掘平台PDMiner是一个高效的数据处理与分析工具，主要面向海量数据集的处理。在保证算法正确性的情况下，构造大数据集来考察算法的性能。系统中开发的并行算法已经在通信领域的实际数据挖掘中应用，以下给出了一些算法在构造的大数据集上的性能测试结果。鉴于隐私性等原因，这里没有给出具体的并行算法名称。
图9、图10、图11、图12、图13给出了2个并行ETL算法和3个并行数据挖掘算法的时间性能。ETL测试的数据规模达到太字节级，而关联规则、分类算法、聚类算法的数据规模分别是30 GB级别、400 GB级别、12 GB级别。我们分别记录了32个节点，64个节点，128个节点的运行时间。若假设32节点执行的时间是标准的理想状态下的时间，图中红线部分给出了理想情况下64节点和128节点的时间性能。从这些图中，可以看到：
·通过增加节点，都可以提高算法的运算速度，较少执行时间。
·算法本身越简单，即并行成分也大，效果越明显，ETL算法显然具有较高的加速比，执行效率也比较高；这说明算法的并行效率与自身可并行化的程度有关。
·如图11所示，算法有时候可以得到线性加速比，说明该并行数据挖掘系统可以有效地利用计算资源。但我们也应该看到这种并行计算模型也不是万能的，增加节点并不能总是能很好地提高效果（如图13所示），有时甚至会由于并行通信而使效果变差。
5 结束语
针对大数据的处理和挖掘，本文开发设计了并行分布式数据挖掘平台——PDMiner。基于Hadoop平台和MapReduce的编程模式，开发实现了各种并行数据预处理操作以及并行数据挖掘算法，包括关联规则算法，分类算法以及聚类算法等。另外，PDMiner还开放了灵活的接口，方便集成新的ETL算法和数据挖掘算法。实验测试表明，开发的并行算法可以处理海量数据，且具有很好的加速比性能。
参考文献
[1] HAN J W， KAMBER M， PEI J. Data mining： Concepts and techniques [M]. 3rd ed. San Francisco， CA，USA： Morgan Kaufmann Publishers， 2011.
[2] LUO P， LU K， SHI Z Z， et al. Distributed data mining in grid computing environments [J]. Future Generation Computer Systems， 2007，23（1）：84-91.
[3] LUO P， LU K， HUANG R， et al. A heterogeneous computing system for data mining workflows in multi-agent environments [J]. Expert Systems， 2006，23（5）：258-272.
[4] ZHUANG F Z， HE Q， SHI Z Z. Multi-agent based on automatic evaluation system for classification algorithm [C]//Proceedings of the International Conference on Information and Automation（ICIA’08），Jun 20-23，2008， Zhangjiajie， China. Piscataway， NJ， USA：IEEE， 2008： 264-269.
[5] HAMEENANTTILA T， GUAN X L， CAROTHERS J D， et al. The flexible hypercube： A new fault-tolerant architecture for parallel computing [J]. Journal of Parallel and Distributed Computing， 1996，37（2）：213-220.
[6] GOUDREAU M W， LANG K， RAO S B， et al. Portable and efficient parallel computing using the BSP model [J]. IEEE Transactions on Computers， 1999，48（7）：670-689 .
[7] CHU C T， KIM S K， LIN Y A， et al. Map-reduce for machine learning on multicore [C]//Proceedings of the 21st Annual Conference on Neural Information Processing Systems （NIPS’07）， Dec 3-6，2007， Vancouver， Canada. Berlin， Germany： Springer-Verlag， 2007：281-288.
[8] BORTHAKUR D. The hadoop distributed file system： Architecture and design [R]. The Apache Software Foundation， 2007.
[9] DEAN J， GHEMAWAT S. MapReduce： Simplified data processing on large clusters [J]. Communications of the ACM， 2008，51（1）：107-113.
[10] 万至臻. 基于MapReduce模型的并行计算平台的设计与实现 [D]. 杭州： 浙江大学， 2008.
[11] HE Q， TAN Q， MA X D， et al. The High-activity parallel implementation of data preprocessing based on MapReduce [C]//Proceedings of the 5th International Conference on Rough Set and Knowledge Technology（RSKT’10）， Oct 15-17， 2010，Beijing， China. LNCS 6401. Berlin， Germany： Springer-Verlag， 2010：646-654.
[12] HE Q， ZHUANG F Z， LI J C， et al. Parallel implementation of classification algorithms based on MapReduce [C]//Proceedings of the 5th International Conference on Rough Set and Knowledge Technology（RSKT’10）， Oct 15-17， 2010， Beijing， China. LNCS 6401. Berlin， Germany： Springer-Verlag， 2010：655-662.
[13] LI N， ZENG L， HE Q， et al. Parallel implementation of apriori algorithm based on MapReduce [C]//Proceedings of the 13th ACIS International Conference on Software Engineering， Artificial Intelligence， Networking and Parallel Distributed Computing （SNPD’12）， Aug 8-12，2012， Kyoto， Japan. Piscataway， NJ，USA： IEEE， 2012：236-241.
[14] ZHAO W Z， MA H F， HE Q. Parallel K-means clustering based on MapReduce [C]//Proceedings of the1st International Conference on Cloud Computing（CloudCom’09）， Dec 1-4， 2009， Beijing， China. LNCS 5931. Berlin， Germany： Springer-Verlag， 2009：674-679.
[15] HE Q， WANG Q， ZHUANG F Z， et al. Parallel CLARANS clustering based on MapReduce [C]//Proceedings of the 3rd International Conference on Machine Learning and Computing （ICMLC’11）：Vol 6， Feb 26-28，2011，Singapore. Piscataway， NJ，USA： IEEE，2011： 236-240.
[16] HALL M， FRANK E， HOLMES G， et al. The WEKA data mining software： An update [J]. ACM SIGKDD Explorations Newsletter，2009，11（1）：10-18.
[17] 宋晓云， 苏宏升. 一种并行决策树学习算法研究 [J]. 现代电子技术， 2007，30（2）： 141-144.
作者简介
何清，中国科学院计算技术研究所研究员、博士生导师；主要研究领域为机器学习、数据挖掘、云计算、并行算法；已承担完成基金项目2项；已发表学术论文近100篇（其中SCI收录27篇，EI收录66篇）。
庄福振，中国科学院计算技术研究所助理研究员；主要研究领域为机器学习、数据挖掘、迁移学习、并行算法；已承担完成基金项目2项；已发表学术论文30余篇。