Affinity Propagation

Affinity Propagation#

Note

Affinity 通常被翻译为近邻传播算法。
它的核心思想是：迭代更新点与点之间的 responsibility 和 availability，得到每个点的 exemplar（代表）作为聚类中心，完成聚类。
它不需要预先指定聚类的个数，但是算法的时间复杂度较高。

所需数据#

As an input, the algorithm requires us to provide two sets of data:

Similarities between data points，越大越好，如果已有点与点之间的距离的话取个负号就好。
Preferences, representing each data point’s suitability to be an exemplar. We may have a priori information which points could be favored for this role. 如果不指定的话，所有点的 preference 被设置为同一个数，比如说 the median of the input similarities 或者 the minimum of the input similarities。

Both similarity and preferences are often represented through a single matrix, where the values on the main diagonal represent preferences（这样会比较方便，自己与自己的 similarity 也没有什么意义）。下面我们用一个例子来加以说明。Suppose that we had the following dataset. Each of the participants is represented as a data point in a 5 dimensional space:

Participants	Tax rate	Fee	Interest rate	Quantity limit	Price limit
Alice	3	4	3	2	1
Bob	4	3	5	1	1
Cary	3	5	3	3	3
Doug	2	1	3	3	2
Edna	1	1	3	2	3

我们先使用点与点之间欧氏距离的相反数作为它们之间的相似度，比如 Alice 和 Bob 之间的相似度是 \(-((3-4)^2 + (4-3)^2 + (3-5)^2 + (2-1)^2 + (1-1)^2) = -7\)，这样我们得到相似度矩阵：

Participants	Alice	Bob	Cary	Doug	Edna
Alice	0	-7	-6	-12	-17
Alice	-7	0	-17	-17	-22
Cary	-6	-17	0	-18	-21
Doug	-12	-17	-18	0	-3
Edna	-17	-22	-21	-3	0

因为没有先验的 preference 信息，我们将所有点的 preference 设置为同一个数。需要注意的是，preference 越小，最后聚类个数一般也越少，反之就越多（了解算法之后我们将知道为什么会这样）。这里我们将 preference 设置为相似度矩阵的最小值 -22：

Participants	Alice	Bob	Cary	Doug	Edna
Alice	-22	-7	-6	-12	-17
Alice	-7	-22	-17	-17	-22
Cary	-6	-17	-22	-18	-21
Doug	-12	-17	-18	-22	-3
Edna	-17	-22	-21	-3	-22

算法#

现在我们输入相似度矩阵 \(s(i, k)\)。The algorithm runs through a number of iterations, each iteration has two message-passing steps:

计算吸引度 responsibility \(r(i, k)\)，表示从 \(i\) 的角度看 \(k\) 作为其代表（exemplar）的适合程度（在考虑了其它 \(k'\) 之后）
计算归属度 availability \(a(i, k)\)，表示从 \(k\) 的角度看 \(i\) 作为其投票人的适合程度（在考虑了其它 \(i'\) 之后）

Resonsibility 的迭代公式如下（初始设置 \(a(i, k) = 0\)）：

\[ r(i, k)\leftarrow s(i, k) - \max_{k'\ne k}(a(i, k') + s(i, k')) \]

\(a(i, k') + s(i, k')\) 大就表示 \(k'\) 离 \(i\) 近而且有空闲的位置，\(k\) 要与其他的候选者 \(k'\) 进行竞争。
\(r(k, k)\) 代表自我吸引度，它的值较小的话，就说明相较于作为聚类中心，点 \(k\) 更适合归属于其他聚类中心！

Availability 的迭代公式如下：

\[\begin{split} \begin{equation} \begin{split} a(i, k)&\leftarrow \min\left(0, r(k, k) + \sum_{i'\notin\{i, k\}}\max(0, r(i', k))\right)\quad (i\ne k)\\ a(k, k)&\leftarrow \sum_{i'\ne k}\max(0, r(i', k)) \end{split} \end{equation} \end{split}\]

\(a(i, k)\) 等于自我吸引度 \(r(k, k)\) 加上从其他点获得的积极吸引度，这里只加上了积极的吸引度，因为只有积极的吸引度才会支持 \(k\) 作为聚类中心。
\(a(k, k)\) 代表自我归属度，它等于从其他点获得的积极吸引度之和（有很多人喜欢我）。

点 \(i\) 选取使得 \(r(i, k) + a(i, k)\) 最大的 \(k\) 作为其代表，有同一个代表的点是同一类。当聚类边界不再变化或者达到最大轮数时停止迭代。

使用方法#

import numpy as np

X = np.array([[1, 2], [1, 4], [1, 0],
              [4, 2], [4, 4], [4, 0]])

from sklearn.cluster import AffinityPropagation

# 输入稀疏矩阵 X
clustering = AffinityPropagation(random_state=5).fit(X)

clustering.labels_

array([0, 0, 0, 1, 1, 1])

clustering.predict([[0, 0], [4, 4]])

array([0, 1])

clustering.cluster_centers_

array([[1, 2],
       [4, 2]])

Affinity Propagation

Contents

Affinity Propagation#

所需数据#

算法#

使用方法#