基于MapReduce的并行子空间聚类算法

摘要

With the data volume we create growing fast,the problem of subspace clustering of very large scale moderate-to-high dimensional dataset becomes highly important.But most subspace clustering methods can't efficiently solve this problem due to serial processing on single machine.Thus,Sample-Ignore Subspace Clustering using MapReduce(SISCMR) was proposed that can effectively solve this question.SISCMR has a great adaptability as it can use most serial clustering methods as a plugged-in clustering subroutine.Through many experiments on real and synthetic data with billions of points,it's proved with good clustering quality,near-linear scalability and high efficiency.Using 128 cores,it only took 10 minutes to cluster one of our biggest experiment dataset with 0.2 TB volume,which proves the feasibility of parallel clustering using MapReduce.%随着现有数据体量的迅速增长,超大规模中高维数据集的聚类问题变得越来越重要;而现有的子空间聚类算法大多是单机串行执行,处理此类问题效率极低.讨论了利用MapReduce对这类数据集进行并行聚类的方法,提出了基于MapRe-duce的抽样-忽略子空间聚类算法(sample-ignore subspace clustering using MapReduce,SISCMR).该算法将串行聚类算法用作插件,具有很好的通用性.在人造和真实数据集上进行了大量实验,其中最大为0.2 TB的数据集在128个核心的集群中仅用不到10 min就完成了聚类,验证了该算法良好的聚类质量、近线性的可扩展性和高效的聚类性能,证明了基于MapReduce的并行聚类的可行性.