关联传播和 Python 和 Scikit-learn 实现

关键词：
Affinity Propagation

一、说明

假设您有一个数据集，其中各个样本之间存在关系，您的目标是识别数据集中的相关样本组。聚类是无监督机器学习算法的一部分，可能是要走的路。但是，当您并不真正知道聚类的数量时，应该应用哪种聚类算法呢？

进入 Affinity Propagation，这是一种八卦风格的算法，它通过传递有关单个样本的受欢迎程度的信息来推断集群的数量，例如他们是否属于某个群体，甚至他们是否是一个群体的领导者。此算法可以估计数据集本身中的集群/组数量，是今天博客文章的主题。

首先，我们将从理论上了解 Affinity Propagation。它是什么 — 群体形成类比是如何运作的？它如何更详细地工作，即数学上？发送了哪些类型的消息，这些受欢迎程度指标是如何确定的？算法是如何收敛的？我们先来看这些问题。

接下来，我们提供使用 Scikit-learn 和 Python 的 Affinity Propagation 示例实现。我们一步一步地解释我们的模型代码，以便您可以逐个了解发生了什么。对于那些已经有一些经验并希望立即玩的人，也可以使用完整的模型代码。因此，今天的博客文章既是理论上的，也是实践的——我最喜欢的博客类型！

在本教程中，您将学习：如何使用 Scikit-learn 执行 Affinity Propagation 聚类。

二、什么是 Affinity Propagation。

2.1 先说Affinity 传播的工作原理

你还记得高中时，那里的学生团体聚集在一起——只有当某个团体的领导认为你很酷时，你才能成为该团体的成员吗？

虽然这个类比可能有点牵强，但我认为这就是用通俗易懂的英语解释聚类的 Affinity Propagation 的方式。对于一组数据点，开始一个 “组形成 ”过程，其中每个样本都与其他样本竞争以获得组成员资格。具有最多组大写的，组长被称为 exemplars （Scikit-learn， n.d.）。

这种机器学习技术的有趣之处在于，与 K-means 聚类 （Scikit-learn， n.d.） 不同，您不必提前配置集群的数量。主要缺点是复杂性：就所需的计算资源而言，它不是最便宜的机器学习算法之一 （Scikit-learn， n.d.）。因此，它是一种仅适用于 “中小型数据集” 的技术 （Scikit-learn， n.d.）。

2.2 更多细节

现在我们已经大致了解了 Affinity Propagation，是时候更详细地了解一下了。我们将看看几件事：

算法在高层次上是如何工作的;
传播的消息类型;
如何计算这些消息中的分数。
每次迭代后消息分数如何更新，从而如何形成真正的集群。
首先，与任何聚类分析算法一样，Affinity Propagation 是迭代的。这意味着它将完成多次迭代，直到完成。与 K-means 聚类相反，收敛性由某个阈值确定，而使用 Affinity Propagation （关联传播） 时，您可以配置要完成的迭代次数。之后，该算法假设收敛并将返回结果集群 （Scikit-learn， n.d.）。

2.3 传播两种类型的消息

在每次迭代期间，每个样本都会向其他样本广播两种类型的消息 （Scikit-learn， n.d.）。第一个称为责任 r（i，k） — 这是“样本 k 应该是样本 i 的示例的证据”（Scikit-learn， n.d.）。我一直记得是这样的：期望 k 的团队领导越大，对团队的责任就越大。这就是你如何知道，从 i 的角度来看，责任总是告诉你一些关于 k 对团队的重要性。

发送的另一种类型的消息是可用性。这与责任相反：i 应该选择 k 作为示例的确定性如何，即加入特定组的可用性如何 （Scikit-learn， n.d.）。在高中的情况下，假设你想加入一个半酷的小组（一些空闲），而你更愿意加入真正酷的小组。对于真正酷的那个，你的可用性要高得多。该责任告诉你需要接受谁才能加入小组，即最有可能的小组负责人或榜样。

2.4 计算责任和可用性的分数

