亲和传播

通过在数据点之间传递消息直到收敛，亲和传播形成聚类。偏好参数（决定使用多少个exemplars（或原型））和阻尼因子（阻尼消息的责任和可用性，以避免在更新这些消息时出现数值振荡）是亲和传播的两个重要参数。

一组有限数量的“exemplars”（即输入集中典型的聚类成员）用于定义一个数据集。成对交换的消息表示一个样本是否适合作为另一个样本的模型，并且这些消息根据从其他配对接收到的值进行更新。最终的exemplars在迭代更新过程结束时被选出，从而产生最终的聚类。

亲和传播算法

输入： s 是一个 NxN 矩阵，其中 s(i, j) 表示给定数据集 D = {d1, d2, d3, …..dn} 中 di 和 dj 之间的相似性。为了计算两个数据点之间的负平方距离，对于点 xi 和 xj，使用了 s(i, j)= -||xi-xj||2。

s 的对角线，即 s(i, i)，尤其重要，因为它表示输入偏好，即给定输入成为 exemplars 的概率。通过将此值设置为所有输入的相同值来控制算法生成的类数。一个接近最小可能相似性的值会产生更少的类。相比之下，一个接近或大于最大可能相似性的值会产生更多的类。

通常，所有输入对的中值相似性被用作初始化。

该算法通过交替进行两次消息传递步骤来更新两个矩阵

• “责任”矩阵 R 中的值 r(i, k) 表示 xk 相对于 xi 的其他潜在 exemplars，作为 xi 的 exemplar 的合适程度。
• “可用性”矩阵 A 中的值 a(i, k) 表示 xi 选择 xk 作为其 exemplar 的“合适”程度，同时考虑了其他点对 xk 作为 exemplar 的偏好。
• 两个矩阵的初始值均为零。然后，算法通过以下方式迭代执行更新：
• 首先，分发责任更新。
  
• 然后，根据以下公式更新可用性：
  

迭代要么在预定义的迭代次数后进行，要么直到聚类边界在多次迭代中保持不变。exemplars 被识别为那些对自己而言“责任 + 可用性”为正（即 (r(i, i) + a(i, i)) > 0）的点，并从最终矩阵中提取出来。

下面展示了使用 scikit-learn 库在 Python 中实现亲和传播聚类：

输出

亲和传播如何工作？

与其他聚类技术不同，亲和传播不需要预先设定聚类数量。相反，它通过迭代调整数据点之间的“责任”和“可用性”来确定聚类数量并将数据点分配到这些聚类中。

亲和传播的基本原理是，每个数据点都可以作为其聚类的exemplar（代表），并且也可以希望成为其他数据点的exemplar。在所有数据点中，算法寻找能产生最高总偏好的exemplars。

该方法有许多应用，例如基因表达分析、图像分割和消费者细分。然而，与其他聚类算法相比，它有时才能产生最佳结果，并且计算成本可能很高，特别是对于大型数据集。

亲和传播的优点

• 尽管数据点之间的大小或密度存在差异，它仍能创建高质量的聚类。
• 能够对具有非线性结构和复杂交互的数据进行分组。
• 它可以应用于各种任务，包括基因表达分析、图像和消费者细分等。

亲和传播的缺点

• 它不适合大规模聚类问题，因为它们可能计算成本很高，尤其是在处理庞大数据集时。
• 与高斯混合模型或 K-Means 等替代聚类技术相比，它可能不总能产生最佳结果。
• 它可能会根据用于评估两个数据项相似程度的相似性度量而有所不同。
• 它可能会导致单个聚类有多个 Exemplar，从而难以理解聚类过程的输出。

亲和传播是一种用于数据分析和机器学习的聚类方法。2007年，Brendan J. Frey 和 Delbert Dueck 首次提出。与传统的聚类方法（如 k-means）需要预先指定聚类数量不同，亲和传播不需要预先设定聚类数量。

以下是亲和传播工作原理的简要概述：

相似性矩阵

初始的相似性矩阵表示数据点对之间的相似性。任何相似性度量，包括欧氏距离或相似性函数，都可以作为该矩阵的基础。

责任和可用性

该方法迭代更新可用性和责任矩阵。

责任矩阵 R 显示了一个数据点作为另一个数据点的 Exemplar 的合适程度。

可用性矩阵 A 显示了一个数据点选择另一个数据点作为其 Exemplar 的合适程度。

消息传递

算法迭代地在数据点之间交换消息，直到出现一组 Exemplars（聚类中心）和聚类。

消息根据可用性和责任的最新估计进行传递。

Exemplar 和聚类分配

该过程产生 Exemplars，然后用于将数据点分配到聚类。

收敛

该过程一直持续，直到满足收敛要求，例如达到一定的迭代次数或算法确定解决方案已稳定。

亲和传播的优点包括其自动确定聚类数量的能力以及对输入数据的敏感性，这使其能够识别聚类数量和 Exemplars。其性能会受到输入参数选择的影响，并且对于大型数据集来说，计算成本可能很高。

在使用亲和传播时，理解要聚类的数据的属性并明智地选择输入参数至关重要。

当然！让我们更详细地探讨亲和传播的一些主要思想和功能。

阻尼

• 阻尼因子

引入该因子是为了实现更稳定的收敛，并防止数值振荡。

通常使用 0.5 到 1 之间的一个值来减少在数据点之间传递的信息量。

偏好

• 偏好参数

它设定了每个数据点的初始 Exemplar，并表示相似性矩阵的对角线。

具有更高值的 Exemplars 会从数据点中被选中。

偏好参数的选择会影响算法。

聚类结果

• 示例

选定的数据点作为聚类中心。

最终的 Exemplars 集定义了聚类。

• 聚类分配

根据数据点与 Exemplars 的接近程度，将它们分组到聚类中。

用例

• 图像分割

亲和传播已用于图像分割，它可以识别图像中的离散区域。

• 生物信息学和生物学

通过聚类基因表达数据，用于对具有相似表达模式的基因进行分组。

• 社交网络分析

在社交网络中用于识别关键参与者或节点。

执行

• 库

Python 实现可在 scikit-learn 和其他包中找到。

• 调整参数

实现最佳性能需要仔细调整参数，特别是偏好参数。

尽管亲和传播是一种强大的方法，具有独特的特性，但其适用性因数据类型和研究的精确目标而异。为了针对特定数据集获得最佳结果，通常建议尝试多种参数值和预处理技术。

结论

总而言之，亲和传播是一种独特的聚类技术，具有多种优势，包括能够找到可能不位于数据中心位置的 Exemplars，以及自动计算聚类数量。然而，它的使用也存在其他挑战，例如处理成本、对参数选择（尤其是偏好参数）的敏感性，以及可能出现大小不均的聚类。

尽管存在困难，亲和传播已在社交网络研究、生物信息学、图像分割等各个领域找到了应用。它在确定数据集中影响的关键中心或事先未知聚类数量的情况下尤其有用。

在实现亲和传播时，仔细评估阻尼、偏好参数和其他参数至关重要。用户还应注意该算法对输入数据特性的敏感性。

亲和传播的独特特性使其成为机器学习和数据分析领域一个有用的工具，尽管它在实践中可能并不总是首选的聚类技术。为了充分发挥算法的潜力并提供有意义的聚类结果，实验、参数调整和对数据的深入理解是必不可少的。