刘宝龙，苏 金

(西安工业大学 计算机科学与工程学院，西安 710021)



双MapReduce改进的Canopy-Kmeans算法

刘宝龙，苏 金

(西安工业大学 计算机科学与工程学院，西安 710021)

由于传统的Canopy-Kmeans算法在中心点的选取存在随机性，其迭代过程的冗余计算降低了算法的运行效率.文中基于“最小最大原则”和三角不等式原理，在Hadoop平台上提出了一种基于双MapReduce改进的Canopy-Kmeans算法.实验结果表明：设计的并行算法精确率在不同大小的数据集上平均提高了15.3%，加速比和扩展性随着数据规模和节点的不断增加也相应的提高了1.5～3倍，解决了Canopy中心点选中存在的问题和迭代过程中冗余的距离计算.

Canopy-Kmeans；冗余计算；Hadoop平台；双MapReduce

常用的K-means算法是一种基于划分的聚类挖掘算法，该算法的思路简单、收敛速度快，使用广泛且易于实现，但在K值及中心点的选取上仍然存在很大的随机性和不科学性，容易使聚类结果陷入局部最优，且在迭代过程中存在大量的冗余计算，并行处理能力差，缺乏可伸缩性，大大降低了算法的运行效率.文献[1]针对传统的K-means算法提出了Canopy改进策略，避免了K值选取的盲目性，进一步提高聚类算法的准确率和稳定性.文献[2-3]应用三角不等式原理对传统的K-means算法进行了改进，避免了算法中冗余计算，提高了收敛速度和降低了内存开销，但并行性不高，缺乏扩展性.文献[4]提出了K-meansCan算法，其先对数据进行多次随机采样，再进行K-means预聚类，然后将来自不同簇的聚类点进行合并，最终实现聚类，在很大程度上提高了聚类……