Research on Parameters of Affinity Propagation Clustering

The affinity propagation clustering is a new clustering algorithm. The volatility is introduced to measure the degree of the numerical oscillations. The research focuses on two main parameters of affinity propagation: preference and damping factor, and co

  • PDF / 1,859,167 Bytes
  • 8 Pages / 439.37 x 666.142 pts Page_size
  • 64 Downloads / 245 Views

DOWNLOAD

REPORT


Abstract The affinity propagation clustering is a new clustering algorithm. The volatility is introduced to measure the degree of the numerical oscillations. The research focuses on two main parameters of affinity propagation: preference and damping factor, and considers their relation with the numerical oscillating and volatility, and we find that the volatility can be reduced by increasing the damping factor or preference, which provides the basis for eliminating the numerical oscillating. Keywords Affinity propagation

 Damping factor  Preference  Volatility

Introduction Affinity propagation (AP) is a new clustering algorithm published in Science magazine and proposed by Frey and Dueck [1]. Its advantage is that it finds clusters with much lower error than other methods, and it does so in less than onehundredth the amount of time [1].Although results on small data sets (900 Bpoints) demonstrate that vertex substitution heuristic (VSH) is competitive with AP, VSH is prohibitively slow for moderate-to-large problems, whereas AP is much faster and could achieve lower error [2]. There are some scholars who have done some improvements on AP algorithm. Literature [3, 4] proposed a new message transmission algorithm soft constraint

B. Gui (&) School of Information, Remin University of China, Beijing, China e-mail: [email protected] X. Yang School of Computer Science and Technology, Huaiyin Normal University, Huaian, China e-mail: [email protected]

Y.-M. Huang et al. (eds.), Advanced Technologies, Embedded and Multimedia for Human-centric Computing, Lecture Notes in Electrical Engineering 260, DOI: 10.1007/978-94-007-7262-5_72, Ó Springer Science+Business Media Dordrecht 2014

637

638

B. Gui and X. Yang

condition who allowed a single cluster exemplar did not represented itself in the search and optimization process of the cluster exemplar. Kaijun Wang proposed an algorithm that could adjust adaptively the damping factors and preferences to eliminate oscillations and find the optimal clustering result [5]. Xiao Yu proposed a semi-supervised clustering method based on affinity propagation, it can produce good clustering results for the datasets with complex cluster structures by using the prior known labeled data or pairwise constraints to adjust the similarity matrix [6]. Although there are some research for AP, no one does overall research on AP.

Affinity Propagation Clustering AP works based on similarities between pairs of data points (Euclidean distance), each similarity is set to negative squared error: For points xi and xk ; sði; kÞ ¼  jj xi  xk jj2 .Take the negative in order to facilitate the calculation, the greater the value, the higher similarity. These similarity can be symmetric, i.e.,sði; kÞ ¼ sði; kÞ; they can also be asymmetric. i.e.,sði; kÞ 6¼ sði; kÞ. The similarity between the N data points is composed of N 9 N similarity matrix S.Rather than requiring that the number of clusters be prespecified, AP takes as input a real number sðk; kÞ for each data point k so that data points with larger v