胡 健,刘祥敏,毛伊敏+,陈志刚

(1.江西理工大学 信息工程学院,江西 赣州 341000;2.赣南科技学院 信息工程学院,江西 赣州 341000;3.中南大学 计算机学院,湖南 长沙 410000)

1 问题的提出

聚类分析[1]作为一种无监督学习,在数据挖掘和机器学习领域中扮演着至关重要的角色,它根据数据对象的特征对数据集进行聚类,使类内相似度最大化、类间相似性最小化,从而发现对象间的内在联系,获取蕴藏在数据背后的价值。然而,随着大数据时代的来临,爆炸式增长的数据使得传统聚类算法的计算性能瓶颈愈加突出,这严重制约了聚类算法在大数据集上的应用。因此,如何降低大数据环境下聚类算法的计算开销成为了一个具有挑战性的问题。

近年来,随着MapReduce并行计算模型以及Hadoop、Spark[2-4]等大数据分布式并行计算框架的快速发展,聚类算法的并行化研究逐渐得到了广泛的关注,相关研究如表1所示。SREEDHAR等[5]设计了基于MapReduce框架的并行k-means算法KM-I2C,根据聚类间和聚类内相似性将不同聚类划分为子聚类,一定程度上提高了聚类精度,但未能合理地调度map和reduce作业从而容易出现节点负载不均衡。针对此问题,文献[6]引入池塘采样方法以等概率采样输出中间数据,然后采用第一自适应调度,将中间数据合理地放入节点,有效地解决了负载不均衡的问题。但该算法对质心的初始化可能存在局部最优问题。为此,文献[7]先初始化随机抽样,然后并行化距离计算过程,最后并行执行聚类分析,该算法处理大规模数据时具有良好的收敛性和较高的聚类精度,但在处理高维数据时仍然存在问题,且聚类精度有待提升。……