🤖 machine learning

Local Cluster Cardinality Estimation for Adaptive Mean Shift

本文介绍了一种具有尺度不变性的全自适应均值漂移算法，该算法通过距离分布分析估计局部簇基数，从而为每个点自动确定局部带宽和核阈值，在无需预先知晓簇数量或全局尺度参数的情况下，实现了具有竞争力的聚类性能。

原作者： Étienne Pepin

发布于 2026-08-13

📖 1 分钟阅读☕ 轻松阅读

原作者： Étienne Pepin

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正身处一个规模宏大、混乱不堪的音乐节。你想找到你的朋友，但人群就像一个旋转交织的漩涡，由成千上万的人组成：有人三五成群地紧凑站立，有人形单影只地徘徊，还有些人群规模巨大，甚至横跨了整个场地。在数据科学的世界里，这就是**聚类（clustering）问题：试图将一堆杂乱无章的信息分类成整齐、有意义的组别，而无需地图。通常情况下，计算机需要人类告诉它：“嘿，这里正好有五个组，”或者“使用五米的搜索半径。”但如果计算机能自己观察人群，理清其中的分组，并意识到其中一组很小很紧凑，而另一组则规模庞大且分散，那会怎样？这就是自适应（adaptive）**聚类的梦想：一种不需要僵化尺子的方法，而是利用自己的眼睛来测量邻居之间的距离。

这篇论文介绍了一种巧妙的新方法，让计算机能够实现这一目标。它提出了一种名为**自适应均值漂移（Adaptive Mean Shift）**的方法，就像一个聪明的磁铁，将点吸引到它们自然的组别中。其核心秘诀在于一种新技巧：通过观察点与点之间的距离，来判断特定组别中有多少人。该算法不再猜测一个固定的搜索范围大小，而是观察“距离分布”——即一个点到其他所有人的距离列表——并寻找这个列表中的自然“间隙”或“凹陷”。这个凹陷会告诉计算机：“好吧，所有比这个间隙近的人都属于我的组；比这个间隙远的人则是陌生人。”这使得算法能够为每一个点实时调整其搜索半径，使其具有尺度不变性（无论数据是以英寸还是光年为单位进行测量，它都能奏效）和局部性（它只关心紧邻的邻域）。

自测量磁铁的故事

让我们认识一下自适应均值漂移算法。把它想象成一群正在寻找营地中心的徒步旅行者。在过去，每个徒步者都会被告知：“观察你周围10英尺范围内的所有人，并向平均位置移动。”如果大家都在一个完美的圆圈内，这没问题；但如果一组人挤在一个紧凑的圆圈里，而另一组人散布在整个足球场上呢？10英尺的规则要么会错过那个分散的群体，要么会误把不属于该营地的成员也拉进来。

这篇论文介绍了一个更聪明的徒步者。这个徒步者不再被给予固定的10英尺规则，而是会问一个简单的问题：“我的邻居离我有多远？”他会创建一个列表，记录到人群中每个人的距离。如果你处于一个紧凑的组别中，你的列表会显示许多短距离，然后突然出现一个跳跃，指向下一组。这篇论文的魔力就在于寻找这个跳跃。

作者使用了一个特殊的数学工具——** $\gamma$ 函数（伽马函数）**来扫描这个距离列表。想象一下，这个距离列表是一条起伏不平的路。 $\gamma$ 函数就像一个灵敏的地震仪，寻找两个山丘之间最深的谷底。第一座山丘代表你所在组的人（近邻），第二座山丘代表其他组的人（远邻）。这两者之间的谷底就是绘制界限的最佳位置。

一旦算法找到了这个谷底，它就确切地知道了局部组别的规模（基数/cardinality）以及该组扩散的范围（半径/radius）。然后，它利用这些特定信息来为该位置设定自己的“搜索半径”和“拉力强度”。这就像变色龙改变颜色以完美融入所处的环境一样。

为什么这很重要：不再需要猜测组别数量

聚类中最令人头疼的问题通常是不知道存在多少个组。大多数算法都需要你说明：“帮我找3个簇”或“找10个簇”。如果你猜错了，整个过程就会崩溃。这种新方法不需要那个数字。它通过观察距离数据中的自然间隙来识别组别。

作者首先在一个“玩具数据集”上测试了这个想法——这是一个拥有四个不同规模和分布程度组别的虚拟世界。算法成功找到了所有四个组，即使其中一组非常微小，而另一组却异常庞大。它意识到微小的组需要微小的搜索半径，而庞大的组需要大的搜索半径，而这一切都不需要被告知组别的数量。

