基于MapReduce的分布式近邻传播聚类算法

Distributed Affinity Propagation Clustering Based on MapReduce

随着信息技术迅速发展,数据规模急剧增长,大规模数据处理非常具有挑战性.许多并行算法已被提出,如基于MapReduce的分布式K平均聚类算法、分布式谱聚类算法等.近邻传播(affinity propagation,AP)聚类能克服K平均聚类算法的局限性,但是处理海量数据性能不高.为有效实现海量数据聚类,提出基于MapReduce的分布式近邻传播聚类算法——DisAP.该算法先将数据点随机划分为规模相近的子集,并行地用AP聚类算法稀疏化各子集,然后融合各子集稀疏化后的数据再次进行AP聚类,由此产生的聚类代表作为所有数据点的聚类中心.在人工合成数据、人脸图像数据、IRIS数据以及大规模数据集上的实验表明:DisAP算法对数据规模有很好的适应性,在保持AP聚类效果的同时可有效缩减聚类时间.

With the rapid development of computer technology, data grows explosively. There are challenges for the traditional machine learning algorithms to deal with the large scale data. Many parallel algorithms have been proposed to address the scalability problem, such as MapReduce-based K-means algorithm and parallel spectral clustering algorithm. Affinity propagation （AP） clustering algorithm is introduced to address some drawbacks of the traditional clustering methods such as K- means algorithm. However, its scalability and performance still need improving when dealing with large scale data. In this paper, we propose a distributed AP clustering algorithm based on MapReduce, named DisAP. At first, large scale data are partitioned into several smaller subsets randomly. Then each subset is sparsified in parallel by using AP clustering algorithm. The results are fused and then clustered again, which forms a set of high-quality exemplars. Finally, all data are assigned to exemplars in parallel. DisAP is implemented on a Hadoop cluster, and the experiments on synthetic datasets,human face image datasets, and IRIS dataset demonstrate that DisAP can achieve high performance on both scalability and accuracy.