AP聚类算法实战：解决高维数据聚类难题的完整方案

1次阅读

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

在处理高维数据时，K-Means 这类传统算法常常力不从心。主要问题集中在三个方面：

维度灾难 ：随着维度增加，数据点之间的距离趋于相等，导致聚类效果急剧下降
球形假设限制 ：K-Means 假设数据呈球形分布，难以处理非凸分布数据
预设 K 值依赖 ：需要人工指定聚类数量，而实际应用中最佳 K 值往往难以确定

AP(Affinity Propagation) 聚类通过数据点间的 ” 投票 ” 机制自动确定聚类中心，其核心是两种消息传递：

吸引度 (Responsibility)：点 i 告诉候选中心点 k，相对于其他候选中心，k 有多适合作为 i 的聚类中心
归属度 (Availability)：候选中心点 k 告诉点 i，考虑到其他点对 k 的偏好，k 有多适合作为 i 的聚类中心

算法特性	AP 聚类	DBSCAN	谱聚类
时间复杂度	O(N²T)	O(NlogN)	O(N³)
需要预设参数	偏好参数	邻域半径	聚类数目
适合数据分布	任意形状	密度均匀	图结构
自动确定簇数	是	是	否

import numpy as np
from sklearn.cluster import AffinityPropagation
from sklearn.metrics import pairwise_distances

# 生成示例数据
np.random.seed(42)
X = np.random.randn(100, 10)  # 100 个 10 维数据点

# 计算相似度矩阵（负欧式距离）sim_matrix = -pairwise_distances(X, metric='euclidean')

# 创建 AP 模型
ap = AffinityPropagation(
    affinity='precomputed',  # 使用预计算相似度
    damping=0.7,            # 阻尼系数 (0.5-1)
    preference=np.median(sim_matrix),  # 初始偏好值
    max_iter=200
)

# 训练模型
try:
    ap.fit(sim_matrix)
    print(f"找到 {len(ap.cluster_centers_indices_)} 个聚类中心")

    # 获取聚类结果
    labels = ap.labels_

except Exception as e:
    print(f"聚类失败: {str(e)}")

damping factor(阻尼系数)：
范围 0.5-1.0，防止数值震荡
越高收敛越慢但更稳定
preference(偏好参数)：
控制成为聚类中心的倾向
默认使用相似度矩阵的中位数
max_iter(最大迭代次数)：
消息传递的最大轮次
实际可能提前收敛

对于大规模数据，使用稀疏矩阵存储相似度：

from scipy.sparse import csr_matrix

# 只保留前 k 个最近邻的相似度
k_nearest = 5
sim_sparse = kneighbors_graph(X, k_nearest, mode='connectivity', include_self=True)
sim_sparse = sim_sparse.multiply(sim_matrix)  # 元素级乘法

对核心的消息传递循环使用 Numba 优化：

from numba import jit

@jit(nopython=True, parallel=True)
def update_messages(R, A, damping):
    # 并行更新消息的代码实现
    ...

距离度量选择 ：
欧式距离：适合数值型特征
余弦相似度：适合文本等高维稀疏数据
内存不足处理 ：
使用 MiniBatch 策略分批计算
降维处理后聚类
结果评估 ：

轮廓系数：衡量簇内紧密度和簇间分离度

from sklearn.metrics import silhouette_score
score = silhouette_score(X, labels)

使用 t -SNE 降维后可视化聚类结果：

from sklearn.manifold import TSNE
import matplotlib.pyplot as plt

tsne = TSNE(n_components=2)
X_2d = tsne.fit_transform(X)

plt.scatter(X_2d[:,0], X_2d[:,1], c=labels, cmap='viridis')
plt.title('AP Clustering Result')
plt.show()

用户画像聚类 ：电商用户行为数据分群
异常检测 ：通过离群点识别异常行为
图像分割 ：相似像素区域聚类

原始论文：Frey & Dueck, “Clustering by Passing Messages Between Data Points”, Science 2007
scikit-learn 官方文档：AffinityPropagation 类详解
开源实现：https://github.com/ulf1/affinity-propagation

经过多个项目的实际应用，AP 聚类在以下场景表现尤为突出：当数据维度较高且真实聚类数量未知时，AP 算法能够自动发现数据中的自然分组。不过需要注意，对于超大规模数据集 (>10 万样本)，可能需要先进行采样或使用近似算法。参数调优方面，建议先用小样本调试好 damping 和 preference 参数，再扩展到全量数据。

正文完