K-AP: Generating specified K clusters by efficient Affinity Propagation

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

57 Scopus citations


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. © 2010 IEEE.
Original languageEnglish (US)
Title of host publication2010 IEEE International Conference on Data Mining
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages6
ISBN (Print)9780769542560
StatePublished - Dec 2010

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'K-AP: Generating specified K clusters by efficient Affinity Propagation'. Together they form a unique fingerprint.

Cite this