motivation：
·手头有几个list，每个list中有一些对象（string），将一个list看做一个节点，两个节点（list）之间的“相似度”定义为：两个list中包含的对象的重合程度（ (listA∩listB) / (listA∪listB) ）。
·现在基于节点和节点之间的相似度，想现有的节点聚类（相似度更高的节点聚在一起）
算法简介：
Affinity Propagation 算法简称AP，是2007年发表在Science上的聚类算法。
Brendan J. Frey and Delbert Dueck, “Clustering by Passing Messages Between Data Points”, Science Feb. 2007
AP算法的基本思想是将全部样本看做网络的节点，然后通过网络中各条边的消息传递计算出个样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是吸引度（responsibility）和归属度（availability）。AP算法通过迭代过程不断更新每一个点的吸引度和归属度，直到产生m个高质量的Exemplar（相当于质心），同时将其余的数据点分配到相应的聚类中。
在实际的使用中，AP有两个需要手动设置的重要参数，preference和damping factor。前者定了聚类数量的多少，值越大聚类数量越多；后者控制算法的收敛效果
AP算法相比于K-means算法，鲁棒性强，准确度较高，但算法复杂度高，运算消耗时间多
算法使用
sklearn中已经实现了AP算法，可以直接调用（当然，首先需要安装）。
安装完成之后，导入AffinityPropagation
from sklearn.cluster import AffinityPropagation
模拟输入数据为一个矩阵，M(i, j)表示i节点和j节点的相关度
M =
[[1, 0.8, 0.1, 0.1, 0.1],
[0.8, 1, 0.1, 0.1, 0.1],
[0.1, 0.1, 1, 0.9, 0.1],
[0.1, 0.1, 0.9, 1, 0.1],
[0.1, 0.1, 0.1, 0.1, 1]]
此时，可以将矩阵M直接输入
af = AffinityPropagation(affinity='precomputed').fit(X)
label = af.fit_predict(X)
此处
affinity='precomputed'
表示AP算法设置的参数，affinity参数表示节点之间相似度的计算方法，'precomputed'表示相似度已经计算完毕，所以输入的矩阵M是相似度矩阵。当设置为'euclidean'时，输入的不是相似度矩阵，而且一个节点的list，每个节点可以通过多维坐标表示（所以是个二维list）。
输出的label是一个lsit：
[1 1 0 0 1]
每一维表示一个聚类标签，长度n即为之前输入的矩阵M（n*n）的n。
至此，聚类完成！
网友评论