面向大数据的并行聚类算法

刘解放，张志辉

(1.湖北交通职业技术学院 交通信息学院，湖北 武汉 430079； 2.武汉科技大学 计算机科学与技术学院，湖北 武汉 430081)

0 引 言

大数据对社会具有潜在价值，它正在推动行业研究人员重新思考计算方案来获取有用信息。但由于高计算成本，使得分析和检索操作非常耗时。因此，高性能计算，如并行计算[1]、分布式计算[2]、云计算[3]和网格计算[4]等无疑是未来解决上述问题的重要手段。

聚类本质上是一种典型的“无监督”数据分析方法，但到目前为止，已提出的所有经典算法都需要用户的大量指导，例如K-means需要预先指定聚类个数和终止条件。最近提出的CLUBS[5]，是一种非常有效的聚类算法，无需用户任何指导，通过4个阶段的不断完善，自动完成聚类任务。它不但能够容忍一定程度的过度分割，而且能够处理异常点的检测及椭圆簇的生成。遗憾的是，该算法针对大数据应用场景无能为力。

本文结合高性能计算提出了CLUBS的并行版本，称为CLUBS‖，类似CLUBS，CLUBS‖时间复杂度关于数据集大小线性缩放，并基于Ad-hoc消息传递实现了所提聚类算法。实验结果表明，随着越来越多的并行节点加入运算，加速比几乎是线性的。CLUBS‖的特性使它可以有效聚类大规模数据，且不要求节点间交换原始数据，仅需交换摘要信息。

1 相关工作

大数据的出现重新激发了研究人员对数据挖掘基础工具的兴趣，例如聚类。为克服聚类的计算复杂度，研究人员已经提出许多方法，无论是单机还是联机方案。

单机版的大数据聚类经典方法大都基于采样、降维和分块技术，例如，文献[6]提出了一种基于加速比和势分布的采样方法，通过使用采样技术减少求解搜索空间，极大地提高了大数据处理的性能；……