孙秀龙1. 近邻传播聚类算法概述
近邻传播聚类算法（Affinity Propagation, AP算法）是一种基于信息传递的聚类方法，由Frey和Dueck于2007年在Science杂志上首次提出。与传统的K-means等聚类算法不同，AP算法最大的特点是无需预先指定聚类数量，而是通过数据点之间的"消息传递"自动确定最佳聚类中心和类别划分。
这个算法在生物信息学、图像处理、社交网络分析等领域都有广泛应用。我第一次接触AP算法是在处理一组基因表达数据时，当时面临的主要困难就是无法预先确定样本应该分为多少类。传统方法需要反复尝试不同的K值，而AP算法一次运行就能给出合理的聚类结果，这让我印象深刻。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. AP算法核心原理解析
2.1 相似度矩阵构建
AP算法的第一步是计算所有数据点之间的相似度矩阵S。对于包含N个数据点的数据集，S是一个N×N的矩阵，其中s(i,j)表示点j作为点i的聚类中心的适合程度。通常使用负的欧氏距离：
matlab复制% MATLAB中计算相似度矩阵的示例
function S = calculate_similarity(X)
n = size(X,1);
S = zeros(n,n);
for i = 1:n
for j = 1:n
S(i,j) = -sum((X(i,:)-X(j,:)).^2); % 负平方欧氏距离
end
end
end
注意：相似度度量可以根据数据类型灵活选择。对于文本数据，可以使用余弦相似度；对于高维数据，可以考虑马氏距离等更复杂的度量方式。
2.2 吸引度与归属度计算
AP算法的核心是两个关键概念：吸引度(responsibility)r(i,k)和归属度(availability)a(i,k)。这两个概念通过迭代更新来实现信息传递：
-
吸引度r(i,k)：表示点k适合作为点i的聚类中心的累积证据，反映了点i对点k作为其中心的"偏好"程度。
-
归属度a(i,k)：表示点i选择点k作为其聚类中心的适合程度，反映了点k作为中心的"可用性"。
更新公式如下：
matlab复制% 吸引度更新
R_new = S - max(repmat(A,1,1,1) + S - repmat(S(:,k),1,n), [], 3);
R_new = (1-lambda)*R_new + lambda*R_old;
% 归属度更新
A_new = min(0, R(k,k) + sum(max(0, R(setdiff(1:n,k),k))));
A_new = (1-lambda)*A_new + lambda*A_old;
2.3 阻尼因子与收敛条件
为了防止振荡，AP算法引入了阻尼因子λ（通常设为0.5-0.9）。每次更新都是新值和旧值的加权平均：
matlab复制lambda = 0.5; % 阻尼因子
收敛条件通常设置为连续多次迭代中聚类中心不再变化，或者吸引度和归属度的变化小于某个阈值。
3. MATLAB实现详解
3.1 完整算法实现
下面是一个完整的AP算法MATLAB实现：
matlab复制function [idx, centers] = affinity_propagation(X, max_iter, conv_iter, lambda)
% 输入参数：
% X: 数据矩阵(n×d)
% max_iter: 最大迭代次数
% conv_iter: 收敛检查迭代次数
% lambda: 阻尼因子(0.5-0.9)
n = size(X,1);
S = calculate_similarity