Affinity propagation

Points exchange responsibility and availability messages until a set of exemplars emerges — no k required.

17 min read1690 wordsadvanced10 viewsupdated 2026-10-07

Definition

Affinity propagation (Frey & Dueck, 2007) clusters data by choosing a subset of the data points themselves as exemplars. Every point repeatedly sends two kinds of messages — responsibility ("how well would kk serve as my exemplar?") and availability ("how much support does kk have to be an exemplar?") — until a stable set of exemplars emerges. The number of clusters is not given; it falls out of a per-point preference for being an exemplar.

At a glance

Task
Clustering (unsupervised), exemplar-based
Input → output
an n×nn\times n similarity matrix s(i,k)s(i,k) (any similarity, not necessarily metric) → a set of exemplars and a label per point
Learns
two n×nn\times n message matrices RR (responsibility) and AA (availability); the exemplars are read off their diagonals
Training
O(n2)O(n^2) time per iteration, typically 20–200 iterations; O(n2)O(n^2) memory for SS, RR, AA
Prediction
assign a new point to its most similar exemplar: O(K)O(K) similarities
Hyperparameters
preference (controls the number of clusters), damping λ, max iterations, convergence window
Assumes
a meaningful similarity; clusters are well represented by one of their own members; n small enough for an n × n matrix

The problem

k-means needs kk in advance, its centres are averages that may not be real data points, and it only works with squared Euclidean distance. k-medoids fixes the last two — the centres become actual points (medoids) and any dissimilarity works — but still needs kk, and its swap search can stop at a poor local optimum that depends on which points it started from.

Affinity propagation attacks both remaining problems at once. It considers every point as a potential exemplar simultaneously (no random initialisation), and replaces "choose kk" with "how much does it cost to open one more exemplar?" — a single number per point, the preference. Points then negotiate who represents whom.

Another way to avoid fixing kk is hierarchical clustering (see hierarchical clustering and agglomerative clustering), which builds a whole dendrogram and lets you cut it later; BIRCH summarises huge datasets into a tree of sub-clusters. Affinity propagation instead returns one flat clustering whose size is set by a cost, and its centres are always real points. For the objective it shares with k-medoids — total dissimilarity of points to their representatives — see the k-medoids article.

The idea

Picture an election in which every voter is also a candidate. Each point ii looks at all candidates kk and tells each one how much better it is than ii's best other option — that is the responsibility. Each candidate kk collects the positive endorsements it received and reports back to every voter how plausible it is as an exemplar given everyone else's support — that is the availability. Voters update their opinions using the availabilities, candidates update using the responsibilities, and after a few dozen rounds a handful of candidates have strong support from both themselves and others. Those are the exemplars; every other point joins the exemplar it is most similar to.

Vocabulary

Similarity s(i,k)
how well kk would represent ii; higher is better. The usual choice is the negative squared distance −∥xi−xk∥2-\lVert x_i-x_k\rVert^2. It need not be symmetric.
Exemplar
a data point chosen to represent a cluster — like a medoid. Exemplar kk represents itself: ck=kc_k=k.
Preference s(k,k)
the diagonal of the similarity matrix: how much kk "wants" to be an exemplar. Higher preference → more exemplars.
Responsibility r(i,k)
message from point ii to candidate kk: the evidence that kk should be ii's exemplar, compared with ii's best alternative.
Availability a(i,k)
message from candidate kk to point ii: the evidence that kk is a good exemplar, judged by the support kk gets from other points.
Self-evidence
r(k,k)+a(k,k)r(k,k)+a(k,k); point kk is an exemplar when this is positive.
Damping λ
each message is a mix of λ × old value and (1−λ) × new value; it stops the messages from oscillating.
Net similarity
the objective: total similarity of points to their exemplars plus the preferences of the exemplars.

The math

Let cic_i be the exemplar of point ii. Affinity propagation searches for the assignment c=(c1,…,cn)c=(c_1,\dots,c_n) that maximises the net similarity, subject to one consistency rule: if anyone picks kk as exemplar, kk must pick itself.

