AP聚类算法原理解析与实战：从数据相似度到聚类结果

1次阅读

共计 1801 个字符，预计需要花费 5 分钟才能阅读完成。

在传统聚类算法中，如 K -Means，一个显著的局限性是需要预先指定聚类数量 K。这一要求在实际应用中往往带来挑战，因为数据的内在结构通常是未知的。AP 聚类算法（Affinity Propagation）通过自动识别数据中的代表性样本（exemplars）来克服这一限制，无需预先指定 K 值，使其在无监督学习任务中更具优势。

AP 聚类算法的第一步是构建相似度矩阵 S，其中 S(i,j)表示数据点 i 与数据点 j 之间的相似度。通常使用负欧氏距离或其他距离度量来定义相似度：

$$
S(i,j) = -||x_i – x_j||^2
$$

对角元素 S(i,i)称为“偏好”（preference），表示数据点 i 成为聚类中心的倾向性。

AP 聚类通过两种消息传递机制来迭代更新聚类中心：

责任度（Responsibility）：数据点 i 向候选聚类中心 j 发送消息，表示 i 选择 j 作为其聚类中心的累积证据。公式为：

$$
r(i,j) = S(i,j) – \max_{j’ \neq j} {a(i,j’) + S(i,j’)}
$$

可用度（Availability）：候选聚类中心 j 向数据点 i 发送消息，表示 j 作为 i 的聚类中心的累积证据。公式为：

$$
a(i,j) = \min \left{0, r(j,j) + \sum_{i’ \neq i, i’ \neq j} \max{0, r(i’,j)} \right}
$$

通过迭代更新责任度和可用度，算法最终收敛到一组稳定的聚类中心。聚类中心的选择由以下条件决定：

$$
\text{argmax}_j {a(i,j) + r(i,j)}
$$

以下是一个使用 Python 的 sklearn 库实现 AP 聚类的完整示例：

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

# 生成示例数据
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5, random_state=0)

# 初始化 AP 聚类模型
af = AffinityPropagation(preference=-50, damping=0.5, random_state=0).fit(X)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_

# 评估聚类效果
print(f"Silhouette Coefficient: {metrics.silhouette_score(X, labels, metric='euclidean'):.3f}")

# 可视化结果
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.7)
plt.scatter(X[cluster_centers_indices, 0], X[cluster_centers_indices, 1], c='red', marker='x', s=100)
plt.title('AP Clustering')
plt.show()

阻尼系数用于控制消息传递的平滑程度，取值范围在 0.5 到 1 之间。较高的阻尼系数可以减少振荡，但可能会减慢收敛速度。

偏好参数决定了数据点成为聚类中心的倾向性。通常设置为相似度矩阵的中位数或最小值。较高的偏好值会导致更多的聚类中心。

AP 聚类算法的时间复杂度为 O(N^2 T)，其中 N 是数据点数量，T 是迭代次数。对于大规模数据集，可以考虑以下优化策略：