这篇博客发出来后，我用 Rust 复现代码出现问题。为此，我对对照了 sklearn 的相关代码，反复比较了两天，发现一处 bug，把 += 误写成了 =，导致数据量大的时候完全无法聚类。这个debug过程让我仔细梳理的 AP 算法的计算过程，今天我对这篇博客做了大规模修改，以便能原样展现原论文思想。
这几天的工作给我的体会是，自己觉得看懂论文了，如果不亲自把代码写出来，对论文原理的理解还是非常肤浅。
1. 基本思路
AP 算法的灵感来自投票选举。我们看下面的故事：
辽阔的草原上居住一群人。为便于组织管理，他们想通过投票选举部落首领，把人群分成若干部落，每个部落有一个首领。
投票行为受两个因素影响：
- 个人支持度： 开始阶段，规则不允许投票给自己，因此，大家最初的投票意向是，把自己的一票投给最亲近的人，比如自己的老公，自己的儿子等。
- 民意支持度： 如果某个打算投票给自己的儿子，但是发现大家都不愿意投票给自己儿子，而自己的侄子支持率还挺高，于是他可能决定退而求其次，支持自己的侄子。
这个方法面临两个问题需要思考：
- 问题1：亲人竞争： 记得台湾地区选举领导人，有一年本来蓝营占优势，但是中间杀出个宋楚瑜，分散了蓝赢得选票，导致本来处于弱势的绿营占了上风。如果一个部落内，有两个人获得的支持度相近，如何决定谁最终胜出呢？有没有对聚类的效果造成负面影响？
- 问题2：选票分散： 如果某个部落内部，父亲投票给母亲、母亲投票给儿子，儿子投票给姐姐，姐姐投票给父亲，部落内每个人的票都不够多，会不会造成聚类失败？
2. 一个简单例子
提供一个简单例子，假设点分布在实数轴上，坐标分别为 ：
A
=
1
,
B
=
2
,
C
=
3
,
D
=
5
,
E
=
6
A=1,B=2,C=3,D=5,E=6
A=1,B=2,C=3,D=5,E=6
2.1 相似度矩阵 s
用两个点之间的距离的负数作为两个点之间相似度：
| s(i \ k) | A | B | C | D | E |
|---|
| A | ? | -1.0 | -2.0 | -4.0 | -5.0 |
| B | -1.0 | ? | -1.0 | -3.0 | -4.0 |
| C | -2.0 | -1.0 | ? | -2.0 | -3.0 |
| D | -4.0 | -3.0 | -2.0 | ? | -1.0 |
| E | -5.0 | -4.0 | -3.0 | -1.0 | ? |
按照距离的负数计算相似度，导致相似度全部都是负数。不过没关系，只要能保证数值越大，相似度越高即可，至于数据的符号，初始阶段并不重要。
对角线
s
(
i
,
i
)
s(i,i)
s(i,i) 表示自己与自己的相似度，AP算法建议选择上述矩阵中元素的最小值或者中位数。接下来我们选择最小值得到完整的相似度矩阵：
| s(i \ k) | A | B | C | D | E |
|---|
| A | -5.0 | -1.0 | -2.0 | -4.0 | -5.0 |
| B | -1.0 | -5.0 | -1.0 | -3.0 | -4.0 |
| C | -2.0 | -1.0 | -5.0 | -2.0 | -3.0 |
| D | -4.0 | -3.0 | -2.0 | -5.0 | -1.0 |
| E | -5.0 | -4.0 | -3.0 | -1.0 | -5.0 |
相似度矩阵可以这样理解，行
i
i
i 代表选民，列
k
k
k 代表竞选人。因为
s
(
i
,
i
)
s(i,i)
s(i,i) 选择了矩阵元素的最小值，这表示开始阶段，每个人都不希望自己被选举为领导人。接下来的过程，我们要说服某些优势候选人提升自己成为领导人的意愿，同时也要说服选民选择把票投给具备民意基础的优势候选人。
2.2 个人支持度矩阵 r
上面的相似度矩阵虽然在一定程度上反映了亲情关系，但是，不同行之间数据是不能进行比较的。例如，第1行第2列最大值是-1，意味着选民1会投票给2。但是第2行的最大值-1有两个，意味着选民2会投票给选民1和3。第2行的两个-1才相当于第一行的一个-1。因此，我们需要把相似度矩阵
s
s
s 归一化，得到一个标准化的＂个人支持度矩阵＂。
归一化的方法，是每一行的每一个元素，都要与其他列最大的元素做差，计算自己在选民 i 这里与最强竞争对手的竞争优势。显然，个人支持度矩阵每一行最多有一个元素大于零。具体用下面的公式生成个人支持度矩阵
r
r
r：
r
n
e
w
(
i
,
k
)
←
s
(
i
,
k
)
−
max
k
′
≠
k
{
s
(
i
,
k
′
)
+
a
(
i
,
k
′
)
}
(1)
\tag1 r_{new}(i,k) \gets s(i,k)-\max_{k' \neq k}\{s(i,k')+a(i,k')\}
rnew(i,k)←s(i,k)−k′=kmax{s(i,k′)+a(i,k′)}(1)
其中
a
(
i
,
k
′
)
a(i,k')
a(i,k′) 在初始阶段为零矩阵，其具体含义后面会解释。因此，矩阵
r
(
i
,
k
)
r(i,k)
r(i,k) 结果如下：
| r_new(i \ k) | A | B | C | D | E |
|---|
| A | -4.0 | 1.0 | -1.0 | -3.0 | -4.0 |
| B | 0.0 | -4.0 | 0.0 | -2.0 | -3.0 |
| C | -1.0 | 1.0 | -4.0 | -1.0 | -2.0 |
| D | -3.0 | -2.0 | -1.0 | -4.0 | 1.0 |
| E | -4.0 | -3.0 | -2.0 | 2.0 | -4.0 |
这个矩阵反映了在选民
i
i
i 对候选人
k
k
k 的支持度。一般来讲，每个选民只能投票给一个候选人，大都数情况下，矩阵的每一行只有一个正向支持度，其余的为负向支持度。
为防止矩阵
r
r
r 的更新幅度过大造成结果不收敛，引入阻尼系数
λ
\lambda
λ，控制更新幅度。一般取
λ
=
0.5
\lambda=0.5
λ=0.5，更新公式如下：
r
←
λ
r
+
(
1
−
λ
)
r
n
e
w
(2)
\tag2 r \gets \lambda r + (1-\lambda)r_{new}
r←λr+(1−λ)rnew(2)
由于矩阵
r
r
r 初始化成零矩阵，当前更新结果如下：
| r(i \ k) | A | B | C | D | E |
|---|
| A | -2.0 | 0.5 | -0.5 | -1.5 | -2.0 |
| B | 0.0 | -2.0 | 0.0 | -1.0 | -1.5 |
| C | -0.5 | 0.5 | -2.0 | -0.5 | -1.0 |
| D | -1.5 | -1.0 | -0.5 | -2.0 | 0.5 |
| E | -2.0 | -1.5 | -1.0 | 1.0 | -2.0 |
2.3 民意支持度矩阵 a
接下来，大家根据当前
r
r
r 提供的支持度结果，做进一步的决策调整。简单地讲，基本策略就是”批评与自我表扬“。虽然一开始大家都很谦虚，自我支持度设置成为一个较低的起点。但是，竞选已经开始了，每个人都需要找理由加强自我支持度，降低对其他人的支持度。所以后续步骤就是找理由增加对自己的支持度，降低对别人的支持度。
2.3.1 表扬自我
我们可以把候选人
k
k
k 对自己的支持度理解为候选人的自信心。初始阶段，自我支持度
r
(
k
,
k
)
r(k,k)
r(k,k) 都是负值，呈现出完全没有自信心的样子。我们需要根据选民的投票意向，提升候选人的自信心。计算方法是，把矩阵
r
r
r 每一列中的正数累加起来保存在对角线
a
(
k
,
k
)
a(k,k)
a(k,k) 的位置。公式如下：
a
n
e
w
(
k
,
k
)
=
∑
i
′
≠
k
max
{
(
0
,
r
(
i
′
,
k
)
)
}
(3)
\tag3 a_{new}(k,k)=\sum_{i'\neq k}\max\{(0,r(i',k))\}
anew(k,k)=i′=k∑max{(0,r(i′,k))}(3)
这样我们得到了民意支持度矩阵 主对角线的值：
| a_new(i \ k) | A | B | C | D | E |
|---|
| A | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| B | 0.0 | 1.0 | 0.0 | 0.0 | 0.0 |
| C | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| D | 0.0 | 0.0 | 0.0 | 1.0 | 0.0 |
| E | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 |
显然，候选人 B、D、E 找到了提升自我支持度的理由。
2.3.2 批评别人
接下来要找理由降低对其他人的支持度。当然这个理由应该优雅一些。主要原则如下：
- 既然是降低对别人的支持度，这个增量必然不会是大于零的数值。
- 也不能太过分，降低幅度尽量不要太多。
选民
i
i
i 对候选者
k
k
k 的支持度，会受其他选民支持度的影响。其影响程度包括两部分：
- 候选者
k
k
k 自信心
r
(
k
,
k
)
r(k,k)
r(k,k) 。候选者自信心很重要，后面我们会看到，候选人
k
k
k 自我支持度大于对其他人的支持度，也就是自己愿意投票给自己时，他才能成为聚类中心。
- 其他选民
i
′
i'
i′ 对候选者
k
k
k 的正的投票意向
∑
i
′
∉
{
i
,
k
}
{
max
(
0
,
r
(
i
′
,
k
)
)
}
\sum_{i' \notin \{i,k\}} \{\max(0,r(i',k))\}
∑i′∈/{i,k}{max(0,r(i′,k))}
也就是说，如果
k
k
k 自己有信心，其他选民也都支持
k
k
k 。显然：
- 如果二者之和大于零，也就是民意非常正面，
i
i
i 就没有理由降低对
k
k
k 的支持度。
- 如果二者之和小于零，也就是民意非常负面，
i
i
i 就可以用这个结果作为对
k
k
k 支持度的增量。因为计算过程中采用
max
\max
max 运算，可以说
i
i
i 对
k
k
k 还是手下留情了，选择了较小幅度的负增量。
综上述，民意支持度矩阵 计算公式如下：
【表扬自我】：
a
n
e
w
(
k
,
k
)
=
∑
i
′
≠
k
max
{
(
0
,
r
(
i
′
,
k
)
)
}
(4)
\tag4 a_{new}(k,k)=\sum_{i'\neq k}\max\{(0,r(i',k))\}
anew(k,k)=i′=k∑max{(0,r(i′,k))}(4)
【批评别人】：
a
n
e
w
(
i
,
k
)
=
min
{
0
,
r
(
k
,
k
)
+
∑
i
′
∉
{
i
,
k
}
{
max
(
0
,
r
(
i
′
,
k
)
)
}
}
,
i
≠
k
(5)
\tag5 a_{new}(i,k)=\min\{0,r(k,k)+\sum_{i' \notin \{i,k\}} \{\max(0,r(i',k))\}\},i \neq k
anew(i,k)=min{0,r(k,k)+i′∈/{i,k}∑{max(0,r(i′,k))}},i=k(5)
按照上述公式，民意矩阵
a
(
i
,
k
)
a(i,k)
a(i,k) 计算结果如下：
| a_new(i \ k) | A | B | C | D | E |
|---|
| A | 0.0 | -1.5 | -2.0 | -1.0 | -1.5 |
| B | -2.0 | 1.0 | -2.0 | -1.0 | -1.5 |
| C | -2.0 | -1.5 | 0.0 | -1.0 | -1.5 |
| D | -2.0 | -1.0 | -2.0 | 1.0 | -2.0 |
| E | -2.0 | -1.0 | -2.0 | -2.0 | 0.5 |
为防止矩阵
a
a
a 的更新幅度过大造成结果不收敛，引入阻尼系数
λ
\lambda
λ，控制更新幅度。一般取
λ
=
0.5
\lambda=0.5
λ=0.5，更新公式如下：
a
←
λ
a
+
(
1
−
λ
)
a
n
e
w
(6)
\tag6 a \gets \lambda a + (1-\lambda)a_{new}
a←λa+(1−λ)anew(6)
由于矩阵
a
a
a 初始化成零矩阵，当前更新结果如下：
| a(i \ k) | A | B | C | D | E |
|---|
| A | 0.0 | -0.75 | -1.0 | -0.5 | -0.75 |
| B | -1.0 | 0.5 | -1.0 | -0.5 | -0.75 |
| C | -1.0 | -0.75 | 0.0 | -0.5 | -0.75 |
| D | -1.0 | -0.5 | -1.0 | 0.5 | -1.0 |
| E | -1.0 | -0.5 | -1.0 | -1.0 | 0.25 |
2.4 决策矩阵 c
决策矩阵用来决定是否结束算法。决策矩阵
c
c
c 计算方法如下：
c
(
i
,
k
)
=
r
(
i
,
k
)
+
a
(
i
,
k
)
(7)
\tag7 c(i,k)=r(i,k)+a(i,k)
c(i,k)=r(i,k)+a(i,k)(7)
即综合考虑个人支持度和民意支持度。根据上述数据，
c
(
i
,
k
)
c(i,k)
c(i,k) 计算结果如下：
| c(i \ k) | A | B | C | D | E |
|---|
| A | -4.0 | -0.5 | -3.0 | -4.0 | -5.5 |
| B | -2.0 | -3.0 | -2.0 | -3.0 | -4.5 |
| C | -3.0 | -0.5 | -4.0 | -2.0 | -3.5 |
| D | -5.0 | -3.0 | -3.0 | -3.0 | -1.0 |
| E | -6.0 | -4.0 | -4.0 | 0.0 | -3.5 |
决策过程如下：
- 矩阵
c
c
c 对角线上大于零的元素对应的列为当前的聚类中心。
- 循环到公式(1) 继续更新矩阵
r
,
a
,
c
r,a,c
r,a,c，如果聚类中心连续多次不发生变化（控制参数
convergence_iter，一般设为 15），则聚类结束。 - 如果循环迭代次数超过最大迭代次数（控制参数
max_iter，一般设为 200），聚类结束，显示聚类失败。
上述的迭代计算结果列举如下，供大家参考：
| c(i \ k) | A | B | C | D | E |
|---|
| A | -2.75 | 0.5 | -2.375 | -2.75 | -4.5 |
| B | -1.625 | -0.75 | -1.625 | -1.5 | -3.25 |
| C | -2.375 | 0.25 | -2.75 | -0.75 | -2.5 |
| D | -4.125 | -1.25 | -2.125 | -1.0 | -0.5 |
| E | -5.125 | -2.25 | -3.125 | 0.5 | -1.75 |
| c(i \ k) | A | B | C | D | E |
|---|
| A | -1.71875 | 1.46875 | -1.28125 | -1.875 | -3.4375 |
| B | [-0.9375 | 0.96875 | -0.75 | -0.1875 | -1.75 |
| C | 1.59375 | 1.0625 | -1.59375 | 0.0 | -1.5625 |
| D | -2.84375 | -0.25 | -0.90625 | 0.375 | 0.0 |
| E | -3.84375 | -1.25 | -1.65625 | 0.875 | -0.4375 |
我们看到 B、D 成为聚类中心。上述循环重复 convergence_iter = 15 次，聚类中心都是 B、D，算法结束。
3. 问题和质疑
回答一下文章开头提的问题。
- 问题1：亲人竞争： 记得台湾地区选举领导人，有一年本来蓝营占优势，但是中间杀出个宋楚瑜，分散了蓝赢得选票，导致本来处于弱势的绿营占了上风。如果一个部落内，有两个人获得的支持度相近，如何决定谁最终胜出呢？有没有对聚类的效果造成负面影响？
我设计了以下几个数进行聚类：
{
1
,
2
,
3
,
4
,
11
,
12
}
\{1,2,3,4,11,12\}
{1,2,3,4,11,12}，其中
2
,
3
2,3
2,3 都可以做前四个元素的聚类中心。迭代了 39 轮（convergence_iter = 15），终于给出收敛答案，聚类中心为：
{
2
,
11
}
\{2,11\}
{2,11}。
- 问题2：选票分散： 如果某个部落内部，父亲投票给母亲、母亲投票给儿子，儿子投票给姐姐，姐姐投票给父亲，部落内每个人的票都不够多，会不会造成聚类失败？
我设计了如下数据集：
{
(
1
,
1
)
,
(
2
,
1
)
,
(
1
,
2
)
,
(
2
,
2
)
,
(
111
,
112
)
,
(
112
,
111
)
}
\{(1,1),(2,1),(1,2),(2,2),(111,112),(112,111)\}
{(1,1),(2,1),(1,2),(2,2),(111,112),(112,111)}，聚类结果：
{
(
1
,
1
)
,
(
2
,
1
)
,
(
1
,
2
)
,
(
2
,
2
)
,
(
111
,
112
)
,
(
112
,
111
)
}
\{(1,1),(2,1),(1,2),(2,2),(111,112),(112,111)\}
{(1,1),(2,1),(1,2),(2,2),(111,112),(112,111)}。
把数据加上随机扰动：
{
(
1.1
,
1.3
)
,
(
2.2
,
1.4
)
,
(
1.01
,
2.22
)
(
2.13
,
2.12
)
,
(
111.31
,
112.12
)
,
(
112.24
,
111.37
)
}
\{(1.1,1.3),(2.2,1.4),(1.01,2.22)(2.13,2.12),(111.31,112.12),(112.24,111.37)\}
{(1.1,1.3),(2.2,1.4),(1.01,2.22)(2.13,2.12),(111.31,112.12),(112.24,111.37)},聚类结果为：
{
(
22.13
，
2.12
)
,
(
111.31
,
112.12
)
}
\{(22.13，2.12),(111.31,112.12)\}
{(22.13，2.12),(111.31,112.12)}。
可以看出，第二个问题从理论上无法解决。随机数据扰动的结果表明，真实应用情况下，不会出现这类极端结果。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
