2026/8/6 1:55:22
FEATURED · 精选文章 
1. 近邻传播聚类算法AP算法概述近邻传播聚类算法Affinity Propagation简称AP算法是一种基于消息传递机制的聚类方法由Frey和Dueck在2007年首次提出。与传统的K-means等聚类算法不同AP算法最大的特点是不需要预先指定聚类数目而是通过数据点之间的消息传递自动确定最佳聚类中心和类别划分。这个算法在生物信息学、图像处理、社交网络分析等领域都有广泛应用。我最早接触AP算法是在处理一组基因表达数据时当时传统聚类方法因为无法确定合适的K值而屡屡碰壁AP算法则完美解决了这个问题。2. AP算法的核心原理与优势2.1 消息传递机制AP算法的核心在于两种消息的迭代传递吸引度消息Responsibility从点i到候选代表点k表示i支持k作为其代表的累积证据归属度消息Availability从候选代表点k到点i表示k适合作为i的代表的累积证据这两种消息的数学表达式为r(i,k) s(i,k) - max{a(i,k) s(i,k)} (k≠k) a(i,k) min{0, r(k,k) Σmax{0,r(i,k)}} (i∉{i,k})其中s(i,k)是相似度矩阵通常定义为负的欧氏距离平方。2.2 与传统聚类算法的对比与K-means相比AP算法有几个显著优势无需预先指定聚类数目聚类中心是真实存在的数据点而非计算均值对初始条件不敏感能发现非球形的聚类结构不过AP算法也有其局限性主要是计算复杂度较高O(N²T)不太适合超大规模数据集。3. MATLAB实现AP算法的完整流程3.1 数据准备与相似度计算首先我们需要准备数据并计算相似度矩阵。以下是一个典型的实现步骤% 生成示例数据 rng(1); % 固定随机种子确保可重复性 data [randn(30,2)*0.51; randn(30,2)*0.5-1]; % 计算相似度矩阵负平方欧氏距离 N size(data,1); S zeros(N,N); for i 1:N for j 1:N S(i,j) -sum((data(i,:)-data(j,:)).^2); end end3.2 关键参数设置AP算法有几个重要参数需要关注% 设置偏好参数通常取相似度矩阵的中值 preference median(S(:)); % 阻尼系数防止振荡通常0.5-0.9 damping 0.7; % 最大迭代次数 maxits 500; % 收敛阈值 convits 50;偏好参数(preference)特别关键它决定了每个点成为聚类中心的倾向性。取值越大得到的聚类数目通常越多。3.3 核心算法实现以下是AP算法的MATLAB核心实现function [idx, centers] APCluster(S, preference, damping, maxits, convits) N size(S,1); A zeros(N,N); % Availability矩阵 R zeros(N,N); % Responsibility矩阵 for iter 1:maxits % 更新Responsibility Rnew S - max(A S, [], 2); R (1-damping)*Rnew damping*R; % 更新Availability Anew min(0, R sum(max(0,R),1) - max(0,R)); A (1-damping)*Anew damping*A; % 检查收敛 if iter convits all(sign(RA) sign(RoldAold)) break; end Rold R; Aold A; end % 确定聚类中心和分配 centers find(diag(RA) 0); [~, idx] max(S(:,centers), [], 2); end3.4 结果可视化聚类结果的可视化对于理解算法效果至关重要[idx, centers] APCluster(S, preference, damping, maxits, convits); figure; gscatter(data(:,1), data(:,2), idx); hold on; plot(data(centers,1), data(centers,2), kx, MarkerSize, 15, LineWidth, 3); title(AP聚类结果); legend(Cluster 1, Cluster 2, 聚类中心);4. 实战中的关键问题与调优技巧4.1 偏好参数的调整策略偏好参数(preference)的设定直接影响聚类数目。经过多次实践我总结出几种有效的设定方法中值法取相似度矩阵的中位数默认方法preference median(S(:));分位数法对于希望获得更多聚类的情况preference quantile(S(:), 0.75);手动调整法通过观察相似度分布直方图选择figure; histogram(S(:), 50);提示实际应用中我通常会先用中值法得到初始结果再根据需求微调preference值。当数据存在明显层级结构时可以尝试不同的preference值来探索不同粒度的聚类。4.2 处理振荡问题AP算法在迭代过程中可能出现振荡现象表现为聚类中心不断变化。解决方法包括增加阻尼系数通常0.5-0.9damping 0.8; % 比默认0.5更保守提前终止条件convits 100; % 增加收敛判断的连续迭代次数限制最大迭代次数maxits 1000; % 对于复杂数据集可能需要更多迭代4.3 大规模数据的优化策略当数据量较大时N5000标准的AP算法会变得非常耗时。可以考虑以下优化稀疏相似度矩阵只计算每个点与最近邻的相似度[IDX, D] knnsearch(data, data, K, 50); S sparse(repmat((1:N),1,50), IDX, -D.^2, N, N);Mini-batch AP对数据进行采样后应用AP算法并行计算利用MATLAB的并行计算功能parfor i 1:N % 计算相似度的并行化部分 end5. 评估聚类质量的实用方法5.1 内部评估指标轮廓系数(Silhouette Coefficient)是评估聚类质量的常用指标silhouette_values silhouette(data, idx); mean_sil mean(silhouette_values); disp([平均轮廓系数, num2str(mean_sil)]);一般来说0.7强聚类结构0.5-0.7合理结构0.25无明显聚类结构5.2 外部评估指标如果有真实标签可以使用调整兰德指数(ARI)和标准化互信息(NMI)% 假设true_labels是真实类别标签 ari adjustedRandIndex(true_labels, idx); nmi normalized_mutual_info(true_labels, idx);这些指标的实现可以在MATLAB的统计和机器学习工具箱中找到或者从File Exchange下载相关函数。6. 实际应用案例客户细分分析让我们看一个真实的应用场景——零售客户细分。假设我们有客户的购买频率和平均消费金额数据% 加载客户数据 customer_data csvread(customer_data.csv); % [购买频率, 平均消费] % 计算相似度矩阵 D pdist2(customer_data, customer_data); S -D.^2; % 运行AP聚类 [idx, centers] APCluster(S, median(S(:)), 0.7, 500, 50); % 分析聚类特征 cluster_stats grpstats(customer_data, idx, {mean, std}); disp(cluster_stats);通过分析各簇的统计特征我们可以识别出高价值常客高频次、高消费潜在流失客户频次下降价格敏感型客户高频次、低消费偶尔大额消费客户低频次、高消费这种细分结果可以帮助企业制定更有针对性的营销策略。7. 常见问题排查指南7.1 算法不收敛现象迭代达到最大次数仍未收敛解决方案检查相似度矩阵是否有异常值figure; imagesc(S); colorbar;增加阻尼系数0.7-0.9调整preference值通常降低7.2 聚类数目不合理现象得到的聚类数目过多或过少解决方案调整preference参数增加preference → 减少聚类数目减小preference → 增加聚类数目检查数据是否真的存在聚类结构通过轮廓系数7.3 内存不足现象处理大数据集时出现内存错误解决方案使用稀疏矩阵存储相似度采用数据采样或Mini-batch方法升级硬件或使用云计算资源8. 进阶技巧与扩展应用8.1 处理非数值数据AP算法本质上依赖相似度矩阵因此可以处理各种类型的数据只需定义合适的相似度度量文本数据使用余弦相似度或Jaccard相似度S 1 - pdist(tfidf_matrix, cosine);图数据使用节点相似性度量如共同邻居数时间序列使用DTW动态时间规整距离8.2 半监督AP聚类当有部分先验信息时可以约束聚类过程% 设置必须链接的约束must-link must_link_pairs [1,5; 3,7]; % 样本1和5必须同簇 for i 1:size(must_link_pairs,1) a must_link_pairs(i,1); b must_link_pairs(i,2); S(a,b) S(b,a) max(S(:)) 1; % 增大相似度 end % 设置不能链接的约束cannot-link cannot_link_pairs [2,4; 6,8]; % 样本2和4不能同簇 for i 1:size(cannot_link_pairs,1) a cannot_link_pairs(i,1); b cannot_link_pairs(i,2); S(a,b) S(b,a) min(S(:)) - 1; % 减小相似度 end8.3 多视图AP聚类对于多源数据可以融合多个相似度矩阵% 假设S1和S2是两个不同特征的相似度矩阵 alpha 0.7; % 融合权重 S_combined alpha*S1 (1-alpha)*S2; % 然后使用融合后的矩阵进行聚类 [idx, centers] APCluster(S_combined, median(S_combined(:)));9. 性能优化与加速技巧9.1 矩阵运算优化AP算法中最耗时的部分是矩阵运算可以通过以下方式优化向量化计算避免使用循环% 替代双重循环计算相似度矩阵 D pdist2(data, data); S -D.^2;使用GPU加速gpuData gpuArray(data); gpuD pdist2(gpuData, gpuData); gpuS -gpuD.^2;9.2 近似算法对于超大规模数据可以考虑近似AP算法分层AP先对数据进行粗聚类再对每个簇应用APLandmark AP选择代表性样本点进行聚类再分配其余点9.3 内存管理技巧使用单精度浮点数减少内存占用S single(S);及时清除不再需要的大变量clear D gpuD;10. 与其他聚类算法的结合使用在实际应用中我经常将AP算法与其他方法结合使用10.1 AP K-means先用AP确定聚类中心和数目再用K-means细化结果% 先用AP确定聚类中心 [idx_ap, centers] APCluster(S, preference); % 提取AP找到的聚类数目 k length(centers); % 使用K-means进行细化 [idx_kmeans] kmeans(data, k, Start, data(centers,:));10.2 AP 层次聚类对于层级结构明显的数据% 先用AP得到粗粒度聚类 [idx_ap, centers] APCluster(S, high_preference); % 对每个簇应用层次聚类 for c 1:max(idx_ap) cluster_data data(idx_apc,:); Z linkage(cluster_data); sub_clusters cluster(Z, maxclust, 3); % 每个粗簇分为3个子簇 end10.3 AP DBSCAN结合密度聚类处理噪声% 先用AP进行主要聚类 [idx_ap, centers] APCluster(S, preference); % 识别噪声点相似度极低的点 noise find(sum(S median(S(:))) 5); % 调整阈值 % 对噪声点应用DBSCAN if ~isempty(noise) [idx_dbscan] dbscan(data(noise,:), 0.5, 5); end在实际数据分析项目中这种组合策略往往能取得比单一算法更好的效果。特别是在处理复杂数据集时AP算法可以作为探索性分析的第一步帮助我们理解数据的固有结构然后再选择合适的细化方法。
AP聚类算法原理与MATLAB实现详解
1. 近邻传播聚类算法AP算法概述近邻传播聚类算法Affinity Propagation简称AP算法是一种基于消息传递机制的聚类方法由Frey和Dueck在2007年首次提出。与传统的K-means等聚类算法不同AP算法最大的特点是不需要预先指定聚类数目而是通过数据点之间的消息传递自动确定最佳聚类中心和类别划分。这个算法在生物信息学、图像处理、社交网络分析等领域都有广泛应用。我最早接触AP算法是在处理一组基因表达数据时当时传统聚类方法因为无法确定合适的K值而屡屡碰壁AP算法则完美解决了这个问题。2. AP算法的核心原理与优势2.1 消息传递机制AP算法的核心在于两种消息的迭代传递吸引度消息Responsibility从点i到候选代表点k表示i支持k作为其代表的累积证据归属度消息Availability从候选代表点k到点i表示k适合作为i的代表的累积证据这两种消息的数学表达式为r(i,k) s(i,k) - max{a(i,k) s(i,k)} (k≠k) a(i,k) min{0, r(k,k) Σmax{0,r(i,k)}} (i∉{i,k})其中s(i,k)是相似度矩阵通常定义为负的欧氏距离平方。2.2 与传统聚类算法的对比与K-means相比AP算法有几个显著优势无需预先指定聚类数目聚类中心是真实存在的数据点而非计算均值对初始条件不敏感能发现非球形的聚类结构不过AP算法也有其局限性主要是计算复杂度较高O(N²T)不太适合超大规模数据集。3. MATLAB实现AP算法的完整流程3.1 数据准备与相似度计算首先我们需要准备数据并计算相似度矩阵。以下是一个典型的实现步骤% 生成示例数据 rng(1); % 固定随机种子确保可重复性 data [randn(30,2)*0.51; randn(30,2)*0.5-1]; % 计算相似度矩阵负平方欧氏距离 N size(data,1); S zeros(N,N); for i 1:N for j 1:N S(i,j) -sum((data(i,:)-data(j,:)).^2); end end3.2 关键参数设置AP算法有几个重要参数需要关注% 设置偏好参数通常取相似度矩阵的中值 preference median(S(:)); % 阻尼系数防止振荡通常0.5-0.9 damping 0.7; % 最大迭代次数 maxits 500; % 收敛阈值 convits 50;偏好参数(preference)特别关键它决定了每个点成为聚类中心的倾向性。取值越大得到的聚类数目通常越多。3.3 核心算法实现以下是AP算法的MATLAB核心实现function [idx, centers] APCluster(S, preference, damping, maxits, convits) N size(S,1); A zeros(N,N); % Availability矩阵 R zeros(N,N); % Responsibility矩阵 for iter 1:maxits % 更新Responsibility Rnew S - max(A S, [], 2); R (1-damping)*Rnew damping*R; % 更新Availability Anew min(0, R sum(max(0,R),1) - max(0,R)); A (1-damping)*Anew damping*A; % 检查收敛 if iter convits all(sign(RA) sign(RoldAold)) break; end Rold R; Aold A; end % 确定聚类中心和分配 centers find(diag(RA) 0); [~, idx] max(S(:,centers), [], 2); end3.4 结果可视化聚类结果的可视化对于理解算法效果至关重要[idx, centers] APCluster(S, preference, damping, maxits, convits); figure; gscatter(data(:,1), data(:,2), idx); hold on; plot(data(centers,1), data(centers,2), kx, MarkerSize, 15, LineWidth, 3); title(AP聚类结果); legend(Cluster 1, Cluster 2, 聚类中心);4. 实战中的关键问题与调优技巧4.1 偏好参数的调整策略偏好参数(preference)的设定直接影响聚类数目。经过多次实践我总结出几种有效的设定方法中值法取相似度矩阵的中位数默认方法preference median(S(:));分位数法对于希望获得更多聚类的情况preference quantile(S(:), 0.75);手动调整法通过观察相似度分布直方图选择figure; histogram(S(:), 50);提示实际应用中我通常会先用中值法得到初始结果再根据需求微调preference值。当数据存在明显层级结构时可以尝试不同的preference值来探索不同粒度的聚类。4.2 处理振荡问题AP算法在迭代过程中可能出现振荡现象表现为聚类中心不断变化。解决方法包括增加阻尼系数通常0.5-0.9damping 0.8; % 比默认0.5更保守提前终止条件convits 100; % 增加收敛判断的连续迭代次数限制最大迭代次数maxits 1000; % 对于复杂数据集可能需要更多迭代4.3 大规模数据的优化策略当数据量较大时N5000标准的AP算法会变得非常耗时。可以考虑以下优化稀疏相似度矩阵只计算每个点与最近邻的相似度[IDX, D] knnsearch(data, data, K, 50); S sparse(repmat((1:N),1,50), IDX, -D.^2, N, N);Mini-batch AP对数据进行采样后应用AP算法并行计算利用MATLAB的并行计算功能parfor i 1:N % 计算相似度的并行化部分 end5. 评估聚类质量的实用方法5.1 内部评估指标轮廓系数(Silhouette Coefficient)是评估聚类质量的常用指标silhouette_values silhouette(data, idx); mean_sil mean(silhouette_values); disp([平均轮廓系数, num2str(mean_sil)]);一般来说0.7强聚类结构0.5-0.7合理结构0.25无明显聚类结构5.2 外部评估指标如果有真实标签可以使用调整兰德指数(ARI)和标准化互信息(NMI)% 假设true_labels是真实类别标签 ari adjustedRandIndex(true_labels, idx); nmi normalized_mutual_info(true_labels, idx);这些指标的实现可以在MATLAB的统计和机器学习工具箱中找到或者从File Exchange下载相关函数。6. 实际应用案例客户细分分析让我们看一个真实的应用场景——零售客户细分。假设我们有客户的购买频率和平均消费金额数据% 加载客户数据 customer_data csvread(customer_data.csv); % [购买频率, 平均消费] % 计算相似度矩阵 D pdist2(customer_data, customer_data); S -D.^2; % 运行AP聚类 [idx, centers] APCluster(S, median(S(:)), 0.7, 500, 50); % 分析聚类特征 cluster_stats grpstats(customer_data, idx, {mean, std}); disp(cluster_stats);通过分析各簇的统计特征我们可以识别出高价值常客高频次、高消费潜在流失客户频次下降价格敏感型客户高频次、低消费偶尔大额消费客户低频次、高消费这种细分结果可以帮助企业制定更有针对性的营销策略。7. 常见问题排查指南7.1 算法不收敛现象迭代达到最大次数仍未收敛解决方案检查相似度矩阵是否有异常值figure; imagesc(S); colorbar;增加阻尼系数0.7-0.9调整preference值通常降低7.2 聚类数目不合理现象得到的聚类数目过多或过少解决方案调整preference参数增加preference → 减少聚类数目减小preference → 增加聚类数目检查数据是否真的存在聚类结构通过轮廓系数7.3 内存不足现象处理大数据集时出现内存错误解决方案使用稀疏矩阵存储相似度采用数据采样或Mini-batch方法升级硬件或使用云计算资源8. 进阶技巧与扩展应用8.1 处理非数值数据AP算法本质上依赖相似度矩阵因此可以处理各种类型的数据只需定义合适的相似度度量文本数据使用余弦相似度或Jaccard相似度S 1 - pdist(tfidf_matrix, cosine);图数据使用节点相似性度量如共同邻居数时间序列使用DTW动态时间规整距离8.2 半监督AP聚类当有部分先验信息时可以约束聚类过程% 设置必须链接的约束must-link must_link_pairs [1,5; 3,7]; % 样本1和5必须同簇 for i 1:size(must_link_pairs,1) a must_link_pairs(i,1); b must_link_pairs(i,2); S(a,b) S(b,a) max(S(:)) 1; % 增大相似度 end % 设置不能链接的约束cannot-link cannot_link_pairs [2,4; 6,8]; % 样本2和4不能同簇 for i 1:size(cannot_link_pairs,1) a cannot_link_pairs(i,1); b cannot_link_pairs(i,2); S(a,b) S(b,a) min(S(:)) - 1; % 减小相似度 end8.3 多视图AP聚类对于多源数据可以融合多个相似度矩阵% 假设S1和S2是两个不同特征的相似度矩阵 alpha 0.7; % 融合权重 S_combined alpha*S1 (1-alpha)*S2; % 然后使用融合后的矩阵进行聚类 [idx, centers] APCluster(S_combined, median(S_combined(:)));9. 性能优化与加速技巧9.1 矩阵运算优化AP算法中最耗时的部分是矩阵运算可以通过以下方式优化向量化计算避免使用循环% 替代双重循环计算相似度矩阵 D pdist2(data, data); S -D.^2;使用GPU加速gpuData gpuArray(data); gpuD pdist2(gpuData, gpuData); gpuS -gpuD.^2;9.2 近似算法对于超大规模数据可以考虑近似AP算法分层AP先对数据进行粗聚类再对每个簇应用APLandmark AP选择代表性样本点进行聚类再分配其余点9.3 内存管理技巧使用单精度浮点数减少内存占用S single(S);及时清除不再需要的大变量clear D gpuD;10. 与其他聚类算法的结合使用在实际应用中我经常将AP算法与其他方法结合使用10.1 AP K-means先用AP确定聚类中心和数目再用K-means细化结果% 先用AP确定聚类中心 [idx_ap, centers] APCluster(S, preference); % 提取AP找到的聚类数目 k length(centers); % 使用K-means进行细化 [idx_kmeans] kmeans(data, k, Start, data(centers,:));10.2 AP 层次聚类对于层级结构明显的数据% 先用AP得到粗粒度聚类 [idx_ap, centers] APCluster(S, high_preference); % 对每个簇应用层次聚类 for c 1:max(idx_ap) cluster_data data(idx_apc,:); Z linkage(cluster_data); sub_clusters cluster(Z, maxclust, 3); % 每个粗簇分为3个子簇 end10.3 AP DBSCAN结合密度聚类处理噪声% 先用AP进行主要聚类 [idx_ap, centers] APCluster(S, preference); % 识别噪声点相似度极低的点 noise find(sum(S median(S(:))) 5); % 调整阈值 % 对噪声点应用DBSCAN if ~isempty(noise) [idx_dbscan] dbscan(data(noise,:), 0.5, 5); end在实际数据分析项目中这种组合策略往往能取得比单一算法更好的效果。特别是在处理复杂数据集时AP算法可以作为探索性分析的第一步帮助我们理解数据的固有结构然后再选择合适的细化方法。 
