平凉市建设厅官方网站,网站备案需要多少时间,做期货要看哪几个网站,网易企业邮箱怎么修改密码从来没有一个算法让我研究好几天都搞不明白#xff0c;AP算法算是第一个。弄了好几天#xff0c;打草纸用了几十页#xff0c;反复琢磨#xff0c;最后都怀疑人生了。我觉得网上那么多介绍 AP 的文章#xff0c;基本上没有一篇能讲明白的。最后我都觉得 AP 的作者可能都没…从来没有一个算法让我研究好几天都搞不明白AP算法算是第一个。弄了好几天打草纸用了几十页反复琢磨最后都怀疑人生了。我觉得网上那么多介绍 AP 的文章基本上没有一篇能讲明白的。最后我都觉得 AP 的作者可能都没弄明白。
看在这篇论文发表在美国科学杂志的份上终于耐着性子梳理出其中的思路。在此奉献给大家如果我这篇文章你都看不懂那就洗洗睡吧别伤脑筋了。
1. 基本思路
AP 算法的灵感来自投票选举。我们看下面的故事
1.1 划分部落选举首领
辽阔的草原上居住一群人。为便于组织管理他们想通过投票选举部落首领把人群分成若干部落每个部落有一个首领。
投票规则很简单(1) 每个人只能推选一个人做自己的首领; (2) 想当部落首领的人必须投票给自己。
AP 算法的基本思路是开始的时候每个人的自我支持度设置为较低的数值然后整个选举过程不断提升潜在首领的自我支持度和其他人对潜在首领的支持度同时降低对民意较差的候选人的支持度。整个过程关注两件事情
如何发现潜在的部落首领如何让选民加入正确的部落
1.2 按亲情投票
其实人性决定了投票的倾向性大家都愿意投给最亲近的人。可是谁是自己最亲近的人呢很显然自己与自己是最亲近的。但是如果每个人都投票给自己按照规则就只能一个人组成一个部落。大家都明白这一点于是人们虚伪宣布自己绝不亲近自己如果世界上只有一个仇人那就是我自己。
接下来我用投票支持度这个词来说明选民对候选人的支持程度或者亲密程度。人群中的每一个人在选举中既是选民又是候选人。
第一轮投票的结果是大家把票都投给了其他与自己最亲近的人比如自己的老公自己的儿子等。因为第一轮投票所有人都不会推选自己所以投票后必然无法完成划分部落的任务。
1.3 发现潜在的部落首领
但是第一轮投票还是有成果的。大家统计了一下票数发现有些人得了一些票未来有可能被推选为某个部落首领还有些人没有得到投票成为首领的可能性就低一些。
要利用这次的投票结果完成两件事情 第一件事情根据当前投票结果每个人都要想法提升对自己的支持度以便能产生部落首领。方法很简单只要把其他人对自己的支持度累加起来叠加到自我支持度上即可。 第二件事情根据当前投票结果每个人都要想法降低对其他人的支持度以便淘汰无希望的候选者。方法也很简单比如张三想降低对李四的支持度他就先看一下李四的自我支持度以及群众张三和李四以外的其他人的支持度如果这个支持度很高张三就不降低对李四的支持度。如果这个支持度不是很高就酌情降低对李四的支持度。
这样一来的话有些人的自信心越来越足越来越愿意把票投给自己。有些人的自信心越来越低越来越越愿意投票给其他人。
1.4 投票方法的可收敛性
最后还剩一个问题为什么自信心较低的这些人愿意把票投给潜在的部落首领呢
这个问题的原因也很简单。例如张三决定降低对李四的支持度的时候如果李四的自我支持度很高可能导致张三不会降低、或者略微降低对李四的支持度从而导致张三对李四的支持度较高一些。反之如果李四自我支持度较低其他人对他支持度也不高就会导致张三会大幅度降低对李四的支持度。也就是说张三对李四支持度的变化是受其他人影响的因此最终产生”从众“效应从而能够形成统一意见选出部落首领。
2. 一个简单例子
为简化问题我们提供一个极为简单的例子假设点分布在实数轴上坐标分别为 A1,B2,C3,D5,E6A1,B2,C3,D5,E6 A1,B2,C3,D5,E6
2.1 相似度矩阵 s
用两个点之间的距离的负数作为两个点之间相似度也就是所谓的亲和力。两个点之间的相似度越大说明两个点属于一个类别的可能性越大。根据上述坐标可以得出相似度矩阵
i \ kABCDEA--1-2-4-5B-1--1-3-4C-2-1--2-3D-4-3-2--1E-5-4-3-1-
按照距离的负数计算相似度导致相似度全部都是负数。不过没关系只要能保证数值越大相似度越高即可至于数据的符号初始阶段并不重要。
对角线 s(i,i)s(i,i)s(i,i) 表示自己与自己的亲和力按理说应该取 000 或上述矩阵中最大的值。但实际上不能这么干如果每个人都认为自己最适合当领导的话就无法聚类了。因此AP算法建议选择上述矩阵中元素的最小值或者中位数。接下来我们选择最小值得到完整的相似度矩阵
i \ kABCDEA-5-1-2-4-5B-1-5-1-3-4C-2-1-5-2-3D-4-3-2-5-1E-5-4-3-1-5
一般来讲AP算法的灵感来自一个群体通过自发投票选举小组领导人的过程。人们投票一般取决于两个策略任人唯亲、兼顾民意。比如你想推选自己的儿子做村长但是考虑到自己的儿子实在不受大家喜欢于是投票给了人缘稍微好一点的侄子。这样做不至于把选票浪费在毫无希望的儿子身上同时又耽误了有希望竞选成功的侄子。
相似度矩阵可以这样理解行 iii 代表选民列 kkk 代表竞选人。因为 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。因此我们需要把相似度矩阵 sss 归一化得到一个标准化的亲情矩阵。 用下面的公式生成亲情矩阵 rrr
r(i,k)s(i,k)−maxk′≠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′)a(i,k)a(i,k′) 在初始阶段为零矩阵其具体含义后面会解释。因此矩阵 r(i,k)r(i,k)r(i,k) 结果如下
i \ kABCDEA-41-1-3-4B0-40-2-4C-21-4-2-3D-3-2-1-41E-4-3-22-4
这个矩阵反映了在选民 iii 对候选人 kkk 的支持度。一般来讲每个选民只能投票给一个候选人大都数情况下矩阵的每一行只有一个正向支持度其余的为负向支持度。
如果我们认为正向支持度表示支持零支持度表示不反对不支持负支持度表示反对那么当前的情况表明A、C支持B但 B 反对自己同时呢D、E都支持对方同时都反对自己。因此目前是无法实现聚类的。
聚类成功的条件应该是聚类中心首先自己要支持自己然后其他候选人都应该支持某个聚类中心。
接下来要解决两个问题
【问题1】如何让 B 支持自己【问题2】如何说服 D、E中的一个支持对方而另一个能支持自己。
解决方法是通过民意调查改变选民的对候选人的支持度。
2.3 民意矩阵 a
接下来大家根据当前 rrr 提供的支持度结果做进一步的决策调整。简单地讲基本策略就是”批评与自我表扬“。虽然一开始大家都很谦虚自我支持度设置成为一个较低的起点。但是竞选已经开始了每个人都需要找理由加强自我支持度降低对其他人的支持度。所以后续步骤就是找理由增加对自己的支持度降低对别人的支持度。
2.3.1 表扬自我
我们可以把候选人 kkk 对自己的支持度理解为候选人的自信心。初始阶段自我支持度 r(k,k)r(k,k)r(k,k) 都是负值呈现出完全没有自信心的样子。我们需要根据选民的投票意向提升候选人的自信心。计算方法是把矩阵 rrr 每一列中的正数累加起来保存在对角线 a(k,k)a(k,k)a(k,k) 的位置。公式如下 a(k,k)∑i′≠kmax{(0,r(i′,k))}(2)\tag2 a(k,k)\sum_{i\neq k}\max\{(0,r(i,k))\} a(k,k)i′k∑max{(0,r(i′,k))}(2)
这样我们得到了民意矩阵主对角线的值
i \ kABCDEA00000B02000C00000D00020E00001
显然候选人 B、D、E 找到了提升自我支持度的理由。
2.3.2 批评别人
接下来要找理由降低对其他人的支持度。当然这个理由应该优雅一些。主要原则如下
既然是降低对别人的支持度这个增量必然不会是大于零的数值。也不能太过分降低幅度尽量不要太多。
选民 iii 对候选者 kkk 的支持度会受其他选民支持度的影响。其影响程度包括两部分
候选者 kkk 自信心 r(k,k)r(k,k)r(k,k) 。候选者自信心很重要后面我们会看到候选人 kkk 自我支持度大于对其他人的支持度也就是自己愿意投票给自己时他才能成为聚类中心。其他选民 i′ii′ 对候选者 kkk 的正的投票意向 ∑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))}
也就是说如果 kkk 自己有信心其他选民也都支持 kkk 。显然
如果二者之和大于零也就是民意非常正面iii 就没有理由降低对 kkk 的支持度。如果二者之和小于零也就是民意非常负面iii 就可以用这个结果作为对 kkk 支持度的增量。因为计算过程中采用 max\maxmax 运算可以说 iii 对 kkk 还是手下留情了选择了较小幅度的负增量。
综上述民意矩阵计算公式如下
【表扬自我】 a(k,k)∑i′≠kmax{(0,r(i′,k))}(3)\tag3 a(k,k)\sum_{i\neq k}\max\{(0,r(i,k))\} a(k,k)i′k∑max{(0,r(i′,k))}(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))}},ik(4)
把亲情矩阵 r(i,k)r(i,k)r(i,k) 复制下来
i \ kABCDEA-41-1-3-4B0-40-2-4C-21-4-2-3D-3-2-1-41E-4-3-22-4
按照上述公式民意矩阵 a(i,k)a(i,k)a(i,k) 计算结果如下
i \ kABCDEA0-3-4-2-3B-42-4-2-3C-4-30-2-3D-4-2-42-4E-4-2-4-41
发现一个很有意思的现象由于候选人 A 没有获得正向支持度他的民意支持度就是自己的自信心 −4-4−4所以 A 这一列很惨哦。同样候选人 C 这一列也很惨烈
这个增量矩阵 aaa 对角线以外的其它元素基本上都是小于零的勇于“批评与自我表扬”的特点表现得淋漓尽致呀
候选人 B 通过 a(2,2)a(2,2)a(2,2) 的计算可以把 r(2,2)−4r(2,2)-4r(2,2)−4 提升至 c(2,2)r(2,2)a(2,2)−2c(2,2)r(2,2)a(2,2)-2c(2,2)r(2,2)a(2,2)−2。候选人的其他列 a(2,k),k≠2a(2,k),k\neq 2a(2,k),k2 都小于等于零因此B 对他们的支持度会下降下降幅度取决于这些列的候选人的民意支持度。如果其他人对这些列支持度较高B对他们支持下降的幅度就会降低否则下降幅度就会加大。但无论如何B 不会提升对他们的支持都。
矩阵 aaa 还有一个很有趣的现象每行元素例如第一、二、三行选民 A、B、C 除了最支持自己外其次就是很支持 D。再看矩阵 aaa 的第四、五行选民 D、E 除了支持自己外其次就是很支持 B。这导致后面 B 和 D 脱颖而出。
2.4 决策矩阵 c
决策矩阵用来决定是否结束算法。决策矩阵 c(i,k)c(i,k)c(i,k) 计算方法如下
c(i,k)r(i,k)a(i,k)(5)\tag5 c(i,k)r(i,k)a(i,k) c(i,k)r(i,k)a(i,k)(5)
即综合考虑亲情和民意。根据上述数据c(i,k)c(i,k)c(i,k) 计算结果如下
i \ kABCDEA-8-2-5-5-7B-4[-2]-4-4-7C-6-2-4-4-6D-7-4-5[-2]-3E-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】如果第一轮投票未能完成聚类接下来的迭代为什么要用 sss 和 sasasa 进行计算? 参见公式(1)。为什么不用决策矩阵 ccc 来计算下一轮的 rrr?
这个算法的机理的确复杂我的解释也未必完美。大家有什么质疑请留言希望能够通过讨论把这个问题彻底整明白。
