Abstract

Affinity Propagation is a state-of-the-art cluster-ing method recently proposed by Frey and Dueck.It has been successfully applied to broad areas of computer science research because it has much bet-ter clustering performance than traditional cluster-ing methods such as k-means. In order to obtain high quality sets of clusters, the original Affinity Propagation algorithm iteratively exchanges real-valued messages between all pairs of data points until convergence. However, this algorithm does not scale for large datasets because it requires quadratic CPU time in the number of data points to compute the messages. This paper proposes an ef-ficient Affinity Propagation algorithm that guaran-tees the same clustering result as the original algo-rithm after convergence. The heart of our approach is (1) to prune unnecessary message exchanges in the iterations and (2) to compute the convergence values of pruned messages after the iterations to de-termine clusters. Experimental evaluations on sev-eral different datasets demonstrate the effectiveness of our algorithm.