张 晓，王 红

(1.山东师范大学信息科学与工程学院，山东 济南 250014;2.山东省分布式计算机软件重点实验室，山东 济南 250014)

一种改进的基于大数据集的混合聚类算法*

张 晓，王 红

(1.山东师范大学信息科学与工程学院，山东 济南 250014;2.山东省分布式计算机软件重点实验室，山东 济南 250014)

针对k-means算法过度依赖初始聚类中心、收敛速度慢等局限性及其在处理海量数据时存在的内存不足问题，提出一种新的针对大数据集的混合聚类算法super-k-means，将改进的基于超网络的高维数据聚类算法与k-means相结合，并经过MapReduce并行化后部署在Hadoop集群上运行。实验表明，该算法不仅在收敛性以及聚类精度两方面得到优化，其加速比和扩展性也有了大幅度的改善。

k-means；超网络；频繁项集；超图划分；MapReduce

1 引言

大数据聚类是当前聚类研究的重点。在海量数据的聚类中，现有的聚类算法在时间复杂性和空间复杂性上都存在一定的局限，解决这个问题的一种途径就是引用并行处理技术，设计出高效的并行聚类算法，来提高算法性能。目前，MapReduce是最主流且实用的并行化模型。

k-means算法是传统的经典聚类算法，但是该算法对初始值具有很强的依赖性[1]，即算法的鲁棒性不高。此外，k-means算法在串行计算方法中的时间复杂度比较高，处理能力难以满足需求。目前，对与k-means算法相结合的混合聚类算法及其并行化方面已经取得了较为理想的研究成果。赖玉霞等人[2]提出的一种优化的基于密度的算法有效地解决了k-means算法过度依赖初始值的问题。……