现在让我们更仔细地了解一下责任和可用性的概念。现在我们知道了它们在高层次上代表什么，是时候详细研究它们了 — 这意味着从数学上。

2.4.1 责任

这是责任的公式 （Scikit-learn， n.d.）：

现在让我们把这个公式分解成简单的英语。我们从左边开始。这里，r（i，k） 再次负责样本 k 是样本 i 的范例。但是什么决定了它呢？两个分量：
s（i， k） 和 max[ a（i， k’） + s（i， k’）∀ k’≠ k]。

首先是样本 i 和 k 之间的相似性。如果它们高度相似，则 k 应该是 i 的示例的几率非常高。然而，这并不是全部，因为我们不能只看相似性——因为其他样本也会试图说服它们是更适合 i 的示例。因此，相似性是相对的，这就是为什么我们需要减去那个大的 max 值。它看起来很复杂，但简单地归结为“所有其他样本 k’ 的最大可用性和相似性，其中 k’ 永远不会是 k”。我们简单地减去 k 的“最大竞争对手”的相似性和意愿，以作为示例来显示它的相对强度。

2.4.2 可用性分解

责任看起来很复杂，但实际上相对容易。可用性的公式也是如此 （Scikit-learn， n.d.）：

正如我们所看到的，可用性被确定为介于 0 和 k 到 k 的责任（即它认为自己是示例或组长的重要性）和所有其他样本 i’ 到 k 的责任之和，其中 i’ 既不是 i 也不是 k。因此，就组形成而言，如果样本本身认为它非常重要，那么它就会更容易被潜在的样本所利用。

2.4.3 更新分数：集群是如何形成的

现在我们已经了解了责任和可用性的公式，让我们看看每次迭代后分数是如何更新的 （Scikit-learn， n.d.）：

很简单：每次更新，我们取旧值的 λ 并将其与新值的 （1-λ） 合并。这个 lambda，也称为“阻尼值”，是确保平滑过渡的平滑因子;它避免了优化过程中的大振荡。

总而言之，Affinity Propagation 是一种算法，它：

2.4.4 估计集群本身的数量。

考虑到计算成本，对于中小型数据集非常有用。
通过四处“八卦”来工作，就好像它试图组建高中学生团体一样。
通过对单个样本随时间变化的 “吸引力” 进行小而平滑的更新，即在每次迭代之后。
确定样本的吸引力，回答问题“这可以是我想属于的小组的领导者吗”和样本本身（“有什么证据证明我是小组领导者？
现在让我们看看如何使用 Python 和 Scikit-learn 实现它！😃

使用 Python 和 Scikit-learn 实现 Affinity Propagation
我们又来了，我们在博客abou t K-means 聚类中看到的聚类，尽管我们今天的样本较少：

图片由作者提供
还记得我们是如何生成它们的吗？打开一个 Python 文件并将其命名为 ‘affinity.py’，添加导入（即 Scikit-learn、Numpy 和 Matplotlib）。

import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import AffinityPropagation

然后，我们添加一些配置选项：我们生成的样本总数、集群的中心以及我们将为其生成样本的类的数量。这些都将在 中使用，它会生成集群并分别将它们分配给 X 和 targets。make_blobs

我们使用 Numpy 保存它们，然后加载它们并再次将它们分配给 X。这两行代码对于您的模型运行不是必需的，但如果您想跨设置进行比较，您可能不希望每次都随机生成样本。通过保存一次，然后注释掉 和 ，您将一次又一次地从文件中加载它们:)savemake_blobs

# Configuration options
num_samples_total = 50
cluster_centers = [(20,20), (4,4)]
num_classes = len(cluster_centers)# Generate data
X, targets = make_blobs(n_samples = num_samples_total, centers = cluster_centers, n_features = num_classes, center_box=(0, 1), cluster_std = 1)np.save('./clusters.npy', X)
X = np.load('./clusters.npy')

然后，我们在加载数据后将数据拟合到 Affinity Propagation 算法中，这只需要两行代码。在另外两行中，我们得出了示例等特征，因此得出了聚类的数量：

