提到聚类多数人条件反射是 K-Means然后就卡在那个万年难题上K 到底设多少肘部图、轮廓系数、Gap Statistic 轮番上阵最后往往还是凭感觉收场。后来我在一个文本聚类项目里接触到 APAffinity Propagation亲和力传播算法才意识到有一类算法是不用先回答 K 的——它自己从数据里挑“代表点”剩余样本自动归属。这篇就聊聊 AP 是怎么回事以及我在实际使用中怎么调参、怎么避坑。如果你正被 K 的选择折磨或者你的任务希望聚类中心是真实样本而不是均值点那 AP 值得花几分钟去理解。它不像 K-Means 那样生成虚拟中心而是从已有数据里选出若干有代表性的点直觉上很像“先立代表再分归属”。下面我会先把原理讲清楚再给出一套能直接上手的实操流程最后把常见问题和排查思路整理成速查式内容。1. 为什么聚类时我总会想起 AP 亲和力传播算法1.1 K-Means 的 K是我过去最不想回答的问题刚接触聚类时我最常听到的一句话是“你先把 K 定下来。” 但 K 从哪来画轮廓系数、看肘部图、做 Gap Statistic每种方法都能给出一个“建议值”可不同方法给出的建议经常互相打架。更要命的是K-Means 对初始中心敏感同一份数据多跑几次结果就可能不一样再加上它算出来的中心是所有样本的平均值最后聚类中心往往是“现实里不存在”的点。在业务场景里这种虚拟中心很尴尬。比如用户分群后你想看看每个群的典型用户长什么样结果中心点是一个并不存在的“平均用户”比如图像检索场景里你希望每个类别能拎出一张真实图片当封面K-Means 就不太好满足。我后来做客服工单聚类时目标是想从几千条工单里挑出几个“代表工单”每条都是真实文案好用来说清楚这个群的问题长什么样。这时候 K-Means 的均值中心根本没法解释只能换成基于样本代表的聚类算法。基于样本代表这个诉求很快会把视线引向 AP 这类算法。AP 把每个数据点都当成潜在的类代表通过点与点之间的消息传递自动选出一小组真实存在的点作为 exemplar类代表其他点分配到离自己最合适的代表上。整个过程不需要预设 K这是它给我的第一印象解放了“K 怎么选”这个头疼问题。1.2 AP 更符合人判断聚类的直觉先立代表再分归属AP 的思路其实很像一个团队选组长一开始没人知道谁当组长每个人都观察别人“我觉得你合适当组长”这种评价会在成员之间不断传递同时每个成员也会评估“如果这个人当组长我愿不愿意归到他那一组”。消息传着传着部分人获得的支持度越来越高其他人逐渐形成归属最终自动形成了一个组织架构。这背后是消息传递message passing机制和 K-Means 那种“先定 K再找中心”的流程完全不同。K-Means 需要你先拍脑袋给 K然后反复计算均值AP 则是先建立一个相似度矩阵让每个样本都作为候选代表参与竞选再通过两套消息不断更新“适不适合当代表”的评价与“愿不愿意支持你”的态度最后收敛时支持度高的样本就成了类代表。所以如果你手头任务里类中心必须是原始样本或者你不想反复试 KAP 会是一个很自然的选择。它还有一个好处结果是确定性的只要相似度矩阵和参数固定多次运行不会出现 K-Means 那种因随机初始化带来的抖动。对需要复现结果的项目来说这是很大的优势。2. 亲和力传播算法的核心原理消息是如何“传”起来的2.1 相似度矩阵一切消息传递的地基AP 并不直接操作原始特征它操作的是相似度矩阵 S。S 是 N×N 的矩阵S(i,k) 表示第 i 个样本相对于第 k 个样本作为代表的“相似程度”。这个相似度怎么定义直接决定聚类效果。最常用的是负的欧氏距离平方$$S(i,k) -|x_i - x_k|^2$$距离越近相似度越大因为取了负号负值越小表示越不相似。对角线 S(k,k) 也很关键它叫 preference代表“第 k 个样本作为代表的自我认可度”也就是先验上我们觉得每个样本适不适合当类代表。AP 最终会选出哪些 exemplar和 diagonal 的值有直接关系。后面我会专门讲 preference 怎么设置。这里有个容易忽略的点AP 用的是相似度不是距离。很多刚接触的朋友直接把距离矩阵丢进去结果全是负的聚类结果看着也不对。常规做法是先算距离矩阵再取负号转成相似度。如果是文本数据也可以用余弦相似度但要注意 AP 默认偏向“相似度越高越好”如果用的是余弦需要根据场景决定是否缩放。2.2 Responsibility 与 Availability两种消息各司其职AP 的核心就是两类消息responsibility 和 availability。为了不让公式把人劝退我用大白话解释它们的直觉。responsibility记作 r(i,k)是从点 i 发给候选代表 k 的消息表达的是“我 i 认为你 k 适合当我的代表”。但它不是盲目夸人它会对比所有其他候选代表如果我选了别人会不会比你更好所以 r(i,k) 的计算会减去其他候选代表对 i 的“吸引力”最大值。换句话说r 衡量的是“相比其他选择你 k 在我心里有多突出”。availability记作 a(i,k)则反过来从候选代表 k 发给点 i 的消息表达“我 k 不仅想当代表而且有足够的群众基础支持我当你代表”。它会把其他点对 k 的正向 responsibility 累积起来反映这个候选代表得到的支持度。如果支持度不足availability 会变成负数相当于“我不太敢当你代表”。这里有个细节a(i,k) 不会超过 0因为它要表达的是“我愿意”而不是“我强推”但对角线上的 a(k,k) 只考虑支持度积累不需要受这个限制。两类消息交替更新responsibility 更新后再更新 availabilityavailability 反过来又影响下一轮的 responsibility。这种交互很像团队选组长时个人意愿和群众支持度互相影响最终收敛到一组稳定的代表。2.3 迭代更新和收敛像会议室里大家终于安静下来在迭代过程中每个点先给所有候选代表发 responsibility然后候选代表综合自己收到的支持度给相关点发 availability。这个循环会一直持续直到两类消息不再发生明显变化或者达到最大迭代次数。为了防止更新太猛导致来回震荡AP 引入了 damping 系数 λ取值一般在 0.5 到 1 之间。每次更新时新值不是直接用当前计算出的结果而是把上一轮的值和本轮计算值做一个加权平均$$r_{new} \lambda \cdot r_{old} (1-\lambda) \cdot r_{update}$$$$a_{new} \lambda \cdot a_{old} (1-\lambda) \cdot a_{update}$$λ 越大更新越保守收敛越慢但越稳定λ 太小消息更新剧烈可能出现不收敛、来回震荡的情况。实际经验是文本或高维特征下如果发现警告说迭代没收敛先把 λ 调到 0.9 试试。收敛后每个点 k 的对角线消息 r(k,k) a(k,k) 如果大于 0说明 k 对自己当代表的决心加上群众支持足够强k 就成了 exemplar。其余每个点 i 会找到使 a(i,k) r(i,k) 最大的 k归属到对应 exemplar 所代表的簇。整个过程像一场吵吵闹闹的会议最后大家安静下来举手表决完成组长也定出来了。3. AP 算法实操从相似度矩阵到聚类结果的完整流程3.1 构建相似度矩阵的几个标准做法实操第一步是把原始特征转成相似度矩阵。最稳妥、最常用的方式是用欧氏距离的负平方from sklearn.metrics import pairwise_distances # X 是 (n_samples, n_features) 的矩阵 sim_matrix -pairwise_distances(X, metricsqeuclidean)这里用 sqeuclidean 而不是欧氏距离是因为平方后能拉开远近点之间的差距让相似度梯度更明显。若数据是文本 TF-IDF 向量我更倾向于用余弦相似度但它不是 AP 默认的“越大越好直接可用”的类型需要做一次线性变换比如from sklearn.metrics.pairwise import cosine_similarity cos_sim cosine_similarity(X) # 余弦相似度范围通常是 [-1, 1]直接用于 AP 有时结果偏少 # 可以整体加 1 或缩放让负值的含义更稳定 sim_matrix cos_sim这里我踩过坑直接用原始余弦相似度矩阵跑 AP结果偏保守代表点总是那两三个。后来把相似度做了一次标准化让数值分布更均匀聚类结果才合理。相似度矩阵的数值范围对 preference 的影响非常大所以先看一眼矩阵分布再决定后续参数比盲目跑一遍有效得多。还有一点值得提醒AP 的相似度矩阵不要求对称但如果你的数据是标准特征矩阵、距离度量是对称的那矩阵就是对称的。个别场景里两个样本之间的相似度可能有方向性比如 A 认为 B 是代表但 B 对 A 的“支持”不一样这种情况 AP 也能接受只是解释起来更绕。常规项目我都按对称矩阵处理。3.2 preference 和 damping 是影响结果的关键参数preference 就是相似度矩阵对角线的值。默认情况下可以直接用相似度矩阵的中位数这会得到一个适中的聚类数。但实际项目里preference 是需要调的核心参数。记住一个很实用的规律把 preference 调高说明每个样本“自我当代表的门槛”变高能当代表的人变少聚类数偏少。把 preference 调低相当于降低当选门槛更多人愿意当代表聚类数会偏多。取中位数时通常得到五六成到七八成人眼认为合理的簇数。取最小值倾向于每个点都自成一派。取最大值倾向于所有点归到同一个簇。调参逻辑类似调节“代表评选的严格程度”而不是去调 K。我通常会在中位数附近扫几个值比如np.median(sim)、np.percentile(sim, 25)、np.percentile(sim, 75)快速看三个结果再用业务指标判断哪个更合理。damping 前面说过是防止震荡的。sklearn 里默认 0.5但对很多真实数据来说0.5 偏激进经常会出现 not convergence 的警告。我一般直接设到 0.9最多迭代 200 次。如果数据量上千收敛次数会明显增加可以再加convergence_iter让算法在连续多轮变化都足够小后再停止。3.3 用 scikit-learn 快速跑通一个 AP 聚类案例下面是一个可以直接跑的最小案例。假设我有一组二维点10 个样本想用 AP 看它能分成几个类import numpy as np from sklearn.cluster import AffinityPropagation from sklearn.metrics import pairwise_distances X np.array([ [1.0, 2.0], [1.1, 1.9], [0.9, 2.1], [5.0, 4.0], [5.1, 4.2], [4.8, 3.9], [8.0, 7.0], [8.2, 7.2], [7.8, 6.8], [12.0, 1.0] ]) sim_matrix -pairwise_distances(X, metricsqeuclidean) ap AffinityPropagation( affinityprecomputed, damping0.9, preferencenp.median(sim_matrix), max_iter200, convergence_iter15 ) labels ap.fit_predict(sim_matrix) exemplars ap.cluster_centers_indices_ print(聚类标签:, labels) print(代表点索引:, exemplars)输出会类似聚类标签: [0 0 0 1 1 1 2 2 2 3] 代表点索引: [1 4 7 9]这里四个簇分别对应三组紧密点和一个孤立点。你可以看到 AP 自动定出 4 个代表点第 10 个点单独成簇。很有意思的是孤立点也能被当成一个代表AP 对“离群点独立成簇”这件事比 K-Means 敏感得多。实际项目中sklearn 的AffinityPropagation的affinity参数如果是euclidean且不传预计算矩阵它内部会自动按负欧氏距离处理。我习惯显式传precomputed这样相似度的定义透明可控制。3.4 如何解读 AP 输出的代表点与聚类标签AP 输出的核心是cluster_centers_indices_它是一组真实样本的索引。这点和 K-Means 的cluster_centers_完全不同K-Means 给的是虚拟坐标AP 给的是数据里真实存在的样本。比如客服工单场景里你可以直接把选出来的工单原文当作该类别的“典型案例”非常便于向业务解释。另外要注意AP 的簇大小差异可能很大。有的簇只有一个样本点有的簇可能有上百个样本。这不一定是坏事。如果你希望簇大小相对均衡可能需要考虑后续合并或者在 preference 扫描时结合业务对簇规模的要求。我自己常用一个校验动作拿到 exemplar 后回看它对应的原始数据是否真具有代表性比如文本就看是不是一段通顺且有代表性的描述图像就看是不是清晰且有代表性的那张图。这一步往往比看评估指标更能发现问题。4. AP 算法常见问题与调试技巧实录4.1 迭代不收敛或者反复震荡先查 damping用 AP 跑真实数据最常看到的警告是Attempting to fit... did not converge。99% 的情况下问题出在 damping 太小消息更新太激进。此时把 damping 调大比如从 0.5 调到 0.9一般就稳定了。还有个细节是max_iter和convergence_iter。增大max_iter只是给算法更多机会但如果 damping 太小给再多轮也没用。正确的顺序是先稳定 damping再调迭代次数。我一般固定 damping0.9max_iter300convergence_iter15。如果数据量特别大比如 2000 个样本有时需要把 max_iter 加到 500同时留意每轮更新是否有明显变化。也可以从责任值的变化幅度判断如果多次迭代后r仍然在正负之间大幅跳动说明更新步长太大必须把 damping 提高到 0.95 左右。反之如果收敛太慢可以适度降低到 0.8观察几次再定。4.2 类簇数目不合理调 preference 比调数据更有效很多人拿到 AP 结果后第一反应是换数据、换特征其实多数情况调 preference 就够了。如果你觉得类簇太多就把 preference 调高比如从np.median(sim)换到np.percentile(sim, 75)或最大值觉得类簇太少就调低 preference。但这里容易走极端preference 调到很高后所有点会归到一个簇调到很低后每个点自成一类。正确做法是沿着中位数为起点做二分搜索先看极端值再逐步逼近想要的簇数。我习惯写一个循环对不同 preference 打印簇数和每个簇的大小快速做一次扫描for p in [np.min(sim), np.percentile(sim, 10), np.median(sim), np.percentile(sim, 90), np.max(sim)]: ap AffinityPropagation(affinityprecomputed, preferencep, damping0.9, random_state0) labels ap.fit_predict(sim) print(fpreference{p:.4f}, 簇数{len(np.unique(labels))})如果惊讶地发现 preference 已经极大或极小了簇数依然不理想就要回头检查相似度矩阵的数值分布。比如文本余弦相似度矩阵分布非常集中大部分值都在 0.3 到 0.7 之间这时中位数和最大值都扎堆preference 对簇数的影响会被压缩。解决方案是做个标准化把相似度范围拉开。4.3 数据量大时内存爆掉我常用的几种降级方案AP 需要计算完整的 N×N 相似度矩阵然后在这个矩阵上做多次矩阵运算所以内存复杂度是 O(N²)。几千个样本还能忍上万就非常吃力。这一点是 AP 最常见的性能瓶颈。面对大样本我常用的降级方案有三种。第一种是降维。先把原始特征用 PCA、Umap 或深度模型 embedding 降到一个较低维度再在这个维度上构建相似度矩阵。维度变低后相似度矩阵的大小不变但计算距离的成本下降聚类趋势往往更清晰。第二种是采样。从全量数据里随机抽样几千个点跑 AP得到 exemplar 后再用最近邻规则把未参与聚类的样本分配到这些 exemplar 上。这种做法速度快但可能丢失少量稀疏簇。如果数据分布比较均匀效果还是不错的。第三种是换近似算法。比如 FastAPFast Affinity Propagation或基于分块计算的近似版本它们对大规模数据的支持比标准 AP 好不少。也可以退一步用 K-Means 先粗分再用 AP 在每簇内部找代表点既保住尺度又得到真实样本代表。4.4 AP 和 K-Means、DBSCAN、谱聚类怎么选型选型这件事没有万能答案但我可以提供一套自己的判断标准。如果你追求速度和简单且数据是低维凸簇K-Means 完全够了。如果你需要类中心是真实样本或者不想预设 KAP 更合适。如果你的数据存在明显不规则形状比如环形、月牙形DBSCAN 这类密度聚类会更好但 DBSCAN 的 eps 和 min_samples 也不见得比 K 好调。谱聚类对复杂结构有优势但同样要指定 K而且要构建相似度图参数更多调起来并不轻松。从可解释性来说AP 在“每个簇的代表是真实样本”这个特性上非常突出。很多时候业务方面对面问“这个类到底是什么意思”你直接把 exemplar 拿出来比给一个均值坐标直观得多。缺点是计算复杂度高、跨尺度数据敏感所以实际项目里我会把 AP 当作“代表样本发现工具”而不是唯一聚类方法常常先用 AP 得到 exemplar再基于这些 exemplar 做后续分类或分析。下面用一张表快速对照算法是否需要预设 K聚类中心是否真实样本主要优点主要不足K-Means需要否均值点快、简单、易扩展对初始化和K敏感中心不可解释AP不需要是exemplar自动定K、代表可解释相似度矩阵O(N²)内存高DBSCAN不需要否核心点概念能处理任意形状密度参数难调密度不均容易失效谱聚类需要否能处理复杂流形计算复杂需要构图和调K5. 我踩过的一些坑与后续的扩展思路5.1 调试 AP 时我最先观察的三个信号第一次认真用 AP 是在一万多条短文本上做聚类。当时我直接拿 TF-IDF 余弦相似度矩阵跑结果差点被一团乱麻的簇数劝退。后来慢慢养成习惯跑之前先看三个信号。第一个是相似度矩阵的分布。用np.percentile(sim, [0, 25, 50, 75, 100])看一下如果数值集中在一个很窄的区间preference 的调节空间就很小很可能需要先做归一化或改用其他相似度。第二个是 exemplar 的索引分布。如果代表点全部扎堆在某个区域说明 preference 或相似度构造有问题聚类严重不均衡。正常情况下代表点应该分散在数据的各个结构区域。第三个是每个簇的大小。AP 允许产生极小的簇但如果你发现有一堆“单人簇”先别急着调 preference检查一下这些点是否真的是孤立点。如果只是特征噪声造成的孤立可以考虑先做一次聚类前去重或平滑再跑 AP。这三个信号比直接看轮廓系数更有指导意义。轮廓系数在 AP 里容易失真毕竟 AP 的目标不是最大化簇间距离而是找出真实代表。5.2 从 AP 出发FastAP、层次聚类思维与增量处理AP 的扩展方向有很多。最实用的是 FastAP它通过把消息更新过程限制在 k 近邻范围内把复杂度从 O(N²) 大幅降下来。我试过在 2 万样本上跑 FastAP速度明显比标准 AP 快但代表选出的结果和标准 AP 略有差异适合对速度敏感的场景。另外可以把 AP 当成一个“代表点提取器”嵌到更大流程里。比如先用层次聚类做粗分再用 AP 在每个粗聚类里选 exemplar或者反过来先用 AP 得到 exemplar然后以 exemplar 为初始中心再跑一次 K-Means 做细分配。这种组合用法比单独用某一个算法更灵活。最后补充一个我自己的经验AP 不是万能药但它最大的价值是帮你“不用拍脑袋定 K”。即使最终不用 AP 的结果它给出一组代表点和簇数也能作为其他聚类算法的参数参考。我现在处理小规模聚类任务时通常会先用 AP 快速扫一遍看到 exemplar 后再决定下一步。你如果在聚类数上调试到怀疑人生不妨给 AP 两分钟把 preference 和 damping 调好答案大概率比你想得清晰。