简介MedoidShift 与 QuickShift 两种聚类算法的完整 Python 实现与演示资源面向机器学习初学者以及需要在项目中快速选型聚类方法的开发者聚焦无监督学习中中心点选取、密度敏感聚类和高维数据效率等常见问题。压缩包共 5 个文件包含两个算法的核心实现脚本、演示程序、说明文档以及聚类结果对比图整体仅 429KB轻量易读。已有 319 人浏览学习适合作为算法原理理解与实践验证的入门材料。通过阅读并运行代码可以直观掌握 MedoidShift 通过迭代更新 medoid 形成稳定聚类的机制以及 QuickShift 借助概率树完成快速密度搜索的思路对比图能帮助理解两者在不同簇形状、噪声干扰和数据集规模下的表现差异从而在实际项目中更合理地选择聚类方案。1. 从 Mean Shift 分支到 MedoidShift、QuickShift一类把“中心”换成真实样本点的聚类算法做图像分割、异常检测这类活儿时数据形态经常很不规整簇不是椭球类别边界模糊还带着不少噪声。K-Means 和 GMM 这种“带质心的聚类算法”天然把结果往圆形拉边界归属一塌糊涂。MedoidShift 和 QuickShift 这类基于密度模式的聚类算法不预设簇形状只是沿着密度上升方向把每个样本归到局部密度峰值附近聚类数目也不用预先指定。它们同源 Mean Shift区别在于MedoidShift 把每步更新从“特征空间重心”换成真实样本点QuickShift 直接沿着最近的高密度邻居跳。适合处理维度几十以下的中小规模点云、图像超像素和簇数量未知的数据。2. MedoidShift 与 QuickShift 的密度上升逻辑均值点、中位数点与最近点的三种移动策略2.1 一个统一框架先在特征空间里估计密度再顺着坡度走到“峰”先立一个基础框架否则后面参数全乱。给定 N 个样本我们需要对每个位置估计局部密度最常见做法是高斯核 Parzen 窗ρ(x) Σ_j exp(-||x - x_j||² / (2σ²))σ 就是带宽它决定“多近才算一个群体”。Mean Shift 家族所有算法都建立在这样一张密度图上每个样本点从当前位置出发沿着密度上升的方向移动最后停到某个局部极大值——这个极大值就是“模式mode”一个模式代表一个簇。关键区别只在“如何判断上升方向”。Mean Shift 把窗口内样本的坐标均值作为下一步中心这是数学上最光滑的做法MedoidShift 把这个中心替换为窗口内真实存在的某个样本点QuickShift 则彻底砍掉迭代直接从每个点跳到它的“最佳父节点”一气呵成。三者产出结果相似但鲁棒性、计算代价和调参手感差得很远。2.2 MedoidShift每次移动都落脚到一个真实样本上给特征空间加几个噪点然后跑一遍 Mean Shift 就会发现均值中心可能停在一个不属于任何一个实际观测点的位置。这在聚类结果解释上有点尴尬——簇中心是个“虚拟样本”没法直接拎出来看它长什么样。MedoidShift 就是冲着这点改的。它把传统 Mean Shift 的“均值步”替换为两步在带宽 σ 范围内找到当前点的所有近邻组成“足迹footprint”在足迹内选择一个真实样本点作为新的“代表”这个样本就是 medoid常见两种定义是“到足迹内其他样本距离和最小”或“离足迹重心最近”。每个样本沿着足迹中 medoid 的链条移动直到落脚点不再变化。因为每一步都落在真实样本上最终得到的模式点一定来自原始数据集这在小样本、图像分割这类需要回看“簇中心长什么样”的场景中非常实用。代价是它对初值敏感而且迭代过程比 QuickShift 慢得多。2.3 QuickShift不做迭代直接用“父节点链”一把走完QuickShift 是 Vedaldi 和 Soatto 在 2008 年提出的算法目的是在保持 Mean Shift 聚类质量的前提下把速度提上去。它放弃迭代改为一次构图先给每个点算局部密度然后对每个点找密度高于它、并且“单位距离密度提升比”最大的那个点作为父节点parent(i) argmax_j (ρ_j - ρ_i) / ||x_j - x_i||其中 ρ_j ρ_i直观理解是每个点朝“近处且有更高密度”的点迈一步而不是朝远处的高密度峰跳。每个点的父节点只有一个所以全体样本构成一片森林——每个局部密度峰是一条链的根。聚类时把每个点沿父链上溯到根挂在同一个根下的点归为一个簇。这个设计绕开了迭代收敛的问题计算也比 MedoidShift 快一个量级。代价是它对噪声更敏感一条噪声链只要每个点都能找到一个更高密度邻居就可能把两个本应分离的簇串成一条。2.4 MedoidShift 与 QuickShift 的复杂度与适用形态对比动手前先看这张对比表决定在什么场景选谁维度MedoidShiftQuickShift每个点的移动目标窗口内的真实样本medoid密度更高且距离提升比最大的父节点是否迭代迭代收敛到模式点单次构图无迭代密度峰值位置一定是原数据集中的样本根点一定是原数据集中的样本聚类结果形式每个样本一个终点索引森林结构按根聚簇抗噪声能力较好较差容易产生链式串簇时间成本迭代次数 × 局部距离矩阵一次近邻搜索 一次父链上溯典型数据规模几千到几万样本几万到几十万样本一句话选型样本量在万以下、需要稳定且可解释的模式点优先 MedoidShift数据上了十万、又不需要精细边界QuickShift 更划算。3. 用 Python 把 MedoidShift 和 QuickShift 跑起来核心代码与最小参数集3.1 最小实现用 NumPy 和 SciPy 写一个可跑的 MedoidShift下面给出一段可以照抄的最小实现用 scipy.spatial 的 cKDTree 做近邻搜索避免全量距离矩阵。以“距离和最小”作为 medoid 的工程化定义。import numpy as np from scipy.spatial import cKDTree class MedoidShift: def __init__(self, bandwidth1.0, max_iter50, tol1e-6): self.bandwidth bandwidth # 邻域半径决定簇的尺度 self.max_iter max_iter # 安全上限防止不收敛 self.tol tol # 浮点比较容忍度 def fit(self, X): n X.shape[0] tree cKDTree(X) medoids X.copy() # 每个样本从自身出发 candidate_idx np.arange(n) for it in range(self.max_iter): moved False for i in range(n): idx tree.query_ball_point(medoids[i], rself.bandwidth) # 窗口内样本个数太少时保持原地不动 if len(idx) 2: continue window X[idx] # 足迹内的真实样本 # 计算窗口内两两距离矩阵选“到其他点距离和最小”的样本 diff window[:, None, :] - window[None, :, :] dist_mat np.linalg.norm(diff, axis2) new_idx idx[np.argmin(dist_mat.sum(axis1))] # 用样本索引判断是否还在移动 if not np.allclose(medoids[i], X[new_idx], atolself.tol): medoids[i] X[new_idx] moved True if not moved: break # 将每个样本的最终 medoid 映射为簇编号 unique_medoids {} labels np.zeros(n, dtypeint) for i in range(n): key tuple(np.round(medoids[i], decimals6)) if key not in unique_medoids: unique_medoids[key] len(unique_medoids) labels[i] unique_medoids[key] return labels, medoids代码逻辑说明每个样本点从自己出发用 query_ball_point 找半径内近邻然后在这个足迹内算距离矩阵选出“距离和最小”的样本作为新落脚点。用 np.allclose 判断是否还在动当所有点都不再找到新的 medoid 时停止。最后把坐标相同的终点合并成簇编号。参数说明bandwidth 是最关键的参数它直接决定足迹大小一般按数据标准差的比例给初始值max_iter 设 50 对大多数二维数据够用高维数据可能需要 100tol 是浮点比较容忍度默认 1e-6 偏严若输出显示迭代频繁触发上限先放宽到 1e-4 试试。3.2 QuickShift 最小实现密度估计、父节点搜索与根节点聚簇QuickShift 的实现比 MedoidShift 短核心在密度估计和父节点选择。下面是可直接运行的最小版本。import numpy as np from scipy.spatial import cKDTree def quick_shift(X, sigma1.0): n, d X.shape tree cKDTree(X) # 1) 高斯核密度估计sigma 就是带宽 rho np.zeros(n) for i in range(n): idx tree.query_ball_point(X[i], rsigma) dist np.linalg.norm(X[idx] - X[i], axis1) rho[i] np.sum(np.exp(-dist**2 / (2 * sigma**2))) # 2) 每个点找一个密度更高的最佳父节点 parent np.full(n, -1, dtypeint) for i in range(n): idx tree.query_ball_point(X[i], rsigma) # 只保留密度严格高于当前点的候选者 candidates [j for j in idx if rho[j] rho[i] 1e-12] if len(candidates) 0: continue # 当前点就是局部峰作为树根 dist np.linalg.norm(X[candidates] - X[i], axis1) # 最大化“密度提升 / 距离”即近处有提升的优先 score (rho[candidates] - rho[i]) / dist parent[i] candidates[np.argmax(score)] # 3) 沿父链上溯到根同一个根归为同一个簇 labels np.zeros(n, dtypeint) root_id {} for i in range(n): cur i vis [cur] while parent[cur] ! -1: cur parent[cur] vis.append(cur) root vis[-1] if root not in root_id: root_id[root] len(root_id) labels[i] root_id[root] return labels, rho, parent代码逻辑说明密度估计用高斯核落在 sigma 邻域内的点按距离加权父节点搜索在邻域内进行限定于密度更高的点用“密度差 ÷ 距离”作为打分标准得分最高的成为父节点。这样每个点都指向近处一个密度提升最快的方向。参数说明sigma 同时是密度估计的带宽和父节点搜索半径含义比 MedoidShift 的 bandwidth 更重建议先按数据的绝对中位差MAD来粗调不要直接拿标准差套。最后的上溯过程由于每个点只沿父链走最坏情况是 O(n²)数据量大时可以加记忆化缓存每个点已算好的根。3.3 两个算法跑完怎么判断结果有没有意义不管用哪种算法跑完第一步不是看轮廓系数而是直接看数据分布和簇标签的叠加图。在二维数据上画散点图把不同标签点成不同颜色检查有没有一条细长的串把多个簇连起来这是 QuickShift 的典型噪声链簇内心是不是落在密度最高的区域而不是偏向某个边缘落在尾部的点是否大量被分成独立小簇如果是说明 sigma 太小。这一步很朴素但极其有效。跑通代码只是开始真正的调参工作从这里才开始。4. 参数怎么设带宽 sigma、距离度量和迭代停止条件的定量把握4.1 带宽 sigma影响簇数的最敏感旋钮也是最玄学的参数两个算法里带宽都是真正的“灵魂参数”它对结果的影响几乎是单调的sigma 越小密度峰越多簇数越多sigma 越大密度图越平滑簇数越少直到整个数据变成一个簇。这里的经验是先做一个“簇数曲线”设一组合适的扫描范围比如从 0.2 倍到 2 倍数据标准差按对数间隔取 10 组每组跑一次算法记录簇数找出簇数从“剧烈下降”转为“平稳缓慢下降”的拐点选拐点附近的 sigma。这个做法比反复试错快得多。二维数据上sigma 取 0.51 倍数据标准差通常是合理起点高维数据上同样的 sigma 在欧氏距离下覆盖的样本数会变少所以要么先把维度降到 20 以下要么改用余弦距离再调整 sigma。4.2 距离度量的选择高维下欧氏距离失效是第一个坑MedoidShift 和 QuickShift 都严重依赖距离度量。维度在 20 以下时欧氏距离没问题维度超过 50 以后所有点之间的距离几乎相等密度估计变得没有区分度聚类结果接近随机。常见的做法是先对特征做 PCA 降维到 1632 维再跑聚类如果特征是文本向量或用户行为向量更推荐余弦距离。需要说明一个细节把欧氏距离换成余弦距离后带宽的含义会变。余弦距离的取值范围是 [0, 2]sigma 就不能按标准差给了通常从 0.1 开始扫描。这个变化很容易被忽略很多人换了距离度量却还沿用原来的 sigma结果一塌糊涂。4.3 MedoidShift 的迭代停止条件索引稳定比坐标稳定更可靠MedoidShift 收敛判断有一个很容易踩的坑直接比较坐标会因为在两个 medoid 之间震荡而永不收敛尤其是数据点密集的区域。我在实践里的做法是双条件并下坐标变化小于 tol默认 1e-6连续两次迭代中所有样本点的 medoid 索引不变。只靠坐标判断浮点误差会让两个点来回跳只靠索引判断可能因为索引提前稳定而错过更好的落脚点。两个条件同时满足再停max_iter 设为 50 一般够用但数据量上万后可能需要放宽到 100。日志里如果看到 max_iter 频繁触顶优先放宽 tol而不是无限加大迭代上限。4.4 什么时候用 MedoidShift什么时候用 QuickShift一句话总结我的选择逻辑要解释、要稳定、数据少选 MedoidShift要速度、要超像素、数据多选 QuickShift。具体展开MedoidShift 的每个簇中心都是真实样本在医疗数据、工业质检这类需要回看“代表样本长什么样”的场景里优势明显但它要迭代样本量上万后速度明显变慢。QuickShift 单次构图速度和解晰度更适合图像超像素分割、大规模点云聚类但它输出的森林容易受噪声链影响聚类边界不如 MedoidShift 干净。此外如果你最终要做的是“一个簇一个代表样本”的后续分析MedoidShift 的终点天然就是代表样本QuickShift 还要额外在簇内再做一次 medoid 选择。5. 避坑与常见问题MedoidShift 和 QuickShift 的六条血泪经验5.1 现象QuickShift 结果被拉成一根根长条簇边界跨过了明显分隔的区域原因QuickShift 的父节点选择只要求“密度更高”和“距离提升比最大”没有像 DBSCAN 那样设定核心点条件。只要噪声带上每个点都能找到一个更高密度的邻居整条链就会把本应分离的簇串起来最终聚成一个巨大的长条。解决先按密度把点分组。做法是计算全部样本的密度 rho取其中位数作为阈值rho 低于阈值的点不参与父链构建最后单独归为“噪声类”。这相当于给 QuickShift 加了一道鲁棒性保险。代码改动很小只用在父节点搜索前加一层判断。5.2 现象同一个数据集换一种 medoid 定义聚类结果完全不一样原因MedoidShift 的 medoid 有两种常见定义一是“到窗口内其他样本距离和最小”二是“离窗口重心最近的样本”。当簇尾部重叠严重时这两个定义选出来的样本经常不是同一个点进而影响后续所有样本的轨迹。解决在项目启动时固定一种定义并且做一致性验证。我的习惯是固定“距离和最小”因为它对离群点更稳健在报告里明确标注。高维数据下两种定义的差异会被放大建议先降维再聚类同时做一次随机剔除 10% 样本的稳定性检查看模式点位移是否在可接受范围内。5.3 现象MedoidShift 日志显示在两个 medoid 之间反复横跳max_iter 设再大也跑不完原因坐标比较用 np.allclose 时如果容忍度 tol 设得太小低于 1e-8密集数据中两个距离极近的样本点会被判定为“不相等”导致算法在两个候选点之间循环。解决不要只比较坐标改为“坐标 索引”双条件。具体修改方式是在 fit 循环里记录上一轮的 medoid 索引数组当索引数组不变时直接 break这样就算睡在浮点误差上也不会死循环。顺手把 tol 放宽到 1e-6两个办法叠加后基本能根治。5.4 现象数据规模到 5 万内存直接爆掉原因不少教程代码会用 X[:, None, :] - X[None, :, :] 一次性构建 N×N 距离矩阵。5 万样本的二值特征也只是 20GB 量级连续特征直接让人崩溃。解决所有距离计算换成 cKDTree 的 query_ball_point 和 query_pairs只对窗口内的子集构建距离矩阵。QuickShift 的密度估计和父节点搜索本来就是邻域内操作没有理由构建全局矩阵MedoidShift 的窗口矩阵大小也被带宽限制最坏情况也不至于全量。如果 KDTree 仍然慢再把特征降到 16 维速度通常提升 3 到 5 倍聚类质量反而更好。5.5 现象聚类结果对初始点的顺序敏感同一次代码改了样本顺序结果就变了原因MedoidShift 是逐个样本迭代的前面样本的 medoid 更新会改变后续样本的近邻搜索环境天然存在顺序依赖。QuickShift 理论上无迭代但如果密度估计部分用了并行累加导致浮点误差顺序不同也会出现细微差异。解决MedoidShift 里可以先做一轮全局近邻排序把样本按密度降序排列再迭代能显著降低顺序敏感性QuickShift 则在并行时固定数据的读取顺序不要使用在线累加。并做好记录聚类结果完全一致是理想情况允许簇号重排下的标签一致即可。5.6 现象降维后聚类效果反而变差原因PCA 降维后用欧氏距离本质上是把高频信息抹掉只保留全局方差大的方向。对某些密度模式关键的区分信息恰恰在小方差方向上。解决降维前先做一个简单的密度可视化检查。如果数据本身不到几十维不降维直接跑可能更好如果一定要降维保留 16 维以上别压到 23 维再聚类。二维可视化只用来展示不要用二维特征作为聚类输入。6. 让聚类结果可信质量验证、超参稳定性与加速技巧验证聚类的几个技巧最能说明问题的是“三个信号 一个交叉检查”。三个信号分别是轮廓系数、簇内平均距离、簇间最小距离。轮廓系数接近 1 表示内外分离明确接近 0 表示大量重叠簇内平均距离应该随着簇数增加而稳步下降如果出现断崖式下跌说明 sigma 切碎了某个正常的簇。交叉检查是把模式点打印出来对比业务意义上是否合理。聚类算法不认业务但最后用的一定是人。超参稳定性检查我建议每换一个数据集都做一遍把 sigma 在当前值的 ±20% 范围内取三档分别聚类看每个样本的归属是否只在少数几个边界簇之间变动。如果一点小扰动就让大量样本换了簇说明数据分布本身没有清晰模式这时候换更复杂的聚类算法也救不回来。加速方面最实用的做法是用 joblib 并行化近邻搜索和密度估计。QuickShift 里每个点的父节点搜索是独立的直接 Parallel 后处理MedoidShift 的迭代本身是串行的但每次迭代中各样本的足记搜索可以并行用多进程能拿到接近线性的加速比。我在实际项目中最深的感受是这类密度模式聚类算法不是一个“设好参数就跑”的黑匣子它的结果对带宽、距离度量极其敏感。别一上来就追求一次跑通先画密度图、做簇数扫描、再固定 medoid 定义这三步做完再谈成功率。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/8 19:07:50 · 阅读 1.2k MedoidShift与QuickShift：真实样本中心的密度聚类算法解析
简介MedoidShift 与 QuickShift 两种聚类算法的完整 Python 实现与演示资源面向机器学习初学者以及需要在项目中快速选型聚类方法的开发者聚焦无监督学习中中心点选取、密度敏感聚类和高维数据效率等常见问题。压缩包共 5 个文件包含两个算法的核心实现脚本、演示程序、说明文档以及聚类结果对比图整体仅 429KB轻量易读。已有 319 人浏览学习适合作为算法原理理解与实践验证的入门材料。通过阅读并运行代码可以直观掌握 MedoidShift 通过迭代更新 medoid 形成稳定聚类的机制以及 QuickShift 借助概率树完成快速密度搜索的思路对比图能帮助理解两者在不同簇形状、噪声干扰和数据集规模下的表现差异从而在实际项目中更合理地选择聚类方案。1. 从 Mean Shift 分支到 MedoidShift、QuickShift一类把“中心”换成真实样本点的聚类算法做图像分割、异常检测这类活儿时数据形态经常很不规整簇不是椭球类别边界模糊还带着不少噪声。K-Means 和 GMM 这种“带质心的聚类算法”天然把结果往圆形拉边界归属一塌糊涂。MedoidShift 和 QuickShift 这类基于密度模式的聚类算法不预设簇形状只是沿着密度上升方向把每个样本归到局部密度峰值附近聚类数目也不用预先指定。它们同源 Mean Shift区别在于MedoidShift 把每步更新从“特征空间重心”换成真实样本点QuickShift 直接沿着最近的高密度邻居跳。适合处理维度几十以下的中小规模点云、图像超像素和簇数量未知的数据。2. MedoidShift 与 QuickShift 的密度上升逻辑均值点、中位数点与最近点的三种移动策略2.1 一个统一框架先在特征空间里估计密度再顺着坡度走到“峰”先立一个基础框架否则后面参数全乱。给定 N 个样本我们需要对每个位置估计局部密度最常见做法是高斯核 Parzen 窗ρ(x) Σ_j exp(-||x - x_j||² / (2σ²))σ 就是带宽它决定“多近才算一个群体”。Mean Shift 家族所有算法都建立在这样一张密度图上每个样本点从当前位置出发沿着密度上升的方向移动最后停到某个局部极大值——这个极大值就是“模式mode”一个模式代表一个簇。关键区别只在“如何判断上升方向”。Mean Shift 把窗口内样本的坐标均值作为下一步中心这是数学上最光滑的做法MedoidShift 把这个中心替换为窗口内真实存在的某个样本点QuickShift 则彻底砍掉迭代直接从每个点跳到它的“最佳父节点”一气呵成。三者产出结果相似但鲁棒性、计算代价和调参手感差得很远。2.2 MedoidShift每次移动都落脚到一个真实样本上给特征空间加几个噪点然后跑一遍 Mean Shift 就会发现均值中心可能停在一个不属于任何一个实际观测点的位置。这在聚类结果解释上有点尴尬——簇中心是个“虚拟样本”没法直接拎出来看它长什么样。MedoidShift 就是冲着这点改的。它把传统 Mean Shift 的“均值步”替换为两步在带宽 σ 范围内找到当前点的所有近邻组成“足迹footprint”在足迹内选择一个真实样本点作为新的“代表”这个样本就是 medoid常见两种定义是“到足迹内其他样本距离和最小”或“离足迹重心最近”。每个样本沿着足迹中 medoid 的链条移动直到落脚点不再变化。因为每一步都落在真实样本上最终得到的模式点一定来自原始数据集这在小样本、图像分割这类需要回看“簇中心长什么样”的场景中非常实用。代价是它对初值敏感而且迭代过程比 QuickShift 慢得多。2.3 QuickShift不做迭代直接用“父节点链”一把走完QuickShift 是 Vedaldi 和 Soatto 在 2008 年提出的算法目的是在保持 Mean Shift 聚类质量的前提下把速度提上去。它放弃迭代改为一次构图先给每个点算局部密度然后对每个点找密度高于它、并且“单位距离密度提升比”最大的那个点作为父节点parent(i) argmax_j (ρ_j - ρ_i) / ||x_j - x_i||其中 ρ_j ρ_i直观理解是每个点朝“近处且有更高密度”的点迈一步而不是朝远处的高密度峰跳。每个点的父节点只有一个所以全体样本构成一片森林——每个局部密度峰是一条链的根。聚类时把每个点沿父链上溯到根挂在同一个根下的点归为一个簇。这个设计绕开了迭代收敛的问题计算也比 MedoidShift 快一个量级。代价是它对噪声更敏感一条噪声链只要每个点都能找到一个更高密度邻居就可能把两个本应分离的簇串成一条。2.4 MedoidShift 与 QuickShift 的复杂度与适用形态对比动手前先看这张对比表决定在什么场景选谁维度MedoidShiftQuickShift每个点的移动目标窗口内的真实样本medoid密度更高且距离提升比最大的父节点是否迭代迭代收敛到模式点单次构图无迭代密度峰值位置一定是原数据集中的样本根点一定是原数据集中的样本聚类结果形式每个样本一个终点索引森林结构按根聚簇抗噪声能力较好较差容易产生链式串簇时间成本迭代次数 × 局部距离矩阵一次近邻搜索 一次父链上溯典型数据规模几千到几万样本几万到几十万样本一句话选型样本量在万以下、需要稳定且可解释的模式点优先 MedoidShift数据上了十万、又不需要精细边界QuickShift 更划算。3. 用 Python 把 MedoidShift 和 QuickShift 跑起来核心代码与最小参数集3.1 最小实现用 NumPy 和 SciPy 写一个可跑的 MedoidShift下面给出一段可以照抄的最小实现用 scipy.spatial 的 cKDTree 做近邻搜索避免全量距离矩阵。以“距离和最小”作为 medoid 的工程化定义。import numpy as np from scipy.spatial import cKDTree class MedoidShift: def __init__(self, bandwidth1.0, max_iter50, tol1e-6): self.bandwidth bandwidth # 邻域半径决定簇的尺度 self.max_iter max_iter # 安全上限防止不收敛 self.tol tol # 浮点比较容忍度 def fit(self, X): n X.shape[0] tree cKDTree(X) medoids X.copy() # 每个样本从自身出发 candidate_idx np.arange(n) for it in range(self.max_iter): moved False for i in range(n): idx tree.query_ball_point(medoids[i], rself.bandwidth) # 窗口内样本个数太少时保持原地不动 if len(idx) 2: continue window X[idx] # 足迹内的真实样本 # 计算窗口内两两距离矩阵选“到其他点距离和最小”的样本 diff window[:, None, :] - window[None, :, :] dist_mat np.linalg.norm(diff, axis2) new_idx idx[np.argmin(dist_mat.sum(axis1))] # 用样本索引判断是否还在移动 if not np.allclose(medoids[i], X[new_idx], atolself.tol): medoids[i] X[new_idx] moved True if not moved: break # 将每个样本的最终 medoid 映射为簇编号 unique_medoids {} labels np.zeros(n, dtypeint) for i in range(n): key tuple(np.round(medoids[i], decimals6)) if key not in unique_medoids: unique_medoids[key] len(unique_medoids) labels[i] unique_medoids[key] return labels, medoids代码逻辑说明每个样本点从自己出发用 query_ball_point 找半径内近邻然后在这个足迹内算距离矩阵选出“距离和最小”的样本作为新落脚点。用 np.allclose 判断是否还在动当所有点都不再找到新的 medoid 时停止。最后把坐标相同的终点合并成簇编号。参数说明bandwidth 是最关键的参数它直接决定足迹大小一般按数据标准差的比例给初始值max_iter 设 50 对大多数二维数据够用高维数据可能需要 100tol 是浮点比较容忍度默认 1e-6 偏严若输出显示迭代频繁触发上限先放宽到 1e-4 试试。3.2 QuickShift 最小实现密度估计、父节点搜索与根节点聚簇QuickShift 的实现比 MedoidShift 短核心在密度估计和父节点选择。下面是可直接运行的最小版本。import numpy as np from scipy.spatial import cKDTree def quick_shift(X, sigma1.0): n, d X.shape tree cKDTree(X) # 1) 高斯核密度估计sigma 就是带宽 rho np.zeros(n) for i in range(n): idx tree.query_ball_point(X[i], rsigma) dist np.linalg.norm(X[idx] - X[i], axis1) rho[i] np.sum(np.exp(-dist**2 / (2 * sigma**2))) # 2) 每个点找一个密度更高的最佳父节点 parent np.full(n, -1, dtypeint) for i in range(n): idx tree.query_ball_point(X[i], rsigma) # 只保留密度严格高于当前点的候选者 candidates [j for j in idx if rho[j] rho[i] 1e-12] if len(candidates) 0: continue # 当前点就是局部峰作为树根 dist np.linalg.norm(X[candidates] - X[i], axis1) # 最大化“密度提升 / 距离”即近处有提升的优先 score (rho[candidates] - rho[i]) / dist parent[i] candidates[np.argmax(score)] # 3) 沿父链上溯到根同一个根归为同一个簇 labels np.zeros(n, dtypeint) root_id {} for i in range(n): cur i vis [cur] while parent[cur] ! -1: cur parent[cur] vis.append(cur) root vis[-1] if root not in root_id: root_id[root] len(root_id) labels[i] root_id[root] return labels, rho, parent代码逻辑说明密度估计用高斯核落在 sigma 邻域内的点按距离加权父节点搜索在邻域内进行限定于密度更高的点用“密度差 ÷ 距离”作为打分标准得分最高的成为父节点。这样每个点都指向近处一个密度提升最快的方向。参数说明sigma 同时是密度估计的带宽和父节点搜索半径含义比 MedoidShift 的 bandwidth 更重建议先按数据的绝对中位差MAD来粗调不要直接拿标准差套。最后的上溯过程由于每个点只沿父链走最坏情况是 O(n²)数据量大时可以加记忆化缓存每个点已算好的根。3.3 两个算法跑完怎么判断结果有没有意义不管用哪种算法跑完第一步不是看轮廓系数而是直接看数据分布和簇标签的叠加图。在二维数据上画散点图把不同标签点成不同颜色检查有没有一条细长的串把多个簇连起来这是 QuickShift 的典型噪声链簇内心是不是落在密度最高的区域而不是偏向某个边缘落在尾部的点是否大量被分成独立小簇如果是说明 sigma 太小。这一步很朴素但极其有效。跑通代码只是开始真正的调参工作从这里才开始。4. 参数怎么设带宽 sigma、距离度量和迭代停止条件的定量把握4.1 带宽 sigma影响簇数的最敏感旋钮也是最玄学的参数两个算法里带宽都是真正的“灵魂参数”它对结果的影响几乎是单调的sigma 越小密度峰越多簇数越多sigma 越大密度图越平滑簇数越少直到整个数据变成一个簇。这里的经验是先做一个“簇数曲线”设一组合适的扫描范围比如从 0.2 倍到 2 倍数据标准差按对数间隔取 10 组每组跑一次算法记录簇数找出簇数从“剧烈下降”转为“平稳缓慢下降”的拐点选拐点附近的 sigma。这个做法比反复试错快得多。二维数据上sigma 取 0.51 倍数据标准差通常是合理起点高维数据上同样的 sigma 在欧氏距离下覆盖的样本数会变少所以要么先把维度降到 20 以下要么改用余弦距离再调整 sigma。4.2 距离度量的选择高维下欧氏距离失效是第一个坑MedoidShift 和 QuickShift 都严重依赖距离度量。维度在 20 以下时欧氏距离没问题维度超过 50 以后所有点之间的距离几乎相等密度估计变得没有区分度聚类结果接近随机。常见的做法是先对特征做 PCA 降维到 1632 维再跑聚类如果特征是文本向量或用户行为向量更推荐余弦距离。需要说明一个细节把欧氏距离换成余弦距离后带宽的含义会变。余弦距离的取值范围是 [0, 2]sigma 就不能按标准差给了通常从 0.1 开始扫描。这个变化很容易被忽略很多人换了距离度量却还沿用原来的 sigma结果一塌糊涂。4.3 MedoidShift 的迭代停止条件索引稳定比坐标稳定更可靠MedoidShift 收敛判断有一个很容易踩的坑直接比较坐标会因为在两个 medoid 之间震荡而永不收敛尤其是数据点密集的区域。我在实践里的做法是双条件并下坐标变化小于 tol默认 1e-6连续两次迭代中所有样本点的 medoid 索引不变。只靠坐标判断浮点误差会让两个点来回跳只靠索引判断可能因为索引提前稳定而错过更好的落脚点。两个条件同时满足再停max_iter 设为 50 一般够用但数据量上万后可能需要放宽到 100。日志里如果看到 max_iter 频繁触顶优先放宽 tol而不是无限加大迭代上限。4.4 什么时候用 MedoidShift什么时候用 QuickShift一句话总结我的选择逻辑要解释、要稳定、数据少选 MedoidShift要速度、要超像素、数据多选 QuickShift。具体展开MedoidShift 的每个簇中心都是真实样本在医疗数据、工业质检这类需要回看“代表样本长什么样”的场景里优势明显但它要迭代样本量上万后速度明显变慢。QuickShift 单次构图速度和解晰度更适合图像超像素分割、大规模点云聚类但它输出的森林容易受噪声链影响聚类边界不如 MedoidShift 干净。此外如果你最终要做的是“一个簇一个代表样本”的后续分析MedoidShift 的终点天然就是代表样本QuickShift 还要额外在簇内再做一次 medoid 选择。5. 避坑与常见问题MedoidShift 和 QuickShift 的六条血泪经验5.1 现象QuickShift 结果被拉成一根根长条簇边界跨过了明显分隔的区域原因QuickShift 的父节点选择只要求“密度更高”和“距离提升比最大”没有像 DBSCAN 那样设定核心点条件。只要噪声带上每个点都能找到一个更高密度的邻居整条链就会把本应分离的簇串起来最终聚成一个巨大的长条。解决先按密度把点分组。做法是计算全部样本的密度 rho取其中位数作为阈值rho 低于阈值的点不参与父链构建最后单独归为“噪声类”。这相当于给 QuickShift 加了一道鲁棒性保险。代码改动很小只用在父节点搜索前加一层判断。5.2 现象同一个数据集换一种 medoid 定义聚类结果完全不一样原因MedoidShift 的 medoid 有两种常见定义一是“到窗口内其他样本距离和最小”二是“离窗口重心最近的样本”。当簇尾部重叠严重时这两个定义选出来的样本经常不是同一个点进而影响后续所有样本的轨迹。解决在项目启动时固定一种定义并且做一致性验证。我的习惯是固定“距离和最小”因为它对离群点更稳健在报告里明确标注。高维数据下两种定义的差异会被放大建议先降维再聚类同时做一次随机剔除 10% 样本的稳定性检查看模式点位移是否在可接受范围内。5.3 现象MedoidShift 日志显示在两个 medoid 之间反复横跳max_iter 设再大也跑不完原因坐标比较用 np.allclose 时如果容忍度 tol 设得太小低于 1e-8密集数据中两个距离极近的样本点会被判定为“不相等”导致算法在两个候选点之间循环。解决不要只比较坐标改为“坐标 索引”双条件。具体修改方式是在 fit 循环里记录上一轮的 medoid 索引数组当索引数组不变时直接 break这样就算睡在浮点误差上也不会死循环。顺手把 tol 放宽到 1e-6两个办法叠加后基本能根治。5.4 现象数据规模到 5 万内存直接爆掉原因不少教程代码会用 X[:, None, :] - X[None, :, :] 一次性构建 N×N 距离矩阵。5 万样本的二值特征也只是 20GB 量级连续特征直接让人崩溃。解决所有距离计算换成 cKDTree 的 query_ball_point 和 query_pairs只对窗口内的子集构建距离矩阵。QuickShift 的密度估计和父节点搜索本来就是邻域内操作没有理由构建全局矩阵MedoidShift 的窗口矩阵大小也被带宽限制最坏情况也不至于全量。如果 KDTree 仍然慢再把特征降到 16 维速度通常提升 3 到 5 倍聚类质量反而更好。5.5 现象聚类结果对初始点的顺序敏感同一次代码改了样本顺序结果就变了原因MedoidShift 是逐个样本迭代的前面样本的 medoid 更新会改变后续样本的近邻搜索环境天然存在顺序依赖。QuickShift 理论上无迭代但如果密度估计部分用了并行累加导致浮点误差顺序不同也会出现细微差异。解决MedoidShift 里可以先做一轮全局近邻排序把样本按密度降序排列再迭代能显著降低顺序敏感性QuickShift 则在并行时固定数据的读取顺序不要使用在线累加。并做好记录聚类结果完全一致是理想情况允许簇号重排下的标签一致即可。5.6 现象降维后聚类效果反而变差原因PCA 降维后用欧氏距离本质上是把高频信息抹掉只保留全局方差大的方向。对某些密度模式关键的区分信息恰恰在小方差方向上。解决降维前先做一个简单的密度可视化检查。如果数据本身不到几十维不降维直接跑可能更好如果一定要降维保留 16 维以上别压到 23 维再聚类。二维可视化只用来展示不要用二维特征作为聚类输入。6. 让聚类结果可信质量验证、超参稳定性与加速技巧验证聚类的几个技巧最能说明问题的是“三个信号 一个交叉检查”。三个信号分别是轮廓系数、簇内平均距离、簇间最小距离。轮廓系数接近 1 表示内外分离明确接近 0 表示大量重叠簇内平均距离应该随着簇数增加而稳步下降如果出现断崖式下跌说明 sigma 切碎了某个正常的簇。交叉检查是把模式点打印出来对比业务意义上是否合理。聚类算法不认业务但最后用的一定是人。超参稳定性检查我建议每换一个数据集都做一遍把 sigma 在当前值的 ±20% 范围内取三档分别聚类看每个样本的归属是否只在少数几个边界簇之间变动。如果一点小扰动就让大量样本换了簇说明数据分布本身没有清晰模式这时候换更复杂的聚类算法也救不回来。加速方面最实用的做法是用 joblib 并行化近邻搜索和密度估计。QuickShift 里每个点的父节点搜索是独立的直接 Parallel 后处理MedoidShift 的迭代本身是串行的但每次迭代中各样本的足记搜索可以并行用多进程能拿到接近线性的加速比。我在实际项目中最深的感受是这类密度模式聚类算法不是一个“设好参数就跑”的黑匣子它的结果对带宽、距离度量极其敏感。别一上来就追求一次跑通先画密度图、做簇数扫描、再固定 medoid 定义这三步做完再谈成功率。希望帮到你。本文还有配套的精品资源点击获取