基于MapReduce的CLOPE并行聚类算法

事务型数据的CLOPE聚类算法在运行速度、内存开销和聚类效果方面表现优异,但随着数据量飞速增长,其运行时间也随之急剧变长甚至无法使用。为此,利用Hadoop框架下的YARN资源管理系统,对CLOPE算法进行改进,提出基于MapReduce架构的CLOPE并行聚类算法。该算法由两个阶段组成,第一阶段执行Map操作,Hadoop架构对数据集分片并行并运行CLOPE算法聚类成小聚簇;第二阶段执行Reduce操作,通过多次迭代把各个小聚簇聚合成大聚簇。实验结果证明：分析1 000条20 000个属性的亚马逊数据记录,MapReduce-CLOPE算法耗时稳定在22 s,而CLOPE算法耗时在50-60 s。随着数据量的增大,CLOPE算法无法计算而MapReduce-CLOPE算法耗时基本稳定。因此,MapReduce-CLOPE算法在计算时间方面要显著地优于CLOPE算法,且计算时间受数据量大小的影响较小,而在聚类质量方面与CLOPE算法相近。

一种分类数据聚类算法及其高效并行实现

针对大规模、高维、稀疏的分类数据聚类,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算法执行时间更短;计算资源充足时,随机顺序的数据集份数越多,执行时间的提升越明显。

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

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