聚类算法之Affinity Propagation(AP)

Affinity Propagation算法简介

AP(Affinity Propagation)通常被翻译为近邻传播算法或者亲和力传播算法。AP算法的基本思想是将全部数据点都当作潜在的聚类中心(称之为exemplar),然后数据点两两之间连线构成一个网络(相似度矩阵),再通过网络中各条边的消息(responsibility和availability)传递计算出各样本的聚类中心。

AP算法中的特殊名词:

  • Exemplar:指的是聚类中心,K-Means中的质心。
  • Similarity(相似度):点j作为点i的聚类中心的能力,记为S(i,j)。一般使用负的欧式距离,所以S(i,j)越大,表示两个点距离越近,相似度也就越高。使用负的欧式距离,相似度是对称的,如果采用其他算法,相似度可能就不是对称的。
  • Preference:指点i作为聚类中心的参考度(不能为0),取值为S对角线的值(图1红色标注部分),此值越大,最为聚类中心的可能性就越大。但是对角线的值为0,所以需要重新设置对角线的值,既可以根据实际情况设置不同的值,也可以设置成同一值。一般设置为S相似度值的中值。
  • Responsibility(吸引度):指点k适合作为数据点i的聚类中心的程度,记为r(i,k)。如图2红色箭头所示,表示点i给点k发送信息,是一个点i选点k的过程。
  • Availability(归属度):指点i选择点k作为其聚类中心的适合程度,记为a(i,k)。如图3红色箭头所示,表示点k给点i发送信息,是一个点k选点i的过程。
  • Damping factor(阻尼系数):主要是起收敛作用的。

在实际计算应用中,最重要的两个参数(也是需要手动指定)是Preference和Damping factor。前者定了聚类数量的多少,值越大聚类数量越多;后者控制算法收敛效果。

AP算法流程:

  • 步骤1:算法初始,将吸引度矩阵R和归属度矩阵初始化为0矩阵;
  • 步骤2:更新吸引度矩阵

$$r_{t+1}(i, k)=\{\begin{array}{l}{S(i, k)-\max _{j \neq k}\left\{a_{t}(i, j)+r_{t}(i, j)\right\}, i \neq k} \\ {S(i, k)-\max _{j \neq k}\{S(i, j)\}, i=k} \end{array}$$

  • 步骤3:更新归属度矩阵步骤4:根据衰减系数 对两个公式进行衰减

$$a_{t+1}(i, k)=\{\begin{array}{l}{\min \left\{0, r_{t+1}(k, k)+\sum_{j \neq i, k} \max \left\{r_{t+1}(j, k), 0\right\}\right\}, i \neq k} \\ {\sum_{j \neq k} \max \left\{r_{t+1}(j, k), 0\right\}, i=k} \end{array}$$

  • 步骤4:根据衰减系数$\lambda$对两个公式进行衰减

$$\begin{aligned} &r_{t+1}(i, k)=\lambda * r_{t}(i, k)+(1-\lambda) * r_{t+1}(i, k)\\ &a_{t+1}(i, k)=\lambda * a_{t}(i, k)+(1-\lambda) * a_{t+1}(i, k) \end{aligned}$$

  • 重复步骤2,3,4直至矩阵稳定或者达到最大迭代次数,算法结束。
  • 最终取a+r最大的k作为聚类中心。

Python下AP算法使用

Python的机器学习库sklearn中已经实现了AP算法,可以直接调用。

参数设置介绍:

  • damping : 衰减系数,默认为5
  • convergence_iter : 迭代次后聚类中心没有变化,算法结束,默认为
  • max_iter : 最大迭代次数,默认
  • copy : 是否在元数据上进行计算,默认True,在复制后的数据上进行计算。
  • preference : S的对角线上的值
  • affinity :S矩阵(相似度),默认为euclidean(欧氏距离)矩阵,即对传入的X计算距离矩阵,也可以设置为precomputed,那么X就作为相似度矩阵。

训练完AP聚类之后可以获得的结果有

  • cluster_centers_indices_ : 聚类中心的位置
  • cluster_centers_ : 聚类中心
  • labels_ : 类标签
  • affinity_matrix_ : 最后输出的A矩阵
  • n_iter_ :迭代次数

AP(Affinity Propagation)算法演示:

AP与K-Means对比

AP聚类算法与经典的K-Means聚类算法相比,具有很多独特之处:

  • 无需指定聚类“数量”参数。AP聚类不需要指定K(经典的K-Means)或者是其他描述聚类个数(SOM中的网络结构和规模)的参数,这使得先验经验成为应用的非必需条件,人群应用范围增加。
  • 明确的质心(聚类中心点)。样本中的所有数据点都可能成为AP算法中的质心,叫做Examplar,而不是由多个数据点求平均而得到的聚类中心(如K-Means)。
  • 对距离矩阵的对称性没要求。AP通过输入相似度矩阵来启动算法,因此允许数据呈非对称,数据适用范围非常大。
  • 初始值不敏感。多次执行AP聚类算法,得到的结果是完全一样的,即不需要进行随机选取初值步骤(还是对比K-Means的随机初始值)。
  • 算法复杂度较高,为O(N*N*logN),而K-Means只是O(N*K)的复杂度。因此当N比较大时(N>3000),AP聚类算法往往需要算很久。
  • 若以误差平方和来衡量算法间的优劣,AP聚类比其他方法的误差平方和都要低。(无论k-center clustering重复多少次,都达不到AP那么低的误差平方和)

AP算法相对K-Means鲁棒性强且准确度较高,但没有任何一个算法是完美的,AP聚类算法的主要缺点:

  • AP聚类应用中需要手动指定Preference和Damping factor,这其实是原有的聚类“数量”控制的变体。
  • 算法较慢。由于AP算法复杂度较高,运行时间相对K-Means长,这会使得尤其在海量数据下运行时耗费的时间很多。

AP和K-Means运行时间对比

图中为了更好的展示数据对比,已经对时间进行log处理,但可以从输出结果直接读取真实数据运算时间。由结果可以看到:当样本量为100时,AP的速度要大于K_Means;当数据增加到500甚至1000时,AP算法的运算时间要大大超过K-Means算法。

参考链接:

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

Python检验数据是否正态分布

判断数据是否符合正态分布,比如使用3-sigma判断数据异常前,首先需要确定的是数据是否符合正态分布。今天一起

数据探索Pandas-Profiling与Dataprep.…

在使用数据前,我们首先要做的事观察数据,包括查看数据的类型、数据的范围、数据的分布等。Pandas-Profi

开源指标可视化工具Graphite

Graphite 是处理可视化和指标数据的优秀开源工具。它有强大的查询 API 和相当丰富的插件功能设置。事实

发表评论

电子邮件地址不会被公开。 必填项已用*标注