摘 要：本文介绍了Hadoop平台下MapReduce的并行编程框架，分析了传统Kmeans聚类算法的优缺点，提出基于Canopy的Canopy-Kmeans聚类算法。使用Canopy聚类先对数据进行“粗”聚类，以优化Kmeans聚类算法初始聚类中心的选取。选用MapReduce并行编程方法。实验表明该方法相对于传统Kmeans聚类算法有着更高的计算效率。
关键词：Hadoop；MapReduce；聚类；Canopy-Kmeans算法
中图分类号：TP391.1
1 MapReduce并行编程模型
MapReduce是现在各种云计算平台的基础模型。此模型的核心是Map和Reduce函数，他们都可以高度并行运行。Map函数可以处理多组数据，把一对Key＼Value对映射成新的Key＼Value对，Reduce的输入数据为Map函数的输出数据。由并发Reduce函数来确保所有映射Key＼Value对中的每组都有相等的Key键值[3]。MapReduce的运行机制是将大数据集分解成为许多小数据集splits，每个数据集分别由集群中的一个节点执行Map过程并生成中间结果。接着这些中间结果被大批的并行执行的 Reduce过程做相应的处理，从而产生最终结果，输出给用户[4]。
2 Canopy-Kmeans算法
2.1 算法的思想
2.2 基于MapReduce的Canopy-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
从算法的迭代时间来看，算法a的迭代时间比本文算法的迭代时间要长。这说明本文在引进Canopy聚类后。大大减少了每次迭代中的计算量，降低了运行时间。
5 结束语
针对大规模数据聚类的问题。本文提出了基于Map Reduce的并行化Canopy-Kmeans算法。对Kmeans聚类算法的优化确实避免了传统Kmeans算法的缺陷，明显降低时间复杂度，减少了计算量，提高聚类效率。MapReduce是目前主流的并行编程模型，但该模型本身存在一些局限性。最新的并行计算框架Prlter，Spark等对MapReduce进行了改进，怎么在最新的并行计算框架上对算法进行并行化设计和实现需要做进一步的实践。
参考文献：
[2]李应安.基于MapReduce聚类算法的并行化研究[D].中山大学，2010.
[3]张石磊，武装.一种基于Hadoop云计算平台的聚类算法优化的研究[J].计算机科学，2012
（10）：114-118.
[4]赖玉霞，刘建平.K-means算法的初始聚类中心的优化[J].计算机工程应用，2008
（10）：147-149.
