Scaling Analysis of Affinity Propagation - Archive ouverte HAL Access content directly
Journal Articles Physical Review E : Statistical, Nonlinear, and Soft Matter Physics Year : 2010

Scaling Analysis of Affinity Propagation

(1) , (1) , (1)
1
Cyril Furtlehner
  • Function : Author
  • PersonId : 838835
Michèle Sebag
  • Function : Author
  • PersonId : 836537

Abstract

We analyze and exploit some scaling properties of the {\em Affinity Propagation} (AP) clustering algorithm proposed by Frey and Dueck (2007). Following a divide and conquer strategy we setup an exact renormalization-based approach to address the question of clustering consistency, in particular, how many cluster are present in a given data set. We first observe that the divide and conquer strategy, used on a large data set hierarchically reduces the complexity ${\cal O}(N^2)$ to ${\cal O}(N^{(h+2)/(h+1)})$, for a data-set of size $N$ and a depth $h$ of the hierarchical strategy. For a data-set embedded in a $d$-dimensional space, we show that this is obtained without notably damaging the precision except in dimension $d=2$. In fact, for $d$ larger than $2$ the relative loss in precision scales like $N^{(2-d)/(h+1)d}$. Finally, under some conditions we observe that there is a value $s^*$ of the penalty coefficient, a free parameter used to fix the number of clusters, which separates a fragmentation phase (for $ss^*$) of the underlying hidden cluster structure. At this precise point holds a self-similarity property which can be exploited by the hierarchical strategy to actually locate its position, as a result of an exact decimation procedure. From this observation, a strategy based on \AP\ can be defined to find out how many clusters are present in a given dataset.
Fichier principal
Vignette du fichier
pre_v2.pdf (356.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00420407 , version 1 (28-09-2009)
inria-00420407 , version 2 (09-06-2010)

Identifiers

Cite

Cyril Furtlehner, Michèle Sebag, Zhang Xiangliang. Scaling Analysis of Affinity Propagation. Physical Review E : Statistical, Nonlinear, and Soft Matter Physics, 2010, 81 (6), pp.066102. ⟨10.1103/PhysRevE.81.066102⟩. ⟨inria-00420407v2⟩
255 View
280 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More