type
status
password
date
slug
summary
category
URL
tags
icon
1. 基本思路
AP 算法的灵感来自投票选举。我们看下面的故事：
辽阔的草原上居住一群人。为便于组织管理，他们想通过投票选举部落首领，把人群分成若干部落，每个部落有一个首领。
投票行为受两个因素影响：
- 个人支持度： 开始阶段，规则不允许投票给自己，因此，大家最初的投票意向是，把自己的一票投给最亲近的人，比如自己的老公，自己的儿子等。
- 民意支持度： 如果某个打算投票给自己的儿子，但是发现大家都不愿意投票给自己儿子，而自己的侄子支持率还挺高，于是他可能决定退而求其次，支持自己的侄子。
这个方法面临两个问题需要思考：
- 问题1：亲人竞争： 记得台湾地区选举领导人，有一年本来蓝营占优势，但是中间杀出个宋楚瑜，分散了蓝赢得选票，导致本来处于弱势的绿营占了上风。如果一个部落内，有两个人获得的支持度相近，如何决定谁最终胜出呢？有没有对聚类的效果造成负面影响？
- 问题2：选票分散： 如果某个部落内部，父亲投票给母亲、母亲投票给儿子，儿子投票给姐姐，姐姐投票给父亲，部落内每个人的票都不够多，会不会造成聚类失败？
2. 一个简单例子
提供一个简单例子，假设点分布在实数轴上，坐标分别为 ：
2.1 相似度矩阵
用两个点之间的距离的负数作为两个点之间相似度：
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 | ? |
按照距离的负数计算相似度，导致相似度全部都是负数。不过没关系，只要能保证数值越大，相似度越高即可，至于数据的符号，初始阶段并不重要。
设置
对角线 表示自己与自己的相似度，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 |
相似度矩阵可以这样理解，行 代表选民，列 代表竞选人。因为 选择了矩阵元素的最小值，这表示开始阶段，每个人都不希望自己被选举为领导人。接下来的过程，我们要说服某些优势候选人提升自己成为领导人的意愿，同时也要说服选民选择把票投给具备民意基础的优势候选人。
2.2 个人支持度矩阵 r
上面的相似度矩阵虽然在一定程度上反映了亲情关系，但是，不同行之间数据是不能进行比较的。例如，第1行第2列最大值是-1，意味着选民1会投票给2。但是第2行的最大值-1有两个，意味着选民2会投票给选民1和3。第2行的两个-1才相当于第一行的一个-1。因此，我们需要把相似度矩阵 归一化，得到一个标准化的＂个人支持度矩阵＂。
归一化的方法，是每一行的每一个元素，都要与其他列最大的元素做差，计算自己在选民 这里与最强竞争对手的竞争优势。显然，个人支持度矩阵每一行最多有一个元素大于零。具体用下面的公式生成个人支持度矩阵 ：
其中 在初始阶段为零矩阵，其具体含义后面会解释。因此，矩阵 结果如下：
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 |
这个矩阵反映了在选民 对候选人 的支持度。一般来讲，每个选民只能投票给一个候选人，大都数情况下，矩阵的每一行只有一个正向支持度，其余的为负向支持度。
为防止矩阵 的更新幅度过大造成结果不收敛，引入阻尼系数 ，控制更新幅度。一般取 ，更新公式如下：
由于矩阵 初始化成零矩阵，当前更新结果如下：
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
接下来，大家根据当前 提供的支持度结果，做进一步的决策调整。简单地讲，基本策略就是”批评与自我表扬“。虽然一开始大家都很谦虚，自我支持度设置成为一个较低的起点。但是，竞选已经开始了，每个人都需要找理由加强自我支持度，降低对其他人的支持度。所以后续步骤就是找理由增加对自己的支持度，降低对别人的支持度。
2.3.1 表扬自我
我们可以把候选人 对自己的支持度理解为候选人的自信心。初始阶段，自我支持度 都是负值，呈现出完全没有自信心的样子。我们需要根据选民的投票意向，提升候选人的自信心。计算方法是，把矩阵 每一列中的正数累加起来保存在对角线 的位置。公式如下：
这样我们得到了民意支持度矩阵 主对角线的值：
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 批评别人
接下来要找理由降低对其他人的支持度。当然这个理由应该优雅一些。主要原则如下：
- 既然是降低对别人的支持度，这个增量必然不会是大于零的数值。
- 也不能太过分，降低幅度尽量不要太多。
选民 对候选者 的支持度，会受其他选民支持度的影响。其影响程度包括两部分：
- 候选者 自信心 。候选者自信心很重要，后面我们会看到，候选人 自我支持度大于对其他人的支持度，也就是自己愿意投票给自己时，他才能成为聚类中心。
- 其他选民 对候选者 的正的投票意向
也就是说，如果 自己有信心，其他选民也都支持 。显然：
- 如果二者之和大于零，也就是民意非常正面， 就没有理由降低对 的支持度。
- 如果二者之和小于零，也就是民意非常负面， 就可以用这个结果作为对 支持度的增量。因为计算过程中采用 运算，可以说 对 还是手下留情了，选择了较小幅度的负增量。
综上
综上述，民意支持度矩阵 计算公式如下：
按照上述公式，民意矩阵 a ( i , k ) a(i,k) a(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 | 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
决策矩阵用来决定是否结束算法。决策矩阵 计算方法如下：
即综合考虑个人支持度和民意支持度。根据上述数据， 计算结果如下：
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 |
决策过程如下：
- 矩阵 对角线上大于零的元素对应的列为当前的聚类中心。
- 循环到公式(1) 继续更新矩阵 ，如果聚类中心连续多次不发生变化（控制参数
convergence_iter，一般设为15），则聚类结束。
- 如果循环迭代次数超过最大迭代次数（控制参数
max_iter，一般设为200），聚类结束，显示聚类失败。
上述的迭代计算结果列举如下，供大家参考：
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 |
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：亲人竞争： 记得台湾地区选举领导人，有一年本来蓝营占优势，但是中间杀出个宋楚瑜，分散了蓝赢得选票，导致本来处于弱势的绿营占了上风。如果一个部落内，有两个人获得的支持度相近，如何决定谁最终胜出呢？有没有对聚类的效果造成负面影响？
我设计了以下几个数进行聚类：，其中 都可以做前四个元素的聚类中心。迭代了 39 轮（
convergence_iter = 15），终于给出收敛答案，聚类中心为：。- 问题2：选票分散： 如果某个部落内部，父亲投票给母亲、母亲投票给儿子，儿子投票给姐姐，姐姐投票给父亲，部落内每个人的票都不够多，会不会造成聚类失败？
我设计了如下数据集：，聚类结果：。
把数据加上随机扰动：，聚类结果为：。
可以看出，第二个问题从理论上无法解决。随机数据扰动的结果表明，真实应用情况下，不会出现这类极端结果。