Theory Behind Affinity Propagation

Affinity Propagation identifies representative observations, known as exemplars, which serve as cluster representatives. It does not require n_clusters; instead, similarities and preference values induce a number of exemplars. Preference does not estimate an optimal number of clusters.

---

1. Key Concepts in Affinity Propagation

1.1 Similarity

The Affinity Propagation algorithm starts by defining a similarity measure between pairs of data points. The similarity $s(i, k)$ represents how well-suited data point $k$ is to be the exemplar for data point $i$. The similarity can be calculated using various distance metrics, such as Euclidean distance or cosine similarity. In the case of Euclidean distance, the similarity is typically defined as:

$$s(i, k) = -\|x_i - x_k\|^2$$

Here, $x_i$ and $x_k$ are the feature vectors of data points $i$ and $k$, respectively, and $\|x_i - x_k\|$ denotes the Euclidean distance between them. The negative sign ensures that points closer to each other have higher similarity.

1.2 Responsibility and Availability

Affinity Propagation relies on two types of messages exchanged between data points: responsibility and availability. These messages are iteratively updated to determine which data points should be exemplars.

• Responsibility $r(i, k)$: The responsibility message reflects how well-suited point $k$ is to be the exemplar for point $i$, considering other potential exemplars for $i$. Mathematically, it is defined as:

  $$r(i, k) = s(i, k) - \max_{k' \neq k} \{a(i, k') + s(i, k')\}$$

  This equation implies that the responsibility $r(i, k)$ is the similarity $s(i, k)$ minus the maximum of the sum of availability and similarity for any other candidate exemplar $k'$. This helps to focus on the best candidate exemplar.

• Availability $a(i, k)$: The availability message reflects how appropriate it would be for point $i$ to choose point $k$ as its exemplar, considering how many other points want to select $k$ as their exemplar. It is computed as:

  $$a(i, k) = \min \left(0, r(k, k) + \sum_{i' \notin \{i, k\}} \max(0, r(i', k))\right)$$

  Here, $r(k, k)$ is the self-responsibility, indicating the extent to which $k$ is suitable as its own exemplar. The sum captures how many other points consider $k$ to be their exemplar.

1.3 Message Passing

The key to Affinity Propagation lies in iteratively updating these responsibility and availability messages until convergence. Initially, all availability values are set to zero:

$$a(i, k) = 0 \quad \text{for all} \quad i, k$$

The responsibility and availability messages are then updated iteratively according to the following rules:

1. Update Responsibility:

   $$r(i, k) \leftarrow s(i, k) - \max_{k' \neq k} \{a(i, k') + s(i, k')\}$$

2. Update Availability:

   $$a(i, k) \leftarrow \min \left(0, r(k, k) + \sum_{i' \notin \{i, k\}} \max(0, r(i', k))\right)$$

3. Self-Responsibility:

   For each point $k$ to consider itself as an exemplar:

   $$a(k, k) \leftarrow \sum_{i' \neq k} \max(0, r(i', k))$$

These updates continue until the changes in responsibility and availability are below a certain threshold, indicating convergence.

1.4 Selection of Exemplars

After the message-passing process converges, the exemplars are selected. For each data point $i$, the exemplar $k$ is chosen based on the maximum of the sum of responsibility and availability:

$$k = \arg\max_{k'} \{r(i, k') + a(i, k')\}$$

This means that the exemplar for point $i$ is the point $k$ that maximizes the sum of responsibility and availability.

2. Preference Parameter

The preference parameter $p$ plays a crucial role in Affinity Propagation. It determines the likelihood of each point being chosen as an exemplar. Typically, $p$ is set to the median or minimum of the input similarities to influence the number of clusters. A higher preference value increases the number of clusters, while a lower value reduces it.

3. Convergence and Stability

Affinity Propagation can be sensitive to initialization and parameter choices, particularly the preference parameter. Convergence is not always guaranteed, and the algorithm may oscillate between configurations. To mitigate this, damping factors are often introduced in the update equations to stabilize the iterations.

3.1 Damping Factor

The damping factor $\lambda$ is introduced to control the update of messages. Damping mixes each old message with the newly computed undamped message:

$$r^{(t)}(i, k) \leftarrow \lambda r^{(t-1)}(i, k) + (1 - \lambda)\tilde r^{(t)}(i, k)$$ $$a^{(t)}(i, k) \leftarrow \lambda a^{(t-1)}(i, k) + (1 - \lambda)\tilde a^{(t)}(i, k)$$

In scikit-learn, damping must be in $[0.5,1)$; larger values can suppress oscillation but slow adaptation. Convergence is still not guaranteed. convergence_iter requires stable exemplar decisions for that many iterations, while max_iter is a hard stop.

Each iteration updates dense $n\times n$ messages, giving roughly quadratic time per iteration and quadratic memory. With affinity='euclidean', scikit-learn uses negative squared Euclidean distances as similarities. With affinity='precomputed', supply similarities where larger is better, including diagonal preferences—not a distance matrix.

4. Advantages and Disadvantages

4.1 Advantages

• Automatic Cluster Detection: Affinity Propagation does not require the number of clusters to be specified beforehand.
• Flexibility: It can find clusters of various shapes and sizes, making it useful for diverse data types.
• Exemplar-Based: The algorithm identifies actual data points as exemplars, providing a clear representative for each cluster.

4.2 Disadvantages

• Computationally Intensive: The algorithm can be computationally expensive, particularly for large datasets.
• Sensitivity to Parameters: The algorithm's performance can be highly sensitive to the choice of the preference parameter.
• Convergence Issues: Without careful tuning, the algorithm may fail to converge, especially in the presence of noise.

Conclusion

Affinity Propagation offers an exemplar-based partition without a requested cluster count. Its output is preference-sensitive, may fail to converge, and has quadratic storage, so similarity semantics, damping, convergence, and stability must all be reported.