Simple KNN-Based Outlier Detection Achieves Robust Clustering¶
会议: NeurIPS 2026
arXiv: 2605.07130
OpenReview: https://openreview.net/forum?id=rGWj7JwpMU
代码: https://github.com/MasterZhou1/Robust-Clustering
领域: 其他
关键词: 鲁棒聚类, 离群点检测, K近邻, 近似算法, 核心集
一句话总结¶
在最优簇规模不小于常数倍离群点预算的实用假设下，直接利用 KNN 距离检测并移除离群点即可实现带离群点 \(k\)-Means 到标准 \(k\)-Means 的常数因子近似归约，无须放宽聚类中心数或多删离群点。
研究背景与动机¶
聚类是无监督学习中的经典核心问题，但常见的 \(k\)-Means 与 \(k\)-Median 等目标函数对噪声和异常值极其敏感。在实际数据集中，即便仅存在少量偏离数据分布主体的离群点，也会极大程度扭曲聚类中心的位置，导致传统聚类算法失效。为了应对这一挑战，鲁棒聚类（Robust \(k\)-Clustering with Outliers）问题应运而生：给定离群点预算 \(z\)，目标是在移除至多 \(z\) 个离群点后，最小化剩余数据点上的聚类代价。然而，现有的鲁棒 \(k\)-Means 高效算法大多依赖超线性的离群点移除流程或复杂的自适应采样，且往往不得不采用双准则近似（Bicriteria Approximation）——即允许使用超过 \(k\) 个聚类中心、剔除超过 \(z\) 个离群点，或者依赖对未知最优代价 \(\mathrm{OPT}\) 的网格猜测，在实用规模上面临质量与效率的双重瓶颈。
与此同时，在异常检测与离群点挖掘领域，基于 \(K\) 近邻（KNN）距离的启发式方法因其实现极度简便、直观且计算易并行，在工业界被广泛用作基线算法。但在理论与算法层面，异常检测通常只关注离群点本身的检出，并不直接优化下游的聚类代价；以往的理论文献不仅缺乏对经典 KNN 离群点检测能否有效服务于鲁棒聚类的严格证明，甚至已有工作认为通用离群点检测方法在聚类代价上远逊于专为鲁棒 \(k\)-Means 设计的复杂算法。
这种理论认知与实践经验的脱节促使本文重新审视最朴素的启发式策略。在实际聚类任务中，真实聚类簇的规模通常远大于噪声点数量（否则极小规模的噪声簇与真实结构在信息论上无法区分）。前人工作常引入最优簇大小至少为 \(3z\) 的假设，但在该假设下依然引入了额外中心或多倍离群点剔除。核心 idea：在最优簇大小不小于 \(cz\)（\(c>1\)）的实际假设下，将 KNN 的近邻数 \(K\) 设为与离群点预算 \(z\) 成线性比例，即可证明最朴素的 KNN 离群点剔除能够在严格保持 \(k\) 个中心和 \(z\) 个离群点约束的前提下，实现鲁棒 \(k\)-Means 到标准 \(k\)-Means 的常数因子近似归约。
方法详解¶
整体框架¶
本文针对带离群点 \(k\)-Means 问题提出了一套极简的两阶段框架：首先通过基于近邻距离的离群点度量筛选出离群程度最高的 \(z\) 个样本点并将其剔除；随后在剩余的内点集合上调用任意标准的 \(k\)-Means 近似算法求解 \(k\) 个聚类中心。为兼顾大规模数据的计算效率，整体流程可无缝结合轻量级核心集（Coreset）采样与 FAISS 向量检索加速，端到端达到近线性时间复杂度。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入数据集 X<br/>样本数 n, 聚类数 k, 离群预算 z"] --> B["阶段1：核心集采样与近邻距离度量<br/>构建代表子集并计算局部密度指标"]
B --> C["阶段2：预算截断离群点剔除<br/>按近邻异常分数移除 top-z 样本"]
C --> D["阶段3：标准 k-Means 求解<br/>在剩余样本集上调用标准近似算法"]
D --> E["输出 k 个最优聚类中心 C<br/>严格满足 k 与 z 的理论约束"]关键设计¶
1. 线性伸缩尺度的朴素近邻检测（OKMeans）：消除双准则放宽的理论归约 传统离群点检测常将近邻数 \(K\) 固定为微小的常数（如 \(K=2, 5, 10\)），但本文从理论上证明，为了抵御恶意分布的离群点抱团干扰，近邻阶数 \(K\) 必须与离群点预算 \(z\) 成正比。当最优簇规模 \(|P^*| \ge cz\)（\(c > 1\)）时，算法选取参数 \(\alpha = \frac{c+1}{2}\)，对每个样本点 \(x \in X\) 计算其到第 \(\frac{c+1}{2}z\) 个近邻的距离 \(r_x = d(x, \mathrm{NN}_X(x, \frac{c+1}{2}z))\)。将按 \(r_x\) 降序排列的前 \(z\) 个点作为检测出的离群集合 \(O\) 并直接剔除。理论证明表明，设门限 \(T = \min_{x \in O} r_x\)，若算法误删了部分真实内点 \(Y = O \cap X_z(C^*)\) 并漏检了等量的真实离群点 \(Z' = (X \setminus O) \setminus X_z(C^*)\)，则每个漏检离群点在其邻域球内必然包含至少 \((\alpha-1)z\) 个真实内点；利用三角不等式与最优解代价的几何下界，建立三类边界情况的数学极值分析，可证明剩余样本集 \(X \setminus O\) 上的聚类代价满足： $\(f(X \setminus O, C^*) \le \Phi(c) \cdot f_z(X, C^*)\)$ 其中当 \(c=3\) 时，选取第 \(2z\) 个近邻距离作为判定阈值，即可得到严格的 \(9\) 倍近似归约比。这意味着调用一个 \(\beta\)-近似的无异常 \(k\)-Means 求解器，最终即可输出全局 \(9\beta\)-近似解，完全无需猜测 \(\mathrm{OPT}\)，亦无需多删任何离群点或多占任何聚类中心。
2. 中段近邻距离累加聚合度量（OKMeans2）：防御对抗噪声并锐化理论界 在朴素 OKMeans 中，单个分位数点距离可能对局部密度波动较为敏感；而若简单地将前 \(K\) 个近邻距离全量求和，若真实离群点彼此在局部聚集抱团，其前 \(z\) 个近邻距离会极小，从而“掩护”彼此逃脱检测。为了克服这一缺陷，OKMeans2 巧妙设计了“避开前 \(z\) 个近邻”的区间累加打分机制：对每个点 \(x\)，仅累加第 \(z+1\) 至第 \(cz\) 个近邻的欧几里得距离，构造异常分数： $\(s_x = \sum_{i=z+1}^{cz} d(x, \mathrm{NN}_X(x, i))\)$ 由于剥离了前 \(z\) 个邻居的干扰，任意离群点群体都无法通过相互抱团来伪造低异常分。结合 Jensen 不等式对累加凸函数的紧致放缩，该设计大幅强化了最优簇内点与离群点的分离度界限。在 \(c=3\) 这一标准设定下，近似归约比从 OKMeans 的 \(9\) 显著缩减至 \(\Psi(3) \approx 5.98\)。
3. 核心集采样与向量检索工程加速：从平方复杂度收敛到近线性耗时 直接在包含数百万样本的全量数据集上计算所有点的 \(K\) 近邻距离具有 \(O(d n^2)\) 的时间开销，无法处理超大规模工业数据。本文将理论算法与采样核心集（Coreset）机制深度融合：首先通过均匀采样以 \(O(d k n \log n)\) 时间构建大小为 \(O(k \log n)\) 的代表性核心集，将离群点预算按采样比例同等缩放；随后在核心集上利用 FAISS 倒排或图索引进行高效批处理最近邻检索，将近邻计算开销压缩至 \(O(d (k \log n)^2)\)，使得整体算法全流程端到端运行时间收敛在 \(O(d k n \log n)\)。
损失函数 / 训练策略¶
作为组合优化与非监督聚类算法，本方法无须基于反向传播的梯度训练。算法流程包含两大核心超参数： - 最优簇规模下界比例系数 \(c\)：理论证明要求 \(c > 1\)，实验表明取 \(c \in [3, 7]\) 即可达到优异的实证聚类代价与离群点召回率； - 近邻阶数与离群点预算配比：OKMeans 设 \(K = \lfloor \frac{c+1}{2} z \rfloor\)，OKMeans2 遍历求和区间 \(i \in [z+1, cz]\)。 离群点剔除后，底层的标准 \(k\)-Means 求解器可采用加权 \(k\)-Means++ 或标准 Lloyd 算法进行局部迭代收敛。
实验关键数据¶
主实验¶
论文在四个公开真实基准数据集（SKIN、SUSY、SHUTTLE、KDDFULL）共计 6 种配置上进行系统评测，样本量最高达 500 万，对比了包括 TIKMeans、IKMeans、RobustKMeans++、NKMeans 及朴素 KMeans++ 在内的 6 种主流基线。主实验报告了 10 次独立随机运行的聚类代价最优值（Cost Best）、均值与标准差（Cost Mean ± Std）、离群点召回率（Recall）及耗时（Time）。
| 数据集 | 样本数 / 维度 (\(k, z\)) | 评估指标 | OKMeans (本文) | OKMeans2 (本文) | 前序 SOTA (TIKMeans) | 经典基准 (NKMeans) |
|---|---|---|---|---|---|---|
| SKIN-5 | 245K / 3 (\(k=10, z=2450\)) | Cost Mean (\(\times 10^4\)) | 6.494 ± 0.312 | 6.410 ± 0.300 | 6.151 ± 0.194 | 6.887 ± 0.646 |
| SKIN-5 | 245K / 3 (\(k=10, z=2450\)) | Time (s) | 2.056 | 2.395 | 3.314 | 4.402 |
| SKIN-10 | 245K / 3 (\(k=10, z=2450\)) | Cost Best (\(\times 10^4\)) | 6.472 | 6.490 | 6.303 | 6.628 |
| SKIN-10 | 245K / 3 (\(k=10, z=2450\)) | Recall | 0.949 | 0.955 | 0.940 | 0.944 |
| SUSY-5 | 5M / 18 (\(k=10, z=50000\)) | Cost Best (\(\times 10^7\)) | 4.756 | 4.756 | 5.103 | 4.795 |
| SUSY-5 | 5M / 18 (\(k=10, z=50000\)) | Time (s) | 12.840 | 13.469 | 94.824 | 17.346 |
| SUSY-10 | 5M / 18 (\(k=10, z=50000\)) | Cost Mean (\(\times 10^7\)) | 4.873 ± 0.023 | 4.876 ± 0.020 | 5.272 ± 0.040 | 4.941 ± 0.028 |
| SUSY-10 | 5M / 18 (\(k=10, z=50000\)) | Time (s) | 12.919 | 13.407 | 89.186 | 17.529 |
| KDDFULL | 4.9M / 37 (\(k=3, z=45747\)) | Cost Best (\(\times 10^7\)) | 3.308 | 3.308 | 3.318 | 3.323 |
| KDDFULL | 4.9M / 37 (\(k=3, z=45747\)) | Time (s) | 9.510 | 10.269 | 49.850 | 14.859 |
消融实验¶
为了验证“\(K\) 必须与离群点预算 \(z\) 成正比”这一关键理论预测，作者在 KDDFULL 数据集上对比了动态线性缩放的 OKMeans 与传统固定小常数近邻的 KNN 启发式策略：
| 配置 / 近邻阶数 | 聚类代价 Cost (\(\times 10^7\)) | 离群点召回率 Recall | 耗时 Time (s) | 说明 |
|---|---|---|---|---|
| OKMeans (\(K = \frac{c+1}{2}z\)) | 4.019 | 0.6160 | 9.510 | 理论保证下的动态线性尺度设置 |
| KNN (\(K=2\)) | 4.612 | 0.5605 | 9.141 | 聚类代价恶化 +14.8%，召回率显著下降 |
| KNN (\(K=5\)) | 4.371 | 0.5208 | 9.273 | 聚类代价恶化 +8.8%，召回率掉点 9.5% |
| KNN (\(K=10\)) | 4.631 | 0.5693 | 9.104 | 聚类代价恶化 +15.2%，局部噪声过度敏感 |
此外，在对参数 \(c \in \{3, 4, 5, 7, 10, 15, 20\}\) 的敏感度分析中，算法在 SUSY-5 上不同 \(c\) 对应的代价在 \(4.814 \times 10^7\) 至 \(4.852 \times 10^7\) 之间保持极高平稳性，验证了算法对超参数设定的鲁棒性。
关键发现¶
- 大规模数据集下的全面超越：在数百万级规模的 SUSY-10 和 KDDFULL 上，OKMeans 不仅聚类代价超越了复杂的 TIKMeans 与 NKMeans，运行速度更比 TIKMeans 快 5 至 7 倍，充分验证了朴素启发式在工业级负载下的优越性。
- 近邻数尺度的致命影响：实验表明，将近邻数 \(K\) 固定为常数会导致离群点召回率锐减、聚类代价剧烈恶化；近邻数与离群点总预算 \(z\) 呈线性联动是保证算法性能与理论下界成立的关键分水岭。
- 两变体的互补性：OKMeans2 凭借中段近邻距离累加，在理论证明上给出了更紧凑的近似上界（\(5.98\) vs \(9\)），在小规模数据集（如 SKIN）上表现出更稳健的方差与略优的聚类质量；而单近邻的 OKMeans 则在计算速度上占据微弱优势。
亮点与洞察¶
- 理论与直觉的完美桥接：首次从严谨理论上回答了“经典的异常检测启发式能否直接用于聚类”这一长期未决问题，证明了极简的 KNN 策略无需任何双准则放宽即可获得常数因子逼近保证。
- 巧妙避让前 \(z\) 个近邻的聚合设计：OKMeans2 识别出离群点局部抱团伪造低分数的本质缺陷，提出跳过前 \(z\) 个近邻、只累加中段近邻距离的打分规则，展现出极具启发性的对抗鲁棒统计设计思维。
- 工业级近线性扩展能力：通过理论指导的线性近邻尺度搭配核心集和 GPU/CPU FAISS 向量检索，将理论近似算法成功落地到了 500 万规模的真实场景中。
局限与展望¶
- 依赖簇规模下界假设：算法的理论分析严格依赖最优解中每个簇规模大于 \(cz\)（\(c>1\)）的前提；若存在天然极小规模的微型簇，算法会因无法区分真实微簇与局部离群簇而出现理论界失效。
- 理论上界仍有紧缩空间：作者明确指出目前的 \(5.98\) 与 \(9\) 倍近似常数界并非紧界，未来有望通过构造匹配的理论下界或更精细的几何刻画进一步收敛理论 gap。
- 拓展至其他鲁棒统计目标：目前主要针对 \(k\)-Means 展开完整实证，附录仅对 \(k\)-Median 与 \(k\)-Center 做了初步推导，未来可进一步拓展至非欧空间、图谱聚类及流式聚类场景。
相关工作与启发¶
- vs TIKMeans (Huang et al., ICML 2024)：TIKMeans 依赖多轮自适应采样和复杂的中心缩减过程，需要使用 \(O(k)\) 个中心或剔除 \((1+\epsilon)z\) 个离群点；本文方法严格满足 \(k\) 个中心和 \(z\) 个离群点约束，且在百万级数据集上速度快数倍。
- vs NKMeans (Im et al., AISTATS 2020)：NKMeans 同样基于密度过滤，但需要预先知晓或通过几何猜测遍历最优聚类代价 \(\mathrm{OPT}\)，且需要剔除 \(2z\) 个点；本文方法无需接触 \(\mathrm{OPT}\)，单次离群点过滤即可完成归约。
- vs 经典 KNN 异常检测 (Ramaswamy et al., SIGMOD 2000)：经典工作通常将 \(K\) 取为微小常数以检测局部异常点；本文揭示了在鲁棒聚类场景下必须将 \(K\) 设为与全局异常预算 \(z\) 呈线性比例的关键机制。
评分¶
- 新颖性: ⭐⭐⭐⭐ 首次给出 KNN 异常检测启发式在鲁棒聚类问题中的常数因子理论近似保证。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖 4 个经典数据集、6 种基准对比、百万级规模全流程验证及详实的参数消融。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨优雅，理论分析与算法设计环环相扣，逻辑脉络极度清晰。
- 价值: ⭐⭐⭐⭐⭐ 兼具扎实的理论深度与卓越的工程实用性，对鲁棒统计与无监督聚类领域有重要参考价值。