A Distributed Multi-exemplar Affinity Propagation Clustering Algorithm Based on MapReduce

摘要

Clustering algorithm is one of the fundamental techniques in data mining, which plays a crucial role in various applications, such as pattern recognition, document retrieval, and computer vision. As so far, many effective algorithms have been proposed. Affinity Propagation is an algorithm requires no parameter indicating the number of clusters, which is the most distinguishing advantage compared to the k-means clustering algorithm. Multi-Exemplar Affinity Propagation (MEAP) extends the single-exemplar model to the multi-exemplar model, which could describe the dataset with more complex structure. With the amount of data increasing rapidly, the growing size of dataset makes the clustering problem become more and more challenging. To solve this problem, the parallel computing framework is widely used, such as MapReduce. However, for the MEAP algorithm, it is not a straightforward task to implement the updating of MEAP messages in MapReduce, which without proper design would be time-consuming. In this paper, we propose to utilize the stability of data distribution to apply the MEAP algorithm on the MapReduce platform and develop an efficient Distributed Multi-Exemplar Affinity Propagation (DisMEAP) clustering algorithm by using three MapReduce stages. The experiment results demonstrate that our algorithm can perform well in processing large-scale datasets and could achieve the same accuracy as the original MEAP algorithm.