刘 燕

(山西大学 商务学院， 太原 030031)

引言

聚类是将物理或抽象的对象分成相似对象集合的过程，簇是数据对象的集合，同一簇中的对象特征相似，而与其它簇中的对象却彼此相异[1]。聚类分析在数据挖掘、模式识别、文本分析、图形处理、市场研究等诸多领域应用广泛。作为一种获得广泛应用的经典聚类划分算法，K-means算法具有算法数学思想清晰且易于实现、收敛速度快等优势[2]，但是需要事先指定初始聚类中心的个数k值，而且由于中心点选取的随机性而容易陷入局部最优解。

随着数据库和网络技术的快速发展，生成的数据呈海量增长，传统的聚类算法很难满足时下的数据分析处理需求。2004年，Google公司研发了一个称为Hadoop的开源MapReduce并行计算框架和系统，给大数据并行处理带来了重大的影响，现已成为迄今为止易于使用、广为接受的业界主流大数据并行处理技术。因此，许多学者运用MapReduce模型陆续展开了有关海量数据的聚类研究。江小平等人[3]提出了一种基于MapReduce的并行K-means聚类算法，该算法的执行效率较高，但由于K-means算法在收敛前需要进行多次迭代计算，不断地重启计算任务及读取原始数据集，因此造成更多的I/O开销。毛典辉[4]提出的基于MapReduce的Canopy-Kmeans改进算法，采用最大最小原则对该算法进行改进。虞倩倩等人[5]提出了基于MapReduce的ACO-Kmeans并行聚类算法，针对K-means聚类算法处理海量数据时存在的内存不足等问题，研究了利用MapReduce实现K-means聚类算法的并行化。

综上这些算法很好地解决了传统K-means算法处理海量数据的一些不足，但是仍存在聚类效果不稳定、准确率不高，也未能充分考虑算法执行过程中的计算量以及通信代价等问题。……