Initializing K-means Clustering Using Affinity Propagation

K-means clustering is widely used due to its fast convergence, but it is sensitive to the initial condition. Therefore, many methods of initializing K-means clustering have been proposed in the literatures. Compared with K-means clustering, a novel clustering algorithm called affinity propagation (AP clustering) has been developed by Frey and Dueck, which can produce a good set of cluster exemplars with fast speed. Taking the convergence property of K-means and the good performance of affinity propagation, we presented a new clustering strategy which can produce much lower squared error than AP and standard K-means: initializing K-means clustering using cluster exemplars produced by AP. Numerical experiments indicated that such combined method outperforms not only AP and original K-means clustering, but also K-means clustering with sophisticated initial conditions designed by various methods.