AP近邻传播聚类算法总结

╰+哭是因爲堅強的太久メ 2022-06-04 06:39 208阅读 0赞

AP（Affinity Propagation）算法是Fery等在2007提出的一种基于近邻传播的半监督聚类算法。算法的基本思想是：首先通过消息传递机制来搜索网络中各个数据点的聚类中心以及数据点与数据中心之间的隶属关系，然后根据数据中心和顶点之间的隶属关系来对待聚类数据集进行划分，形成若干个具有特定意义的子集。该算法的优点众多，比如算法在聚类的过程中不需要明确确定与聚类个数相关的参数；聚类中心是待聚类数据的某个确切的数据点；算法的输入可以是对称的相似度矩阵，也可以是非对称的相似性矩阵。  
从文献中可知，原始AP算法的输入为相似性为一个矩阵S，相似性矩阵可以是对称的，也可以是非对称的。另外，针对AP算法，所有的数据点都是潜在的聚类中心，所以相似性矩阵对角线上的数值s(i,j)进行统一赋值，一般是所有相似性的中位数或者平均值，叫做自身参考度（Preference），算法中可以通过调节自身参考度来控制聚类结果的粒度，自身参考度数值越大聚类结果的数量就越多，反之越少。AP算法中在迭代的过程中对两种信息进行更新：可信度（Avaliability）和责任度（Responsibility）。可信度用来表示网络中顶点i选择顶点j作为聚类中心的程度，定义为a(i,j)。责任度用来表示顶点j适合作为顶点i的聚类中心的程度，定义为r(i,j)。AP算法的对责任度和可信度更新的公式定义如公式4-1和4-2所示：  
![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]  
通过对公式4-1和公式4-2的理解，可以将AP算法模拟为一个选举的过程，假如网络中每个人都参与选举，选举目的是从所有参与选举的顶点中推荐出最合适的几个顶点作为代表。具体选举的过程描述如图4-1所示：

1.所有人都参加选举，参与选举的人既是选民也是候选人，并从中选出若干个作为代表。  
2.相似性s(i,j)可描述为选民i推荐候选人j的一个偏好程度，也就是说s(i,j)越大，i选择j的可能性就越大。  
3.r(i,j)等于用s(i,j)减去最强竞争者（候选人）的评分，可以理解为候选人j对选民i的吸引度，r(i,j)的更新过程对应选民i对各个候选人的挑选，候选人越出众就越有吸引力。  
4.a(i,j)的更新过程对应候选人k的民意调查结果对选民i的影响。从公式中可以看出，责任度 r(i,j)>0的值对可信度a(i,j)都有正的加成。可以理解为很多人觉得候选j不错，那么选民i也会觉得j不错。  
5.对r(i,j)和a(i,j)交替更新的过程也就可以理解为选民在各个候选人之间不断的进行比较，不断的参考民意调查。  
6.若最终选择出来的代表趋于稳定状态，则怎个选举过程完成。

AP算法有两个条件来停止对责任度和可信度的更新，第一种条件是算法的迭代次数达到了预先设置的最大迭代次数，第二种条件是迭代过程中聚类中心在后面若干次迭代后没有改变（收敛）。

算法的输入

1.顶点相似性

原始AP算法需要输入待聚类数据集的相似性矩阵S，相似性可以用不同的方法进行计算，比如欧氏距离，Jaccard相似性，余弦相似性以及各种适用于不同应用场景的相似性等。相似性矩阵既可以是对称的，也可以是非对称的。  
2.自我相似性  
在AP算法中，待聚类数据集中的数据点都是潜在的聚类中心，算法对潜在的聚类中心的描述主要表现在自我相似性s(i, i)上，自我相似性描述的是数据集中的某个数据点能够被选举出来并成为聚类中心的程度。因为AP算法规定了算法在初始状态的情况下数据集中每个数据点都是潜在的数据中心，所以在利用AP算法进行聚类之前，需要将自我相似性进行统一设置。从文献可知，可以将自我相似性设置成为相似性矩阵的中位数，或者平均值，本文进行仿真实验时自我相似性使用的是中位数。自我相似性的值的大小将会直接影响聚类结果数量，若自我相似性值越大，所有数据点都倾向于选择自己作为聚类中心，最终聚类数量就会越多，反之聚类数量越少。  
3.阻尼因子λ  
算法在迭代更新可信度和责任度的过程中，还涉及了另外一个参数，叫做阻尼因子，用λ来表示。该参数的作用是让AP算法能够快速收敛。阻尼因子的取值范围为0~1，本论文中将λ的值固定为0.75。AP算法的每次迭代过程中，λ作用于责任度和可信度，针对上一次迭代的责任度和可信度进行加权更新，更新规则如公式4-3和公式4-4所示。  
![这里写图片描述][SouthEast 2]

结果的划分

1.聚类中心的选取  
AP算法迭代完成后，首先需要确定数据集中所有的聚类中心。AP算法对聚类中心的判定主要参考责任度和可信度迭代更新完成后的值，判定为聚类中心的规则如公式4-5所示，即顶点i对自身的责任度和自身的可信度之和大于0时，则选择对应顶点作为聚类中心。  
r(i,i)+a(i,i)>0 (4-5)

2.数据点与聚类中心之间的隶属关系

AP算法迭代完成后，若要获得对应的聚类结果，同样需要根据算法迭代完成后的责任度和可信度进行确认，选择聚类中心的规则如公式4-6所示，即选择与当前顶点i责任度与可信度之和最大的顶点j作为其聚类中心。  
max\{a(i,j)+r(i,j)\} (4-6)  
算法的流程  
整个AP聚类的算法流程的描述如图4-2所示：  
1.初始化curIterNum, maxIterNum, a(i,k)=0，λ，δ=0，stableNum  
其中curIterNum表示当前已经迭代了的次数，maxIterNum表示算法最大迭代次数，λ为阻尼因子，默认为0.75,δ来记录聚类中心是否已经达到指定稳定次数stableNum  
2.更新责任度r(i,j)  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]  
3.更新可信度a(i,j)  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]  
4.判断迭代是否稳定  
根据公式4-6获取当前第t次迭代后聚类中心集合Et，如果Et=Et−1，则稳定次数δ加1，否则δ重置为0。若此时δ=stableNum则跳转至步骤6，否则跳转至步骤5  
5.curIterNum=curIterNum+1,若curIterNum=maxIterNum,则跳转至步骤6否则跳转至步骤2  
6.从聚类结果中获取聚类中心，以及顶点之间的隶属关系

[SouthEast]: /images/20220604/978f7256a0e74978b4c1d5ddb6aacb1c.png
[SouthEast 1]: /images/20220604/c2600c0b54824bfd9d628f43b92cd25a.png
[SouthEast 2]: /images/20220604/80b6e0cdbacc484987701bd8af5c6cce.png
[SouthEast 3]: /images/20220604/65f25c4fae8d4c75af1cf5c2e291f037.png
[SouthEast 4]: /images/20220604/ebfdd0962dd4493f8af6a0e8d4fe7b46.png
[SouthEast 5]: /images/20220604/3351c8bf0f864b69942c97adc0f66b4e.png
[SouthEast 6]: /images/20220604/928ef8efd4de4b0d872dd1d6cb7f1d85.png