简介围绕 MedoidShift 与 QuickShift 两种聚类算法这份 Python 代码包为机器学习学习者和数据挖掘工程师提供了可直接运行的实现参考。MedoidShift 算法属于基于对象的聚类方法通过反复迭代将数据点移动到更接近其邻居的 medoid 位置直至聚类稳定因此对异常值具有较好的鲁棒性QuickShift 算法采用密度敏感思路利用树形结构快速查找相邻样本从而在高维数据处理中有效减少计算开销。压缩包内共 5 个文件包括 3 个 Python 脚本、1 张聚类结果对比图和 1 份说明文档整体仅 429 KB轻量易用便于快速部署。脚本分别实现两种算法演示脚本串联数据加载、预处理、聚类计算与可视化输出对比图直观展示不同算法在同一数据集上的划分效果说明文档则提供运行环境和参数含义说明帮助使用者理解与复现。目前已有 319 人学习下载。通过实际运行和调参读者可对比两种算法在聚类速度、抗噪能力及面对不规则簇时的差异从而为实际项目中的算法选择提供实证参考并加深对无监督学习的理解。1. MedoidShift 与 QuickShift同样是聚类算法为什么一个要选代表一个要找山顶MedoidShift 与 QuickShift 这两个聚类算法初看都在做同一件事——把相近的样本归成一堆。但只要你真正跑过一次对比实验就会发现它们的工作方式完全是两个物种MedoidShift 每轮迭代都在样本点之间来回跳向一个真实存在的代表点宁可多扫几遍邻居也要保住中心的可解释性QuickShift 则只做一次密度寻父计算让每个点沿着密度升高的方向大步跳向局部最高点聚类中心连坐标都不用给。搞懂这套底层机制不是为了背两个算法的名字而是为了回答一个很实际的问题当你的数据里有异常值、有不规则形状的簇、有上千维特征时谁会稳稳出结果谁会悄悄翻车——以及为什么。理解了这一点你才算真正把聚类这件事从调库层面下沉到了机制层面。2. MedoidShift为什么真实存在的代表点比虚拟质心更稳2.1 从质心到 medoid一个点的身份变化改写聚类的抗噪性能先用 K-Means 做参照系。K-Means 的质心是簇内样本在欧氏空间里的算术平均位置它是一个虚拟点——数据集中完全可以不存在这样一个样本。这个设计在数学上很干净但有两个隐患第一质心会被离群点拖拽一两个极端值就能让整个簇的边界明显偏移第二质心不具备业务语义你没法指着算术平均坐标说这就是该簇最具代表性的那条真实记录。MedoidShift 换了一条路它要求簇的代表必须来自数据集本身这个代表叫 medoid严格定义是簇内到其他所有样本距离之和最小的那个真实样本。因为 medoid 是从实际观测值里选出来的它天然落在稠密区域中部离群点对它的影响力远小于对算术质心的影响力。MeDoIDShift 这个名字本身也透露了它的血统——它和 MeanShift 同属模式漂移家族但 MeanShift 是在连续空间里滑动窗口中心MedoidShift 则把每次滑动限制在离散的样本点上。别小看这个限制它换来了两个实打实的收益代表点永远有真实对应记录且不会出现 MeanShift 那种质心飘到无数据区域的空洞情况这一点在后续迭代收敛稳定性上体现得很充分。2.2 迭代漂移距离矩阵、邻居投票与收敛判定MedoidShift 的核心循环不复杂但魔鬼全在细节里。我按一个典型的实现思路拆给你看import numpy as np def medoid_shift(X, radius0.5, max_iter30): n X.shape[0] # 预计算成对距离矩阵MedoidShift 的核心输入 D np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)) # current[i] 保存的是样本 i 当前所属代表点的原始索引 current np.arange(n) for _ in range(max_iter): changed 0 for i in range(n): # 邻域与当前代表点距离小于 radius 的所有真实样本 nbrs np.where(D[current[i]] radius)[0] if len(nbrs) 2: continue # 在这组真实样本里选到所有邻居距离总和最小的点作为新代表 cost D[nbrs][:, nbrs].sum(axis1) best nbrs[np.argmin(cost)] if best ! current[i]: current[i] best changed 1 # 整轮没有点再改变归属说明已经稳定提前终止 if changed 0: break return current这个循环里最关键的是cost D[nbrs][:, nbrs].sum(axis1)这一行它在候选邻居集合内部两两算距离然后按行求和取和最小的那个点作为新代表。这恰好是 medoid 的定义方式——一个点在多大程度上是簇中心不是看它离某个虚拟质心多近而是看它到周围所有邻居的总远近。radius控制邻域尺度相当于 MeanShift 里的带宽max_iter是安全阀防止极小概率下出现振荡循环。一个有意思的细节是每一轮迭代里current[i]可能在循环中途被更新也就是说本轮更新过的点会立即影响后面点的邻域判断这是一种在线更新的策略收敛通常比批量同步更新更快但代价是依赖样本遍历顺序。我在 2.1 里说的离散滑动的好处到这里就清楚了——质心永远不会出现在两个样本之间的空地上所以每个点总能找到一个确切的落点不会出现 MeanShift 里因窗口内无样本而无法更新的尴尬局面。2.3 复杂度瓶颈与常见的加速手段把上面的代码直接扔给大数据集是撑不住的原因一目了然距离矩阵是 O(n²) 的存储和计算而每一轮迭代里每个点都要做一次邻域扫描极端情况下max_iter轮就是 O(n²·max_iter)。实际的 medoid_shift_.py 实现里通常不会真的把整个距离矩阵都算出来再开循环常见的加速手段有两种。其一是用 KD 树或球树替代全量距离计算——邻域查询是这类索引的主场距离小于radius的候选点不必全部显式求距离查询复杂度能从 O(n²) 降到期望 O(n log n)其二是增量更新思路每次只更新代表点发生变化的样本的邻居关系而不是每轮重建全量邻域。还有一个工程细节值得注意np.partition可以在不排序的情况下拿到第 k 小的距离很多实现会用它对距离做分位数截断从而自动确定radius——比如把radius设成所有成对距离的中位数。这样做的理由是中位数距离对数据尺度不敏感且能让每个点的邻域包含大约一半的样本迭代漂移的图结构不会过早退化成完全图或孤立点图。3. QuickShift把聚类转换成在密度地形上找最高点的一次寻父3.1 密度极值点聚类中心为什么可以不是簇的中心QuickShift 的出发点完全是另一套世界观它根本不问哪些点离哪个中心近而是问一个点在密度地形上应该往哪走。这个走法的依据是两个条件同时满足——目标点的密度比自己高且在所有密度更高的点里距离自己最近。沿着这条路走每个样本最终都会收敛到一个密度局部极大点上这个点就是聚类中心。注意这个中心不要求是簇的几何中心它只是密度场里的一个峰值。这里的核心概念是密度。怎么估密度常见的实现里两种手段最普遍高斯核密度估计——以每个点为中心叠加一个核函数再看某点周围聚集了多少核质量以及第 k 近邻距离的倒数——某个点到它第 k 个邻居的距离越小说明周围越拥挤密度越高。后一种实现尤其直观简洁代价是需要多算一遍 KNN。和 MedoidShift 相比QuickShift 的优势在于它不需要预设簇的个数也不需要迭代收敛——只要密度估计出来了每个点到其父节点的映射一次计算就能完成。聚类本质上是从点出发沿着树形结构上溯到根的过程。想想看这意味着 QuickShift 甚至不需要代表点这个概念聚类中心只是一些密度峰值对应的样本位置阔以理解为一种隐式的簇标签传播。3.2 父节点映射从每个样本到密度更高、距离更近的那个点quick_shift_.py 里最核心的逻辑可以提炼成下面这段代码import numpy as np def quick_shift(X, k10): n X.shape[0] # 第一步用第 k 近邻距离的倒数粗估局部密度 D np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)) knn_dist np.partition(D, k, axis1)[:, k] density 1.0 / (knn_dist 1e-10) # 第二步每个样本找一个密度更高且距离最近的父节点 parent np.zeros(n, dtypeint) for i in range(n): higher np.where(density density[i])[0] if len(higher) 0: parent[i] i # 密度局部最高成为根节点 continue j higher[np.argmin(D[i, higher])] parent[i] j return parent, density这段代码的意识流是先给每个点标定海拔密度再从当前点看向所有比自己还高的点选最近的一个作为父节点。密度最高的那些点没有父节点它们就是若干座山的山顶。到这里所有点已经挂在一棵或者几棵树上了。但树还不是簇——要得到最终聚类还需要一步剪枝沿着 parent 链上溯的时候如果某条边跨越的距离超过一个阈值 τ就把它切断让下层的点自成一体。这个 τ 相当于一个密度连通性阈值控制着最终簇的粒度。我在阅读这些代码时注意到一个最容易让人误解的地方np.partition(D, k, axis1)[:, k]拿到的并不是排好序后的第 k 个距离而是第 k 小的距离——因为 partition 只是把第 k 小的元素放到第 k 位并不保证其他位置有序。这正是密度估计里的一个实用的小技巧想要第 k 近邻距离根本不需要全排序。3.3 复杂度分析一次寻父为什么能显著快于多轮漂移如果把上面的代码原样跑起来它其实也是 O(n²)——距离矩阵照样逃不掉。但 QuickShift 在实际项目里被称作快速是因为它的计算循环比 MedoidShift 少了一个维度MedoidShift 要反复迭代到收敛每轮都重新扫描邻域QuickShift 的寻父过程一轮就能完成后续的聚类只是沿着已经建好的树做连通性分析。这个复杂度优势在大规模数据集上非常明显尤其在配合 KD 树做密度估计和寻父搜索时期望复杂度可以降到接近 O(n log n)。不过要提醒一句QuickShift 的快是拿密度估计的参数敏感性换来的。k 的选择直接决定了密度场的形状——k 太小每个点都可能成为局部极大簇数爆炸k 太大密度场被过度平滑真正的密度低谷被填平相邻的簇会被粘在一起。所以高维大数据集上 QuickShift 往往表现出跑得飞快但参数要反复试的特点。这也解释了为什么项目里那两份代码放一起对比会很有意思一个把复杂度花在迭代稳定性上一个把复杂度花在密度估计的准确性上代价的分配方式完全相反。4. 让两个算法同台竞技demo 脚本里的完整链路与对比图读法4.1 demo 的执行链路数据准备、两个算法调用与可视化demo_medoid_quick.py 做的事本质上是把两个算法塞进同一条流水线里做横向对比。典型链路分成五步加载或生成合成数据做特征归一化分别调用两个聚类函数把返回的标签数组转成可视化用的颜色映射最后把两幅图并排保存成一张对比图。下面是一个可以对照的调用骨架from medoid_shift_ import medoid_shift from quick_shift_ import quick_shift import matplotlib.pyplot as plt # 同一份数据喂给两种算法 X load_or_generate_samples() # 加载或构造数据 labels_medoid medoid_shift(X, radius0.5) # 返回代表点索引 labels_quick, _ quick_shift(X, k10) # 返回父节点和密度 # 对 quick_shift 的树结构做剪枝得到最终簇标签 labels_quick_final cut_tree_at_threshold(labels_quick, tau0.3) # 左右子图画两种结果保存为 clusters_comparison.png这里有个很值得注意的细节MedoidShift 返回的直接就是每个样本最终的代表点索引这个词里已经包含了聚类的语义——代表点索引相同就属于同一个簇不需要再加工而 QuickShift 返回的是父节点关系是树形结构距离阈值 τ 的剪枝是附加的一步它被放在 demo 脚本里单独处理。这种返回形式的差异正好反映了两个算法世界观的差异MedoidShift 从代表出发结果天然自带解释性QuickShift 从密度连通出发结果需要额外一步阈值决策才能落到簇的粒度上。README 里如果写了运行说明一般也会强调这一步剪枝参数的重要性——它是 QuickShift 唯一的、也是最关键的自由参数。4.2 从 clusters_comparison.png 读出两种算法的真实性格对比图通常左边是 MedoidShift右边是 QuickShift点的颜色代表簇归属。读这种图有三个关注点同一簇是否被切碎簇边缘是否有拖尾单点以及两种算法对噪声点的着色是否稳定。把这三点对应到机制上就能得出结论。对比项MedoidShiftQuickShift代表点性质簇内真实样本medoid密度局部极大点不强制输出坐标收敛方式多轮迭代漂移直至稳定单轮父节点搜索阈值剪边典型瓶颈每轮邻域重扫描迭代次数不可预知密度估计参数敏感高维距离退化异常值响应代表点落在稠密区异常值被边缘化异常值常成为低密度根点容易单独成簇典型适用中小规模、需要可解释簇标签的场景大规模、高维、快速粗聚类读图时你会看到 MedoidShift 对不规则形状的簇往往保留得比较完整因为它的邻域是局部的迭代漂移只会在局部稠密区内部传播不会像全局质心那样把形状拉平QuickShift 在密度均匀的球形簇上边界干净利落但一旦数据里存在密度渐变区域剪枝阈值 τ 稍微调不准就容易出现高密度区被切碎、低密度区被粘连的连锁反应。这张图能直观说明一个观点没有绝对更优的算法只有对特定数据假设更贴合的选择。5. 实战避坑MedoidShift 与 QuickShift 最容易翻车的 5 个细节5.1 MedoidShift 把所有点吸进同一个簇现象不管数据长什么样运行后所有样本都指向同一个代表点簇数等于 1。原因radius设得比数据整体尺度还大邻域图变成完全连通图。MeDoIDShift 的邻居投票在完全图里退化为全局求一次 medoid——它找到的全局代表点最终把所有人都拉了过去这和 K-Means 里 K1 是等效的退化情形。解决用成对距离的分位数来定radius不要拍脑袋。我一般先算所有样本两两距离取其中位数作为初始值再以 ±20% 为步长扫几遍看簇数目随半径变化的曲线。曲线出现平坦平台的那段就是值得用的半径区间。5.2 QuickShift 的簇数量和样本数一样多现象结果里几乎每个样本自成一簇没有任何聚合等价于没聚类。原因密度估计失效。比如用第 k 近邻距离倒数估密度时 k 取得太小k1每个点在自己的最近邻关系里都成了局部极大密度比较就退化成了随机大小关系几乎所有点都成了根节点。解决把 k 提高到数据点数的对数量级以上经验值是 k 取max(10, int(log2(n) * 2))。同时加一道密度兜底低于全局密度 1% 分位的根节点不开启新簇改为并入最近的父节点。剪枝在工程上是必须的不能省。5.3 高维稀疏数据下 QuickShift 退化成一堆碎片现象数据维度到几百上千后QuickShift 划分的簇毫无意义每个簇像是流形上切下来的一块碎骨头。原因L2 距离在高维空间趋同最近邻与最远邻的距离之比接近 1密度估计失去对比度。整个算法的地基——密度高的点靠得近——在高维下不成立了。解决先做降维或特征筛选把有效维度压到几十以内再跑 QuickShift或者改用余弦相似度配合维度归一化。我常用的核验手法是对标准化后的数据算一次成对距离直方图如果直方图是一根细柱方差极小说明当前距离度量对这个问题已经失效换什么聚类都白搭。5.4 MedoidShift 多次运行结果不稳定现象同一份数据、同一份代码两次运行得到不同的簇边界。原因迭代时逐样本做在线更新平局打破规则不固定。当两个候选代表点的距离总和完全相等时实现里的np.argmin返回第一个最小索引而数据的读入顺序一旦被打乱这个第一个就会变最终标签也跟着变。解决在迭代前固定样本遍历顺序对距离和相等的情况强制取索引较小的那个代表点。更稳妥的做法是跑多次参数扫描用多数投票集成最终标签——把出现次数最多的标签组合作为确定性结果。5.5 真实数据上复现不出 README 里的效果现象自己的业务数据一跑两种算法的结果和 README 里贴的对比图差距巨大。原因README 里的对比图通常是构造数据加参数调优后的最佳快照——比如对两三个球形簇或弯月形簇专门调好了radius和k。真实数据的特征尺度差异巨大类别数未知分布也远非各向同性拿默认参数直接上不可能复现出那张图。解决先做标准化去均值、单位方差再做小规模参数网格扫描。注意观察簇数目的变化趋势如果簇数在一定参数范围内都很稳定说明聚类结果是结构性的如果簇数临界处剧烈跳变说明数据本身没有清晰的簇结构换算法也救不回来。我把它当作聚类任务的第一课先确认数据里有没有簇再讨论用哪个算法。6. 算法选择的设计取舍你真正要付出的成本是什么走到这里应该能看出来选 MedoidShift 还是 QuickShift本质上不是选一个更好的算法而是选一种愿意承受的代价。MedoidShift 的代价是迭代它用多轮邻域扫描换取代表点一定是一个真实样本的强约束这约束让聚类结果可解释、对异常值迟钝但代价是迭代次数不可预知radius 设置不当就可能全局吞并。QuickShift 的代价是密度场假设它用单轮寻父换取速度把聚类问题压缩成一次海拔标定 父节点搜索但密度估计对 k 和距离度量高度敏感高维下整个假设都会崩塌。这两种代价处在跷跷板的两端没有免费午餐。那怎么验证自己到底该付出哪种成本我现在的习惯是强制走一遍小样本参数扫描而不是直接拿全量数据跑from medoid_shift_ import medoid_shift # 先在小样本上扫半径看簇数-半径曲线是否出现平台 for radius in np.percentile(pairwise_dist, [10, 30, 50, 70, 90]): labels medoid_shift(X_sample, radiusradius) print(fradius{radius:.3f}, clusters{len(set(labels))})曲线稳定在某个簇数上说明数据确实有可识别的簇结构曲线剧烈振荡那问题不在算法而在数据。这个流程走完我才会运行完整脚本把 MedoidShift 和 QuickShift 的结果并排画出来再回头比对那一张 clusters_comparison.png。聚类的选择说到底是一道假设对齐题数据形状适合密度场就用 QuickShift 的速度簇里存在真实业务含义需要代表样本就用 MedoidShift 的解释性。从那以后我每次拿到聚类任务都会强制先走一遍标准化 → 距离分布检查 → 小样本参数扫描 → 簇稳定性验证的流程再决定用哪个算法。这套流程帮我避开过太多次把参数玄学当算法缺陷的误判——希望帮到你。本文还有配套的精品资源点击获取
