Clustering by evidence accumulation on affinity propagation

Affinity propagation (AP) is a clustering algorithm which has much better performance than traditional clustering approach such as k-means algorithm. In this paper, we present an algorithm called voting partition affinity propagation (voting-PAP) which is a method for clustering using evidence accumulation based on AP. Resulting clusters by voting-PAP are not constrained to be hyper-spherically shaped. Voting-PAP consists of three parts: partition affinity propagation (PAP), relaxed multi-root minimum spanning tree (MST) and majority voting. PAP is a method which can produce different exemplar set based on AP. Relaxed multi-root MST is a data point assign algorithm which has better performance than nearest assign rule. Majority voting is a scheme used to find a consistent clustering result of different partitions based on the idea of evidence accumulation. We also discuss how to find an appropriate threshold corresponding to an approximate ideal consistent partition in this paper.