type
status
password
date
slug
summary
category
URL
tags
icon
一种半监督聚类算法，近邻传播聚类算法
简介
Affinity Propagation聚类算法简称AP， 特别适合高维、多类数据快速聚类，相比传统的聚类算法，该算法算是比较新的，从聚类性能和效率方面都有大幅度的提升。AP算法的基本思想：将全部样本看作网络的节点，然后通过网络中各条边的消息传递计算出各样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是吸引度( responsibility)和归属度(availability) 。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值，直到产生m个高质量的Exemplar（类似于质心），同时将其余的数据点分配到相应的聚类中。
名词介绍
- Exemplar：指的是聚类中心，K-Means中的质心。
- Similarity：数据点和点的相似度记为，是指点作为点的聚类中心的相似度。一般使用欧氏距离来计算，一般点与点的相似度值全部取为负值；因此，相似度值越大说明点与点的距离越近，便于后面的比较计算。
- preference参数：在相似度矩阵中，对角线的值为样本自身的距离，理论上是0，但是为了后续更好的应用相似度来更新吸引度和归属度，引入了preference参数。可以取相似度的均值或者中位数；在scikit-learn中，默认取相似度值的中值。这个参数会影响聚类的类别数目，该值越大，聚类的类别数越多。
- Responsibility：用来描述点适合作为数据点的聚类中心的程度。
- Availability：用来描述点选择点作为其聚类中心的适合程度。
- Damping factor(阻尼系数)：为了避免振荡，AP算法更新信息时引入了衰减系数 。每条信息被设置为它前次迭代更新值的 倍加上本次信息更新值的倍。其中，衰减系数 是介于0到1之间的实数。
聚类过程
聚类就是个不断迭代的过程，迭代的过程主要更新两个矩阵：
- 代表(Responsibility)矩阵：，描述点适合作为数据点的聚类中心程度。
- 适选(Availabilities)矩阵：，描述点选择点作为其聚类中心的适合程度。
初始化
、这两个矩阵才初始化为，是所有样本的数目。表示第个样本适合作为第个样本的类代表点的代表程度，表示第个样本选择第个样本作为类代表样本的适合程度。
更新迭代
与k-means的比较
优点
AP聚类算法与经典的 K-Means 和 k-centers 聚类算法相比，具有很多独特之处：
- 无需指定聚类“数量”参数。AP聚类不需要指定K（经典的K-Means）或者是其他描述聚类个数（SOM中的网络结构和规模）的参数，这使得先验经验成为应用的非必需条件，人群应用范围增加。
- 明确的质心（聚类中心点）。样本中的所有数据点都可能成为AP算法中的质心，叫做Examplar，而不是由多个数据点求平均而得到的聚类中心（如K-Means）。
- 对距离矩阵的对称性没要求。AP通过输入相似度矩阵来启动算法，因此允许数据呈非对称，数据适用范围非常大。
- 初始值不敏感。多次执行AP聚类算法，得到的结果是完全一样的，即不需要进行随机选取初值步骤（还是对比K-Means的随机初始值）。
- 若以误差平方和来衡量算法间的优劣，AP聚类比其他方法的误差平方和都要低。（无论k-center clustering重复多少次，都达不到AP那么低的误差平方和）
- AP算法相对K-Means鲁棒性强且准确度较高
缺点
- AP聚类应用中需要手动指定Preference和Damping factor，这其实是原有的聚类“数量”控制的变体。
- 算法复杂度较高，为，而K-Means只是的复杂度。因此运行较慢。当比较大时()，AP聚类算法往往需要算很久。
参考资料：