一分钟理解 AP(Affinity Propagation) 亲和⼒传播算法

从来没有一个算法让我研究好几天都搞不明白，AP算法算是第一个。弄了好几天，打草纸用了几十页，反复琢磨，最后都怀疑人生了。我觉得网上那么多介绍 AP 的文章，基本上没有一篇能讲明白的。最后我都觉得 AP 的作者可能都没弄明白。

看在这篇论文发表在美国科学杂志的份上，终于耐着性子，梳理出其中的思路。在此奉献给大家，如果我这篇文章你都看不懂，那就洗洗睡吧，别伤脑筋了。

1. 基本思路

AP 算法的灵感来自投票选举。我们看下面的故事：

1.1 划分部落，选举首领

辽阔的草原上居住一群人。为便于组织管理，他们想通过投票选举部落首领，把人群分成若干部落，每个部落有一个首领。

投票规则很简单，(1) 每个人只能推选一个人做自己的首领; (2) 想当部落首领的人必须投票给自己。

AP 算法的基本思路是，开始的时候每个人的自我支持度设置为较低的数值，然后整个选举过程不断提升潜在首领的自我支持度和其他人对潜在首领的支持度，同时降低对民意较差的候选人的支持度。整个过程关注两件事情：

• 如何发现潜在的部落首领？
• 如何让选民加入正确的部落？

1.2 按亲情投票

其实人性决定了投票的倾向性，大家都愿意投给最亲近的人。可是谁是自己最亲近的人呢？很显然自己与自己是最亲近的。但是，如果每个人都投票给自己，按照规则就只能一个人组成一个部落。大家都明白这一点，于是人们虚伪宣布自己绝不亲近自己，如果世界上只有一个仇人，那就是我自己。

接下来，我用投票支持度这个词来说明选民对候选人的支持程度或者亲密程度。人群中的每一个人在选举中，既是选民，又是候选人。

第一轮投票的结果是，大家把票都投给了其他与自己最亲近的人，比如自己的老公，自己的儿子等。因为第一轮投票所有人都不会推选自己，所以投票后必然无法完成划分部落的任务。

1.3 发现潜在的部落首领

但是，第一轮投票还是有成果的。大家统计了一下票数，发现有些人得了一些票，未来有可能被推选为某个部落首领，还有些人没有得到投票，成为首领的可能性就低一些。

要利用这次的投票结果完成两件事情：

• 第一件事情，根据当前投票结果，每个人都要想法提升对自己的支持度，以便能产生部落首领。方法很简单，只要把其他人对自己的支持度累加起来，叠加到自我支持度上即可。

• 第二件事情，根据当前投票结果，每个人都要想法降低对其他人的支持度，以便淘汰无希望的候选者。方法也很简单，比如张三想降低对李四的支持度，他就先看一下李四的自我支持度以及群众（张三和李四以外的其他人）的支持度，如果这个支持度很高，张三就不降低对李四的支持度。如果这个支持度不是很高，就酌情降低对李四的支持度。

这样一来的话，有些人的自信心越来越足，越来越愿意把票投给自己。有些人的自信心越来越低，越来越越愿意投票给其他人。

1.4 投票方法的可收敛性

最后还剩一个问题，为什么自信心较低的这些人愿意把票投给潜在的部落首领呢？

这个问题的原因也很简单。例如张三决定降低对李四的支持度的时候，如果李四的自我支持度很高，可能导致张三不会降低、或者略微降低对李四的支持度，从而导致张三对李四的支持度较高一些。反之，如果李四自我支持度较低，其他人对他支持度也不高，就会导致张三会大幅度降低对李四的支持度。也就是说，张三对李四支持度的变化，是受其他人影响的，因此，最终产生”从众“效应，从而能够形成统一意见，选出部落首领。

2. 一个简单例子

为简化问题，我们提供一个极为简单的例子，假设点分布在实数轴上，坐标分别为 ：
$$A=1,B=2,C=3,D=5,E=6$$

2.1 相似度矩阵 s

用两个点之间的距离的负数作为两个点之间相似度，也就是所谓的亲和力。两个点之间的相似度越大，说明两个点属于一个类别的可能性越大。根据上述坐标，可以得出相似度矩阵：

i \ k	A	B	C	D	E
A	-	-1	-2	-4	-5
B	-1	-	-1	-3	-4
C	-2	-1	-	-2	-3
D	-4	-3	-2	-	-1
E	-5	-4	-3	-1	-

按照距离的负数计算相似度，导致相似度全部都是负数。不过没关系，只要能保证数值越大，相似度越高即可，至于数据的符号，初始阶段并不重要。

对角线 $s(i,i)$ 表示自己与自己的亲和力，按理说应该取 $0$ 或上述矩阵中最大的值。但实际上不能这么干，如果每个人都认为自己最适合当领导的话，就无法聚类了。因此，AP算法建议选择上述矩阵中元素的最小值或者中位数。接下来我们选择最小值得到完整的相似度矩阵：

