谱聚类和 AP 聚类是基于图的两种聚类，在这里我介绍 AP 聚类。
Affinity Propagation Clustering（简称 AP 算法）是 2007 提出的，过后发表在 Science 上《single-exemplar-based》。特地适宜高维、多类数据疾速聚类，相比传统的聚类算法，该算法算是比拟新的，从聚类性能和效率方面都有大幅度的晋升。
Affinity Propagation 能够翻译为关联流传，它是一种基于数据点之间“消息传递”概念的聚类技术，所以咱们称其为基于图的聚类办法。
该算法通过在数据点之间发送音讯直到收敛来创立簇。它以数据点之间的相似性作为输出，并依据肯定的规范确定范例。在数据点之间替换音讯，直到取得一组高质量的范例。与 k -means 或 k -medoids 等聚类算法不同，流传在运行算法之前不须要确定或预计簇的数量。
公式详解
咱们应用上面的数据集，来介绍算法的工作原理。
相似矩阵
类似度矩阵中的每一个单元格都是通过对参与者之间的差值平方和求负来计算的。
比方 Alice 和 Bob 的类似度，差的平方和为 (3–4)² + (4–3)² + (3–5)² + (2–1)² + (1– 1)² = 7。因而，Alice 和 Bob 的类似度值为 -(7)。
如果为对角线抉择较小的值，则该算法将围绕大量集群收敛，反之亦然。因而咱们用 -22 填充相似矩阵的对角元素，这是咱们相似矩阵中的最小值。
吸引度（Responsibility）矩阵
咱们将首先结构一个所有元素都设为 0 的可用性矩阵。而后，咱们将应用以下公式计算吸引度矩阵中的每个单元格:
这里 i 指的是行，k 指的是相关矩阵的列。
例如，Bob(列)对 Alice(行)的吸引度是 -1，这是通过从 Bob 和 Alice 的类似度 (-7) 中减去 Alice 所在行的最大类似度 (Bob 和 Alice 的类似度(-6) 除外)来计算的。
在计算了其余参与者对的吸引度之后，咱们失去了上面的矩阵。
吸引度是用来形容点 k 适宜作为数据点 i 的聚类核心的水平。
归属度（Availability）矩阵
为了结构一个归属度矩阵，将应用对角和非对角元素的两个独自的方程进行计算，并将它们利用到咱们的吸引度矩阵中。
对角线元素将应用上面的公式。
这里 i 指的是关联矩阵的行和 k 列。
该等式通知咱们沿列计算所有大于 0 的值的总和，但值等于所探讨列的行除外。例如，Alice 的对角线上元素值将是 Alice 列的正值之和，但不包含 Alice 列的值，等于 21(10 + 11 + 0 + 0)。
批改后，咱们的归属度矩阵将如下所示：
当初对于非对角元素，应用以下等式更新它们的值。
通过一个例子来了解下面的等式。假如咱们须要找到 Bob（列）对 Alice（行）的归属度，那么它将是 Bob 的自我归属（在对角线上）和 Bob 列的残余踊跃吸引度的总和，不包含 Bob 的 Alice 行（-15 + 0 + 0 + 0 = -15）。
在计算其余部分后，失去以下归属度矩阵。
归属度能够了解为用来形容点 i 抉择点 k 作为其聚类核心的适宜水平。
准据（Criterion）矩阵
准据矩阵中的每个单元格只是该地位的吸引度矩阵和归属度矩阵相加的和。
每行中具备最高准据值的列被指定为样本。共享同一个实例的行在同一个簇中。在咱们的示例中。Alice、Bob、Cary、Doug 和 Edna 都属于同一个集群。
如果状况是这样：
那么 Alice、Bob 和 Cary 形成一个簇，而 Doug 和 Edna 形成第二个簇。
Criterion 被我翻译成准据也就是说明这个矩阵是咱们聚类算法判断的规范和根据。
代码示例
在 sklearn 中曾经蕴含了该算法，所以咱们能够拿来间接应用：
import numpy as np
from matplotlib import pyplot as plt
import seaborn as sns
sns.set()
from sklearn.datasets import make_blobs
from sklearn.cluster import AffinityPropagation从 Sklearn 生成聚类数据
X, clusters = make_blobs(n_samples=1000, centers=5, cluster_std=0.8, random_state=0)
plt.scatter(X[:,0], X[:,1], alpha=0.7, edgecolors='b')
初始化和拟合模型。
af = AffinityPropagation(preference=-50)
clustering = af.fit(X)AP 聚类利用中须要手动指定 Preference 和 Damping factor，尽管不须要显式指定簇的数量，然而这两个参数其实是原有的聚类“数量”管制的变体：
Preference：数据点 i 的参考度称为 p(i)或 s(i,i)，是指导 i 作为聚类核心的参考度，聚类的数量受到参考度 p 的影响, 如果认为每个数据点都有可能作为聚类核心, 那么 p 就应取雷同的值。如果取输出的类似度的均值作为 p 的值, 失去聚类数量是中等的。如果取最小值, 失去类数较少的聚类。
Damping factor(阻尼系数)：次要是起收敛作用的。
绘制聚类后果的数据点
plt.scatter(X[:,0], X[:,1], c=clustering.labels_, cmap=’rainbow’, alpha=0.7, edgecolors=’b’)
总结
Affinity Propagation 是一种无监督机器学习技术，特地实用于咱们不晓得最佳集群数量的状况。并且该算法复杂度较高，所以运行工夫绝对比 K -Means 长很多，这会使得尤其在海量数据下运行时消耗的工夫很多。
https://avoid.overfit.cn/post/70c0efd697ef43a6a43fea8938afff60
作者：Sarthak Kedia