当前位置：首页 > news >正文

聚类算法 ap 聚类谱聚类

news 来源：原创 2025/9/21 11:06:30

AP聚类（Affinity Propagation Clustering）是一种基于消息传递的聚类算法，由Brendan J. Frey和Delbert Dueck于2007年提出。与传统的聚类算法（如K-Means）不同，AP聚类不需要预先指定聚类数量，而是通过数据点之间的相似度自动确定聚类中心和聚类数量。

AP聚类的核心思想

相似度矩阵：
- AP聚类通过一个相似度矩阵 ( S ) 来描述数据点之间的关系。矩阵中的元素 ( s(i, k) ) 表示数据点 ( i ) 与数据点 ( k ) 之间的相似度。
- 通常，相似度可以定义为数据点之间的负欧氏距离（或其他距离度量），即 ( s(i, k) = -||x_i - x_k||^2 )。
责任矩阵（Responsibility）：
- 责任矩阵 ( R ) 中的元素 ( r(i, k) ) 表示数据点 ( i ) 向数据点 ( k ) 发送的消息，反映了数据点 ( k ) 作为数据点 ( i ) 的聚类中心的适合程度。
可用性矩阵（Availability）：
- 可用性矩阵 ( A ) 中的元素 ( a(i, k) ) 表示数据点 ( k ) 向数据点 ( i ) 发送的消息，反映了数据点 ( k ) 作为聚类中心的可用性。
消息传递：
- AP聚类通过迭代更新责任矩阵和可用性矩阵，直到收敛。最终，每个数据点会被分配到其最适合的聚类中心。
聚类中心：
- 聚类中心是那些具有较高责任和可用性值的数据点。算法会自动确定聚类中心的数量。

AP聚类的优点

无需指定聚类数量：
- 与K-Means等算法不同，AP聚类不需要预先指定聚类数量，而是通过数据点之间的相似度自动确定。
对初始值不敏感：
- AP聚类对初始值的依赖性较低，通常能获得稳定的聚类结果。
适合中小规模数据集：
- AP聚类在处理中小规模数据集时表现良好。

AP聚类的缺点

计算复杂度高：
- AP聚类的时间复杂度为 ( O(N^2) )，其中 ( N ) 是数据点的数量。因此，它不适合处理大规模数据集。
对相似度矩阵敏感：
- 聚类结果依赖于相似度矩阵的定义，如果相似度矩阵定义不合理，聚类效果可能较差。

Python实现

以下是使用 scikit-learn 实现AP聚类的示例代码：

from sklearn.cluster import AffinityPropagation
import numpy as np# 示例数据
X = np.array([[1, 2], [1, 4], [1, 0],[4, 2], [4, 4], [4, 0]])# 创建AP聚类模型
af = AffinityPropagation(preference=-50).fit(X)# 获取聚类结果
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_print("聚类中心索引:", cluster_centers_indices)
print("聚类标签:", labels)

参数说明

preference：
- 控制数据点成为聚类中心的倾向性。值越大，聚类中心越多；值越小，聚类中心越少。默认情况下，preference 为所有相似度的中位数。
damping：
- 阻尼系数（取值范围为0.5到1），用于控制消息传递的收敛速度。默认值为0.5。
max_iter：
- 最大迭代次数，默认值为200。

总结

AP聚类是一种强大的聚类算法，特别适合中小规模数据集和不需要预先指定聚类数量的场景。然而，它的计算复杂度较高，不适合处理大规模数据。在实际应用中，可以根据数据特点选择合适的聚类算法。

我来给你简单介绍一下 AP 聚类，也叫 Affinity Propagation 聚类（亲和传播聚类）。

什么是 AP 聚类？
AP 聚类是一种不需要提前指定簇数量的聚类算法。
和 KMeans 这种算法不同，它通过让数据点互相“发送消息”，自动决定哪些点是簇的中心（即“代表点”或“样本代表”），最后形成不同的簇。

由两位学者 Brendan J. Frey 和 Delbert Dueck 在 2007 年提出。

原理简介
AP 聚类的核心思想是：

每个点都可以是潜在的聚类中心。

点之间互相传递两种消息：

归属度（Responsibility）：点 i 认为点 k 作为它的簇中心的适合程度。

可用度（Availability）：点 k 认为自己作为点 i 簇中心的适合程度。

算法通过迭代更新这两个值，直到收敛。

特点
优点

不需要提前指定簇数量。

能自动选择代表点。

对异常值不敏感。

适用于复杂的样本分布。

缺点

时间复杂度较高，一般是 O(N²)，适合中小规模数据。

相似度矩阵要提前计算，内存消耗大。

适用场景
文本分类

图像处理与图像分割

基因数据聚类

推荐系统

Python 简单示例
你可以用 sklearn 来实现：

python
复制
编辑
from sklearn.cluster import AffinityPropagation
from sklearn import datasets
import matplotlib.pyplot as plt

加载数据

X, y = datasets.make_blobs(random_state=42)

建立模型

ap = AffinityPropagation(random_state=0)
ap.fit(X)

可视化

plt.scatter(X[:, 0], X[:, 1], c=ap.labels_)
plt.scatter(ap.cluster_centers_[:, 0], ap.cluster_centers_[:, 1], c=‘red’, marker=‘x’)
plt.title(‘Affinity Propagation Clustering’)
plt.show()

AP（Affinity Propagation）聚类是一种基于“消息传递”（Message Passing）的聚类算法，其核心思想是不需要预先指定簇的数量，而由数据点间的相似度自动决定聚类中心。下面介绍其主要数学推导公式及其含义：