i \ k	A	B	C	D	E
A	-5	-1	-2	-4	-5
B	-1	-5	-1	-3	-4
C	-2	-1	-5	-2	-3
D	-4	-3	-2	-5	-1
E	-5	-4	-3	-1	-5

一般来讲，AP算法的灵感来自一个群体通过自发投票选举小组领导人的过程。人们投票一般取决于两个策略：任人唯亲、兼顾民意。比如，你想推选自己的儿子做村长，但是考虑到自己的儿子实在不受大家喜欢，于是投票给了人缘稍微好一点的侄子。这样做不至于把选票浪费在毫无希望的儿子身上，同时又耽误了有希望竞选成功的侄子。

相似度矩阵可以这样理解，行 $i$ 代表选民，列 $k$ 代表竞选人。因为 $s(i,i)$ 选择了矩阵元素的最小值，这表示开始阶段，每个人都不希望自己被选举为领导人。接下来的过程，我们要说服某些优势候选人提升自己成为领导人的意愿，同时也要说服选民选择把票投给具备民意基础的优势候选人。

2.2 亲情矩阵 r

上面的相似度矩阵虽然在一定程度上反映了亲情关系，但是，不同行之间数据是不能进行比较的。例如，第1行第2列最大值是-1，意味着选民1会投票给2。但是第2行的最大值-1有两个，意味着选民2会投票给选民1和3。第2行的两个-1才相当于第一行的一个-1。因此，我们需要把相似度矩阵 $s$ 归一化，得到一个标准化的＂亲情矩阵＂。
用下面的公式生成亲情矩阵 $r$：

r(i,k)=s(i,k)−max⁡k′≠k{s(i,k′)+a(i,k′)}(1)\tag1 r(i,k)=s(i,k)-\max_{k' \neq k}\{s(i,k')+a(i,k')\} r(i,k)=s(i,k)−k′=kmax​{s(i,k′)+a(i,k′)}(1)
其中 $a(i,k^{\prime })$ 在初始阶段为零矩阵，其具体含义后面会解释。因此，矩阵 $r(i,k)$ 结果如下：

i \ k	A	B	C	D	E
A	-4	1	-1	-3	-4
B	0	-4	0	-2	-4
C	-2	1	-4	-2	-3
D	-3	-2	-1	-4	1
E	-4	-3	-2	2	-4

这个矩阵反映了在选民 $i$ 对候选人 $k$ 的支持度。一般来讲，每个选民只能投票给一个候选人，大都数情况下，矩阵的每一行只有一个正向支持度，其余的为负向支持度。

如果我们认为正向支持度表示支持，零支持度表示不反对不支持，负支持度表示反对，那么，当前的情况表明：A、C支持B，但 B 反对自己；同时呢，D、E都支持对方，同时都反对自己。因此，目前是无法实现聚类的。

聚类成功的条件应该是，聚类中心首先自己要支持自己，然后其他候选人都应该支持某个聚类中心。

接下来要解决两个问题：

• 【问题1】如何让 B 支持自己
• 【问题2】如何说服 D、E中的一个支持对方，而另一个能支持自己。

解决方法是通过民意调查，改变选民的对候选人的支持度。

2.3 民意矩阵 a

接下来，大家根据当前 $r$ 提供的支持度结果，做进一步的决策调整。简单地讲，基本策略就是”批评与自我表扬“。虽然一开始大家都很谦虚，自我支持度设置成为一个较低的起点。但是，竞选已经开始了，每个人都需要找理由加强自我支持度，降低对其他人的支持度。所以后续步骤就是找理由增加对自己的支持度，降低对别人的支持度。

2.3.1 表扬自我

我们可以把候选人 $k$ 对自己的支持度理解为候选人的自信心。初始阶段，自我支持度 $r(k,k)$ 都是负值，呈现出完全没有自信心的样子。我们需要根据选民的投票意向，提升候选人的自信心。计算方法是，把矩阵 $r$ 每一列中的正数累加起来保存在对角线 $a(k,k)$ 的位置。公式如下：
$$a(k,k)=\sum _{i^{\prime }\ne k}\max \{(0,r(i^{\prime },k))\}\text{\hspace{1em}(2)}$$

这样我们得到了民意矩阵主对角线的值：

i \ k	A	B	C	D	E
A	0	0	0	0	0
B	0	2	0	0	0
C	0	0	0	0	0
D	0	0	0	2	0
E	0	0	0	0	1

显然，候选人 B、D、E 找到了提升自我支持度的理由。

2.3.2 批评别人

接下来要找理由降低对其他人的支持度。当然这个理由应该优雅一些。主要原则如下：

• 既然是降低对别人的支持度，这个增量必然不会是大于零的数值。
• 也不能太过分，降低幅度尽量不要太多。

选民 $i$ 对候选者 $k$ 的支持度，会受其他选民支持度的影响。其影响程度包括两部分：

• 候选者 $k$ 自信心 $r(k,k)$ 。候选者自信心很重要，后面我们会看到，候选人 $k$ 自我支持度大于对其他人的支持度，也就是自己愿意投票给自己时，他才能成为聚类中心。
• 其他选民 $i^{\prime }$ 对候选者 $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$ 。显然：

• 如果二者之和大于零，也就是民意非常正面，$i$ 就没有理由降低对 $k$ 的支持度。
• 如果二者之和小于零，也就是民意非常负面，$i$ 就可以用这个结果作为对 $k$ 支持度的增量。因为计算过程中采用 $\max$ 运算，可以说 $i$ 对 $k$ 还是手下留情了，选择了较小幅度的负增量。

综上述，民意矩阵计算公式如下：

【表扬自我】：
$$a(k,k)=\sum _{i^{\prime }\ne k}\max \{(0,r(i^{\prime },k))\}\text{\hspace{1em}(3)}$$
【批评别人】：
a(i,k)=min⁡{0,r(k,k)+∑i′∉{i,k}{max⁡(0,r(i′,k))}},i≠k(4)\tag4 a(i,k)=\min\{0,r(k,k)+\sum_{i' \notin \{i,k\}} \{\max(0,r(i',k))\}\},i \neq k a(i,k)=min{0,r(k,k)+i′∈/{i,k}∑​{max(0,r(i′,k))}},i=k(4)