# Fit AFfinity Propagation with Scikit
afprop = AffinityPropagation(max_iter=250)
afprop.fit(X)
cluster_centers_indices = afprop.cluster_centers_indices_
n_clusters_ = len(cluster_centers_indices)

最后，通过使用我们拟合的算法，我们预测所有样本属于哪个集群：

# Predict the cluster for all the samples
P = afprop.predict(X)

最后可视化结果：

# Generate scatter plot for training data
colors = list(map(lambda x: '#3b4cc0' if x == 1 else '#b40426', P))
plt.scatter(X[:,0], X[:,1], c=colors, marker="o", picker=True)
plt.title(f'Estimated number of clusters = {n_clusters_}')
plt.xlabel('Temperature yesterday')
plt.ylabel('Temperature today')
plt.show()

在这里的结果

完整型号代码
如果您希望立即获得完整的模型代码，以便您可以立即开始使用 — 开始吧！它也在我的 Github 存储库中可用。

import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import AffinityPropagation# Configuration options
num_samples_total = 50
cluster_centers = [(20,20), (4,4)]
num_classes = len(cluster_centers)# Generate data
X, targets = make_blobs(n_samples = num_samples_total, centers = cluster_centers, n_features = num_classes, center_box=(0, 1), cluster_std = 1)np.save('./clusters.npy', X)
X = np.load('./clusters.npy')# Fit AFfinity Propagation with Scikit
afprop = AffinityPropagation(max_iter=250)
afprop.fit(X)
cluster_centers_indices = afprop.cluster_centers_indices_
n_clusters_ = len(cluster_centers_indices)# Predict the cluster for all the samples
P = afprop.predict(X)# Generate scatter plot for training data
colors = list(map(lambda x: '#3b4cc0' if x == 1 else '#b40426', P))
plt.scatter(X[:,0], X[:,1], c=colors, marker="o", picker=True)
plt.title(f'Estimated number of clusters = {n_clusters_}')
plt.xlabel('Temperature yesterday')
plt.ylabel('Temperature today')
plt.show()Summary

三、亲和力传播的一些应用

Affinity Propagation 是一种强大的聚类算法，已在各个领域得到应用。它能够自动确定集群数量，使其在集群数量未知或难以确定的情况下特别有用。以下是 Affinity Propagation （AP） 算法的一些关键应用：

图像和视频分析：Affinity Propagation 已成功应用于图像和视频分析任务，例如对象识别、图像分割和视频摘要。通过将图像或视频中的相似区域或对象聚集起来，它可以帮助识别和分类不同的对象或场景。
自然语言处理：Affinity Propagation 已用于自然语言处理任务，例如文档聚类、主题建模和情感分析。它可以根据内容将类似的文档分组在一起，从而更轻松地组织和分析大型文本数据集。
生物信息学：AP 算法已应用于生物信息学中，用于基因表达分析、蛋白质结构预测和蛋白质相互作用网络聚类等任务。它可以帮助识别生物数据中的模式和关系，从而在基因组学和蛋白质组学领域获得见解和发现。
社交网络分析：Affinity Propagation 已用于社交网络分析，以识别网络中的社区或组。通过根据个人的社交关系或互动对个人进行聚类，它可以帮助理解社交网络的结构和动态。
市场划分：Affinity Propagation （AP） 已用于市场细分研究，根据客户的偏好、行为或人口统计数据对客户进行分组。这可以帮助企业针对特定的客户群并相应地定制他们的营销策略。

四、总结

在此博客文章中，我们了解了 Affinity Propagation 算法。这种聚类算法允许机器学习工程师通过 “消息传递” 来聚类他们的数据集。类似于高中时的小组组建方式，小组领导决定谁进入，谁必须选择另一个，拉动游戏也由算法玩。

通过查看传播的消息、与这些消息一起发送的责任和可用性指标，以及它们如何迭代收敛，我们首先了解了 Affinity Propagation 算法的理论部分。接下来是一个使用 Python 和 Scikit-learn 的实际示例，我们在其中逐步解释了如何实现 Affinity Propagation。对于那些感兴趣的人，上面也可以找到整个模型。