简介MedoidShift 与 QuickShift 是两种典型的聚类算法前者基于代表点medoid迭代更新后者利用密度敏感搜索快速分组与 K-Means 等质心类方法相比各有侧重。资源附带了完整 Python 实现和演示脚本配以对比图与说明文档适合机器学习初学者以及需要在实际项目中选用聚类算法的数据分析人员。压缩包共 5 个文件包含 3 个 Python 脚本算法核心与 demo、1 份 Markdown 说明和 1 张聚类效果对比图整体仅 429KB结构精简可直接查看运行。演示脚本覆盖数据加载、预处理、聚类调用与结果可视化等完整流程。已有 319 人学习使用。通过阅读代码与运行演示可以理解 medoid 选取、密度敏感搜索等关键机制并结合对比图比较两者对不同簇形状和异常值的处理效果从而在实际数据挖掘任务中做出更合适的算法选择。1. 聚类翻车之后MedoidShift 和 QuickShift 是怎么跑起来的做无监督聚类时我一开始只会 K-Means直到在一个人脸特征数据集上翻车——簇形状不均匀K-Means 把中间那一撮直接劈成两半。换到这套 MedoidShift-and-QuickShift 的代码包后同一份数据结果肉眼可见地合理了。这个项目是两套聚类算法的 Python 实现加一个演示脚本解压就能跑。MedoidShift 用样本点本身当簇代表不依赖均值对离群点不敏感QuickShift 走密度树路线适合高维和大量样本。适合谁想对比聚类算法、给项目选型踩点、或者找可改代码的人。下文我会把两个算法的核心逻辑、关键代码、怎么跑通 demo、以及踩过的参数坑一次讲清。2. MedoidShift 算法拆解为什么「用真实样本当代表」比质心更稳2.1 从 K-Means 到 MedoidShiftmedoid 到底解决什么问题K-Means 每一轮迭代都会计算质心质心是簇内所有样本的均值问题在于这个均值点可能根本不在数据集里而且离群点只要被划进某个簇质心就会被明显带偏。MedoidShift 的思路则是簇的代表必须是从数据集里挑出来的一个真实样本这个代表点称为 medoid。它不像 K-Means 那样用公式去合成一个新坐标而是从候选样本里选「离大家总距离最近」的那一个所以聚类结果天然可解释——你可以直接把 medoid 对应的样本拿去访谈、做画像、跑审批流程。实现上MedoidShift 每一轮做两件事先把所有点分配给离它最近的 medoid再在每个簇内部票选新的 medoid。重复这两步直到 medoid 的位置不再明显变化。你会发现这个流程和 K-Means 长得几乎一样唯一的差别就是「更新中心」这一步K-Means 取平均MedoidShift 取簇内总距离最小的样本。这里有个容易被忽略的细节MedoidShift 对距离度量不敏感不一定要用欧氏距离。曼哈顿距离、余弦距离都能用甚至可以直接传一个两两距离矩阵进来。这点在实际业务里很值钱因为很多项目里特征是用户 id、分类属性和缺失值算不出干净的坐标向量。MedoidShift 还有个近亲叫 K-Medoids也叫 PAM很多教科书里把它写成 K-Means 的鲁棒替代品。MedoidShift 可以理解成 PAM 的迭代式实现每次只把 medoid 移动到簇内最优位置不做全局置换搜索。这样收敛更快但也更容易掉进局部最优。所以初始化很重要随机种子不同结果可能差很远这一点后面避坑章节会展开。2.2 medoid_shift_.py 核心代码逐段看这套包里 medoid_shift_.py 的核心逻辑我拆出来大概是下面这个样子。注意这是保留了算法骨架的简写版本实际包里还有边界处理和可视化辅助函数但迭代主体的逻辑是一样的。import numpy as np def assign_to_nearest(data, medoids): # data: (N, d)medoids: (k, d) # 返回长度为 N 的数组每个位置是最近 medoid 的下标 dist_matrix np.linalg.norm(data[:, None, :] - medoids[None, :, :], axis2) return np.argmin(dist_matrix, axis1) def medoid_shift(data, k3, max_iter100, tol1e-4, random_state0): rng np.random.default_rng(random_state) # 初始化从数据里随机抽 k 个不同样本作初始 medoid init_idx rng.choice(len(data), sizek, replaceFalse) medoids data[init_idx].copy() for it in range(max_iter): labels assign_to_nearest(data, medoids) new_medoids [] for cluster_id in range(k): cluster_points data[labels cluster_id] if len(cluster_points) 0: # 空簇保留旧 medoid确保簇数不缩水 new_medoids.append(medoids[cluster_id]) continue # 计算簇内两两距离行和最小的样本就是新 medoid intra_dist np.linalg.norm( cluster_points[:, None, :] - cluster_points[None, :, :], axis2 ) cost intra_dist.sum(axis1) new_medoids.append(cluster_points[np.argmin(cost)]) new_medoids np.array(new_medoids) shift np.linalg.norm(new_medoids - medoids) medoids new_medoids if shift tol: print(fiter {it}: converged, shift{shift:.6f}) break return medoids, labelsassign_to_nearest 里用了广播运算一步得到 N 行 k 列的距离矩阵每行取 argmin 就完成了分配。注意这一步的空间复杂度是 O(Nk)N 到十万、k 到几百时内存会吃紧后面二次开发我会提到用 cKDTree 或分批计算来替代。更新 medoid 的代码是重点先对当前簇内的点构造两两距离矩阵然后intra_dist.sum(axis1)得到每个点与簇内其它点的距离总和argmin选到的就是簇内总距离最小的真实样本。这就是「medoid 是数据集里的点」这个特性的来源。参数说明k 是目标簇数max_iter 是最大迭代次数防止不收敛时死循环tol 是收敛阈值shift 小于 tol 就提前停止random_state 控制初始采样的随机种子。代码里保留空簇的逻辑值得学习如果你把空簇直接删掉下一次循环 labels 的取值范围会缩小而 medoids 数组长度也变了很容易导致索引错位。很多改 K-Means 代码踩过的坑在这里同样会出现。2.3 收敛性和计算量MedoidShift 为什么慢但稳MedoidShift 的收敛性质其实很好证明每一轮把 medoid 移到簇内距离成本最小的点所以目标函数所有点到所属 medoid 的距离总和不会上升。又因为候选 medoid 只能是有限个样本点算法最终必然停在某个局部最优。这个局部最优不一定全局最优因此它对初始化敏感和 K-Means 一样。计算量上朴素的实现就很吃亏了。每次迭代的分配阶段要算 N×k 的距离矩阵更新阶段还要对每个簇算一次两两距离最坏情况下是 O(N²) 的复杂度因为一个簇大到接近 N 时两两矩阵就是 N²。一万个样本、k3 的时候每轮更新都要算三四个百万级距离矩阵纯 Python 加 NumPy 还能扛到五万样本就开始变得卡顿。我的经验是N 在两万以内随便跑再往上就要考虑降采样、先 K-Means 预聚类、或者直接用 QuickShift。但慢有慢的价值。K-Means 更新质心只需要求均值一次遍历就是 O(Nd)可均值点很容易被离群点拉走。MedoidShift 因为候选点必须是真实样本离群点要被选为 medoid必须得让簇内其它所有点到它的距离总和都足够小这个条件很难满足所以它对离群点的鲁棒性天然就好。如果你的下游任务里「代表样本」会被拿去人工审核那这种鲁棒性和可解释性就非常值得付出计算代价。2.4 非欧氏距离场景直接吃距离矩阵前面提到 MedoidShift 可以用任意距离。这里给出一个更通用的版本它不接收坐标 X而是接收一个预先算好的 N×N 距离矩阵 D。这对文本、类别特征、带缺失值的数据特别有用你不需要想办法把对象编码成向量。def medoid_shift_from_dist(D, k3, max_iter100, tol1e-4, random_state0): rng np.random.default_rng(random_state) N D.shape[0] medoid_idx rng.choice(N, sizek, replaceFalse) for _ in range(max_iter): # D[:, medoid_idx] 是 N*k 矩阵每行找距离最近的 medoid labels np.argmin(D[:, medoid_idx], axis1) new_idx [] for c in range(k): cluster_ids np.where(labels c)[0] if len(cluster_ids) 0: new_idx.append(medoid_idx[c]) continue # 子距离矩阵每行求和和最小的是簇内中心对象 sub D[np.ix_(cluster_ids, cluster_ids)] cost sub.sum(axis1) new_idx.append(cluster_ids[np.argmin(cost)]) new_idx np.array(new_idx) if np.array_equal(new_idx, medoid_idx): break medoid_idx new_idx return medoid_idx这里唯一的技巧是np.ix_用来按行和列同时索引子矩阵避免频繁拷贝数据。sub.sum(axis1)算的是每个簇内样本到其它簇内样本的距离和argmin选出最小距离和的原始样本索引。参数和上一个版本完全一致只是输入从坐标换成了矩阵。注意这个版本不会保存坐标 medoid只返回距离矩阵的行索引使用时把它映射回原数据 id 就行。这种写法的好处是你可以把任意业务上的两两距离丢进来比如用户之间的编辑距离、商品之间的语义相似度。代价是 D 本身是 N×N 的N 超过几万就很难存下所以这种版本更适合中小规模数据或者先按业务划分子集再分别跑。3. QuickShift 算法拆解密度树怎么把复杂度降下来3.1 从 MeanShift 到 QuickShift把爬山改为指针跳转QuickShift 属于密度聚类它的理论基础是核密度估计把每个样本周围一定半径内的其它样本用高斯核累加密度高的地方就是簇中心。MeanShift 的做法是把每个点沿密度梯度方向爬山直到峰顶QuickShift 则更直接——它不迭代而是给每个点找一个「密度比自己高、距离又近」的父节点然后沿着父节点一路向上直到某个密度局部极大值点这个极大值点就是簇中心。父节点的选择标准不是单纯的「最近节点」而是「距离除以密度」最小的节点。这个比例设计得很妙一个点如果离密度峰很近那么距离和密度都占优ratio 自然会小如果两个候选点距离相近密度高的一方 ratio 更小更容易被选为父节点。这样构造出的父节点链天然是从密度低的地方指向密度高的地方链的终点就是峰。因为每个点只指向数量有限、密度更高的邻居所以 QuickShift 是一棵树而不是一张图不会出现环。一个很吸引人的特性是QuickShift 不需要预先指定簇数 K。簇的数量由带宽 bandwidth 决定。带宽大密度估计平滑峰合并簇少带宽小密度峰被分开簇多。这个参数是 QuickShift 里最需要花时间调的东西。很多文章把它包装成「无参数聚类」实际并不是只是把 K 换成了 bandwidth调节难度一点没降低。3.2 quick_shift_.py 关键代码解读下面是我读 quick_shift_.py 时还原出的核心流程。为了说清楚建树过程我把密度估计、父节点构建、标签传播三部分单独拆开。import numpy as np from scipy.spatial import cKDTree from sklearn.neighbors import KernelDensity def _estimate_local_density(X, bandwidth): # 高斯核密度估计返回每个样本点的对数密度 kde KernelDensity(kernelgaussian, bandwidthbandwidth).fit(X) return kde.score_samples(X) def build_parent_links(X, bandwidth, leaf_size40): tree cKDTree(X, leafsizeleaf_size) log_density _estimate_local_density(X, bandwidth) # 从密度高到低遍历保证建链方向一致 order np.argsort(-log_density) parent np.full(len(X), -1, dtypeint) for idx in order: neighbors tree.query_ball_point(X[idx], rbandwidth) if len(neighbors) 1: parent[idx] idx continue # 只看密度比当前点更高的邻居 higher [n for n in neighbors if log_density[n] log_density[idx]] if not higher: parent[idx] idx continue candidates np.array(higher, dtypeint) dists np.linalg.norm(X[candidates] - X[idx], axis1) # 距离除以密度分子越小越好分母越大越好 ratio dists / np.exp(log_density[candidates]) parent[idx] candidates[np.argmin(ratio)] return parent, log_density def quick_shift_labels(X, bandwidthNone): if bandwidth is None: # 常见做法抽样算中位数距离乘一个系数 sample X[:min(500, len(X))] median_dist np.median(np.linalg.norm(sample[:, None, :] - sample[None, :, :], axis2)) bandwidth float(median_dist * 0.5) parent, _ build_parent_links(X, bandwidth) labels np.empty(len(X), dtypeint) for i in range(len(X)): node i while parent[node] ! node: node parent[node] labels[i] node return labels先看密度估计。KernelDensity.score_samples返回的是对数密度取np.exp后用于 ratio 计算。直接把对数密度传入也行但 ratio 里np.exp和log_density的数值关系要看清楚ratio dist / exp(log_density)。如果你改成用对数密度计算应该写成 dist (-log_density)不要混。build_parent_links里最值得学习的是「按密度从高到低遍历」这个顺序。因为每个点只关心密度比它高的点按密度降序处理那么遍历到当前点时所有潜在父节点都已经处理过至少 parent 数组里它们是有效值但注意这里并不依赖父节点的父节点只需要候选节点存在。query_ball_point只找半径 bandwidth 内的邻居避免了全量两两比较。标签传播部分对每个点沿 parent 链向上走到根。因为链可能很长在一万个点时会稍慢常见优化是记忆化把已经算过的根存进字典后续节点直接复用。我提供的这段为了可读性没加缓存实际项目里建议加。3.3 复杂度分析和场景选择什么时候该翻 QuickShift 的牌子建树阶段的复杂度来自两部分cKDTree 构建约 O(N log N)每个点查邻居平均在局部范围内整体接近 O(N log N)。标签传播如果朴素写最坏可能 O(N²)比如一条长链所有点串在一起但密度聚类里链通常很短。所以整体性能远好于朴素 MedoidShift。对比一下两个算法维度MedoidShiftQuickShift是否要预设簇数要 K不要用 bandwidth 控制簇代表真实样本点密度峰中心非样本点代表性样本可直接拿 medoid 用需要额外找峰附近样本复杂度最坏 O(N²)约 O(N log N)对距离类型任意距离矩阵通常需要欧氏距离高维表现中等维度高时 k-d 树退化从实践角度我一般这样选明确要拿代表样本做后续访谈的无脑 MedoidShiftN 超过两万、坐标能转成欧氏空间、又不想调 K 的QuickShift 更合适如果数据是带缺失值的表格MedoidShift 的矩阵版本更稳。QuickShift 在高维下性能会掉是因为 cKDTree 在高维空间中搜索性能骤降且密度估计对维度灾难很敏感这时最好先降维到 10 维以内再用。3.4 bandwidth 估算省心套路和翻车现场QuickShift 的带宽可以用 sklearn 的estimate_bandwidth函数自动估算这个函数内部从数据集里抽样一部分计算样本间的最近邻距离中位数。from sklearn.cluster import estimate_bandwidth bw estimate_bandwidth(X, quantile0.3, n_samples500) labels quick_shift_labels(X, bandwidthbw)quantile 是控制估算线性尺度0.3 意味着取最近邻距离的第 30 百分位通常经验值在 0.20.5 之间。n_samples 控制抽样的样本数抽样太少估计会抖动太多计算变慢。注意这个函数返回的是一个全局带宽如果数据里不同簇的密度差异很大全局带宽会顾此失彼稀疏区域的簇被拆碎稠密区域的簇被合并。遇到这种情况我的做法是先对全部数据跑一次粗聚类然后在每个粗簇内分别估算带宽再对每个簇单独跑 QuickShift。这听着麻烦但比调一个全局带宽调试半天要省心。最终输出标签的数量可以直观反映带宽是否合适如果标签数接近样本数明显带宽太小如果标签只有 1 个带宽太大。这个白盒诊断在调试时很有用。4. 实操从解压到读懂 clusters_comparison.png4.1 环境准备别漏了 scipy 和 scikit-learn这个项目的核心代码只依赖 numpy但 demo 脚本里大概率会用到 scikit-learn 的数据生成器和 scipy 的距离计算。我建议一次性装齐省得跑两步发现缺一个。python -m venv cluster_env source cluster_env/bin/activate pip install numpy scipy scikit-learn matplotlib装完之后直接在解压目录下执行python demo_medoid_quick.py。如果一切正常屏幕上会弹出一张对比图或者自动保存为 clusters_comparison.png。README.md 里一般会写清楚运行命令和依赖版本跑之前最好扫一眼。我第一次没看直接跑结果图形界面弹不出来后来发现 demo 里把 matplotlib 后端设成了 Agg只保存不展示并不是程序坏了。4.2 demo_medoid_quick.py 的调用链长什么样这个 demo 脚本的结构拆开看基本是五段生成数据、调用 MedoidShift、调用 QuickShift、画图对比、打印指标。它是在同一个数据集上做对比实验所以会用固定的随机种子生成数据保证两个算法面对的是同一份输入。我简化后的调用逻辑大概是from medoid_shift_ import medoid_shift from quick_shift_ import quick_shift_labels from sklearn.datasets import make_moons, make_blobs from sklearn.metrics import silhouette_score # 1. 生成测试数据 X, _ make_moons(n_samples300, noise0.1, random_state42) # 2. MedoidShift指定簇数 medoids, labels_m medoid_shift(X, k2, random_state0) score_m silhouette_score(X, labels_m) # 3. QuickShift指定带宽 labels_q quick_shift_labels(X, bandwidth0.3) score_q silhouette_score(X, labels_q) # 4. 画图并保存 fig, axes plt.subplots(1, 2, figsize(10, 4)) ... plt.savefig(clusters_comparison.png)注意 MedoidShift 的入口函数返回 medoids 和 labelsQuickShift 的实现可能只返回标签也可能返回中心点这取决于原包作者。如果你发现 quick_shift_labels 只给标签而你想画中心点可以自己算取每个簇内密度最高的样本作为中心即可。demo 脚本里一般会处理这个差别所以你读它比直接读算法实现更容易理解两个算法的接口差异。另外我建议从入口开始看如果脚本里包裹着if __name__ __main__:说明它既可被 import 又可独立运行。如果你的业务代码要复用 demo 里的画图函数最好把生成数据、聚类、绘制三步拆成独立函数。4.3 从 clusters_comparison.png 反推参数调节方向这张图通常左边是 MedoidShift 的结果右边是 QuickShift 的结果。看的时候我一般先看三处有没有明显把一个簇拆成几瓣有没有离群点被单独拎出来两边的子图在簇边界处是否一致。如果 QuickShift 结果碎成很多小簇是带宽太小密度峰被过度识别。无需去翻源码直接用指数步长加大带宽比如 0.2 提到 0.4、0.8看趋势。如果 MedoidShift 的 medoid 点画出来很靠近簇的边缘通常不是代码 bug而是 k 选大了本来两簇数据被分成了四簇每个小簇的 medoid 自然都偏。这时候先调 k用轮廓系数或肘部法确定合理区间。对比图还有一种常见用法是看实际边界权MedoidShift 按距离分配QuickShift 按密度分配两者在密度较低的狭长区域会出不同结果。如果业务关心的是「密度低的夹缝地带归哪边」看图比看任何指标都直观。4.4 改成你自己的对比实验多数据集加指标汇总demo 只跑一个数据集太浪费了。我建议改成循环把生成数据、聚类、打分串起来一次性对比多个数据集结果汇总成表格避免反复改参数重跑。from sklearn.datasets import make_circles, make_moons, make_blobs import pandas as pd datasets [ (blobs, make_blobs(n_samples500, centers4, random_state0)), (moons, make_moons(n_samples300, noise0.08, random_state0)), (circles, make_circles(n_samples400, factor0.5, noise0.05, random_state0)), ] rows [] for name, (X, _) in datasets: labels_m medoid_shift(X, k4 if name blobs else 2, random_state0)[1] labels_q quick_shift_labels(X, bandwidth0.2) rows.append({ dataset: name, medoid_sil: silhouette_score(X, labels_m), quick_sil: silhouette_score(X, labels_q), quick_clusters: len(set(labels_q)), }) df pd.DataFrame(rows) print(df)这里的重点是控制变量所有数据集都固定随机种子bandwidth 可以按照每个数据集大致取一个值也可以记录到表格里方便回溯。quick_clusters列能立刻发现带宽设得合不合理。跑完之后再看 clusters_comparison.png 那张图的语义你会发现很多问题其实是参数选择不合适不是算法本身有这个毛病。为了不把文件搞乱我会给每个数据集单独保存一张图fig, axes plt.subplots(1, 2, figsize(10, 4)) ... fig.savefig(f{name}_comparison.png) plt.close(fig)plt.close 很重要不然循环里图会越叠越多内存疯涨。这个我在一次完整批量实验里翻过车最后连运行环境也跟着卡死。记住循环画图的规范是「用完即关」。5. 避坑与常见问题五个让新手血压升高的现场5.1 结果每次跑都不一样现象同一个 demo 脚本连续运行两次两次的聚类标签变化很大甚至簇数量都不一致。原因MedoidShift 初始 medoid 是随机采样QuickShift 本身是确定性的但如果 demo 生成数据时没固定随机种子数据本身每次都会变。两个随机源叠加结果自然不稳定。解决先给数据生成固定随机种子比如 make_blobs(random_state0)再给 medoid_shift 传 fixed random_state。QuickShift 只要数据固定就确定但如果你改写了标签传播顺序也记得把遍历顺序绑定到 np.argsort不要用 set 去重set 的顺序不稳定。判断是否稳定跑两遍后对比 labels 的一致性不一致就排查随机源。5.2 QuickShift 内存直接爆炸现象样本数从一万加到五万QuickShift 跑了一会儿之后内存飙升电脑卡死甚至 OOM。原因如果实现里用了全量距离矩阵np.linalg.norm(X[:, None, :] - X[None, :, :])五万样本就是 25 亿个浮点数绝无可能装下。QuickShift 的 cKDTree 就是为了避免这个但如果你在 query_ball_point 之后拿着 neighbours 列表又去构造完整距离矩阵同样会把内存打爆。解决确认父节点构建时用的是tree.query_ball_point(X[idx], rbandwidth)而不是一次性对所有点查邻居后再全量拼接。同时 leaf_size 调到 2040能减少叶子节点内的线性扫描。如果维度大于 20先降维如果用 scipy 的 cKDTree 也没救可以考虑用更贴近工程的距离搜索库替代但引入额外依赖要评估收益。调试时打开另一个终端用top -p PID看进程内存如果 RSS 涨到几个 G 再爆基本可以把嫌疑锁定在某一步触碰了全量矩阵。5.3 MedoidShift 跑成死循环现象脚本卡在迭代里不收敛打印出的 shift 数值一直在某个小值附近震荡或者完全不动。原因最常见是 tol 设得太小比如 1e-8超出浮点精度后 medoid 在两个候选点之间反复横跳其次是空簇处理成删除逻辑导致 medoid 数量不稳定labels 数组长度对不上程序在循环里进退两难。解决tol 设置到 1e-4 或 1e-5并在循环里保留 max_iter 兜底。空簇保留旧 medoid 的写法是标准做法不要删。如果你自己实现了「如果空簇就全局重跑」的逻辑一定要小心标签索引重跑后 medoid 的初始索引要重新对齐不然越跑越乱。如果怀疑死循环在 medoid_shift 内加一行打印每轮的 shift低于 1e-6 后还反复横跳就是 tol 太小的铁证。5.4 保存的图片全黑或空白现象在 Windows 上跑 demo生成的 clusters_comparison.png 全黑或者画布上什么都没有。原因常见的两个原因一是脚本先调了 plt.show() 再调 plt.savefig()show 之后画布内容被清空二是 matplotlib 后端在无 head 环境下不兼容比如在服务器上跑还开着默认的 Qt 后端。解决把 savefig 放在 show 的前面或者干脆注释 show只保留 savefig。无 head 运行就强制用 Aggimport matplotlib; matplotlib.use(Agg)。查看当前后端用python -c import matplotlib; print(matplotlib.get_backend())。这是在 Linux 服务器上跑聚类可视化的经典玄学多留意一次就能省十分钟。5.5 轮廓系数报错样本数小于等于簇数现象计算 silhouette_score 时抛出 ValueError提示 labels 数量不对或者某个簇只有 1 个样本。原因QuickShift 的带宽太小会把每个离群点都单独成一个簇少数簇变成单样本MedoidShift 的 k 设得比样本数还大也会触发。轮廓系数的定义要求每个簇至少有 2 个样本单样本簇会直接让整个评估失效。解决算指标前先用np.unique(labels)检查簇数过滤掉单样本簇后再计算如果簇数太多加大 bandwidth 或减小 k。这条经验通用任何聚类评估都应该先看标签分布再决定能不能跑轮廓系数。当簇数很少或单例很多时改用 calinski_harabasz_score它不需要两两样本距离对单例簇更宽容或者直接用簇内距离和 medoid 距离做业务侧评估不依赖 sklearn。不要迷信一个数字看一眼分布比什么指纹都准。6. 二次开发把两个算法集成到自己的聚类流程里如果想拿这套代码做实打实的项目第一件事别急着改算法内部先封装。我一般会在项目里新建一个 cluster_model.py把两个算法都包一层相同的接口上层调用只依赖 fit_predict()方便后续换算法不影响业务代码。class MedoidClusterer: def __init__(self, k3, max_iter100, tol1e-4, random_state0): self.k k self.max_iter max_iter self.tol tol self.random_state random_state def fit_predict(self, X): medoids, labels medoid_shift(X, kself.k, max_iterself.max_iter, tolself.tol, random_stateself.random_state) self.medoids_ medoids return labels class QuickClusterer: def __init__(self, bandwidthNone, leaf_size40): self.bandwidth bandwidth self.leaf_size leaf_size def fit_predict(self, X): labels quick_shift_labels(X, bandwidthself.bandwidth) return labels接下来做两个必做的验证第一用 sklearn 的calinski_harabasz_score和davies_bouldin_score在多个模拟数据集上过一遍把两个算法的分数存下来而不是只凭一张 png 下结论第二检查 medoid 的稳定性。对同一个数据集跑十次 MedoidShift把十次出来的 medoid 坐标求两两距离如果最大距离小于数据总体方差的 5%说明结果稳定否则说明这个数据不适合随机初始化。数据量上来以后朴素的 MedoidShift 会追不上了。我的血泪经验是先用 K-Means 粗聚类得到初始 medoid再把这个初始 medoid 传给 MedoidShift 微调。这样既保留了 medoid 的鲁棒性又减少了迭代轮数。对于 QuickShift带宽自动估算可以用sklearn.cluster.estimate_bandwidth返回值乘一个系数我常用的系数是 1.01.5具体要看数据分布这是最需要手工干预的参数多跑几遍对比图再定。从那以后我每次跑聚类之前都强制先问自己三件事要不要真实样本作为簇代表要不要预设簇数数据量是不是过万。把这三点想清楚再去选 MedoidShift 还是 QuickShift几乎不会再出现选错算法的场面。希望这次拆解能帮你在自己的数据上少绕几个弯。本文还有配套的精品资源点击获取 
长河君 · 2026/10/18 16:37:02 · 阅读 1.2k MedoidShift与QuickShift聚类算法解析及Python实现对比
简介MedoidShift 与 QuickShift 是两种典型的聚类算法前者基于代表点medoid迭代更新后者利用密度敏感搜索快速分组与 K-Means 等质心类方法相比各有侧重。资源附带了完整 Python 实现和演示脚本配以对比图与说明文档适合机器学习初学者以及需要在实际项目中选用聚类算法的数据分析人员。压缩包共 5 个文件包含 3 个 Python 脚本算法核心与 demo、1 份 Markdown 说明和 1 张聚类效果对比图整体仅 429KB结构精简可直接查看运行。演示脚本覆盖数据加载、预处理、聚类调用与结果可视化等完整流程。已有 319 人学习使用。通过阅读代码与运行演示可以理解 medoid 选取、密度敏感搜索等关键机制并结合对比图比较两者对不同簇形状和异常值的处理效果从而在实际数据挖掘任务中做出更合适的算法选择。1. 聚类翻车之后MedoidShift 和 QuickShift 是怎么跑起来的做无监督聚类时我一开始只会 K-Means直到在一个人脸特征数据集上翻车——簇形状不均匀K-Means 把中间那一撮直接劈成两半。换到这套 MedoidShift-and-QuickShift 的代码包后同一份数据结果肉眼可见地合理了。这个项目是两套聚类算法的 Python 实现加一个演示脚本解压就能跑。MedoidShift 用样本点本身当簇代表不依赖均值对离群点不敏感QuickShift 走密度树路线适合高维和大量样本。适合谁想对比聚类算法、给项目选型踩点、或者找可改代码的人。下文我会把两个算法的核心逻辑、关键代码、怎么跑通 demo、以及踩过的参数坑一次讲清。2. MedoidShift 算法拆解为什么「用真实样本当代表」比质心更稳2.1 从 K-Means 到 MedoidShiftmedoid 到底解决什么问题K-Means 每一轮迭代都会计算质心质心是簇内所有样本的均值问题在于这个均值点可能根本不在数据集里而且离群点只要被划进某个簇质心就会被明显带偏。MedoidShift 的思路则是簇的代表必须是从数据集里挑出来的一个真实样本这个代表点称为 medoid。它不像 K-Means 那样用公式去合成一个新坐标而是从候选样本里选「离大家总距离最近」的那一个所以聚类结果天然可解释——你可以直接把 medoid 对应的样本拿去访谈、做画像、跑审批流程。实现上MedoidShift 每一轮做两件事先把所有点分配给离它最近的 medoid再在每个簇内部票选新的 medoid。重复这两步直到 medoid 的位置不再明显变化。你会发现这个流程和 K-Means 长得几乎一样唯一的差别就是「更新中心」这一步K-Means 取平均MedoidShift 取簇内总距离最小的样本。这里有个容易被忽略的细节MedoidShift 对距离度量不敏感不一定要用欧氏距离。曼哈顿距离、余弦距离都能用甚至可以直接传一个两两距离矩阵进来。这点在实际业务里很值钱因为很多项目里特征是用户 id、分类属性和缺失值算不出干净的坐标向量。MedoidShift 还有个近亲叫 K-Medoids也叫 PAM很多教科书里把它写成 K-Means 的鲁棒替代品。MedoidShift 可以理解成 PAM 的迭代式实现每次只把 medoid 移动到簇内最优位置不做全局置换搜索。这样收敛更快但也更容易掉进局部最优。所以初始化很重要随机种子不同结果可能差很远这一点后面避坑章节会展开。2.2 medoid_shift_.py 核心代码逐段看这套包里 medoid_shift_.py 的核心逻辑我拆出来大概是下面这个样子。注意这是保留了算法骨架的简写版本实际包里还有边界处理和可视化辅助函数但迭代主体的逻辑是一样的。import numpy as np def assign_to_nearest(data, medoids): # data: (N, d)medoids: (k, d) # 返回长度为 N 的数组每个位置是最近 medoid 的下标 dist_matrix np.linalg.norm(data[:, None, :] - medoids[None, :, :], axis2) return np.argmin(dist_matrix, axis1) def medoid_shift(data, k3, max_iter100, tol1e-4, random_state0): rng np.random.default_rng(random_state) # 初始化从数据里随机抽 k 个不同样本作初始 medoid init_idx rng.choice(len(data), sizek, replaceFalse) medoids data[init_idx].copy() for it in range(max_iter): labels assign_to_nearest(data, medoids) new_medoids [] for cluster_id in range(k): cluster_points data[labels cluster_id] if len(cluster_points) 0: # 空簇保留旧 medoid确保簇数不缩水 new_medoids.append(medoids[cluster_id]) continue # 计算簇内两两距离行和最小的样本就是新 medoid intra_dist np.linalg.norm( cluster_points[:, None, :] - cluster_points[None, :, :], axis2 ) cost intra_dist.sum(axis1) new_medoids.append(cluster_points[np.argmin(cost)]) new_medoids np.array(new_medoids) shift np.linalg.norm(new_medoids - medoids) medoids new_medoids if shift tol: print(fiter {it}: converged, shift{shift:.6f}) break return medoids, labelsassign_to_nearest 里用了广播运算一步得到 N 行 k 列的距离矩阵每行取 argmin 就完成了分配。注意这一步的空间复杂度是 O(Nk)N 到十万、k 到几百时内存会吃紧后面二次开发我会提到用 cKDTree 或分批计算来替代。更新 medoid 的代码是重点先对当前簇内的点构造两两距离矩阵然后intra_dist.sum(axis1)得到每个点与簇内其它点的距离总和argmin选到的就是簇内总距离最小的真实样本。这就是「medoid 是数据集里的点」这个特性的来源。参数说明k 是目标簇数max_iter 是最大迭代次数防止不收敛时死循环tol 是收敛阈值shift 小于 tol 就提前停止random_state 控制初始采样的随机种子。代码里保留空簇的逻辑值得学习如果你把空簇直接删掉下一次循环 labels 的取值范围会缩小而 medoids 数组长度也变了很容易导致索引错位。很多改 K-Means 代码踩过的坑在这里同样会出现。2.3 收敛性和计算量MedoidShift 为什么慢但稳MedoidShift 的收敛性质其实很好证明每一轮把 medoid 移到簇内距离成本最小的点所以目标函数所有点到所属 medoid 的距离总和不会上升。又因为候选 medoid 只能是有限个样本点算法最终必然停在某个局部最优。这个局部最优不一定全局最优因此它对初始化敏感和 K-Means 一样。计算量上朴素的实现就很吃亏了。每次迭代的分配阶段要算 N×k 的距离矩阵更新阶段还要对每个簇算一次两两距离最坏情况下是 O(N²) 的复杂度因为一个簇大到接近 N 时两两矩阵就是 N²。一万个样本、k3 的时候每轮更新都要算三四个百万级距离矩阵纯 Python 加 NumPy 还能扛到五万样本就开始变得卡顿。我的经验是N 在两万以内随便跑再往上就要考虑降采样、先 K-Means 预聚类、或者直接用 QuickShift。但慢有慢的价值。K-Means 更新质心只需要求均值一次遍历就是 O(Nd)可均值点很容易被离群点拉走。MedoidShift 因为候选点必须是真实样本离群点要被选为 medoid必须得让簇内其它所有点到它的距离总和都足够小这个条件很难满足所以它对离群点的鲁棒性天然就好。如果你的下游任务里「代表样本」会被拿去人工审核那这种鲁棒性和可解释性就非常值得付出计算代价。2.4 非欧氏距离场景直接吃距离矩阵前面提到 MedoidShift 可以用任意距离。这里给出一个更通用的版本它不接收坐标 X而是接收一个预先算好的 N×N 距离矩阵 D。这对文本、类别特征、带缺失值的数据特别有用你不需要想办法把对象编码成向量。def medoid_shift_from_dist(D, k3, max_iter100, tol1e-4, random_state0): rng np.random.default_rng(random_state) N D.shape[0] medoid_idx rng.choice(N, sizek, replaceFalse) for _ in range(max_iter): # D[:, medoid_idx] 是 N*k 矩阵每行找距离最近的 medoid labels np.argmin(D[:, medoid_idx], axis1) new_idx [] for c in range(k): cluster_ids np.where(labels c)[0] if len(cluster_ids) 0: new_idx.append(medoid_idx[c]) continue # 子距离矩阵每行求和和最小的是簇内中心对象 sub D[np.ix_(cluster_ids, cluster_ids)] cost sub.sum(axis1) new_idx.append(cluster_ids[np.argmin(cost)]) new_idx np.array(new_idx) if np.array_equal(new_idx, medoid_idx): break medoid_idx new_idx return medoid_idx这里唯一的技巧是np.ix_用来按行和列同时索引子矩阵避免频繁拷贝数据。sub.sum(axis1)算的是每个簇内样本到其它簇内样本的距离和argmin选出最小距离和的原始样本索引。参数和上一个版本完全一致只是输入从坐标换成了矩阵。注意这个版本不会保存坐标 medoid只返回距离矩阵的行索引使用时把它映射回原数据 id 就行。这种写法的好处是你可以把任意业务上的两两距离丢进来比如用户之间的编辑距离、商品之间的语义相似度。代价是 D 本身是 N×N 的N 超过几万就很难存下所以这种版本更适合中小规模数据或者先按业务划分子集再分别跑。3. QuickShift 算法拆解密度树怎么把复杂度降下来3.1 从 MeanShift 到 QuickShift把爬山改为指针跳转QuickShift 属于密度聚类它的理论基础是核密度估计把每个样本周围一定半径内的其它样本用高斯核累加密度高的地方就是簇中心。MeanShift 的做法是把每个点沿密度梯度方向爬山直到峰顶QuickShift 则更直接——它不迭代而是给每个点找一个「密度比自己高、距离又近」的父节点然后沿着父节点一路向上直到某个密度局部极大值点这个极大值点就是簇中心。父节点的选择标准不是单纯的「最近节点」而是「距离除以密度」最小的节点。这个比例设计得很妙一个点如果离密度峰很近那么距离和密度都占优ratio 自然会小如果两个候选点距离相近密度高的一方 ratio 更小更容易被选为父节点。这样构造出的父节点链天然是从密度低的地方指向密度高的地方链的终点就是峰。因为每个点只指向数量有限、密度更高的邻居所以 QuickShift 是一棵树而不是一张图不会出现环。一个很吸引人的特性是QuickShift 不需要预先指定簇数 K。簇的数量由带宽 bandwidth 决定。带宽大密度估计平滑峰合并簇少带宽小密度峰被分开簇多。这个参数是 QuickShift 里最需要花时间调的东西。很多文章把它包装成「无参数聚类」实际并不是只是把 K 换成了 bandwidth调节难度一点没降低。3.2 quick_shift_.py 关键代码解读下面是我读 quick_shift_.py 时还原出的核心流程。为了说清楚建树过程我把密度估计、父节点构建、标签传播三部分单独拆开。import numpy as np from scipy.spatial import cKDTree from sklearn.neighbors import KernelDensity def _estimate_local_density(X, bandwidth): # 高斯核密度估计返回每个样本点的对数密度 kde KernelDensity(kernelgaussian, bandwidthbandwidth).fit(X) return kde.score_samples(X) def build_parent_links(X, bandwidth, leaf_size40): tree cKDTree(X, leafsizeleaf_size) log_density _estimate_local_density(X, bandwidth) # 从密度高到低遍历保证建链方向一致 order np.argsort(-log_density) parent np.full(len(X), -1, dtypeint) for idx in order: neighbors tree.query_ball_point(X[idx], rbandwidth) if len(neighbors) 1: parent[idx] idx continue # 只看密度比当前点更高的邻居 higher [n for n in neighbors if log_density[n] log_density[idx]] if not higher: parent[idx] idx continue candidates np.array(higher, dtypeint) dists np.linalg.norm(X[candidates] - X[idx], axis1) # 距离除以密度分子越小越好分母越大越好 ratio dists / np.exp(log_density[candidates]) parent[idx] candidates[np.argmin(ratio)] return parent, log_density def quick_shift_labels(X, bandwidthNone): if bandwidth is None: # 常见做法抽样算中位数距离乘一个系数 sample X[:min(500, len(X))] median_dist np.median(np.linalg.norm(sample[:, None, :] - sample[None, :, :], axis2)) bandwidth float(median_dist * 0.5) parent, _ build_parent_links(X, bandwidth) labels np.empty(len(X), dtypeint) for i in range(len(X)): node i while parent[node] ! node: node parent[node] labels[i] node return labels先看密度估计。KernelDensity.score_samples返回的是对数密度取np.exp后用于 ratio 计算。直接把对数密度传入也行但 ratio 里np.exp和log_density的数值关系要看清楚ratio dist / exp(log_density)。如果你改成用对数密度计算应该写成 dist (-log_density)不要混。build_parent_links里最值得学习的是「按密度从高到低遍历」这个顺序。因为每个点只关心密度比它高的点按密度降序处理那么遍历到当前点时所有潜在父节点都已经处理过至少 parent 数组里它们是有效值但注意这里并不依赖父节点的父节点只需要候选节点存在。query_ball_point只找半径 bandwidth 内的邻居避免了全量两两比较。标签传播部分对每个点沿 parent 链向上走到根。因为链可能很长在一万个点时会稍慢常见优化是记忆化把已经算过的根存进字典后续节点直接复用。我提供的这段为了可读性没加缓存实际项目里建议加。3.3 复杂度分析和场景选择什么时候该翻 QuickShift 的牌子建树阶段的复杂度来自两部分cKDTree 构建约 O(N log N)每个点查邻居平均在局部范围内整体接近 O(N log N)。标签传播如果朴素写最坏可能 O(N²)比如一条长链所有点串在一起但密度聚类里链通常很短。所以整体性能远好于朴素 MedoidShift。对比一下两个算法维度MedoidShiftQuickShift是否要预设簇数要 K不要用 bandwidth 控制簇代表真实样本点密度峰中心非样本点代表性样本可直接拿 medoid 用需要额外找峰附近样本复杂度最坏 O(N²)约 O(N log N)对距离类型任意距离矩阵通常需要欧氏距离高维表现中等维度高时 k-d 树退化从实践角度我一般这样选明确要拿代表样本做后续访谈的无脑 MedoidShiftN 超过两万、坐标能转成欧氏空间、又不想调 K 的QuickShift 更合适如果数据是带缺失值的表格MedoidShift 的矩阵版本更稳。QuickShift 在高维下性能会掉是因为 cKDTree 在高维空间中搜索性能骤降且密度估计对维度灾难很敏感这时最好先降维到 10 维以内再用。3.4 bandwidth 估算省心套路和翻车现场QuickShift 的带宽可以用 sklearn 的estimate_bandwidth函数自动估算这个函数内部从数据集里抽样一部分计算样本间的最近邻距离中位数。from sklearn.cluster import estimate_bandwidth bw estimate_bandwidth(X, quantile0.3, n_samples500) labels quick_shift_labels(X, bandwidthbw)quantile 是控制估算线性尺度0.3 意味着取最近邻距离的第 30 百分位通常经验值在 0.20.5 之间。n_samples 控制抽样的样本数抽样太少估计会抖动太多计算变慢。注意这个函数返回的是一个全局带宽如果数据里不同簇的密度差异很大全局带宽会顾此失彼稀疏区域的簇被拆碎稠密区域的簇被合并。遇到这种情况我的做法是先对全部数据跑一次粗聚类然后在每个粗簇内分别估算带宽再对每个簇单独跑 QuickShift。这听着麻烦但比调一个全局带宽调试半天要省心。最终输出标签的数量可以直观反映带宽是否合适如果标签数接近样本数明显带宽太小如果标签只有 1 个带宽太大。这个白盒诊断在调试时很有用。4. 实操从解压到读懂 clusters_comparison.png4.1 环境准备别漏了 scipy 和 scikit-learn这个项目的核心代码只依赖 numpy但 demo 脚本里大概率会用到 scikit-learn 的数据生成器和 scipy 的距离计算。我建议一次性装齐省得跑两步发现缺一个。python -m venv cluster_env source cluster_env/bin/activate pip install numpy scipy scikit-learn matplotlib装完之后直接在解压目录下执行python demo_medoid_quick.py。如果一切正常屏幕上会弹出一张对比图或者自动保存为 clusters_comparison.png。README.md 里一般会写清楚运行命令和依赖版本跑之前最好扫一眼。我第一次没看直接跑结果图形界面弹不出来后来发现 demo 里把 matplotlib 后端设成了 Agg只保存不展示并不是程序坏了。4.2 demo_medoid_quick.py 的调用链长什么样这个 demo 脚本的结构拆开看基本是五段生成数据、调用 MedoidShift、调用 QuickShift、画图对比、打印指标。它是在同一个数据集上做对比实验所以会用固定的随机种子生成数据保证两个算法面对的是同一份输入。我简化后的调用逻辑大概是from medoid_shift_ import medoid_shift from quick_shift_ import quick_shift_labels from sklearn.datasets import make_moons, make_blobs from sklearn.metrics import silhouette_score # 1. 生成测试数据 X, _ make_moons(n_samples300, noise0.1, random_state42) # 2. MedoidShift指定簇数 medoids, labels_m medoid_shift(X, k2, random_state0) score_m silhouette_score(X, labels_m) # 3. QuickShift指定带宽 labels_q quick_shift_labels(X, bandwidth0.3) score_q silhouette_score(X, labels_q) # 4. 画图并保存 fig, axes plt.subplots(1, 2, figsize(10, 4)) ... plt.savefig(clusters_comparison.png)注意 MedoidShift 的入口函数返回 medoids 和 labelsQuickShift 的实现可能只返回标签也可能返回中心点这取决于原包作者。如果你发现 quick_shift_labels 只给标签而你想画中心点可以自己算取每个簇内密度最高的样本作为中心即可。demo 脚本里一般会处理这个差别所以你读它比直接读算法实现更容易理解两个算法的接口差异。另外我建议从入口开始看如果脚本里包裹着if __name__ __main__:说明它既可被 import 又可独立运行。如果你的业务代码要复用 demo 里的画图函数最好把生成数据、聚类、绘制三步拆成独立函数。4.3 从 clusters_comparison.png 反推参数调节方向这张图通常左边是 MedoidShift 的结果右边是 QuickShift 的结果。看的时候我一般先看三处有没有明显把一个簇拆成几瓣有没有离群点被单独拎出来两边的子图在簇边界处是否一致。如果 QuickShift 结果碎成很多小簇是带宽太小密度峰被过度识别。无需去翻源码直接用指数步长加大带宽比如 0.2 提到 0.4、0.8看趋势。如果 MedoidShift 的 medoid 点画出来很靠近簇的边缘通常不是代码 bug而是 k 选大了本来两簇数据被分成了四簇每个小簇的 medoid 自然都偏。这时候先调 k用轮廓系数或肘部法确定合理区间。对比图还有一种常见用法是看实际边界权MedoidShift 按距离分配QuickShift 按密度分配两者在密度较低的狭长区域会出不同结果。如果业务关心的是「密度低的夹缝地带归哪边」看图比看任何指标都直观。4.4 改成你自己的对比实验多数据集加指标汇总demo 只跑一个数据集太浪费了。我建议改成循环把生成数据、聚类、打分串起来一次性对比多个数据集结果汇总成表格避免反复改参数重跑。from sklearn.datasets import make_circles, make_moons, make_blobs import pandas as pd datasets [ (blobs, make_blobs(n_samples500, centers4, random_state0)), (moons, make_moons(n_samples300, noise0.08, random_state0)), (circles, make_circles(n_samples400, factor0.5, noise0.05, random_state0)), ] rows [] for name, (X, _) in datasets: labels_m medoid_shift(X, k4 if name blobs else 2, random_state0)[1] labels_q quick_shift_labels(X, bandwidth0.2) rows.append({ dataset: name, medoid_sil: silhouette_score(X, labels_m), quick_sil: silhouette_score(X, labels_q), quick_clusters: len(set(labels_q)), }) df pd.DataFrame(rows) print(df)这里的重点是控制变量所有数据集都固定随机种子bandwidth 可以按照每个数据集大致取一个值也可以记录到表格里方便回溯。quick_clusters列能立刻发现带宽设得合不合理。跑完之后再看 clusters_comparison.png 那张图的语义你会发现很多问题其实是参数选择不合适不是算法本身有这个毛病。为了不把文件搞乱我会给每个数据集单独保存一张图fig, axes plt.subplots(1, 2, figsize(10, 4)) ... fig.savefig(f{name}_comparison.png) plt.close(fig)plt.close 很重要不然循环里图会越叠越多内存疯涨。这个我在一次完整批量实验里翻过车最后连运行环境也跟着卡死。记住循环画图的规范是「用完即关」。5. 避坑与常见问题五个让新手血压升高的现场5.1 结果每次跑都不一样现象同一个 demo 脚本连续运行两次两次的聚类标签变化很大甚至簇数量都不一致。原因MedoidShift 初始 medoid 是随机采样QuickShift 本身是确定性的但如果 demo 生成数据时没固定随机种子数据本身每次都会变。两个随机源叠加结果自然不稳定。解决先给数据生成固定随机种子比如 make_blobs(random_state0)再给 medoid_shift 传 fixed random_state。QuickShift 只要数据固定就确定但如果你改写了标签传播顺序也记得把遍历顺序绑定到 np.argsort不要用 set 去重set 的顺序不稳定。判断是否稳定跑两遍后对比 labels 的一致性不一致就排查随机源。5.2 QuickShift 内存直接爆炸现象样本数从一万加到五万QuickShift 跑了一会儿之后内存飙升电脑卡死甚至 OOM。原因如果实现里用了全量距离矩阵np.linalg.norm(X[:, None, :] - X[None, :, :])五万样本就是 25 亿个浮点数绝无可能装下。QuickShift 的 cKDTree 就是为了避免这个但如果你在 query_ball_point 之后拿着 neighbours 列表又去构造完整距离矩阵同样会把内存打爆。解决确认父节点构建时用的是tree.query_ball_point(X[idx], rbandwidth)而不是一次性对所有点查邻居后再全量拼接。同时 leaf_size 调到 2040能减少叶子节点内的线性扫描。如果维度大于 20先降维如果用 scipy 的 cKDTree 也没救可以考虑用更贴近工程的距离搜索库替代但引入额外依赖要评估收益。调试时打开另一个终端用top -p PID看进程内存如果 RSS 涨到几个 G 再爆基本可以把嫌疑锁定在某一步触碰了全量矩阵。5.3 MedoidShift 跑成死循环现象脚本卡在迭代里不收敛打印出的 shift 数值一直在某个小值附近震荡或者完全不动。原因最常见是 tol 设得太小比如 1e-8超出浮点精度后 medoid 在两个候选点之间反复横跳其次是空簇处理成删除逻辑导致 medoid 数量不稳定labels 数组长度对不上程序在循环里进退两难。解决tol 设置到 1e-4 或 1e-5并在循环里保留 max_iter 兜底。空簇保留旧 medoid 的写法是标准做法不要删。如果你自己实现了「如果空簇就全局重跑」的逻辑一定要小心标签索引重跑后 medoid 的初始索引要重新对齐不然越跑越乱。如果怀疑死循环在 medoid_shift 内加一行打印每轮的 shift低于 1e-6 后还反复横跳就是 tol 太小的铁证。5.4 保存的图片全黑或空白现象在 Windows 上跑 demo生成的 clusters_comparison.png 全黑或者画布上什么都没有。原因常见的两个原因一是脚本先调了 plt.show() 再调 plt.savefig()show 之后画布内容被清空二是 matplotlib 后端在无 head 环境下不兼容比如在服务器上跑还开着默认的 Qt 后端。解决把 savefig 放在 show 的前面或者干脆注释 show只保留 savefig。无 head 运行就强制用 Aggimport matplotlib; matplotlib.use(Agg)。查看当前后端用python -c import matplotlib; print(matplotlib.get_backend())。这是在 Linux 服务器上跑聚类可视化的经典玄学多留意一次就能省十分钟。5.5 轮廓系数报错样本数小于等于簇数现象计算 silhouette_score 时抛出 ValueError提示 labels 数量不对或者某个簇只有 1 个样本。原因QuickShift 的带宽太小会把每个离群点都单独成一个簇少数簇变成单样本MedoidShift 的 k 设得比样本数还大也会触发。轮廓系数的定义要求每个簇至少有 2 个样本单样本簇会直接让整个评估失效。解决算指标前先用np.unique(labels)检查簇数过滤掉单样本簇后再计算如果簇数太多加大 bandwidth 或减小 k。这条经验通用任何聚类评估都应该先看标签分布再决定能不能跑轮廓系数。当簇数很少或单例很多时改用 calinski_harabasz_score它不需要两两样本距离对单例簇更宽容或者直接用簇内距离和 medoid 距离做业务侧评估不依赖 sklearn。不要迷信一个数字看一眼分布比什么指纹都准。6. 二次开发把两个算法集成到自己的聚类流程里如果想拿这套代码做实打实的项目第一件事别急着改算法内部先封装。我一般会在项目里新建一个 cluster_model.py把两个算法都包一层相同的接口上层调用只依赖 fit_predict()方便后续换算法不影响业务代码。class MedoidClusterer: def __init__(self, k3, max_iter100, tol1e-4, random_state0): self.k k self.max_iter max_iter self.tol tol self.random_state random_state def fit_predict(self, X): medoids, labels medoid_shift(X, kself.k, max_iterself.max_iter, tolself.tol, random_stateself.random_state) self.medoids_ medoids return labels class QuickClusterer: def __init__(self, bandwidthNone, leaf_size40): self.bandwidth bandwidth self.leaf_size leaf_size def fit_predict(self, X): labels quick_shift_labels(X, bandwidthself.bandwidth) return labels接下来做两个必做的验证第一用 sklearn 的calinski_harabasz_score和davies_bouldin_score在多个模拟数据集上过一遍把两个算法的分数存下来而不是只凭一张 png 下结论第二检查 medoid 的稳定性。对同一个数据集跑十次 MedoidShift把十次出来的 medoid 坐标求两两距离如果最大距离小于数据总体方差的 5%说明结果稳定否则说明这个数据不适合随机初始化。数据量上来以后朴素的 MedoidShift 会追不上了。我的血泪经验是先用 K-Means 粗聚类得到初始 medoid再把这个初始 medoid 传给 MedoidShift 微调。这样既保留了 medoid 的鲁棒性又减少了迭代轮数。对于 QuickShift带宽自动估算可以用sklearn.cluster.estimate_bandwidth返回值乘一个系数我常用的系数是 1.01.5具体要看数据分布这是最需要手工干预的参数多跑几遍对比图再定。从那以后我每次跑聚类之前都强制先问自己三件事要不要真实样本作为簇代表要不要预设簇数数据量是不是过万。把这三点想清楚再去选 MedoidShift 还是 QuickShift几乎不会再出现选错算法的场面。希望这次拆解能帮你在自己的数据上少绕几个弯。本文还有配套的精品资源点击获取