当作者将该方法与其他智能聚类技术（特别是 Ren 等人在 2014 年提出的 WAMS 方法）进行对比时，结果令人期待。在九个真实世界数据集（如手写字母图像或生物数据）中，他们的这种新方法在七个数据集上表现出了优于竞争对手的分组能力。它不仅赢了，而且往往以明显的优势获胜，例如在 Iris 数据集上获得了 0.9575 的“兰德指数”（Rand Index，衡量分组与真相匹配程度的分数），而竞争对手的方法为 0.9495。在某些数据集上，差距很小（小于 0.012），但在另一些数据集上，差异是非常显著的。

游戏规则

论文谨慎地指出，这种方法并不是什么能解决所有问题的“万能钥匙”。

它并不完美适用于超大型组别： 算法有一个规则，即“我们不会寻找规模超过总数据量一半的组”。如果一个数据集有一个占据了全部数据 60% 的巨型组，这种方法可能会产生困惑并将这个巨型组拆分成碎片。作者承认这是一个局限性，并建议未来的“最大边界”规则需要更加智能化。
它并非对所有领域都是经过验证的突破： 虽然它在特定的测试中击败了竞争对手，但作者指出，他们仅将其与另一种自适应方法进行了对比。他们建议需要针对更新的方法进行更多测试。
它是一个原型： 作者将其描述为一个“首个功能性原型”。他们看到了改进的空间，比如使用不同的方式来寻找距离列表中的“谷底”，或者测试它如何处理极高维度的数据（具有数百个特征的数据）。

总结

最后，这篇论文为计算机如何组织混乱数据提供了一个全新的视角。它不再是将僵化的尺子强加给灵活的人群，而是教会计算机去感受人群的脉搏。通过测量邻居之间的距离并寻找自然的间隙，该算法可以适应任何规模或形状的组别，无论是亲密的朋友圈，还是规模宏大的音乐节人群。它不需要在开始前就知道答案；它只需要观察距离，让数据本身讲述故事。虽然它仍有一些粗糙之处和需要完善的假设，但它表明，通过正确的局部测量，计算机可以学会如何在噪声中找到自己的方向。

技术摘要：用于自适应均值漂移的局部簇基数估计

问题陈述

本文探讨了**自适应均值漂移（Adaptive Mean Shift, AMS）**聚类中参数选择的挑战。传统的 AMS 算法依赖于带宽参数来定义计算加权均值的局部邻域。虽然基础的 AMS 使用固定的全局带宽，但自适应变体试图对该参数进行局部调整，这通常依赖于局部密度估计（例如核密度估计或 KDE）。

作者指出了现有方法中的两个主要局限性：

尺度依赖性（Scale Dependence）： 许多方法需要为整个数据集选择一个长度常数（带宽），这使得它们对数据的尺度非常敏感。
局部性与噪声： 标准 KDE 在固定大小的邻域内测量密度。如果该邻域过大，会包含来自远处簇的点，从而干扰局部估计；如果过小，则可能丢失簇结构。此外，KDE 需要选择一个非平凡的带宽参数，这在处理小规模簇或高维数据时尤为困难，因为可能会发生过度平滑现象。

本文提出了一种直接从点到其邻居的距离分布中估计基数（点的数量）的方法。随后，利用该估计的基数来推导均值漂移过程中的带宽和核半径，从而消除了对预定义全局带宽或固定簇数量的需求。

方法论

所提出的算法分为三个主要阶段：簇基数估计、自适应均值漂移以及离群点分类。

1. 局部簇基数估计

其核心创新在于使用点 $x_i$ 到所有其他点的距离分布来估计局部簇基数 ( $\hat{n}$ )。

距离分布： 对于每个点，将其到所有其他点的距离进行排序。作者假设在一个多峰数据集中，这种分布是双峰的：第一个峰代表同一局部簇内点之间的距离，第二个峰代表与其他簇中点之间的距离。
$\gamma$ 函数： 为了定位这两个峰之间的边界（即最小密度的“谷底”），论文引入了一个函数 $\gamma$ ：
$\gamma(y^{(k)}) = \frac{s^2}{(\bar{y} - y^{(k)})^2}$
其中 $y^{(k)}$ 是第 $k$ 个有序距离， $\bar{y}$ 是前 $k$ 个距离的平均值， $s^2$ 是它们的方差。
估计逻辑： 算法在定义的搜索窗口（$minBoundary $到$ maxBoundary $）内寻找使$ \gamma $最小值的秩$ k $。这个最小值对应于估计的簇基数$ \hat{n}_i$。
关键特性：
- 尺度不变性（Scale Invariance）： $\gamma$ 函数是方差与距离平方的比值。将数据乘以一个正数常数不会改变 $\gamma$ 的值，这意味着不需要长度尺度常数。
- 局部性（Locality）： 秩 $k$ 处的 $\gamma$ 值仅取决于其前 $k$ 个最近的距离。更远的点不会影响局部簇边界的估计。

