K-AP: Generating Specified K Clusters by Efficient Affinity Propagation

Xiangliang Zhang, Wei Wang, Kjetil Nørvåg, Michèle Sebag

Abstract

The Affinity Propagation (AP) clustering algorithm proposed by Frey and Dueck (2007) provides an understandable, nearly optimal summary of a data set. However, it suffers two major shortcomings: i) the number of clusters is vague with the user-defined parameter called self-confidence, and ii) the quadratic computational complexity. When aiming at a given number of clusters due to prior knowledge, AP has to be launched many times until an appropriate setting of self-confidence is found. The re-launched AP increases the computational cost by one order of magnitude. In this paper, we propose an algorithm, called K-AP, to exploit the immediate results of K clusters by introducing a constraint in the process of message passing. Through theoretical analysis and experimental validation, K-AP was shown to be able to directly generate K clusters as user defined, with a negligible increase of computational cost compared to AP. In the meanwhile, K-AP preserves the clustering quality as AP in terms of the distortion. K-AP is more effective than k-medoids w.r.t. the distortion minimization and higher clustering purity.
BibTeX
@inproceedings{zhang2010k,
  author = {Xiangliang Zhang and Wei Wang and Kjetil Nørvåg and Michèle Sebag},
  title = {{K-AP: Generating Specified K Clusters by Efficient Affinity Propagation}},
  booktitle = {ICDM},
  year = {2010},
  doi = {10.1109/icdm.2010.107},
}

Loading related content...

Figure