Stability-based preference selection in affinity propagation

Recently, as one of the most popular exemplar-based clustering algorithms, affinity propagation has attracted a great amount of attention in various fields. The advantages of affinity propagation include the efficiency, insensitivity to cluster initialization and capability of finding clusters with less error. However, one shortcoming of the affinity propagation algorithm is that, the clustering results generated by affinity propagation strongly depend on the selection of exemplar preferences, which is a challenging model selection task. To tackle this problem, this paper investigates the clustering stability of affinity propagation for automatically selecting appropriate exemplar preferences. The basic idea is to define a novel stability measure for affinity propagation, based on which we can select exemplar preferences that generate the most stable clustering results. Consequently, the proposed approach is termed stability-based affinity propagation (SAP). Experimental results conducted on extensive real-world datasets have validated the effectiveness of the proposed SAP algorithm.