2. 自适应均值漂移

一旦为每个点估计出 $\hat{n}_i$ ，这些值将驱动均值漂移过程：

核定义： 使用截断高斯核 $K(x; h, \omega)$ $K (x; h, ω)$ 。
- 带宽 ( $h$ )： 计算受限于估计基数 $\hat{n}_i$ 的局部距离分布的标准差。
- 阈值 ( $\omega$ )： 设置为第 $\hat{n}_i$ 个有序距离，从而有效地将核函数在估计的簇半径处截断。超过此半径的点权重为零。
高维自适应： 针对高维空间提出了一个改进的核函数（公式 6），通过抵消距离来防止自距离（零）主导权重，并避免数值不稳定。
逐渐增加面积： 为了减轻在簇边界附近点产生的基数估计正偏差，算法在迭代均值漂移步骤期间逐渐增加考虑的点数 ( $n_k^*$ )，从而允许加权均值向真实的众数收敛。

3. 处理“坏”估计

对于基数估计触及搜索边界（例如，位于簇之间且分布具有歧义的点）的点，会被标记为“坏”点。这些点被排除在迭代均值漂移之外。在最后一步中，它们根据该簇的带宽被分配给最近的簇众数。

核心贡献

基于基数的参数化： 本文引入了一种方法，直接从估计的局部簇基数中推导出带宽和核半径，从而不再需要全局带宽参数。
$\gamma$ 函数： 一种新颖的、具有尺度不变性的局部函数，用于检测距离分布中两个峰之间的最小密度，避免了 KDE 中固有的带宽选择问题。
尺度与簇独立性： 该算法不需要输入簇的数量，并且对数据的缩放具有不变性。
截断核策略： 通过在估计的簇半径处截断核函数，该方法确保了远处的点（来自其他簇）不会污染局部加权均值。

实验结果

作者在两组基准测试上评估了该算法：

与 Ren 等人 (2014) 的 WAMS 对比：
- 在 9 个数据集（Iris, Yeast, Steel, USPS, CTG, Letter, Image, Pen, Wave）上进行了测试。
- 所提方法在 9 个数据集中的 7 个上取得了比加权自适应均值漂移 (WAMS) 算法更高的 Rand 指数。
- 在这 7 个数据集上，它优于所有已发表的基准方法（WAMS, k-means, EM, Single-linkage）。
- 在剩余两个数据集（USPS, Image）上表现具有竞争力，尽管作者指出无法获取这些基准的具体实现细节，因此无法完全调查差异的原因。
与 Gagolewski (2022) 基准对比：
- 在 8 个 UCI 数据集（Ecoli, Glass, Ionosphere, Sonar, Statlog, WDBC, Wine, Yeast）上进行了测试。
- 在 Rand 指数能清晰区分方法的任务中，该算法的表现与成熟方法（GIc, EM, k-means, Spectral, Birch）相当。
- 局限性： 当最大的簇包含超过 50% 的数据时，该算法表现不佳（默认 maxBoundary 为 $0.5n$ ）。在这种情况下（例如 Ionosphere, Sonar, WDBC），算法无法将多数类表示为一个单一的簇，导致较低的 Rand 指数。作者指出，调整 maxBoundary 参数可以改善这些特定数据集的结果，但这需要了解数据分布。

意义与声明

论文声称所提出的算法在自适应均值漂移家族中具有竞争力，并通过不需要输入簇的数量这一特点提供了明显的优势。

谦逊态度： 作者承认基数估计器是一个“初步的功能原型”且“仍在开发中”。他们承认与 WAMS 算法的比较仅涵盖了自适应均值漂移家族的一个成员，因此需要更广泛的比较。
尺度不变性： 作者强调，其尺度不变性是一个重要的理论改进，因为它消除了为数据尺度选择长度常数的需求。
局部性： 该方法强调其严格的局部性，确保局部簇的估计不会受到远处数据点的干扰。
未来工作： 论文建议，基数估计任务本身具有新颖性，值得进一步研究。未来的改进可能包括使用算法化的模式查找（例如一维均值漂移）来替换固定边界，以及优化 maxBoundary 参数的处理，使其完全由数据驱动。

总之，本文提出了一种新颖的自适应均值漂移方法，该方法利用距离分布自动确定局部簇参数，在保持尺度不变性和局部性等理论特性的同时，在标准基准测试中展示了强大的实证性能。