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

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算法相比于传统的聚类算法在聚类质量及运行速度上都有很大的提升。然而CLOPE算法存在聚类的质量不稳定、没有区分每维属性对聚类的贡献度、需要预先指定排斥因子r等问题。为此,提出基于随机顺序迭代和属性加权的分类数据聚类算法(RW-CLOPE)。该算法利用"洗牌"模型对原始数据进行随机排序以排除数据输入顺序对聚类质量的影响。同时,根据信息熵计算各个属性的权重,以区别每维属性对聚类的贡献度,极大地提升了数据聚类的质量。最后,在高效的集群平台Spark上,实现了RW-CLOPE算法。在三个真实数据集上的实验结果表明:在数据集乱序后的份数相同时,RW-CLOPE算法比p-CLOPE算法取得更好的聚类质量。对蘑菇数据集,当CLOPE算法取得最优聚类结果时,RW-CLOPE比CLOPE取得高68%的收益值,比p-CLOPE取得高25%的收益值;针对大量数据,基于Spark的RW-CLOPE算法比基于Hadoop的p-CLOPE算法执行时间更短;计算资源充足时,随机顺序的数据集份数越多,执行时间的提升越明显。