Affinity Propagation

Imagine trying to group a set of customers, documents, or images without deciding in advance how many groups there should be. Affinity Propagation tackles that by letting the data points “negotiate” which points are the best representatives of each cluster, instead of forcing you to pick cluster centers up front.

How it works

Affinity Propagation is a clustering method built around pairwise similarities between data points. Rather than computing an average center like k-means, it chooses actual data points as cluster representatives, called exemplars. The algorithm repeatedly exchanges two kinds of messages between points:

Responsibility: how strongly point i thinks point k should represent it.
Availability: how appropriate point k is as an exemplar for point i, based on support from other points.

These messages are updated until they stabilize. The points with strong combined evidence become exemplars, and the rest are assigned to them. A key control is the preference value, which affects how many exemplars get selected: higher preferences produce more clusters, lower ones produce fewer.

Why it matters

This is useful when the number of clusters is unknown or when using real data points as representatives is more meaningful than using synthetic centroids. In customer segmentation, an exemplar can be an actual customer profile. In document clustering, it can be a real article that best represents a topic. Ignore this distinction, and you can end up with clusters that are mathematically neat but hard to interpret in practice.

Practical use

Affinity Propagation works from a similarity matrix, such as negative Euclidean distance or cosine similarity. In scikit-learn, the class sklearn.cluster.AffinityPropagation implements it. It can discover clusters without setting k, but it is more computationally expensive than simpler methods and can be sensitive to the similarity scale and preference setting.

Affinity Propagation is a clustering algorithm that identifies representative data points, called exemplars, by iteratively passing responsibility and availability messages between pairs of samples based on their similarities. It forms clusters around these exemplars without requiring the number of clusters to be specified in advance. This matters because it enables data-driven cluster discovery and is effective when meaningful pairwise similarity structure is more informative than geometric centroids.

Imagine a group of people trying to choose a few “representatives” for the whole crowd. Instead of deciding the number ahead of time, they keep comparing who seems most like a good example of others, and a set of natural representatives gradually emerges. That is the basic idea behind Affinity Propagation.

In AI, it is a way of grouping similar things without being told the groups in advance. Each group is organized around an exemplar, meaning a real data point that best represents that group. This matters because in messy real-world data—like customer types, photos, or documents—the right number of groups is often unknown, and Affinity Propagation can help uncover it automatically.