Reference : K-AP: Generating Specified K Clusters by Efficient Affinity Propagation
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
K-AP: Generating Specified K Clusters by Efficient Affinity Propagation
Zhang, Xiangliang [MCSE, King Abdullah University of Science and Technology (KAUST), Saudi Arabia]
Wang, Wei [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) > ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)]
Nørvåg, Kjetil [Norwegian University of Science and Technology, Norway]
Sebag, Michèle [Université Paris-Sud 11, France]
ICDM '10 Proceedings of the 2010 IEEE International Conference on Data Mining
IEEE Computer Society
IEEE International Conference on Data Mining (ICDM)
13-17 December 2010
[en] 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, KAP 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.

File(s) associated to this reference

Fulltext file(s):

Limited access
Wang.pdfPublisher postprint530.9 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.