max⁡c  ∑i=1ns(i,ci)  +  ∑k=1nδk(c),δk(c)={−∞if ck≠k but ∃i:ci=k0otherwise\max_{c}\; \sum_{i=1}^{n} s(i,c_i) \;+\; \sum_{k=1}^{n}\delta_k(c),\qquad \delta_k(c)=\begin{cases}-\infty & \text{if } c_k\ne k \text{ but } \exists i: c_i=k\\ 0 & \text{otherwise}\end{cases}
cic_i
index of the exemplar chosen by point ii
s(i,k)s(i,k)
similarity of ii to kk (i≠ki\ne k); s(k,k)s(k,k) is the preference pkp_k
δk(c)\delta_k(c)
exemplar-consistency constraint: forbids choosing kk unless kk chooses itself

Each exemplar contributes s(k,k)=pks(k,k)=p_k, so the objective equals (sum of similarities of non-exemplars to their exemplars) +  p⋅K+\;p\cdot K when all preferences are equal to pp. Since p<0p<0 in practice, each extra exemplar costs ∣p∣|p| and is only opened if it raises the members' similarity by more than that. This is exactly the NP-hard facility-location / k-medoids objective with a price on KK instead of a fixed KK.

Exact maximisation is intractable, so AP runs max-sum belief propagation on the factor graph that has one variable cic_i per point and one constraint δk\delta_k per candidate. Max-sum messages are differences of best achievable scores, and they simplify to two scalars per pair (i,k)(i,k).

r(i,k)  ←  s(i,k)  −  max⁡k′≠k[ a(i,k′)+s(i,k′) ]r(i,k)\;\leftarrow\; s(i,k)\;-\;\max_{k'\ne k}\big[\,a(i,k')+s(i,k')\,\big]
r(i,k)r(i,k)
responsibility: how much better kk is for ii than ii's best competing candidate
a(i,k′)a(i,k')
current availability of competitor k′k' to ii (all zero at the start)

Derivation of rr. Point ii's variable cic_i receives a message a(i,k)a(i,k) from each constraint and contributes s(i,ci)s(i,c_i). The best total score achievable with ci=kc_i=k is s(i,k)+a(i,k)s(i,k)+a(i,k); the best with ci≠kc_i\ne k is max⁡k′≠k[s(i,k′)+a(i,k′)]\max_{k'\ne k}[s(i,k')+a(i,k')]. The message ii sends to constraint kk is the score of "ci=kc_i=k" minus the score of "ci≠kc_i\ne k", excluding kk's own message a(i,k)a(i,k) (belief propagation never echoes a message back to its sender). That leaves exactly the formula above. On the diagonal, r(k,k)=pk−max⁡k′≠k[a(k,k′)+s(k,k′)]r(k,k)=p_k-\max_{k'\ne k}[a(k,k')+s(k,k')]: kk's preference minus how attractive its best alternative exemplar is.

a(i,k)  ←  min⁡(0,  r(k,k)+ ⁣ ⁣∑i′∉{i,k} ⁣ ⁣max⁡(0, r(i′,k)))(i≠k),a(k,k)  ←  ∑i′≠kmax⁡(0, r(i′,k))a(i,k)\;\leftarrow\;\min\Big(0,\; r(k,k)+\!\!\sum_{i'\notin\{i,k\}}\!\!\max\big(0,\,r(i',k)\big)\Big)\quad (i\ne k),\qquad a(k,k)\;\leftarrow\;\sum_{i'\ne k}\max\big(0,\,r(i',k)\big)
a(i,k)a(i,k)
availability: how plausible kk is as an exemplar for ii, from kk's self-responsibility and the positive support of others
max⁡(0,r(i′,k))\max(0,r(i',k))
only positive endorsements count — a point that prefers another exemplar is simply not kk's member
min⁡(0,⋅)\min(0,\cdot)
caps availability at 0: strong support for kk cannot make kk more attractive to ii than "free"

Derivation of aa. Constraint δk\delta_k compares two worlds for cic_i. If ci=kc_i=k, then kk must be an exemplar, which earns r(k,k)r(k,k), and every other point i′i' may join kk whenever that helps: ∑i′max⁡(0,r(i′,k))\sum_{i'}\max(0,r(i',k)). If ci≠kc_i\ne k, the constraint is free to choose whichever is better — kk an exemplar (same score) or not (score 0) — so it gets max⁡(0,that score)\max(0,\text{that score}). The difference of the two is score−max⁡(0,score)=min⁡(0,score)\text{score}-\max(0,\text{score})=\min(0,\text{score}). For a(k,k)a(k,k), "ck=kc_k=k" means kk is an exemplar and collects positive support; "ck≠kc_k\ne k" forces nobody to choose kk, which scores 0. Hence no min⁡\min on the diagonal.

ci=arg⁡max⁡k[a(i,k)+r(i,k)],k is an exemplar  ⟺  r(k,k)+a(k,k)>0c_i=\arg\max_{k}\big[a(i,k)+r(i,k)\big],\qquad k\text{ is an exemplar}\iff r(k,k)+a(k,k)>0
a(i,k)+r(i,k)a(i,k)+r(i,k)
the max-marginal belief that kk is ii's exemplar
r(k,k)+a(k,k)r(k,k)+a(k,k)
self-evidence: positive means k is better off as an exemplar than not
R  ←  λR+(1−λ)Rnew,A  ←  λA+(1−λ)AnewR\;\leftarrow\;\lambda R+(1-\lambda)R^{\text{new}},\qquad A\;\leftarrow\;\lambda A+(1-\lambda)A^{\text{new}}
λ\lambda
damping factor in [0.5,1)[0.5,1); scikit-learn's default is 0.5
Rnew,AnewR^{\text{new}},A^{\text{new}}
the values just computed by the update rules

What each hyperparameter does. The preference pp enters the objective once per exemplar, so it is literally the price of a cluster: raising pp toward 0 makes r(k,k)r(k,k) larger for every kk and more points cross the self-evidence threshold. The default p=median(s)p=\text{median}(s) gives a moderate number of clusters, p=min⁡(s)p=\min(s) a small number. Damping does not change the fixed points of the updates — only the path to them. Loopy max-sum on this graph tends to flip between "everyone is an exemplar" and "no one is"; averaging old and new messages turns that period-2 swing into a smooth approach, at the cost of more iterations.

Worked example: eight points, two exemplars

Eight points in 2-D, with similarity s(i,k)=−∥xi−xk∥2s(i,k)=-\lVert x_i-x_k\rVert^2. The 56 off-diagonal similarities have median −30.5-30.5, so every preference is set to p=−30.5p=-30.5 (scikit-learn's default). Damping λ=0.5\lambda=0.5.

Pointx₁x₂
A12
B21
C22
D33
E76
F87
G77
H58
The data. Highlighted: the two points that become exemplars.
s(i,k)ABCDEFGH
A−30.5−2−1−5−52−74−61−52
B−2−30.5−1−5−50−72−61−58
C−1−1−30.5−2−41−61−50−45
D−5−5−2−30.5−25−41−32−29
E−52−50−41−25−30.5−2−1−8
F−74−72−61−41−2−30.5−1−10
G−61−61−50−32−1−1−30.5−5
H−52−58−45−29−8−10−5−30.5
Similarity matrix s(i,k) = −squared distance; the diagonal holds the preference p = −30.5.

Iteration 1 by hand (all messages start at 0)

  1. 1Responsibilities. With A=0A=0, rnew(i,k)=s(i,k)−max⁡k′≠ks(i,k′)r^{\text{new}}(i,k)=s(i,k)-\max_{k'\ne k}s(i,k'). Row A's best candidate is C (−1-1), second best B (−2-2). So rnew(A,C)=−1−(−2)=1r^{\text{new}}(A,C)=-1-(-2)=1, and for every other kk: rnew(A,k)=s(A,k)−(−1)r^{\text{new}}(A,k)=s(A,k)-(-1), e.g. rnew(A,A)=−30.5+1=−29.5r^{\text{new}}(A,A)=-30.5+1=-29.5.
  2. 2Row D: best C (−2-2), second A or B (−5-5), so rnew(D,C)=3r^{\text{new}}(D,C)=3. Row B gives rnew(B,C)=1r^{\text{new}}(B,C)=1. Row C itself: rnew(C,C)=−30.5−(−1)=−29.5r^{\text{new}}(C,C)=-30.5-(-1)=-29.5.
  3. 3Damping. R=0.5⋅0+0.5 RnewR=0.5\cdot 0+0.5\,R^{\text{new}}: r(A,C)=0.5r(A,C)=0.5, r(B,C)=0.5r(B,C)=0.5, r(D,C)=1.5r(D,C)=1.5, r(C,C)=−14.75r(C,C)=-14.75.
  4. 4Availabilities for candidate C. Positive responsibilities into C come from A, B, D: 0.5+0.5+1.5=2.50.5+0.5+1.5=2.5. So anew(C,C)=2.5a^{\text{new}}(C,C)=2.5 and anew(A,C)=min⁡(0, −14.75+0.5+1.5)=−12.75a^{\text{new}}(A,C)=\min(0,\,-14.75+0.5+1.5)=-12.75. After damping: a(C,C)=1.25a(C,C)=1.25, a(A,C)=−6.375a(A,C)=-6.375.
  5. 5Self-evidence. r(C,C)+a(C,C)=−14.75+1.25=−13.5<0r(C,C)+a(C,C)=-14.75+1.25=-13.5<0. Every point is still negative (G is also −13.5-13.5, H −12.75-12.75), so after iteration 1 there are no exemplars.
  6. 6Keep iterating. Each round, C and G gather more support. At iteration 4 they become the first points with positive self-evidence (5.815.81 and 6.186.18) and the exemplar set {C,G}\{C,G\} then stays unchanged; after 15 unchanged iterations the run stops at iteration 19.
kiter 1iter 4iter 19exemplar?
A−14.75−10.30−29.50no
B−14.75−10.30−29.50no
C−13.505.8187.27yes
D−14.25−12.99−28.50no
E−14.75−10.15−29.50no
F−14.75−11.93−29.50no
G−13.506.1884.30yes
H−12.75−14.33−25.50no
Self-evidence r(k,k) + a(k,k) at iterations 1, 4 and 19 (converged). Only C and G end positive.

Reading off the clustering

  1. 1Labels. Each non-exemplar joins its most similar exemplar: A, B, D → C (similarities −1,−1,−2-1,-1,-2); E, F, H → G (−1,−1,−5-1,-1,-5).
  2. 2Net similarity. (−1−1−2)+(−1−1−5)+2×(−30.5)=−11−61=−72(-1-1-2)+(-1-1-5)+2\times(-30.5)=-11-61=-72. No other pair of exemplars does better: the best 2-point exemplar set by brute force is also {C,G}\{C,G\} with member similarity −11-11.
  3. 3Exemplars are data points. G =(7,7)=(7,7) represents {E,F,G,H}\{E,F,G,H\} although their mean is (6.75,7)(6.75,7) — AP never invents a centre.
  4. 4New point (4,3)(4,3): squared distance 5 to C and 25 to G, so it is assigned to C's cluster.

Watch the messages

arrow → preferred candidate · ring = exemplar0112233445566778899ABCDEFGHa(i,k) + r(i,k) · iter 19AABBCCDDEEFFGGHH-29-3029-32-80-102-60-76-30-2929-32-78-100-60-82-87-8787-87-127-147-106-127-32-3228-28-52-68-30-52-80-78-40-52-29-3029-32-102-100-60-68-30-2929-34-144-144-103-114-84-8484-84-76-82-40-52-32-3425-25rows send · columns receive■ positive ■ negativeexemplar ⇔ diagonal a+r > 0self-evidence r(k,k)+a(k,k) per iteration01iteration 1987-29# exemplars vs preference0123median-150-2preference s(k,k)

Iteration 19: exemplars C, G (self-evidence 87.27, 84.30). Converged: the exemplar set has not changed for 15 iterations.

iter 19/19
preference -30.5
damping λmatrix
exemplars C, Gnet similarity -72.0converged at iteration 19
fig.The worked example, live. Arrows show the candidate each point currently prefers (argmax of a + r); rings mark exemplars; the matrix shows r, a or a + r for the selected iteration; the bottom-left chart traces every point's self-evidence. At the default preference (median, −30.5) and λ = 0.5, C and G cross zero at iteration 4 and the run converges at iteration 19 with net similarity −72. Drag the preference: the bottom-right curve shows 3 exemplars for p ≥ −5, 2 for −127 ≤ p ≤ −6 and 1 (point D) below. Set λ = 0 to see the undamped messages flip between all-exemplars and none for 200 iterations; λ = 0.9 converges to the same answer but needs 38 iterations. Drag any point to re-run everything.

The algorithm, step by step

AffinityPropagation(S, p, λ)

  1. 1Similarities. Build SS with s(i,k)s(i,k) for i≠ki\ne k and set the diagonal to the preference (default: median off-diagonal similarity). Set R=A=0R=A=0.
  2. 2Responsibility update. For each row ii, find the largest and second-largest value of a(i,k)+s(i,k)a(i,k)+s(i,k). Then rnew(i,k)=s(i,k)−largestr^{\text{new}}(i,k)=s(i,k)-\text{largest}, except in the argmax column, where the second largest is used. Damp: R←λR+(1−λ)RnewR\leftarrow\lambda R+(1-\lambda)R^{\text{new}}.
  3. 3Availability update. For each column kk, sum the positive responsibilities max⁡(0,r(i′,k))\max(0,r(i',k)) plus r(k,k)r(k,k). Then anew(i,k)=min⁡(0,column sum−max⁡(0,r(i,k)))a^{\text{new}}(i,k)=\min(0,\text{column sum}-\max(0,r(i,k))) off the diagonal and anew(k,k)=column sum−r(k,k)a^{\text{new}}(k,k)=\text{column sum}-r(k,k). Damp AA the same way.
  4. 4Exemplars. E={k:r(k,k)+a(k,k)>0}E=\{k: r(k,k)+a(k,k)>0\}.
  5. 5Stop when EE has not changed for a window of iterations (15 by default) or after max_iter (200); otherwise go to step 2.
  6. 6Assign each point to its most similar exemplar; exemplars label themselves. New points are assigned the same way.

Complexity. Each update touches every pair once with the "largest / second-largest" and "column sum" tricks, so one iteration is O(n2)O(n^2) time, and the run is O(Tn2)O(Tn^2). Memory is three dense n×nn\times n float matrices: for n=10,000n=10{,}000 that is 3×108×83\times10^8\times 8 bytes =2.4=2.4 GB. With a sparse similarity graph (e.g. each point's nearest neighbours only), messages live only on the edges and the cost becomes O(T⋅∣edges∣)O(T\cdot|\text{edges}|).

Hyperparameters, variants and tuning

Preference pλ = 0λ = 0.5λ = 0.9
−3C, G, H · 17 itC, G, H · 18 itC, G, H · 30 it
−30.5 (median)oscillates, no convergenceC, G · 19 itC, G · 38 it
−74 (min)oscillates, no convergenceC, G · 19 itC, G · 43 it
−140oscillates, no convergenceD · 21 itD · 56 it
Effect of preference and damping on the worked example (our implementation; every run checked against scikit-learn's exemplars).

Tuning guide

preference
the main knob. Median → moderate KK; min → few clusters; scan a log-spaced grid between them and pick by silhouette score or by domain need. Per-point preferences let you favour some points as exemplars (e.g. known prototypes).
damping
0.5–0.9 (scikit-learn requires ≥0.5\ge 0.5). Raise it when the run hits max_iter without converging or the exemplar count jumps around.
convergence_iter / max_iter
15 / 200 by default. With high damping, messages move slowly — increase both, or AP can stop on a set that only looked stable.
similarity
negative squared Euclidean by default; with affinity="precomputed" you can pass any similarity: negative edit distance between strings, sequence-alignment scores, cosine similarity of embeddings, even non-symmetric ones.
Scaling
standardize features first when using Euclidean similarity; one large-range feature otherwise dominates every message.

Variants

Sparse AP
messages only on a k-nearest-neighbour graph; scales to far larger nn (the original paper ran it on such graphs).
Adaptive AP
scans the preference automatically and damps adaptively when oscillations are detected.
Hierarchical AP
stacks several AP layers so exemplars of one level are clustered again at the next.
Soft-constraint AP
relaxes the 'exemplar must choose itself' rule, allowing clusters that are not centred on a single point.

In code

python
1import numpy as np
2
3def affinity_propagation(S, preference=None, damping=0.5, max_iter=200, convergence_iter=15):
4 S = S.astype(float).copy()
5 n = len(S)
6 if preference is None:
7 preference = np.median(S[~np.eye(n, dtype=bool)]) # median off-diagonal similarity
8 np.fill_diagonal(S, preference)
9 R = np.zeros((n, n)); A = np.zeros((n, n))
10 rows = np.arange(n)
11 last, stable = None, 0
12 for it in range(1, max_iter + 1):
13 # responsibilities: r(i,k) = s(i,k) - max_{k' != k} [a(i,k') + s(i,k')]
14 AS = A + S
15 best = AS.argmax(1)
16 first = AS[rows, best]
17 AS[rows, best] = -np.inf
18 second = AS.max(1)
19 R_new = S - first[:, None]
20 R_new[rows, best] = S[rows, best] - second
21 R = damping * R + (1 - damping) * R_new
22 # availabilities: a(i,k) = min(0, r(k,k) + sum_{i' not in {i,k}} max(0, r(i',k)))
23 Rp = np.maximum(R, 0)
24 np.fill_diagonal(Rp, R.diagonal())
25 A_new = Rp.sum(0)[None, :] - Rp
26 self_avail = A_new.diagonal().copy() # a(k,k) = sum_{i' != k} max(0, r(i',k))
27 A_new = np.minimum(A_new, 0)
28 np.fill_diagonal(A_new, self_avail)
29 A = damping * A + (1 - damping) * A_new
30 # exemplars: points whose self-evidence r(k,k) + a(k,k) is positive
31 E = tuple(np.flatnonzero((R + A).diagonal() > 0))
32 stable = stable + 1 if E == last else 0
33 last = E
34 if E and stable >= convergence_iter:
35 break
36 E = np.array(last)
37 labels = S[:, E].argmax(1)
38 labels[E] = np.arange(len(E)) # each exemplar labels itself
39 return E, labels, it
40
41X = np.array([[1, 2], [2, 1], [2, 2], [3, 3], [7, 6], [8, 7], [7, 7], [5, 8]], float)
42S = -((X[:, None, :] - X[None, :, :]) ** 2).sum(-1) # negative squared distance
43E, labels, it = affinity_propagation(S)
44print("exemplars:", E, "->", X[E].tolist()) # [2 6] -> [[2.0, 2.0], [7.0, 7.0]]
45print("labels: ", labels) # [0 0 0 0 1 1 1 1]
46print("iterations:", it) # 19
47new = np.array([4, 3])
48print("new point (4,3) -> exemplar", E[np.argmax(-((X[E] - new) ** 2).sum(1))]) # 2 (= C)
From scratch in NumPy, vectorised updates. Prints exemplars [2 6] (C and G), labels [0 0 0 0 1 1 1 1], 19 iterations, and assigns (4, 3) to exemplar 2.
python
1import numpy as np
2from sklearn.cluster import AffinityPropagation
3
4X = np.array([[1, 2], [2, 1], [2, 2], [3, 3], [7, 6], [8, 7], [7, 7], [5, 8]])
5ap = AffinityPropagation(damping=0.5, random_state=0).fit(X) # preference = median similarity
6print("exemplars:", ap.cluster_centers_indices_, ap.cluster_centers_.tolist()) # [2 6] [[2, 2], [7, 7]]
7print("labels: ", ap.labels_) # [0 0 0 0 1 1 1 1]
8print("iterations:", ap.n_iter_) # 17
9print("predict (4,3):", ap.predict([[4, 3]])) # [0]
10
11for pref in [-3, -30.5, -74, -140]:
12 m = AffinityPropagation(preference=pref, random_state=0).fit(X)
13 print(f"preference {pref:>6}: exemplars {m.cluster_centers_indices_}")
14# preference -3: exemplars [2 6 7]
15# preference -30.5: exemplars [2 6]
16# preference -74: exemplars [2 6]
17# preference -140: exemplars [3]
scikit-learn on the same data. Same exemplars and labels; scikit-learn reports n_iter_ = 17 because it counts its convergence window slightly differently and adds tiny noise to S to break ties.

Use when

  • +You do not know K and would rather set a price per cluster than a count.
  • +Cluster centres must be real data points (a representative image, sentence, gene or customer).
  • +Your similarity is non-metric or non-symmetric, so means make no sense.
  • +n is in the hundreds to low thousands and you want a deterministic answer with no random restarts.

Avoid when

  • −nn is large: O(n2)O(n^2) memory and time per iteration rule it out beyond roughly 10410^4 points without sparsification.
  • −Clusters are elongated or non-convex — one exemplar cannot represent a curved shape; use DBSCAN or spectral clustering.
  • −You need exactly K clusters: hitting a given K means searching over the preference.
  • −Data are noisy with many outliers: each outlier may become its own exemplar at high preferences.

Where it's used

Choosing representative images or faces

The original paper clustered face images and picked exemplar faces — real images that summarise each group.

Gene-expression and bioinformatics

Exemplar genes or protein sequences selected from alignment-score similarities, which are not Euclidean.

Text summarisation

Clustering sentences by embedding similarity and using each exemplar sentence in an extractive summary.

Facility and hub placement

Choosing which existing sites (airports, stores, sensors) should serve as hubs — the original paper's airline-travel example.

Check yourself

In the worked example (p=−30.5p=-30.5, λ=0.5\lambda=0.5), what is r(D,C)r(D,C) after the first iteration?

Check yourself

You raise every preference from the median similarity toward 0. What happens?

Check yourself

In the example, one exemplar (D) gives net similarity −139+p-139+p and two (C, G) give −11+2p-11+2p. Below which preference does AP prefer a single cluster?

Check yourself

Point kk is declared an exemplar when…

Remember

  • ✓Exemplars are real data points; every point is a candidate from the start, so there is no random initialisation.
  • ✓Responsibility r(i,k)=s(i,k)−max⁡k′≠k[a(i,k′)+s(i,k′)]r(i,k)=s(i,k)-\max_{k'\ne k}[a(i,k')+s(i,k')]; availability a(i,k)=min⁡(0,r(k,k)+∑i′∉{i,k}max⁡(0,r(i′,k)))a(i,k)=\min(0,r(k,k)+\sum_{i'\notin\{i,k\}}\max(0,r(i',k))).
  • ✓kk is an exemplar when r(k,k)+a(k,k)>0r(k,k)+a(k,k)>0; others join their most similar exemplar.
  • ✓The preference is the price of a cluster: higher (closer to 0) → more clusters. Median and min of the similarities are the usual starting points.
  • ✓Damping (0.5–0.9) stops the max-sum messages from oscillating; it changes the path, not the answer.
  • ✓Cost is O(n2)O(n^2) time per iteration and O(n2)O(n^2) memory — fine for thousands of points, not millions.
← back to ML Algorithms roadmap