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

Letx₁ throughx_n be a set of data points, with no assumptions made about their internal structure, and lets be a function that quantifies the similarity between any two points, such thats(i,j) >s(i,k)if and only ifx_i is more similar tox_j than tox_k. For this example, the negative squared distance of two data points was used i.e. for pointsx_i andx_k,${\displaystyle s(i,k)=-{\Vert x_i-x_k\Vert }^2}$.^[1]

The diagonal ofs (i.e.${\displaystyle s(i,i)}$) is particularly important, as it represents the instance preference, meaning how likely a particular instance is to become an exemplar. When it is set to the same value for all inputs, it controls how many classes the algorithm produces. A value close to the minimum possible similarity produces fewer classes, while a value close to or larger than the maximum possible similarity produces many classes. It is typically initialized to the median similarity of all pairs of inputs.

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

• The "responsibility" matrixR has valuesr(i,k) that quantify how well-suitedx_k is to serve as the exemplar forx_i, relative to other candidate exemplars forx_i.
• The "availability" matrixA contains valuesa(i,k) that represent how "appropriate" it would be forx_i to pickx_k as its exemplar, taking into account other points' preference forx_k as an exemplar.

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

• First, responsibility updates are sent around:${\displaystyle r(i,k)\leftarrow s(i,k)-\underset{k^{\prime }\ne k}{max}\left\{a(i,k^{\prime })+s(i,k^{\prime })\right\}}$
• Then, availability is updated per$${\displaystyle a(i,k)\leftarrow min\left(0,r(k,k)+\sum _{i^{\prime }\notin \{i,k\}}max(0,r(i^{\prime },k))\right)\text{ for }i\ne k}$$ and$${\displaystyle a(k,k)\leftarrow \sum _{i^{\prime }\ne k}max(0,r(i^{\prime },k)).}$$

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

The inventors of affinity propagation showed it is better for certain computer vision andcomputational biology tasks, e.g. clustering of pictures of human faces and identifying regulated transcripts, thank-means,^[1] even whenk-means was allowed many random restarts and initialized usingPCA.^[2]A study comparing affinity propagation andMarkov clustering onprotein interaction graph partitioning found Markov clustering to work better for that problem.^[3] A semi-supervised variant has been proposed fortext mining applications.^[4] Another recent application was in economics, when the affinity propagation was used to find some temporal patterns in the output multipliers of the US economy between 1997 and 2017.^[5]

• AJava implementation is included in theELKI data mining framework.
• AJulia implementation of affinity propagation is contained in Julia Statistics's Clustering.jl package.
• APython version is part of thescikit-learn library.
• AnR implementation is available in the "apcluster" package.

• Cluster analysis algorithms

• Articles with short description
• Short description matches Wikidata