一：基本思想

近邻传播聚类（Affinity Propagation Clustering, AP聚类）：基本思想是将全部数据点都当作潜在的聚类中心（exemplar），然后数据点亮亮之间连线构成一个网络（相似度矩阵），再通过网络中各条边的消息（responsibility和availability）传递计算出各样本的聚类中心

在这里插入图片描述

此过程中，共有如下两种消息在各节点之间传递

吸引度（responsibility）：对于 $r (i, k)$ 而言，用于定量描述样本 $k$ 作为样本 $i$ 的聚类中心的程度
归属度（availability）：对于 $a (i, k)$ 而言，用于定量描述样本 $i$ 支持样本 $k$ 作为其聚类中心的程度

在这里插入图片描述

吸引度和归属度会分别形成吸引度矩阵和归属度的矩阵，然后算法会不断迭代更新两个矩阵

二：相关定义及术语

（1）相似度 Similarity

相似度（Similarity）：对于数据点 $i$ 和 $k$ ，使用 $s (i, k)$ 描述两点之间的相似度，反映出了 $j$ 作为 $i$ 的聚类中心能力的大小，采用欧氏距离负值表示。 $s (i, k)$ 值越大就表示 $i$ , $j$ 之间距离越近，也即 $j$ 作为 $i$ 的聚类中心的能力越强

$s(i,k)=-||x_{i}-x_{k}||^{2}$

（2）相似度矩阵

相似度矩阵：作为算法的初始化矩阵， $n$ 个点就有由 $n$ × $n$ 个相似度组成的矩阵

在这里插入图片描述

（3）偏好参数 Preference

偏好参数Preference：相似度矩阵中，主对角线上的值理论上为0，但是为了后续更好的应用相似度来更新吸引度和归属度，所以引入了该参数，用于定义相似度矩阵主对角线上的值。偏好参数越大说明各数据点成为聚类中心的能力越强，最终聚类中心的个数也就越多。偏好参数一般设置为相似度矩阵中所有值的最小值或中位数

（4）吸引度和归属度

吸引度（responsibility）：对于 $(i, k)$ 而言，用于定量描述样本 $k$ 作为样本 $i$ 的聚类中心的程度

$r(i,k)\leftarrow s(i,k)-\mathop{max}\limits_{k^{丶}s.t. k^{丶}\not=k}\{a(i,k^{丶})+s(i,k^{丶})\}$

$a(i,k^{丶})$ 表示除 $k$ 外其他点对 $i$ 的归属度，初始值为0
$s(i,k^{丶})$ 表示除 $k$ 外其他点对 $i$ 的相似度
$r (i, k)$ 值大于0，表示数据点 $k$ 成为聚类中心的能力强。但是注意此时只考虑哪个点 $k$ 成为点 $i$ 的聚类中心可能性最大，但是没有考虑整个吸引度最大的 $k$ 是否也经常成为其他点的聚类中心

归属度（availability）：对于 $a (i, k)$ 而言，用于定量描述样本 $i$ 支持样本 $k$ 作为其聚类中心的程度

$a(i,k)\leftarrow min\{0,r(k,k)+\sum\limits_{i^{丶}s.t. i^{丶}\notin\{i,k\}}max\{0,r(i^{丶},k)\}$

$\leftarrow \sum\limits_{i^{丶}\not=k}max(0,r(i^{丶},k)$

$r(i^{丶},k)$ 表示点 $k$ 作为除 $i$ 外其他点的聚类中心的相似度值，取所有大于等于0的吸引度值，加上 $k$ 作为聚类中心的可能程度。即点 $k$ 在这些吸引度值大于0的数据点的支持下，数据点 $i$ 选择 $k$ 作为其聚类中心的累积证明

$r (i, k) + a (i, k)$ 越大，则 $k$ 点作为聚类中心的可能性就越大，并且 $i$ 点隶属于以 $k$ 点为聚类中心得的聚类可能性也就越大

（5）阻尼系数 Damping factor

阻尼系数 Damping factor：为防止数据振荡，引入阻尼系数，每个信息值等于前一次更新的信息值的 $\lambda$ 倍加上此轮更新值的 $1-\lambda$ 倍（ $\lambda$ 位于0-1之间，默认为0.5）

三：算法流程

（1）专业描述

给定数据集 $D$
计算相似度矩阵，并且设置偏好参数 Preference（这里设置为中值）
计算吸引度矩阵 $R$
计算归属度矩阵 $A$ （注意开始计算时 $R$ 和 $A$ 需要进行初始化）
迭代更新 $R$ 和 $A$ ，直至聚类中心在一定程度上不再更新或者达到最大的迭代次数
根据得到的聚类中心，对数据进行聚类

（2）类比

近邻传播聚类算法中涉及的参数较多，尤其是在吸引度和归属度的计算公式，所以这里我们可以将该聚类算法比作一个选举过程进行理解

数据集中的所有点都会参加选举，它们既是选民也是参选人，聚类的目标是要选出几个人作为代表
$s (i, k)$ 是指 $i$ 对选 $k$ 这个人有一个固定的偏好程度
$r (i, k)$ 是指 $k$ 在对 $i$ 这个选民的竞争中的优势程度（用 $s (i, k)$ 减去最强竞争者的评分）
$r (i, k)$ 的更新过程就是选民 $i$ 对各个参选人的挑选
从 $a(i,k)\leftarrow min\{0,r(k,k)+\sum\limits_{i^{丶}s.t. i^{丶}\notin\{i,k\}}max\{0,r(i^{丶},k)\}$ 中可以看到，所有 $r(i^{丶},k)>0$ 的值都对 $a$ 有正的加成。这个公式可以理解为：选民 $i$ 在选择 $k$ 时，通过民意调查可看到，有很多人（也即 $i^{丶}$ 们）都觉得 $k$ 很不错（ $r(i^{丶},k)>0$ ），那么选民 $i$ 也就会觉得 $k$ 不错，是个可以值得信任的选择
$a (i, k)$ 的更新过程对应了参选人 $k$ 的民意调查对于选民 $i$ 的影响
两者交替的过程也就可以理解为选民在各个参选人之间不断比较和不断参考各个参选人给出的民意调查。 $r (i, k)$ 反应的是竞争， $a (i, k)$ 是为了让聚类更成功