简介MedoidShift与QuickShift是两种主流的无监督聚类算法常用于图像分割、数据降维与特征聚类等任务。这份资料面向机器学习初学者和需要做聚类算法选型的开发者以可运行的Python代码为主线清晰说明了两类算法的迭代逻辑、密度敏感特性和适用场景。压缩包共包含5个文件其中三个Python脚本分别实现算法主体、演示调用与结果可视化一张PNG聚类对比图直观展示两种算法在不同分布数据上的划分效果一份Markdown文档对代码结构和运行方式做了必要说明整个资源包仅429KB轻巧易用。目前已有三百一十八人浏览学习。运行演示后读者可以对比观察MedoidShift对不规则簇和离群点的稳健性以及QuickShift在大数据量和高维空间中的速度优势同时借助聚类对比图还能深入理解两者在抗噪能力、参数敏感度及聚类稳定性上的差别这对于处理真实数据时的算法选择尤其关键。这份资料既适合作为课程设计的参考实现也可为实际项目中的算法选择提供实证依据。1. MedoidShift 与 QuickShift命名的背后是两套密度聚类策略当你手里是一批不规整的真实样本比如社区服务需求分类里整理出的工单关键词向量KMeans 给不出落在样本上的簇中心DBSCAN 又卡在邻域半径上。MedoidShift 和 QuickShift 是这一族聚类算法里的两种解法一个把 Mean Shift 的漂移中心钉回真实样本一个用“指向最近高密度点”的一次建树替代多轮迭代都保留密度聚类的语义也都能给出可解释的分组和中心。这个组合适合特征维度不高、密度起伏明显但又需要把簇中心讲给业务方听的场景。下面我会用 numpy/scipy 从定义写到可运行代码把 h、k、δ 这些参数讲清楚顺带记录几个调参踩坑的血泪记录。2. 先搞清楚谁在漂移Mean Shift 慢在哪MedoidShift 和 QuickShift 改了什么2.1 均值漂移为什么贪心又慢收敛点落在空白处Mean Shift 的做法是先估计核密度再把每个样本或每个候选点沿着密度上升方向移动公式上就是用当前点周围样本的加权平均位置作为新位置反复迭代。这个方向在当前核窗口内总是向上走的所以叫“漂移”。实际跑起来有两点让人难受一是计算量每轮迭代每个点都要扫一遍窗口内的邻居数据量稍大就非常吃力二是收敛点往往处在特征空间的空白处不是任何一条真实样本后续想解释“这一类代表是谁”时只能拿最近邻去凑。这也是“均值”这个词的代价均值天然会落在数据中心而不是数据点上。周志华的《机器学习》里把这类做法归进密度聚类与 DBSCAN 并列但 DBSCAN 靠“密度直达/可达”关系划分连通域Mean Shift 靠“沿密度上升方向找峰”两者的边界和中心语义完全不同。到这里思路就很自然了如果不想要连续漂移能不能让中心就是样本点本身如果不想一轮一轮漂能不能一步到位把点指向该去的峰。2.2 MedoidShift 把中心钉回样本邻域里挑一个代替“平均”MedoidShift 的做法是保留“向窗口内高密度位置移动”的框架但把目标从加权平均位置换成样本点。严格定义里这个目标取邻域内的 medoid窗口中到其他样本点距离总和最小的那个样本工程实现里更常用的是直接取邻域内密度最高的样本点两者都能保证迭代终点是真实样本也让“这个簇的代表是谁”有了明确指向。每步移动写成当前点从它的 h 半径窗口里挑一个符合条件的样本把编号记下来下一轮再从新位置继续挑直到挑出的编号不再变化。这个改动消掉了两个痛点。第一中心可解释聚类结束后可以直接输出中心样本的原始记录比如工单主键或用户 ID业务方要复核时不需要看高维坐标。第二迭代过程变成在样本之间跳转配合“目标点密度严格大于当前点”的约束后无环收敛更直接。代价是需要额外维护密度值而且 h 的选择比传统 Mean Shift 更敏感因为每一次跳跃都可能直接跳到另一个局部峰上——这点在避坑部分会专门展开。2.3 QuickShift 用一条父边代替多轮漂移最近高密度点建树QuickShift 换了个思路不再让每个点沿着密度上升路径一步一步走而是直接为每个点找“密度比我高、离我最近的样本”作为父节点密度最高的点没有父节点成为根。这样全局构成一棵树严格说是若干棵树组成的森林任何一个点沿父链向上最终都会爬到某个密度峰。聚类时只要把“父节点到我这条边”按距离阈值切掉剩下的连通块就是簇边权超过阈值的节点自己成为新根。之所以叫“一次建树”是因为建树过程没有循环迭代剩下的只是裁剪。复杂度上如果老老实实对每个点扫全部更高密度样本仍然是 O(n²)用 KDTree 在邻域内查候选可以把常见规模压到近线性。对比路径QuickShift 的树结构还能直接看两簇间的桥接距离这在调参时比黑匣子的迭代过程好用得多。对照项MedoidShiftQuickShiftDBSCAN聚类本质样本向局部高密度样本漂移构建高密度最近邻树再剪枝密度直达/密度可达连通域簇中心有真实样本点根节点为密度峰可视为中心无明确中心主要参数带宽/半径 h密度带宽 h、邻域查询数 k、剪枝阈值 δeps、min_samples计算特征每轮依赖窗口内邻居数建 KDTree 后近邻查询近邻查询约 O(n log n)适合场景中等规模、要解释中心规模偏大、图像超像素形状任意、密度相对均匀选型时我一般看三件事是否需要“代表样本”来解释簇是就选 MedoidShift数据量大到迭代不动或想先看树结构判断参数就用 QuickShift想要形状自由度且愿意调 epsDBSCAN 也可以但它给不出中心。多数项目里两者不是互斥关系——先用 QuickShift 做粗分和结构诊断再用 MedoidShift 在每个簇里取中心样本是我推荐的一套组合。3. 用 NumPy 手写 MedoidShift从密度估计到样本间跳转3.1 最小可运行版本密度、窗口、朝高密度点跳先给一个可以直接复制的实现。密度部分我用“h 半径内样本数”做近似方便解释想更平滑就换成下个小节末尾的高斯核版本。import numpy as np from scipy.spatial import cKDTree def medoid_shift(X, h, max_iter30): X: (n, d) 特征矩阵h: 邻域半径。返回每个样本最终停留的样本索引。 X np.asarray(X, dtypefloat) n X.shape[0] tree cKDTree(X) # 1. 用窗口内点数近似密度点数越多这个位置越像局部峰 density np.zeros(n) for i in range(n): density[i] len(tree.query_ball_point(X[i], h)) # 2. 每个样本从当前位置出发跳到 h 窗口内密度更大的样本点 y np.arange(n) for _ in range(max_iter): moved 0 for i in range(n): cand tree.query_ball_point(X[y[i]], h) # 严格大于防止两个密度相等的点互相跳 better [j for j in cand if density[j] density[y[i]]] if not better: continue target max(better, keylambda j: density[j]) if target ! y[i]: y[i] target moved 1 if moved 0: break return y这段代码的核心逻辑是“密度单调上升”。因为每步只接受密度更高的目标链路上必然无环多数情况下 20 轮以内就能停下来。max_iter 设 30 是保守值如果连续多轮 moved 都很大说明 h 窗口把多个峰连到了一起这会在后面避坑章节再讲。query_ball_point 返回邻域内所有样本编号所以候选集天然限制在半径 h 内。整体复杂度是 O(n·k·iter)k 是平均窗口大小数据均匀时远小于全量 O(n²)。这个版本对 n 到 2 万、d 到几十都还算能跑再大就建议先抽样确定 h再回到全量跑一次而不是换暴力矩阵。想严格按 medoid 语义来把 target 的选法换成在 better 里取“到窗口内其他样本距离和最小”的那一个。代价是每次要额外算候选点到窗口内所有点的距离适合 n 很小的场景我不会拿它跑大数据集。3.2 换高斯核密度让 h 从“硬半径”变成核宽邻域计数版本容易在窗口边界处产生锯齿两个样本隔一个 h 的距离就可能得到完全不同的密度。更常见的做法是用高斯核做核密度估计h 变成标准差窗口外样本按指数衰减参与而不是一刀切。def kde_density(X, h): 高斯核密度估计h 为标准差截断到 3 个 h。 tree cKDTree(X) density np.zeros(len(X)) for i, x in enumerate(X): idx tree.query_ball_point(x, h * 3) w np.exp(-np.sum((X[idx] - x) ** 2, axis1) / (2 * h * h)) density[i] w.sum() return density注意 h 的含义变了。邻域计数版本里 h 是半径高斯核版本里 h 是标准差所以同样的 h 在高斯核下邻居范围其实是 3h。换用这个密度函数后medoid_shift 里的移动目标选法不变直接把 density 替换掉即可。实际调试中我习惯先用计数版本看 h 的大致量级再换高斯核微调能省不少时间。3.3 结果解读与 h 的初始值从“簇数-带宽”阶梯图开始跑完返回的 y 是每个样本最终所在的中心样本索引。把 y 去重就能得到簇中心给每个样本打簇标签就是 y 本身。以社区服务需求分类为例如果特征是从工单描述里提的关键词向量那么中心样本就是一条真实工单业务方复核时直接看这条工单就能明白聚类含义。h 是这类算法最不好拍脑袋的参数我一般用“第 k 近邻距离的分位数”定初值k 取 0.02 倍样本数h 取这些距离的 90 分位。意思是每个样本窗口里平均能覆盖约 2% 的样本保证密度有起伏。确定 h 后再画一张“h 变化 → 簇数变化”的阶梯图取中间平台期的 h 作为最终值而不是只看一个点的结果。注意特征必须先做标准化否则窗口半径会被量纲大的维度主导聚出来的簇只是某一列的数值分段。max_iter 和收敛条件不需要太精调只要保证 moved 降为 0 就好。如果总是超过 30 轮才收敛优先怀疑 h 太大而不是加大迭代次数。4. 用 QuickShift 建一棵密度树KDTree 实现与 δ 剪枝4.1 建父边在密度更高的点里找最近的一个QuickShift 的树由父边决定。每个点找“密度比我高、距离我最近”的样本做父节点找不到就说明它是局部密度峰成为根。最朴素的实现是每个点扫一遍全部样本找更高密度点O(n²)我用 KDTree 的 query 查固定 k 个近邻在这 k 个近邻里找复杂度会低很多。def build_parent_knn(X, density, k30): 返回 parent 和 edge_distparent[i] -1 表示 i 是根。 tree cKDTree(X) n X.shape[0] parent -np.ones(n, dtypeint) edge_dist np.full(n, np.inf) for i in range(n): # 第 0 个近邻是它自己所以查 k1 dists, idx tree.query(X[i], kmin(k 1, n)) best, best_d -1, np.inf for d, j in zip(dists[1:], idx[1:]): if density[j] density[i] and d best_d: best, best_d j, d parent[i] best edge_dist[i] best_d return parent, edge_distk 的含义不是聚类簇数而是“最多检查几个近邻来寻找高密度父节点”。k 太小父边会被漏掉点过早成为根k 太大查询开销上升而且 KDTree 在高维下的优势会退化。我一般从 30 开始观察“根节点比例”如果超过 5% 的点没有父节点先怀疑 k 不够再把 k 加大到 50100。这个函数也暴露了 QuickShift 的一个弱点它依赖密度排序的局部性。如果当前点和更高密度的父节点之间隔着很多低密度点而 k 又不大父边就会连到更远的点上边权虚高后面剪枝时容易切成碎片。对明显呈长链分布的数据我会先把 k 设到 100再对比根比例做决定。4.2 剪枝成簇边权大于 δ 就断开树建好后聚类就变成剪枝问题。父边距离 edge_dist[i] 表示点 i 到父节点的跨越距离这条边超过 δ就认为跨到了另一个密度峰剪断它让 i 成为新根。剪完后每个样本沿未断开的父链爬到根同根样本属于同一簇。def cut_tree(parent, edge_dist, delta): 按阈值剪枝返回每个样本的簇标签。 parent parent.copy() for i in range(len(parent)): if parent[i] 0 and edge_dist[i] delta: parent[i] -1 # 路径压缩求根 root {} def find_root(i): if i not in root: p i while parent[p] ! -1: p parent[p] root[i] p return root[i] labels np.array([find_root(i) for i in range(len(parent))]) # 把根编号压缩成 0..C-1 _, labels np.unique(labels, return_inverseTrue) return labelsdelta 越大越多的边被保留簇越粗delta 越小树被切得越碎。这里有一个容易看走眼的地方cut_tree 修改 parent 时根节点的 parent 本来就是 -1不会被误伤但剪枝后新产生的根比如边权超阈值的节点也要能在 find_root 循环里正常停下所以 while 条件必须是 parent[p] ! -1而不是“有没有访问过”。写条件时手滑成访问标记会让部分点陷入死循环。4.3 δ 怎么定先看边权直方图别瞎猜δ 是 QuickShift 相对好调的参数因为边权是建树后已经算好的数值可以直接画分布再选切点。父边距离小的边是簇内部连接距离大的边是跨峰跳跃理想情况下直方图应该呈现双峰取谷底即可。import matplotlib.pyplot as plt valid edge_dist[parent ! -1] plt.hist(valid, bins100) plt.xlabel(edge distance) plt.ylabel(count) plt.show()如果直方图是单峰说明 h 或密度估计没把密度差异拉开此时调 δ 作用不大要先回头改 h。单峰但确实需要分割时我习惯取 8590 分位数作为 δ再根据簇数量反馈微调。实际项目中QuickShift 参数的调试顺序是固定的先标准化特征再定 h然后看建树后的根比例判断 k最后才用直方图定 δ。反过来调经常变成“调 δ 调半天其实是 h 选错了”。提示如果数据量到几万以上build_parent_knn 里的循环仍然会成为瓶颈。折中做法是先用 5000 条样本把 h、k、δ 的合理区间定下来再在这个区间里全量跑一次完整聚类。5. MedoidShift 与 QuickShift 实战避坑5 条踩坑记录这五个问题里前两个是参数设置造成的中间两个和数据形态有关最后一个是资源管理问题。它们有一个共同特征表面症状都像“算法不收敛”或“聚类质量差”但改了对应参数之后症状立刻缓解。5.1 两个高密度峰互相跳中心落在另一簇的峰上现象MedoidShift 迭代结束后部分样本的中心不是本簇的点而是隔壁密度更高峰上的样本簇内样本被“吸”走。原因h 选得过大当前点的窗口把另一簇的高密度峰包了进来而“选窗口内密度最大样本”的规则不会判断峰是否属于本簇。解决把 h 缩小让窗口尽量只覆盖本簇内部同时画簇数-h 阶梯图选择平台期的 h。如果业务上必须用大 h就给跳转加约束只接受与当前点在窗口内同属一个连续高密度区域的样本这需要额外做连通性检查成本高我一般直接缩小 h 而不是加复杂约束。5.2 QuickShift 无父节点比例奇高簇数虚高现象叶子点大量直接成为根簇数比预期多一个数量级树结构图看起来全是孤立点。原因build_parent_knn 的 k 太小每个点当前的 k 个近邻里恰好没有密度更高的样本。这在低密度区域尤其明显因为最近邻可能全是与自己密度差不多的点。解决把 k 从 30 提到 50100并统计无父节点比例比例超过 5% 就继续加 k 或怀疑密度估计不平滑。注意 k 加大会显著增加建树时间先用 3000 点小样本测试它的影响再决定全量参数。5.3 δ 切不断两峰之间的长链桥现象QuickShift 剪枝后两个明显的簇还是被一条细长链连在一起怎么调 δ 都没用调大合并、调小碎块。原因两个高密度峰之间如果存在一条连续的低密度样本链链上相邻样本的父边距离都很小δ 无法在不切碎链的前提下断开它们。这是 QuickShift 的固有特性不是参数没调好。解决改用 edge_dist / h 这种相对距离做剪枝阈值或者先对高密度骨干样本聚类再把剩余样本按最近骨干归属。我一般先在密度最高的 1% 样本上建树剪枝得到粗结构再回贴全体样本能绕开长链桥问题。5.4 忘记标准化聚类退化成单维分段现象聚类结果跟某一列数值的区间完全对应其他特征几乎没有作用簇中心事后看只是按那一列取了几个典型值。原因特征量纲不同距离计算里方差大的维占绝对主导密度排序自然被它绑架。这个坑在社区服务需求分类这类场景里出现过年龄字段数值跨度大工单关键词向量稀疏距离几乎全被年龄决定做出来的“人群分群”其实是“年龄段分箱”。解决跑算法前用 StandardScaler 或 min-max 归一化加这一行代码就是后悔药聚类后还要检查每个簇在各维上的均值差若只有单一维显著考虑该维降权或去掉。5.5 直接上全距离矩阵数据没跑完就先内存溢出现象n 到 2 万左右程序停在矩阵构造阶段报 MemoryError或者系统开始疯狂换页看起来像死机。原因教程里的朴素写法要用 pdist 构造 n×n 距离矩阵2 万点就是 3 亿多个浮点数内存轻松超过 2GB这个复杂度没有回旋余地换 float32 也只是延后崩溃。解决全程使用 cKDTree 版本的实现避免物化距离矩阵先抽样调参再全量跑。另一个实用办法是把数据随机拆成多个子集分别调参等参数区间确定后再合并结果虽然会损失个别边界簇但至少不会让机器先倒下。6. 进阶一招QuickShift 粗分、MedoidShift 提中心的超像素组合6.1 用同一套代码跑图像超像素顺便验证聚类质量图像超像素本质也是聚类把像素点按“位置 颜色”特征分组组内尽量紧凑组间尽量贴合成像边界。我常用 QuickShift 做粗分因为它的树结构天然适合空间邻接不会像 KMeans 那样产生跨越图像两端的簇。from skimage import io, transform from sklearn.preprocessing import StandardScaler img io.imread(demo.png).astype(float) # 长边缩到 160 以内控制参与聚类的像素数 scale 160.0 / max(img.shape[:2]) if scale 1.0: img transform.resize(img, (int(img.shape[0] * scale), int(img.shape[1] * scale))) h, w img.shape[:2] xs, ys np.meshgrid(np.arange(w), np.arange(h)) # 假设是三通道彩色图灰度图取单通道即可 feat np.column_stack([xs.ravel(), ys.ravel(), img[..., 0].ravel(), img[..., 1].ravel(), img[..., 2].ravel()]) feat StandardScaler().fit_transform(feat) density kde_density(feat, h2.5) parent, edge build_parent_knn(feat, density, k50) # δ 取边权 90 分位超像素偏碎一点更适合后续处理 delta np.percentile(edge[parent ! -1], 90) labels cut_tree(parent, edge, delta).reshape(h, w)注意超像素验证方式和普通聚类不太一样如果手上有带掩膜的标注图最直接是算调整互信息 AMI但要固定超像素数量后再比否则数量差异会误导结果。没有标注时就看两个指标超像素边界是否贴合图像边缘以及每个超像素内部的 RGB 方差是否够小。我常用一个更简单的检查统计超像素面积分布如果出现大量只含几个像素的碎块说明 δ 偏小或者 h 偏大。组合用法上QuickShift 只负责把图切块每个块的代表色可以用块内均值但如果下游要做模板匹配我更推荐在块内再跑一次 MedoidShift取出真实存在的像素作为代表。这套组合在特征维度高、样本量大时尤其划算先快速切开再局部精取中心不需要修改任何一处核心代码。这些年我的习惯是任何密度聚类项目都先跑一遍 QuickShift 看树和边权直方图再决定要不要换 MedoidShift 或 DBSCAN——树结构给出的诊断信息比瞎猜参数有用得多。希望帮到你。本文还有配套的精品资源点击获取