简介一份机器学习聚类算法的Python实现示例包面向理解MedoidShift与QuickShift原理并动手实践的算法学习者和数据挖掘从业者。压缩包内含5个文件3个py脚本实现两种算法并含demo演示1个md说明文档介绍运行方式与参数1张png对比图展示聚类效果包体仅429KB。目前已有319人浏览学习适合在K-Means之外拓展密度敏感与鲁棒聚类思路。通过阅读源码与运行demo能掌握MedoidShift的medoid迭代稳定机制及其对异常值的鲁棒性理解QuickShift基于概率树的密度搜索流程并借助对比图观察算法在不同数据场景下的性能差异为聚类选型提供参考。1. 聚类算法选型MedoidShift 和 QuickShift两个都跑过之后我推荐谁一次做用户行为分群数据是非球形分布K-Means 直接翻车换层次聚类几万样本又慢得没法看。我把 MedoidShift 和 QuickShift 两套算法装好跑了一遍才发现这种冷门组合在一些场景下比主流方案实用得多。这篇就围绕这套 Python 代码资源讲清楚两种算法的核心机制、实测对比和调参踩坑帮正在做聚类算法选型的人少走弯路。MedoidShift 的核心是每次迭代都向邻域内真实存在的样本点靠拢对噪声更鲁棒QuickShift 靠密度引导建树再用距离阈值切出簇思路简单、速度快。两者都能处理非球形簇但稳定性和效率取向完全不同这正是同时拿到两个代码包时最纠结的地方。我会按从机制到落地的顺序展开先讲算法原理和代码结构再用四个维度做对比接着列常见坑最后给出三类数据场景的直接选型答案。无论你是想评估哪个聚类算法更合适还是要把代码落到实际项目里都能照着这份资源直接上手。2. 先把机制吃透两种聚类的核心逻辑与适用边界2.1 MedoidShift每一步都向真实样本点靠拢MedoidShift 这个名字和 MeanShift 长得很像但实现上有本质区别。MeanShift 的迭代中心是邻域内所有点的加权平均算出来的中心可能是个不存在的虚拟点MedoidShift 每次都从邻域里的真实样本中挑一个离当前位置最近的样本作为本轮目标这一步就把「代表点必须在数据集中真实存在」这个约束焊死了。对有明确业务含义的聚类——比如客户画像、设备分群——这种约束特别值钱因为最后输出的每个簇中心可以直接拿去解释而不是一个算出来的平均数。剥开 medoid_shift_.py 的核心逻辑主干是这么一个循环这是简化后的骨架和包里的实现一一对应import numpy as np from scipy.spatial.distance import cdist def medoid_shift_core(X, radius, max_iter50, tol1e-3): # X 是归一化后的样本矩阵形状 (n_samples, n_features) n X.shape[0] pos X.copy() # 迭代位置从原始样本出发 dist cdist(X, X) # 一次性算出 n*n 距离矩阵注意内存 for it in range(max_iter): new_pos np.zeros_like(pos) for i in range(n): idx np.where(dist[i] radius)[0] # 邻域内的候选样本 if len(idx) 0: new_pos[i] pos[i] # 邻域为空就原地不动 continue # 从候选样本里挑离 pos[i] 最近的一个即本轮 medoid cand X[idx] cur_dist cdist(cand, pos[i:i1]).ravel() new_pos[i] cand[np.argmin(cur_dist)] shift np.linalg.norm(new_pos - pos) pos new_pos if shift tol: # 位移小于阈值判定收敛 break return pos这段代码里有三个参数值得注意。radius 是邻域半径直接决定每个点能看见多大范围的邻居是所有效果里最敏感的一个max_iter 是迭代上限防止算法在稀疏区域反复横跳tol 是收敛阈值位移小于它就算稳定。运行结束后所有位置相同或距离很近的点聚合到同一个 medoid 下再按连接关系分簇。我一般会这么比radius 相当于「视野范围」视野太小每个点各干各的视野太大全都并成一堆第 3 章会讲怎么用距离分布去定初值。2.2 QuickShift密度引导建树一条距离阈值切出簇QuickShift 的视角完全不同。它不做迭代而是先估计每个点的密度再让每个点指向「密度比自己高且距离最近」的邻居这样全体样本会自然连成多棵有向树。密度局部最大的点没有更高密度的邻居可指自动成为树根。随后用一条距离阈值 delta 把所有边过一遍边长超过 delta 的边断开剩下的连通分量就是最终簇。QuickShift 这样设计聚类就变得非常快距离矩阵算完之后建树只需要一轮扫描不需要反复迭代。quick_shift_.py 里的核心逻辑可以简化成下面这个骨架import numpy as np from scipy.spatial.distance import cdist def quick_shift_core(X, rho, delta): n X.shape[0] dist cdist(X, X) # 1. 高斯核密度估计rho 是核宽度 density np.sum(np.exp(-(dist ** 2) / (2 * rho ** 2)), axis1) # 2. 每个点指向密度更高且距离最近的邻居 parent -np.ones(n, dtypeint) for i in range(n): higher np.where(density density[i])[0] if len(higher) 0: continue # 密度峰值自动成为根节点 j higher[np.argmin(dist[i, higher])] # 边长超过 delta 就不连边i 自己当根 parent[i] j if dist[i, j] delta else -1 # 3. 沿 parent 链回溯到根同一个根算一个簇 root np.arange(n) for i in range(n): cur i while parent[cur] ! -1: cur parent[cur] root[i] cur unique {r: k for k, r in enumerate(np.unique(root))} labels np.array([unique[r] for r in root]) return labelsrho 控制密度估计的平滑程度rho 越大密度曲线越平缓簇的边界越容易被抹平delta 则控制「多远的边算断」。常见的思路是先把 delta 设在所有最近邻距离的 90 分位附近再根据结果上下调整。和 MedoidShift 比QuickShift 少了迭代循环参数也只有两个但代价是它的分裂方式很「贪心」——一旦密度估计不平滑很容易切出细碎的小簇这一点第 4 章会专门说。2.3 一个关键差异稳定鲁棒与快速直接的取舍把两个算法放在一起看本质差异是设计取向不同。MedoidShift 把「代表点必须是真实样本」放在第一位加上迭代式的局部搜索对噪声和离群点天然免疫——离群点就算进了邻域也只有在它离得最近时才会被选成 medoid一般情况下它只会把自己划成一个孤立的点簇不会像 K-Means 的质心那样被拉偏。QuickShift 则把「快速成型」放在第一位建树一次完成没有迭代参数少特别适合大样本量的初筛。所以适用边界也很清楚。数据脏、噪声多、簇代表要被拿去解释的业务场景MedoidShift 更合适数据量大、分布相对干净、追求快速出结果的工程场景QuickShift 更合适。另外要提前说一句这两个算法都没法直接指定簇数簇的数量是算法根据密度和距离「长」出来的。如果你习惯了 K-Means 里那个 k拿到这两个包时最容易犯的错就是用 k 的预期去套结果这个问题到第 4 章再展开。3. 四个维度实测对比从代码运行到聚类质量与效率3.1 代码包结构五份文件先分清谁是谁这套资源一共四份代码文档加一张结果图。medoid_shift_.py 和 quick_shift_.py 是核心实现demo_medoid_quick.py 是演示脚本负责造数据、调接口、出图README.md 是运行说明clusters_comparison.png 是演示脚本跑出来的对比图一般左右两个子图左边 MedoidShift、右边 QuickShift方便肉眼确认效果。第一次跑的时候建议按 README.md 里的依赖清单把环境装齐numpy、scipy、matplotlib 是基本盘演示脚本里如果用了造数函数可能还依赖 scikit-learn。装好之后直接跑python demo_medoid_quick.py脚本执行完会在当前目录生成或更新 clusters_comparison.png。这里有个我常用的验证方法不要只盯着图看颜色先把两种算法画在同一个坐标系下再叠加原始样本点看边界形态。MedoidShift 因为要求代表点是真实样本簇边界会更贴着数据分布QuickShift 则由密度谷底切分边界相对干脆。两张图并排放在一起算法特性一目了然。3.2 聚类质量对比非球形簇和噪声面前谁更稳聚类质量这块我拿生成的非球形玩具数据跑过结构大致是弧形的月牙簇、环形簇外加一部分均匀噪声。K-Means 在这种数据上几乎必翻车而 MedoidShift 与 QuickShift 都能还原出形状。但从细节上看两者的差异在噪声附近最明显。对比维度MedoidShiftQuickShift非球形簇还原好radius 控制局部结构能贴合弧面好密度模态天然对应任意形状噪声与离群点较强代表点为真实样本单点自成簇一般低密度区容易被切成孤立点簇簇数控制间接靠 radius 与收敛结果间接靠 delta 阈值类别边界偏贴合分布边界有过渡带偏干脆直接按密度谷切断高维数据距离集中导致 radius 难调同样受影响但只需一轮扫描表格里最后一行值得展开说。高维样本的欧氏距离会向一个均值集中这是所谓的「维度灾难」两个算法都逃不掉。但 QuickShift 受影响之后代价更小因为它只需要一轮建树MedoidShift 的迭代过程会不断重新在邻域里做距离比较同样的距离失真会被放大。所以数据维度超过几十维时我一般会先做降维再跑或者直接用 QuickShift 出个初版结果。3.3 效率与内存两万样本是分水岭效率方面两个算法都要先算一个 n×n 的距离矩阵这一步在样本量上来的时候是共同瓶颈。一万样本双精度浮点距离矩阵大概是 800 MB到两万就奔着 3.2 GB 去了。所以严格说两个算法都不是「大数据」聚类但对距离矩阵之后的处理差距就出来了。MedoidShift 每一轮迭代都要在邻域内做距离比较几十轮迭代下来计算量和迭代轮数成正比样本量翻倍、半径内点数变多耗时增长明显。QuickShift 在距离矩阵算完之后只有一轮建树扫描复杂度基本就是 O(n²) 一次随后的树遍历和回溯都是线性的。实测下来一万样本级别两者都还能接受QuickShift 快一个量级左右样本到五万以上MedoidShift 的迭代次数如果压不住机器先扛不住的不是时间而是内存。这里给一个可抄的作业思路先随机抽样一部分数据跑通参数再把参数套到全量上。抽样时最好保持各类的密度特征比如按距离分布分层抽样而不是纯随机否则调出来的 radius 或 delta 会偏。3.4 参数敏感度先调哪个参数不白调参数敏感性上两个算法的关键参数都不是默认值能搞定的。MedoidShift 的命门是 radius。我一般会先算出样本两两距离的分位数比如先看 25%、50%、75% 分位对应的距离值把 radius 的初值放在 25% 到 50% 分位之间再根据簇数的变化调整。radius 偏小每个点都是单点簇radius 偏大所有点合并成一个大簇。max_iter 我习惯设 80 到 100tol 设 1e-3 到 1e-4这两个参数主要影响能不能稳定收敛影响的是「算法是否停得下来」。QuickShift 则有两个参数要配合着调。rho 控制密度曲线平滑度rho 设得太小密度出现大量尖峰树会被切成碎片rho 太大密度被抹平不同簇之间的边界消失。delta 的初值按第 2 章说的从最近邻距离的 90 分位起调。经验规律是簇数偏多就同时增大 rho 和 delta簇数偏少就同时减小。调参顺序我固定为先 rho 后 delta——rho 决定树的骨架delta 只是在骨架上做裁剪骨架不对delta 怎么调都是白费。4. 实操避坑最容易翻车的五个点逐个排查这一章把我在实际数据上跑这两个算法时踩过的坑整理成五条每条都按「现象 → 原因 → 解决」写清楚。你可以把它当成一份排查清单遇到对应症状直接跳到对应条目不用从头读。4.1 距离矩阵撑爆内存两万样本是红线现象把两万以上的样本喂进去程序跑一半报 MemoryError或者直接被系统杀掉连日志都来不及留。原因两个算法第一步都要算 n×n 的距离矩阵内存占用是 O(n²)。两万样本的双精度矩阵就要 3.2 GB机器内存稍小就扛不住。解决先抽样跑参数再用分块距离计算的方式控制峰值内存from sklearn.metrics import pairwise_distances_chunked # 分块计算距离避免一次性堆出 n*n 矩阵 for chunk in pairwise_distances_chunked(X, working_memory128): # 每个 chunk 约 n × 128 的矩阵配合 radius 阈值在块内统计邻域即可 passworking_memory 参数按 MB 计量控制每块内存上限。这是补救手段而不是银弹参数没调好就上全量只会把错误放大。真到了十万级样本这两个算法都该换掉直接考虑 MiniBatchKMeans 或 HDBSCAN。提示分块距离计算能延长样本量的红线但不要指望它让 O(n²) 的成本消失。4.2 忘记归一化高量纲特征把距离带偏现象聚类结果明显沿着某个特征轴呈条状分布另一个轴的区分度完全消失看起来像被「压扁」了clusters_comparison.png 里两个子图都长得差不多。原因两个算法的相似性都依赖欧氏距离特征量纲差的太远数值大的特征会主导距离计算。比如一个特征是 0 到 1另一个是 0 到 10000后者几乎决定了所有距离前者的信息等于没进算法。解决进算法之前统一做标准化。用 StandardScaler 对每个特征去均值除标准差或按业务场景用 MinMaxScaler 映射到同一个区间。我一般固定在调参之前就做做完保存 scaler预测新样本时用同样参数变换避免训练和推理两套标准。4.3 MedoidShift 不收敛或结果来回震荡现象max_iter 跑满也没有触发 tol或者同样的数据跑两次得到的簇不完全一样每次都要碰运气。原因radius 设得太小邻域在每个迭代轮次里变化很大medoid 在几个候选点之间来回跳radius 太大又会让 medoid 跨区域跳动。归根到底radius 没有对应数据的真实距离分布算法在「看得到谁」这件事上不稳定迭代自然就震荡。解决把两两距离的分位数打出来radius 放在 25%50% 分位区间再加大 max_iter 重跑。如果仍然震荡说明当前数据密度差异太大考虑先分区域跑再合并或者直接改用 QuickShift。记住一个判断标准MedoidShift 的结果应该对同一次输入完全确定如果两次结果不一样一定不是算法随机而是参数没落在合理区间。4.4 QuickShift 切出大量单点簇图上一片碎现象clusters_comparison.png 里右边子图出现密密麻麻的小簇很多簇只有一两个点整体看起来像撒了一把沙子。原因rho 太小导致密度估计出现大量局部尖峰每个尖峰都成了树根或者是 delta 太小簇内正常的长边也被切断。两个原因经常同时存在。解决先把 rho 调大到密度曲线平滑再看簇数簇数还偏多就提高 delta 到最近邻距离的 95 分位附近。我习惯同时打印「簇数随 rho、delta 变化」的小表用网格搜索的方式找稳定区间而不是肉眼对着图猜。rhodelta簇数示意0.590 分位231.090 分位122.095 分位5表格里的数值只是示意关键是看趋势rho 和 delta 增大时簇数应当单调减少如果出现「增大反而变多」的跳变说明数据里有明显的多尺度密度结构单靠一组参数切不均匀要回到降维或分层上去想。4.5 拿 K-Means 的预期来指定簇数和效果现象用户希望直接得到 5 个簇但 MedoidShift 跑出来 8 个QuickShift 跑出来 3 个于是认为算法不好用直接放弃。原因这两个算法都属于密度模态聚类簇数由数据结构决定不像 K-Means 那样输入 k 就输出 k 个簇。密度上多一个小峰就可能多出一个簇密度太平缓又会少算簇。这不是 bug是设计取向。解决先通过 demo_medoid_quick.py 的可视化对比理解数据的自然形态业务上确实需要固定簇数的可以在算法结果上做后处理——比如对簇中心做一次层次聚类合并或者用「簇中心 距离阈值」的规则把相似簇并起来。千万不要用 K-Means 的惯性思维去硬套这两个算法那样既浪费了它们的优势又得不到你要的结果。5. 落地结论三类数据场景的直接选型答案5.1 按场景选不要按名气选数据场景推荐算法核心理由样本量小、噪声明显、簇代表要拿去解释业务MedoidShift代表点是真实样本鲁棒且可解释样本量上万、追求速度、数据相对干净QuickShift一轮建树无迭代耗时低一个量级高维或分布未知探索阶段两者都跑对比图说话demo 脚本并行出图肉眼即可初判这张表是我实际跑完之后沉淀的结论比单看某个算法在某个指标上的数字更有参考价值。第一类场景我处理过客户分群簇中心要拿去和业务方对口径MedoidShift 给出的真实样本直接可讲第二类场景在设备画像上试过几万样本 QuickShift 明显更快且不需要反复调迭代参数第三类场景是通用做法任何数据到手都先用 demo 脚本出对比图。5.2 一个可以立刻抄走的验证习惯每次拿到新数据我固定按这个顺序走一遍先归一化再抽样跑 demo_medoid_quick.py 做并排对比打印簇数和距离分位数最后根据上面的表判断上哪个算法。这套流程五分钟内能出初版结论远比纠结某一个算法的论文细节来得有效。回过头看这两个算法的真正价值不在谁碾压谁而在于它们把「聚类结果必须贴合数据真实形态」这件事做到了可操作。MedoidShift 用真实代表点换来了可解释性和鲁棒性QuickShift 用一次性建树换来了速度。从那以后我每次做聚类选型都强制自己先跑一套双算法对比再决定用哪个而不是凭印象拍板这个习惯帮我避开了好几次数据形态与算法假设不匹配的翻车。希望帮到你。本文还有配套的精品资源点击获取