把亲情矩阵 $r(i,k)$ 复制下来：

i \ k	A	B	C	D	E
A	-4	1	-1	-3	-4
B	0	-4	0	-2	-4
C	-2	1	-4	-2	-3
D	-3	-2	-1	-4	1
E	-4	-3	-2	2	-4

按照上述公式，民意矩阵 $a(i,k)$ 计算结果如下：

i \ k	A	B	C	D	E
A	0	-3	-4	-2	-3
B	-4	2	-4	-2	-3
C	-4	-3	0	-2	-3
D	-4	-2	-4	2	-4
E	-4	-2	-4	-4	1

发现一个很有意思的现象，由于候选人 A 没有获得正向支持度，他的民意支持度就是自己的自信心 $-4$，所以 A 这一列很惨哦。同样候选人 C 这一列也很惨烈！

这个增量矩阵 $a$ 对角线以外的其它元素基本上都是小于零的，勇于“批评与自我表扬”的特点表现得淋漓尽致呀！

• 候选人 B 通过 $a(2,2)$ 的计算，可以把 $r(2,2)=-4$ 提升至 $c(2,2)=r(2,2)+a(2,2)=-2$。
• 候选人的其他列 $a(2,k),k\ne 2$ 都小于等于零，因此，B 对他们的支持度会下降，下降幅度取决于这些列的候选人的民意支持度。如果其他人对这些列支持度较高，B对他们支持下降的幅度就会降低，否则，下降幅度就会加大。但无论如何，B 不会提升对他们的支持都。

矩阵 $a$ 还有一个很有趣的现象，每行元素，例如第一、二、三行，选民 A、B、C 除了最支持自己外，其次就是很支持 D。再看矩阵 $a$ 的第四、五行，选民 D、E 除了支持自己外，其次就是很支持 B。这导致后面 B 和 D 脱颖而出。

2.4 决策矩阵 c

决策矩阵用来决定是否结束算法。决策矩阵 $c(i,k)$ 计算方法如下：

$$c(i,k)=r(i,k)+a(i,k)\text{\hspace{1em}(5)}$$

即综合考虑亲情和民意。根据上述数据，$c(i,k)$ 计算结果如下：

i \ k	A	B	C	D	E
A	-8	-2	-5	-5	-7
B	-4	[-2]	-4	-4	-7
C	-6	-2	-4	-4	-6
D	-7	-4	-5	[-2]	-3
E	-8	-4	-6	-2	-3

决策过程如下：

• 首先把每一行的最大值标出来（黑体字），如果最大的元素在对角线上，该元素就是聚类中心。
• 然后检查矩阵每一个行，看看是否都投票给了聚类中心，即该行的最大值都落在某个聚类中心那一列上，本例是B、D这两列。如果有些选民没有投票给聚类中心，接下来要回到步骤 “3.亲情矩阵r(i,k)”，继续迭代。

本例可以看出聚类中心是 B 和 D，两个聚类子集分别是：
SB={A,B,C}SD={D,E}S_B=\{A,B,C\}\\ S_D=\{D,E\} SB​={A,B,C}SD​={D,E}

3. 问题和质疑

先回答一下文章开头提的问题。

• 如何发现潜在的部落首领？
  答：亲情 + 民意。

• 如何让选民加入正确的部落？
  答：亲情 + 民意。

写到这里，我已经精疲力尽了。还有些问题，等下一篇博文再仔细讨论。

【问题1】如果第一轮投票未能完成聚类，接下来的迭代为什么要用 $s$ 和 $s+a$ 进行计算? 参见公式(1)。为什么不用决策矩阵 $c$ 来计算下一轮的 $r$?

这个算法的机理的确复杂，我的解释也未必完美。大家有什么质疑请留言，希望能够通过讨论把这个问题彻底整明白。