Introduction to Affinity Propagation

Affinity Propagation identifies representative observations, called "exemplars," by passing messages over a similarity matrix. It does not require a requested cluster count, but preference does not estimate an optimal number of clusters: the result depends strongly on the similarities and diagonal preference values.

---

What is Affinity Propagation?

Affinity Propagation is a message-passing algorithm that treats all observations as potential exemplars. Responsibilities and availabilities are exchanged until the exemplar decisions stabilize or the iteration limit is reached. Dense message and similarity matrices impose quadratic memory, so it is not automatically a large-data method.

Key Features:

• Exemplar-Based Clustering: Instead of relying on centroids like K-Means, Affinity Propagation identifies actual data points as exemplars around which other points are clustered.
• Preference-controlled cluster count: Higher preferences usually produce more exemplars; lower preferences usually produce fewer. The relationship can be discontinuous, so sensitivity analysis matters.
• Message Passing: Affinity Propagation uses a unique approach of exchanging messages between data points to iteratively refine clusters.

How Affinity Propagation Works

At its core, Affinity Propagation operates by transmitting two types of messages between data points:

1. Responsibility $r(i, k)$: How well-suited a data point is to be the exemplar for another data point.
2. Availability $a(i, k)$: How appropriate it would be for the candidate exemplar to be an exemplar for another point.

These messages are updated iteratively until the clusters stabilize. The data point with the highest combined responsibility and availability for another point is chosen as the exemplar for that point. This process continues until all data points are assigned to their most suitable exemplars.

Applications of Affinity Propagation

Affinity Propagation is versatile and can be applied to various domains, including:

• Image and Object Recognition: Grouping similar images or objects based on their features.
• Document Clustering: Clustering text documents based on content similarity, useful in search engines and recommendation systems.
• Gene Expression Data Analysis: Grouping genes with similar expression patterns, aiding in biological research.

Advantages of Affinity Propagation

• No Need to Predefine Clusters: Unlike many clustering algorithms, Affinity Propagation does not require the number of clusters to be specified in advance.
• Flexibility: It can handle different types of data, including non-Euclidean data, by customizing the similarity measure.
• Flexible similarities: A domain-specific similarity can be supplied, but the resulting exemplar partition has no general arbitrary-shape or noise-recovery guarantee.

Limitations

• Computational Complexity: Dense message matrices require quadratic memory and roughly quadratic work per iteration; convergence may need many iterations.
• Sensitivity to Parameters: The performance of the algorithm can be sensitive to the choice of the preference parameter, which influences the number of clusters.

Conclusion

Affinity Propagation is useful when actual observations make meaningful representatives and a defensible similarity can be specified. Treat its cluster count as a preference-sensitive model outcome, not an automatically discovered truth.

In the next articles, we will delve deeper into the theoretical foundation of Affinity Propagation, followed by practical implementations using popular machine learning libraries such as Scikit-learn, TensorFlow, and PyTorch.

---