AP聚类算法实战指南：从原理到Python实现

1次阅读

没有评论

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

传统聚类算法如 K -Means 虽然简单高效，但在实际应用中存在两个主要痛点：

K 值确定困难 ：需要预先指定聚类数量，但现实数据中往往难以确定最佳 K 值
数据分布敏感 ：假设数据呈凸分布，对非均匀分布或流形结构数据效果较差

而 AP 聚类算法通过消息传递自动确定聚类中心，且不依赖数据分布假设，特别适合以下场景：

数据分布形态未知
需要自动确定聚类数量
存在离群点的数据集

AP 聚类使用负欧式距离作为样本间相似度度量：

$$s(i,k) = -||x_i – x_k||^2$$

其中 $s(i,i)$ 称为 ”preference”，控制样本成为聚类中心的倾向，通常设置为相似度的中位数。

算法通过两类消息迭代更新：

Responsibility（吸引度）：
$$r(i,k) = s(i,k) – \max_{k’ \neq k}{a(i,k’) + s(i,k’)}$$
表示样本 $i$ 选择样本 $k$ 作为其代表的累积证据
Availability（归属度）：
$$a(i,k) = \min\left(0, r(k,k) + \sum_{i’ \notin {i,k}}\max(0,r(i’,k))\right)$$
反映样本 $k$ 适合作为聚类中心的累积证据

迭代过程如下图所示：

graph LR
    A[初始化相似度矩阵] --> B[计算 Responsibility]
    B --> C[计算 Availability]
    C --> D{收敛?}
    D -->| 否 | B
    D -->| 是 | E[确定聚类中心]

import numpy as np

def compute_similarity(X, preference=None):
    """
    计算负欧式距离相似度矩阵
    :param X: 样本矩阵，形状 (n_samples, n_features)
    :param preference: 对角线偏好值，默认为相似度中位数
    :return: 相似度矩阵
    """
    n_samples = X.shape[0]
    # 计算两两样本间欧式距离
    dist = np.sum((X[:, None] - X) ** 2, axis=2)
    S = -dist  # 转换为负欧式距离

    # 设置对角线偏好值
    if preference is None:
        preference = np.median(S)
    np.fill_diagonal(S, preference)

    return S

def affinity_propagation(S, max_iter=200, damping=0.5):
    """
    AP 聚类核心实现
    :param S: 相似度矩阵
    :param max_iter: 最大迭代次数
    :param damping: 阻尼系数 (0.5-1)
    :return: 聚类标签
    """
    n = S.shape[0]
    R = np.zeros((n, n))  # Responsibility 矩阵
    A = np.zeros((n, n))  # Availability 矩阵

    for _ in range(max_iter):
        # 保存旧值用于收敛判断
        old_R, old_A = R.copy(), A.copy()

        # 更新 Responsibility
        AS = A + S
        max_col = np.max(AS, axis=1, keepdims=True)
        np.fill_diagonal(AS, -np.inf)
        second_max = np.max(AS, axis=1, keepdims=True)
        R = S - max_col
        np.fill_diagonal(R, S.diagonal() - second_max.diagonal())

        # 应用阻尼系数
        R = (1 - damping) * R + damping * old_R

        # 更新 Availability
        Rp = np.maximum(R, 0)
        np.fill_diagonal(Rp, R.diagonal())

        A = np.sum(Rp, axis=0, keepdims=True) - Rp
        A = np.minimum(A, 0)
        np.fill_diagonal(A, np.sum(np.maximum(R, 0), axis=0) - R.diagonal())

        # 应用阻尼系数
        A = (1 - damping) * A + damping * old_A

        # 检查收敛
        if np.allclose(R, old_R, atol=1e-6) and np.allclose(A, old_A, atol=1e-6):
            break

    # 确定聚类中心
    exemplars = np.where(np.diagonal(R + A) > 0)[0]
    labels = np.argmax(R + A, axis=1)
    return labels, exemplars

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

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

# 运行 AP 聚类
S = compute_similarity(X)
labels, exemplars = affinity_propagation(S, damping=0.7)

# 可视化结果
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.scatter(X[exemplars, 0], X[exemplars, 1], marker='*', s=200, c='red')
plt.title("AP Clustering Result")
plt.show()

典型值范围 ：0.5-0.9
低阻尼 (0.5-0.6)：收敛快但可能振荡
高阻尼 (0.7-0.9)：稳定但收敛慢

建议从 0.7 开始尝试，根据收敛情况调整

设为相似度中位数 ：产生中等数量的聚类
设为最小值 ：倾向于少量大聚类
设为最大值 ：倾向于大量小聚类

可通过以下方式动态设置：

# 基于数据规模自动调整 preference
preference = np.min(S) + (np.max(S) - np.min(S)) * 0.1

对于大数据集（n>5000），可采用以下策略：

稀疏矩阵优化 ：

from scipy.sparse import csr_matrix

# 只保留每个样本的前 k 个最近邻
k = 50
knn_indices = np.argsort(S, axis=1)[:, -k:]
sparse_S = csr_matrix((n, n))
for i in range(n):
    sparse_S[i, knn_indices[i]] = S[i, knn_indices[i]]

分批处理 ：将数据分为多个子集分别聚类

症状：计算相似度矩阵时内存不足

解决方案 ：
1. 使用 float32 替代默认 float64
2. 采用内存映射文件处理大数据

S = np.memmap('similarity.dat', dtype='float32', mode='w+', shape=(n,n))

3. 使用近似最近邻算法减少计算量

可能原因 ：
1. 阻尼系数设置不当
2. 数据尺度差异大
3. 存在大量噪声点

调试步骤 ：
1. 检查数据标准化

from sklearn.preprocessing import StandardScaler
X = StandardScaler().fit_transform(X)

2. 增加 max_iter（如 500-1000）
3. 尝试不同的 preference 值

将 AP 聚类应用于文本数据的关键步骤：

使用 TF-IDF 或 BERT 提取文本特征

采用余弦相似度构建相似度矩阵

from sklearn.metrics.pairwise import cosine_similarity
S = cosine_similarity(tfidf_matrix)

调整 preference 控制聚类粒度

特性	AP 聚类	谱聚类
聚类数量	自动确定	需预设 K 值
数据假设	无分布假设	假设数据在流形上
计算复杂度	O(N²)	O(N³)
最佳场景	中小规模数据	非凸分布数据