一种大规模分类数据聚类算法及其并行实现

来源：计算机研究与发展杂志2016年第5期北京时间：

作者：丁祥武,郭涛,王梅,金冉,

摘要：CLOPE算法在大规模、稀疏、高维的分类数据集的聚类上取得了很好的聚类效果.然而该算法受输入数据的顺序影响，难以获得稳定且全局最优的聚类结果.因此提出一种基于等分划分再排列思想的p-CLOPE算法对这一缺陷进行改进.在p-CLOPE算法的每一轮迭代过程中，对输入数据集等分为p部分再排列生成不同顺序的p!份数据集，对这些数据集分别聚类并选取最优的聚类结果作为下一轮迭代的输入.为了降低上述过程的时间复杂度，提出了一种中间结果复用策略，较大程度地提高了聚类速度.最后，在Hadoop平台上实现了一个包含p-CLOPE相关算法的开源聚类工具.实验表明：p-CLOPE算法比CLOPE算法取得了更优的聚类结果.对蘑菇数据集，当CLOPE算法取得最优聚类结果时，p-CLOPE比CLOPE取得了高35.7%的收益值；在处理大量数据时，并行p-CLOPE比串行p-CLOPE极大地缩短了聚类时间，并在计算资源充足时，取得了接近p!倍的加速比.

关键词：分类数据, CLOPE, p-CLOPE, 并行聚类, MapReduce,