K-Means requires you to choose the number of clusters k before running the algorithm. This is often the hardest part — the right number of natural groups in real data usually isn't known ahead of time, and getting it wrong distorts every cluster. Affinity Propagation removes this requirement entirely. It discovers both the number of clusters and a representative point for each one — called an exemplar — purely from a similarity matrix between data points, no k required.

Instead of iteratively updating centroids like K-Means, Affinity Propagation works by having every point send messages to every other point about how well-suited that point would be as its exemplar, repeating until the messages converge.

The two messages: responsibility and availability

Affinity Propagation starts from a similarity matrix s(i, k), where a higher value means point *i* is more similar to (and would be well represented by) point *k*. Each point then exchanges two kinds of messages with every other point, iteratively:

Responsibility r(i, k) — sent from point *i* to candidate exemplar *k* — reflects how well-suited *k* is to be *i*'s exemplar, accounting for how strongly other candidate exemplars are competing for that role.

Availability a(i, k) — sent from candidate exemplar *k* back to point *i* — reflects how appropriate it would be for *i* to choose *k*, accounting for how much support *k* already has from other points wanting to pick it as their exemplar.

These messages are updated repeatedly, each round incorporating a damping factor to prevent oscillation, until the exemplar assignments stabilize.

Preference: the hidden control over cluster count

Affinity Propagation doesn't take k as input, but it does take a preference value for each point — its own self-similarity s(k, k) — which represents how likely that point is to become an exemplar for itself. Higher preference values make more points likely to become exemplars, producing more, smaller clusters; lower preference values produce fewer, larger clusters.

In practice, you typically set a single shared preference value (often the median or minimum of all pairwise similarities) and treat it as a tunable hyperparameter, similar in spirit to how you'd tune eps in DBSCAN — you're not picking the cluster count directly, but you are still controlling it indirectly.

python

Note

Unlike K-Means centroids, which are synthetic points computed as a mean (and may not resemble any real data point), Affinity Propagation's exemplars are always actual points from the dataset. This makes results more interpretable in domains where the "center" of a cluster needs to be a real, inspectable example — such as picking a representative document from a cluster of similar documents, or a representative customer profile from a segment.

Affinity Propagation vs. K-Means

Dimension	Affinity Propagation	K-Means
Cluster count	Emerges automatically from preference + similarities	Must be chosen in advance (k)
Cluster centers	Real data points (exemplars)	Synthetic means of assigned points
Computational cost	O(n^2) per iteration — expensive for large n	O(n*k) per iteration — scales much better
Determinism	Deterministic given inputs and damping	Sensitive to random initialization
Best for	Smaller datasets where interpretable exemplars matter	Large datasets with roughly known cluster count

Note

Affinity Propagation requires storing and updating an n-by-n similarity matrix, plus responsibility and availability matrices of the same size. For datasets beyond roughly tens of thousands of points, this becomes impractical on typical hardware. K-Means, DBSCAN, or mini-batch variants are the usual fallback once data volume grows past that point.

Contrast: K-Means requires choosing k upfront — see it in action

📊 K-Means Clustering Simulator

Interactive

k = 3

Points: 0Iteration: 0Inertia: N/A

What's next

Affinity Propagation and K-Means both operate on fully-formed similarity or distance structures. The next lesson steps back to the simplest possible supervised model — the decision stump — and why these trivially weak learners are the fundamental building block of boosting algorithms.

I build these systems professionally.

Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.

Work With Me →

Need production AI or MarTech expertise? I build custom LLM workflows, server-side GTM tagging, and analytics infrastructures professionally.

Need custom AI or MarTech setup? Let's build together.

Let's talk →