Affinity propagation

In statistics and data mining, affinity propagation (AP) is a clustering algorithm based on the concept of "message passing" between data points.^[1] Unlike clustering algorithms such as k-means or k-medoids, affinity propagation does not require the number of clusters to be determined or estimated before running the algorithm. Similar to k-medoids, affinity propagation finds "exemplars", members of the input set that are representative of clusters.^[1]

Algorithm

Let x₁ through x_n be a set of data points, with no assumptions made about their internal structure, and let s be a function that quantifies the similarity between any two points, such that s(x_i, x_j) > s(x_i, x_k) iff x_i is more similar to x_j than to x_k. For this example, the negative squared distance of two data points was used i.e. for points x_i and x_k, ${\displaystyle s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}}$^[1]

The algorithm proceeds by alternating two message passing steps, to update two matrices:^[1]

• The "responsibility" matrix R has values r(i, k) that quantify how well-suited x_k is to serve as the exemplar for x_i, relative to other candidate exemplars for x_i.
• The "availability" matrix A contains values a(i, k) that represent how "appropriate" it would be for x_i to pick x_k as its exemplar, taking into account other points' preference for x_k as an exemplar.

Both matrices are initialized to all zeroes, and can be viewed as log-probability tables. The algorithm then performs the following updates iteratively:

• First, responsibility updates are sent around: $r(i,k) \leftarrow s(i,k) - \max_{k' \neq k} \left\{ a(i,k') + s(i,k') \right\}$
• Then, availability is updated per

$a(i,k) \leftarrow \min \left( 0, r(k,k) + \sum_{i' \not\in \{i,k\}} \max(0, r(i',k)) \right)$ for $i \neq k$ and

$a(k,k) \leftarrow \sum_{i' \neq k} \max(0, r(i',k))$.

The iterations are performed until either the cluster boundaries remain unchanged over a number of iterations, or after some predetermined number of iterations. The exemplars are extracted from the final matrices as those whose 'responsibility' for themselves is positive (i.e. ${\displaystyle r(i,i)>0}$).

Applications

The inventors of affinity propagation showed it is better for certain computer vision and computational biology tasks, e.g. clustering of pictures of human faces and identifying regulated transcripts, than k-means,^[1] even when k-means was allowed many random restarts and initialized using PCA.^[2] A study comparing affinity propagation and Markov clustering on protein interaction graph partitioning found Markov clustering to work better for that problem.^[3] A semi-supervised variant has been proposed for text mining applications.^[4]

Software

• A Java implementation is included in the ELKI data mining framework.
• Java Apro library implements parallelized affinity propagation and hierarchical affinity propagation.
• A Julia implementation of affinity propagation is contained in Julia Statistics's Clustering.jl package.^[5]
• A Python version is part of the scikit-learn library.^[6]
• An R implementation is available in the "apcluster" package.^[7]

References

1. Brendan J. Frey; Delbert Dueck (2007). "Clustering by passing messages between data points". Science. 315 (5814): 972–976. doi:10.1126/science.1136800. PMID 17218491.
2. Delbert Dueck; Brendan J. Frey (2007). Non-metric affinity propagation for unsupervised image categorization. Int'l Conf. on Computer Vision.
3. James Vlasblom; Shoshana Wodak (2009). "Markov clustering versus affinity propagation for the partitioning of protein interaction graphs". BMC Bioinformatics. 10 (1): 99. doi:10.1186/1471-2105-10-99.
4. Renchu Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang; Yanchun Liang (2011). "Text Clustering with Seeds Affinity Propagation". IEEE Transactions on Knowledge & Data Engineering. 23 (4): 627–637. doi:10.1109/tkde.2010.144.
5. Clustering.jl www.github.com
6. "Clustering — scikit-learn 0.14.1 documentation". Retrieved 15 July 2014.
7. apcluster cran.r-project.org>