AP聚类算法原理剖析与Python实战：从数据预处理到结果可视化

1次阅读

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

传统聚类算法如 K -Means 有个致命弱点：需要预先指定聚类数量 K。但现实中，我们往往对数据该分成多少类毫无概念。AP 聚类 (Affinity Propagation) 的巧妙之处在于——它能自动确定最佳聚类数量，这个过程完全由数据驱动。

K-Means 的局限：尝试不同 K 值跑多次，依赖肘部法则等经验方法
AP 聚类的优势：通过消息传递自动涌现聚类中心，适合社交网络分析、基因数据等复杂场景
核心创新点：用数据点间的 ” 投票 ” 机制代替人工设 K，每个点都可能成为聚类中心(称为 exemplar)

AP 聚类通过两类消息在数据点间流动来完成聚类：

吸引度(Responsibility) $r(i,k)$：表示点 $i$ 有多适合选择点 $k$ 当代表，同时考虑其他潜在代表
$$r(i,k) \leftarrow s(i,k) – \max_{k’ \neq k}{a(i,k’) + s(i,k’)}$$
归属度(Availability) $a(i,k)$：反映点 $k$ 有多适合作为 $i$ 的代表，需综合其他点的意见
$$a(i,k) \leftarrow \min\left(0, r(k,k) + \sum_{i’ \notin {i,k}}\max(0,r(i’,k))\right)$$
阻尼系数 λ ：引入 0.5 到 1 之间的衰减项避免数值震荡
停止条件：当代表点连续多次迭代不变或达到最大迭代次数

from sklearn.cluster import AffinityPropagation
import numpy as np

# 生成测试数据
X, _ = make_blobs(n_samples=300, centers=4, random_state=42)

# 关键参数说明：# damping=0.7 (推荐 0.5-0.9)
# preference=None (自动取相似度中位数)
ap = AffinityPropagation(damping=0.75, random_state=42).fit(X)
print(f"自动发现的聚类数：{len(cluster_centers_indices_)}")

def affinity_propagation(S, max_iter=200, damping=0.7):
    """
    S: 相似度矩阵，S[i,j]表示 i 到 j 的相似度
    使用对数域计算防止数值溢出
    """
    n = S.shape[0]
    R, A = np.zeros((n,n)), np.zeros((n,n))

    for _ in range(max_iter):
        # 更新吸引度（稳定性处理）old_R = R.copy()
        AS = A + S
        max_col = np.max(AS, axis=1, keepdims=True)
        R = S - max_col
        np.fill_diagonal(R, S.diagonal() - max_col.flatten())

        # 更新归属度（考虑对角元素特殊处理）old_A = A.copy()
        Rp = np.maximum(R, 0)
        A = np.sum(Rp, axis=0, keepdims=True) - Rp
        diag_A = R.diagonal() + np.sum(Rp, axis=0) - Rp.diagonal()
        np.fill_diagonal(A, diag_A)

        # 阻尼更新
        R = damping*old_R + (1-damping)*R
        A = damping*old_A + (1-damping)*A

        # 打印进度（每 20 次迭代）if _ % 20 == 0:
            clusters = np.argmax(A+R, axis=1)
            print(f"Iter {_}, 临时聚类数：{len(np.unique(clusters))}")

    return np.argmax(A+R, axis=1)

from sklearn.datasets import make_blobs
import seaborn as sns

# 生成带明显聚类结构的数据
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.7, random_state=42)

# 关键步骤：负欧式距离作为相似度
def neg_squared_euclidean(X):
    """向量化计算相似度矩阵"""
    sum_X = np.sum(np.square(X), axis=1)
    D = np.add(np.add(-2 * np.dot(X, X.T), sum_X).T, sum_X)
    return -D

S = neg_squared_euclidean(X)

# 获取聚类标签
labels = affinity_propagation(S, damping=0.75)

# 绘制结果
sns.scatterplot(x=X[:,0], y=X[:,1], hue=labels, palette='viridis', 
                style=labels, s=100, legend=False)
plt.title("AP 聚类结果（自动发现 4 个类）")
plt.show()

# 决策图（帮助理解代表点选择）decision_values = np.max(A+R, axis=1)
sns.scatterplot(x=range(len(decision_values)), y=decision_values, 
                hue=(labels == np.arange(len(labels))), 
                style=(labels == np.arange(len(labels))), s=80)
plt.axhline(y=0, color='red', linestyle='--')
plt.title("决策值分布（峰值点即聚类中心）")