๐ Introduction
Affinity Propagation (AP) is an unsupervised machine learning clustering algorithm that identifies representative data points called exemplars and forms clusters around them. Unlike algorithms such as K-Means, Affinity Propagation does not require the number of clusters to be specified beforehand. Instead, it automatically determines the optimal number of clusters through a process of message passing between data points.
Information
๐ฏ Learning Objectives
- Understand the Affinity Propagation algorithm.
- Learn the concept of exemplars.
- Understand responsibility and availability messages.
- Compare Affinity Propagation with K-Means and Hierarchical Clustering.
๐ What is Affinity Propagation?
Affinity Propagation treats every observation as a potential cluster center (exemplar). During training, observations exchange messages that indicate how suitable a point is to serve as the exemplar for another point. After repeated message updates, a set of exemplars naturally emerges, and all remaining observations are assigned to them.
| Characteristic | Affinity Propagation |
|---|---|
| Learning Type | Unsupervised |
| Requires Number of Clusters | No |
| Cluster Representative | Exemplar |
| Based On | Message Passing |
๐ Key Concepts
| Concept | Description |
|---|---|
| Exemplar | Representative observation selected as the cluster center. |
| Similarity Matrix | Measures similarity between every pair of observations. |
| Responsibility | How strongly one point prefers another point as its exemplar. |
| Availability | How appropriate it is for a point to become an exemplar. |
| Preference | Controls how likely observations are to become exemplars. |
๐ Similarity Matrix
Affinity Propagation begins by computing similarities between all pairs of observations. The similarity is commonly defined as the negative squared Euclidean distance.
Where:
- s(i,k) โ Similarity between observations i and k.
- xแตข, xโ โ Feature vectors.
Remember
๐จ Responsibility Message
The responsibility message measures how suitable observation k is to serve as the exemplar for observation i, compared to all other candidate exemplars.
๐ฅ Availability Message
The availability message measures how appropriate it is for observation k to become the exemplar for observation i, based on support from other observations.
โ๏ธ How Affinity Propagation Works
Compute the similarity matrix.
Initialize responsibility and availability messages.
Update responsibility messages.
Update availability messages.
Repeat message updates until convergence.
Select exemplars and assign observations to them.
๐ณ Affinity Propagation Workflow
๐๏ธ Preference Parameter
The preference parameter strongly influences the number of clusters produced.
- Fewer observations become exemplars.
- Produces fewer, larger clusters.
- More observations become exemplars.
- Produces many smaller clusters.
๐ Affinity Propagation vs K-Means vs Hierarchical Clustering
| Feature | Affinity Propagation | K-Means | Hierarchical |
|---|---|---|---|
| Requires Number of Clusters | No | Yes | No |
| Cluster Representative | Exemplar | Centroid | No Fixed Representative |
| Optimization | Message Passing | Centroid Optimization | Distance-Based Merging |
| Cluster Shape | Flexible | Spherical | Flexible |
| Scalability | Moderate | Excellent | Moderate |
๐๏ธ Important Hyperparameters
| Hyperparameter | Description |
|---|---|
| preference | Controls the number of exemplars. |
| damping | Prevents oscillations during message updates. |
| max_iter | Maximum number of iterations. |
| convergence_iter | Iterations required for convergence. |
| affinity | Similarity measure used by the algorithm. |
๐ Evaluation Metrics
- Silhouette Score
- Davies-Bouldin Index
- Calinski-Harabasz Index
- Adjusted Rand Index (when ground-truth labels are available).
โ๏ธ Advantages and Limitations
- Automatically determines the number of clusters.
- Selects real observations as exemplars.
- No random centroid initialization.
- Works well for moderate-sized datasets.
- Can identify clusters with varying sizes.
- Requires storing the full similarity matrix.
- Memory usage grows quadratically with dataset size.
- Sensitive to the preference parameter.
- Less suitable for very large datasets.
๐ Real-World Applications
| Application | Purpose |
|---|---|
| ๐ผ๏ธ Image Segmentation | Group visually similar regions. |
| ๐ Document Clustering | Identify representative documents. |
| ๐ Customer Segmentation | Find representative customer profiles. |
| ๐งฌ Bioinformatics | Cluster genes using representative exemplars. |
| ๐ต Recommendation Systems | Identify representative products or media. |
| ๐ Social Network Analysis | Detect influential representative users. |
๐ป Practical Example
Affinity Propagation Using Scikit-learn
from sklearn.cluster import AffinityPropagation
import numpy as np
# Sample data
X = np.array([
[1, 2], [1, 3], [2, 2],
[8, 8], [9, 8], [8, 9]
])
# Create model
model = AffinityPropagation(
damping=0.8,
random_state=42
)
# Train model
labels = model.fit_predict(X)
print("Cluster Labels:")
print(labels)
print("Exemplar Indices:")
print(model.cluster_centers_indices_)
print("Cluster Centers:")
print(model.cluster_centers_)โ ๏ธ Common Mistakes
- Ignoring the impact of the preference parameter on the number of clusters.
- Using the algorithm on extremely large datasets.
- Not scaling numerical features before computing similarities.
- Using a damping value that is too low, causing oscillations.
- Expecting Affinity Propagation to outperform simpler algorithms on every dataset.