科技论文发表基于Hadoop的并行聚类算法的研究

来源：职称驿站所属分类：计算机应用论文
发布时间：2015-04-15浏览：35次

　　摘要：本文介绍了Hadoop平台下MapReduce的并行编程框架，分析了传统Kmeans聚类算法的优缺点，提出基于Canopy的Canopy-Kmeans聚类算法。使用Canopy聚类先对数据进行“粗”聚类，以优化Kmeans聚类算法初始聚类中心的选取。选用MapReduce并行编程方法。实验表明该方法相对于传统Kmeans聚类算法有着更高的计算效率。

　　关键词：科技论文发表,Hadoop,MapReduce,聚类,Canopy-Kmeans算法

　　Hadoop[1]是一种开源式的分布式平台，由它的分布式文件系统(HDFS)和MapReduce编程模型组成，这是Hadoop的核心。Kmeans算法[2]是被广泛使用的经典的聚类算法之一，思想简单，收敛速度快，而且易于实现，但是要先确立初始聚类中心，容易受主观因素的影响而造成聚类结果的局部最优。为解决该问题，本文引入Canopy对算法初始中心点的选取进行优化处理。

　　1 MapReduce并行编程模型

　　MapReduce是现在各种云计算平台的基础模型。此模型的核心是Map和Reduce函数，他们都可以高度并行运行。Map函数可以处理多组数据，把一对KeyValue对映射成新的KeyValue对，Reduce的输入数据为Map函数的输出数据。由并发Reduce函数来确保所有映射KeyValue对中的每组都有相等的Key键值[3]。MapReduce的运行机制是将大数据集分解成为许多小数据集splits，每个数据集分别由集群中的一个节点执行Map过程并生成中间结果。接着这些中间结果被大批的并行执行的 Reduce过程做相应的处理，从而产生最终结果，输出给用户[4]。

　　2 Canopy-Kmeans算法

　　2.1 算法的思想

　　Canopy-Kmeans算法采用Canopy进行初始聚类中心点的优化。数据子集分别分布在集群中的各个不同的站点。在Map阶段引用Canopy算法迅速地产生多个局部Canopy中心，各站点传来的局部Canopy中心在Reduce阶段被再次利用 Canopy算法得到全局的canopy中心集合。与Map阶段不同的是可对阈值t1、t2(t1>t2)进行重置。意思是Reduce阶段的阈值可与Map阶段的不同，以便能得到下步Kmeans所需的k个初始聚类中心。

　　2.2 基于MapReduce的Canopy-Kmeans算法

　　在基于Hadoop的并行Kmeans算法的基础上，本文使用Canopy算法对Kmeans 算法进行优化。Canopy-Kmeans算法包括两部分：Canopy生成中心点算法和Kmeans算法。Canopy中心点的生成过程包括Map和Reduce函数。算法实现需四个阶段，分别用四个Job实现。如图1所示。Job1生成k个canopy中心。Job2借助Job1阶段的k个canopy中心点来生成k个相互重叠的canopy。Job3对处于同一canopy内的数据集进行K-means聚类。通过多次的迭代，生成稳定的Kmeans聚类中心。最后，Job4使用稳定的Kmeans聚类中心点开始聚类。直到输出最终结果。

　　图1 Canopy-Kmeans 实现流程

　　3 算法时间复杂度分析

　　传统的Kmeans算法的时间复杂度为O(nck)。其中n为数据对象数量，c为迭代次数，k为类数量。该文引入Canopy聚类，产生k个canopy，每一个数据对象有可能同时属于q(q≤k)个canopy。当集群数量为p时，可知算法的时间复杂度为O(ncq2k/p)。可以看出该算法的时间复杂度与传统的Kmeans时间复杂度相比明显降低了。

　　4 实验与结果分析

　　4.1 数据集和实验环境

　　实验数据是从UCI机器学习库中选取的部分数据集，如表1所示。这些标准数据集用以准确度量本文算法的聚类效果。

　　表1 实验数据集

　　数据集样本数属性数类别数

　　Synthetic_Control 600 60 6

　　Segmentation 2310 18 7

　　Waveform-40 5000 40 3

　　Hadoop为开发平台，运用MapReduce编程框架完成实验。本实验是在5台VMWare平台下的虚拟机搭建成的Hadoop集群环境中完成，实验由5台PC机构成，其中一台作为主节点，剩余四台作为从节点。

　　4.2 实验结果及分析

　　将本文算法与MapReduce框架下的Kmeans聚类(算法a)、Weka环境下的串行Kmeans聚类(算法b)做比较。实验结果如表2所示。实验结果表明，算法a、b的正确率和误差平方和相对接近，可以看出该算法的聚类效果明显更好。

　　表2 实验结果

　　数据集算法a 算法b 本文算法

　　正确率/(%) 误差平方和迭代时间/ms 正确率/(%) 误差平方和迭代时间/ms 正确率/(%) 误差平方和 Canopy聚类时间/ms 迭代时间/ms

　　Synthetic_Control 66.9 600.07 191543 64.8 604.65 10948 71.35 533.54 18945 173475

　　Segmentation 56.70 606.07 203762 54.9 607.20 11693 65.21 390.65 19715 145665

　　Waveform-40 61.83 530.32 998557 59.1 540.74 10946 69.36 490.97 94810 564431

　　从算法的迭代时间来看，算法a的迭代时间比本文算法的迭代时间要长。这说明本文在引进Canopy聚类后。大大减少了每次迭代中的计算量，降低了运行时间。

　　5 结束语

　　针对大规模数据聚类的问题。本文提出了基于Map Reduce的并行化Canopy-Kmeans算法。对Kmeans聚类算法的优化确实避免了传统Kmeans算法的缺陷，明显降低时间复杂度，减少了计算量，提高聚类效率。MapReduce是目前主流的并行编程模型，但该模型本身存在一些局限性。最新的并行计算框架Prlter，Spark等对MapReduce进行了改进，怎么在最新的并行计算框架上对算法进行并行化设计和实现需要做进一步的实践。

　　参考文献：

　　[1]陆嘉恒.Hadoop实战[M].北京：机械工业出版社，2012.

　　[2]李应安.基于MapReduce聚类算法的并行化研究[D].中山大学，2010.

　　[3]张石磊，武装.一种基于Hadoop云计算平台的聚类算法优化的研究[J].计算机科学，2012(10)：114-118.

　　[4]赖玉霞，刘建平.K-means算法的初始聚类中心的优化[J].计算机工程应用，2008(10)：147-149.

　　作者简介：崔莉霞(1989-)，女，甘肃会宁人，硕士研究生，主要研究方向：数据挖掘、并行分布式计算。

《科技论文发表基于Hadoop的并行聚类算法的研究》

本文由职称驿站首发，您身边的高端学术顾问

文章名称：科技论文发表基于Hadoop的并行聚类算法的研究

文章地址： https://m.zhichengyz.com/p-28326

免费咨询获取帮助

上一篇：BIM应用下项目主体间信任和被信任感对合作创新绩效的影响研究