一、基本概念
相似度函数
𝑠
(
𝑖
,
𝑘
)
s(i,k)
表示数据点
𝑖
i 与候选聚类中心
𝑘
k 之间的相似度。

一般来说，常用的定义是负距离：

𝑠
(
𝑖
,
𝑘
)

−
∥
𝑥
𝑖
−
𝑥
𝑘
∥
2
s(i,k)=−∥x
i

−x
k

∥
2

对于
𝑖

𝑘
i=k（也就是把自己作为中心），还会引入一个偏好值
𝑝
p（preference），该值控制簇的数量。通常，所有数据点的偏好值设为相同值。

责任值
𝑟
(
𝑖
,
𝑘
)
r(i,k)
表示数据点
𝑖
i “认为”数据点
𝑘
k 作为簇中心的合适程度，相当于 i 选择 k 的论据。

可用度
𝑎
(
𝑖
,
𝑘
)
a(i,k)
表示数据点
𝑘
k “适合”被
𝑖
i 选择作为簇中心的支持程度。
注意：两者都是通过“消息”传递机制在所有数据点之间迭代更新的。

二、消息传递更新公式

责任值更新公式
对于每个数据点
𝑖
i 和候选中心
𝑘
k，责任值
𝑟
(
𝑖
,
𝑘
)
r(i,k) 的更新公式为：

𝑟
(
𝑖
,
𝑘
)
←
𝑠
(
𝑖
,
𝑘
)
−
max
⁡
𝑘
′
≠
𝑘
{
𝑎
(
𝑖
,
𝑘
′
)
+
𝑠
(
𝑖
,
𝑘
′
)
}
r(i,k)←s(i,k)−
k
′


=k
max

{a(i,k
′
)+s(i,k
′
)}
解释：

𝑠
(
𝑖
,
𝑘
)
s(i,k) 表示
𝑖
i 与
𝑘
k 的直接相似度。

max
⁡
𝑘
′
≠
𝑘
{
𝑎
(
𝑖
,
𝑘
′
)
+
𝑠
(
𝑖
,
𝑘
′
)
}
max
k
′


=k

{a(i,k
′
)+s(i,k
′
)} 则是除了
𝑘
k 之外的所有候选中心中，能给予
𝑖
i 的最大支持（可用度加上相似度）。

因此，责任值表示
𝑖
i 与
𝑘
k 的相似度相对于其它候选中心的优势。

可用度更新公式
对于
𝑎
(
𝑖
,
𝑘
)
a(i,k) 的更新分为两种情况：

当
𝑖
≠
𝑘
i

=k（非自引用）时：

𝑎
(
𝑖
,
𝑘
)
←
min
⁡
{
0
,

𝑟
(
𝑘
,
𝑘
)
+
∑
𝑖
′
∉
{
𝑖
,
𝑘
}
max
⁡
(
0
,

𝑟
(
𝑖
′
,
𝑘
)
)
}
a(i,k)←min
⎩
⎨
⎧

0,r(k,k)+
i
′
∈
/
{i,k}
∑

max(0,r(i
′
,k))
⎭
⎬
⎫

解释：

𝑟
(
𝑘
,
𝑘
)
r(k,k) 表示候选点
𝑘
k 作为自身作为簇中心的自信程度。

∑
𝑖
′
∉
{
𝑖
,
𝑘
}
max
⁡
(
0
,

𝑟
(
𝑖
′
,
𝑘
)
)
∑
i
′
∈
/
{i,k}

max(0,r(i
′
,k)) 累计了其他所有数据点对
𝑘
k 的正面反馈（责任值非负部分）。

取两者之和与 0 的较小值，确保当负反馈过大时，可用度不会超过 0，避免对不适合做中心的数据点给予过高可用度。

当
𝑖

𝑘
i=k（自引用）时：

𝑎
(
𝑘
,
𝑘
)
←
∑
𝑖
′
≠
𝑘
max
⁡
(
0
,

𝑟
(
𝑖
′
,
𝑘
)
)
a(k,k)←
i
′


=k
∑

max(0,r(i
′
,k))
解释：

自可用度是所有其他数据点对
𝑘
k 的正面责任值的累计和，反映了
𝑘
k 作为聚类中心的总体吸引力。

三、算法流程简述
初始化：
通常先将所有责任值
𝑟
(
𝑖
,
𝑘
)
r(i,k) 和可用度
𝑎
(
𝑖
,
𝑘
)
a(i,k) 设置为 0。

消息传递迭代：
交替更新责任值和可用度，反复迭代直到收敛或达到迭代次数上限。

确定聚类中心：
对于每个数据点
𝑖
i，计算
𝑎
(
𝑖
,
𝑘
)
+
𝑟
(
𝑖
,
𝑘
)
a(i,k)+r(i,k)；令

𝑘
∗

arg
⁡
max
⁡
𝑘
{
𝑎
(
𝑖
,
𝑘
)
+
𝑟
(
𝑖
,
𝑘
)
}
k
∗
=arg
k
max

{a(i,k)+r(i,k)}
如果
𝑘
∗

𝑖
k
∗
=i，则数据点
𝑖
i 被选为聚类中心；否则，
𝑖
i 分配到
𝑘
∗
k
∗
对应的簇中。

四、总结
AP 聚类不需要预先指定聚类数，而是基于数据点之间的相似度、责任值和可用度的相互作用来自适应地确定聚类中心和簇的数量。

关键公式为责任值和可用度的更新公式，其中责任值反映了某点认为另一个点适合作为中心的优势，可用度反映了候选点对其他点的吸引力。

迭代更新这些消息，最终就能得到每个数据点对应的聚类分配。

这些公式和流程构成了 AP 聚类的数学基础。希望这个详细讲解对你理解 AP 聚类有所帮助