基于粒球计算的自适应$k$近邻分类器

# 基于粒球计算的自适应 k 近邻分类器

来源：https://arxiv.org/html/2608.12903

Shuyin Xia\*，Hongxuan He，Lifeng Shen，Guoyin Wang，Xinbo Gao

致谢：X. Lian, S. Xia, H. He, L. Shen 和 X. Gao 任职于重庆邮电大学计算智能重庆市重点实验室、网络空间大数据智能安全教育部重点实验室、数字经济智能与大数据智能计算川渝共建重点实验室，重庆，400065，中国。电子邮箱：[email protected], [email protected], [email protected], [email protected], [email protected]。

致谢：G. Wang 任职于重庆师范大学计算机与信息科学学院、重庆国家应用数学中心，重庆，401331，中国。电子邮箱：[email protected]。

###### 摘要

k 近邻（KNN）算法被广泛应用于各种任务中。k 值的选择是一个关键问题，因为它显著影响性能。本文提出了一种基于粒球计算的自适应高效 KNN 方法。该方法包含两个阶段。在训练阶段，首先对数据集进行粗粒度划分，以降低粒球内数据分布的复杂度，然后引入 Fisher 准则控制粒球的分裂与停止，从而生成多粒度粒球表示。在预测阶段，首先通过加权距离机制定位最近的粒球，然后在测试样本周围构建自适应邻域。有效的 k 值由该邻域内实际包含的样本数量动态确定。由最近粒球诱导的邻域提供了更稳定的局部群体信息，从而提高了对噪声和局部扰动的鲁棒性。实验结果表明，所提方法在多个数据集上的准确率和效率均优于现有的 KNN 变体。代码已开源以供复现：https://github.com/lianxiaoyu724/Adaptive-GBKNN。

###### 索引术语

KNN，粒球计算，粒球分裂，分类，自适应性。

## I 引言

k 近邻（KNN）算法是一种经典的监督学习算法\[22 (https://arxiv.org/html/2608.12903#bib.bib1)\]。它计算测试实例到所有训练样本的欧氏距离，然后找出 k 个最近邻，并通过其类标签的多数投票进行最终分类。该算法广泛应用于语音识别\[18 (https://arxiv.org/html/2608.12903#bib.bib33)\]、模式识别\[37 (https://arxiv.org/html/2608.12903#bib.bib34),25 (https://arxiv.org/html/2608.12903#bib.bib21),2 (https://arxiv.org/html/2608.12903#bib.bib22),38 (https://arxiv.org/html/2608.12903#bib.bib20),1 (https://arxiv.org/html/2608.12903#bib.bib23)\]、分类和聚类任务\[10 (https://arxiv.org/html/2608.12903#bib.bib38),21 (https://arxiv.org/html/2608.12903#bib.bib37),36 (https://arxiv.org/html/2608.12903#bib.bib35),13 (https://arxiv.org/html/2608.12903#bib.bib36),8 (https://arxiv.org/html/2608.12903#bib.bib39)\]中。然而，该算法仍存在两个局限性。在高维和大规模数据集中，距离计算和排序的成本急剧增加，导致计算复杂度不可接受\[24 (https://arxiv.org/html/2608.12903#bib.bib2)\]。此外，k 的选择会影响分类准确率：较小的 k 可能导致过拟合，而较大的 k 往往包含噪声样本，从而损害模型的鲁棒性。

参见图 Fig. 1：k 的选择对 KNN 分类效果的影响，其中测试样本应被分类为类别 2。

KNN 算法中 k 值的选择对分类准确率起着关键作用。如图 1 (https://arxiv.org/html/2608.12903#S1.F1)(a) 所示，在类别 2 的局部分布中，少数类别 1 的样本可被视为噪声。设置 k=3 可能导致测试样本被误分类为“类别 1”。因此，在存在噪声的情况下，应选择较大的 k（例如 k=15）以增强模型鲁棒性。相反，当测试样本位于决策边界附近时，如图 1 (https://arxiv.org/html/2608.12903#S1.F1)(b) 所示，较小的 k 更有利于捕捉局部结构特征，从而提高分类精度。目前，估计最优 k 值\[7 (https://arxiv.org/html/2608.12903#bib.bib24)\]或使用距离度量\[6 (https://arxiv.org/html/2608.12903#bib.bib25),4 (https://arxiv.org/html/2608.12903#bib.bib26)\]的改进 KNN 算法已被广泛应用于各个研究领域。邻域搜索的概念已成为 KNN 的一个重要发展方向。2007 年，Yiu 等人通过引入反向 k 近邻（RKNN）搜索的概念，扩展了传统的反向最近邻查询\[35 (https://arxiv.org/html/2608.12903#bib.bib27)\]。然而，与传统的 KNN 一样，RKNN 也容易受到 k 选择的影响。核心挑战在于如何针对不同数据集有效地检测邻域结构，尤其是在数据特征未知的情况下尤为困难。针对这一挑战，研究者提出了自然邻域这一有趣的思想，并引发了广泛的研究\[20 (https://arxiv.org/html/2608.12903#bib.bib29)\]。自然邻域是一种无尺度的邻域关系，能够更好地反映数据的真实特征。如果数据点 x 认为 y 是其邻居，且 y 同样认为 x 是其邻居，则 x 和 y 形成自然邻域关系\[40 (https://arxiv.org/html/2608.12903#bib.bib18)\]。当数据集中的每个对象都能找到其自然邻域时，数据集即达到稳定状态。

自然邻域为传统 kNN 中预设的 k 提供了一种自适应替代方案。然而，基于自然邻域的方法往往高度依赖于数据点的局部几何结构\[34 (https://arxiv.org/html/2608.12903#bib.bib19)\]。当数据中存在噪声或离群点时，这些异常点可能显著改变邻域结构，导致分类结果的稳定性和准确率下降。特别是当数据呈现高维和复杂分布（例如非凸形状或多峰分布）时，距离度量的判别能力下降，自然邻域关系可能无法准确捕捉类间的边界特征，从而对分类性能产生负面影响。近年来，一些研究将粒球计算引入 KNN 分类。通过用粒球替代原始样本点，并基于最近粒球进行决策，这些方法在一定程度上提高了分类效率和鲁棒性\[28 (https://arxiv.org/html/2608.12903#bib.bib3),26 (https://arxiv.org/html/2608.12903#bib.bib9)\]。然而，现有方法主要依赖与纯度相关的函数来生成粒球，而纯度不足以充分刻画粒球内样本的几何结构。在分类阶段，它们通常直接基于单个最近粒球进行决策，缺乏对查询样本局部邻域的显式建模。尽管已有研究进一步将粒球计算与自然邻域方法（MGKNN）\[32 (https://arxiv.org/html/2608.12903#bib.bib4)\]相结合，但其粒球划分过程仍主要依赖无监督机制，无法充分利用类别监督信息。因此，如何自适应地生成更好的监督粒球表示，并在此基础上构建适用于查询样本的自适应邻域决策机制，仍是一个值得进一步研究的问题。

为解决上述局限，本文提出了一种基于粒球计算的高效自适应粒球 KNN（GBKNN）算法。该算法首先通过将包含 n 个样本的原始数据集划分为 \(\sqrt{n}\) 个粒球，简化每个粒球内的数据分布。同时引入 Fisher 准则来控制粒球的自适应生成。随后，根据测试样本与最近粒球的空间关系，为其构建自适应局部邻域，从而自适应地确定有效 k 值。具体而言，本研究的贡献包括：

- 提出了一种高效且完全自适应的粒球生成方法。该方法首先以粗粒度对数据进行划分，以降低粒球内数据分布的复杂度，然后利用 Fisher 准则指导粒球分裂，从而建立从粗到细的自适应粒球生成框架。
- 提出了一种基于粒球结构构建自适应邻域关系的 KNN 方法。该方法不直接通过最近粒球进行分类，而是以最近粒球为参考，为测试样本构建局部自适应邻域，并根据该邻域内实际包含的样本数量自适应地确定 k 值。
- 在多个基准数据集上的实验结果表明，与几种对比方法相比，GBKNN 在分类准确率、鲁棒性和时间效率方面均取得了更优的整体性能。

本文其余部分组织如下：第 II 节 (https://arxiv.org/html/2608.12903#S2) 概述了 KNN 技术的发展历程，并讨论了粒球计算的相关研究。第 IV 节 (https://arxiv.org/html/2608.12903#S4) 介绍了一种完全自适应的粒球生成方法，并在此基础上设计了自适应 GBKNN 算法。第 V 节 (https://arxiv.org/html/2608.12903#S5) 报告了实验结果，并对算法性能进行了全面分析。最后，第 VI 节 (https://arxiv.org/html/2608.12903#S6) 对全文进行了总结，并指出了未来值得探索的方向。

## II 相关工作

### II-A KNN 分类方法

基于邻域的 KNN 算法已通过整合多种策略在各个领域得到广泛发展，以克服传统 KNN 的局限性\[11 (https://arxiv.org/html/2608.12903#bib.bib30),19 (https://arxiv.org/html/2608.12903#bib.bib31),9 (https://arxiv.org/html/2608.12903#bib.bib32)\]。这些发展大致可分为三个方法论方向。首先，一些方法旨在重构邻域结构，以更好地反映真实的数据流形。为了解决固定最近邻定义的僵化性，Yiu 等人\[35 (https://arxiv.org/html/2608.12903#bib.bib27)\]引入了反向 KNN（RKNN）模型，利用反向最近邻搜索来提高查询效率。类似地，Brito 等人\[5 (https://arxiv.org/html/2608.12903#bib.bib28)\]提出了互 k 近邻（MKNN）模型，通过构建互最近邻图来提高鲁棒性并降低大规模数据集的计算复杂度。此外，Zhu 等人\[40 (https://arxiv.org/html/2608.12903#bib.bib18)\]提出了自然邻域（NaNEKNN）方法，通过基于数据集中相互邻近性识别邻居，消除了手动选择 k 参数的需要。这些方法重新定义了邻域的形成方式，为更具适应性的 KNN 变体奠定了基础。

其次，采用自适应策略根据局部密度或分布来确定邻域大小。Mullick 等人\[17 (https://arxiv.org/html/2608.12903#bib.bib5)\]提出了自适应 KNN（AdaKNN），利用局部密度和分布模式，并与神经网络集成，以提高分类性能。类似地，OneStepKNN\[39 (https://arxiv.org/html/2608.12903#bib.bib17)\]、无参数 KNN（PLKNN）\[12 (https://arxiv.org/html/2608.12903#bib.bib7)\]和 Dr.k-NN\[41 (https://arxiv.org/html/2608.12903#bib.bib8)\]根据数据特征动态推断最优邻居数量，而非依赖预先指定的 k 值。这些方法有效缓解了对 k 的敏感性，并增强了 KNN 对复杂数据分布的适应性。

第三，在表示层面，使用粗粒度或结构化近似来提高效率，同时不显著牺牲精度。为此，Ayyad 等人\[3 (https://arxiv.org/html/2608.12903#bib.bib6)\]提出了一种在测试样本周围定义圆形加权区域的策略，结合 SMKNN 和 LMKNN 变体，以提高基因表达数据中的分类精度、稳定性和效率。最近，Xie 等人\[32 (https://arxiv.org/html/2608.12903#bib.bib4)\]提出了 MGKNN 算法，利用粒球计算构建多粒度粒球表示和邻域关系，同时动态确定 k 值，从而显著提高了 KNN 的分类精度。然而，该方法仍依赖传统 KNN 算法，并且在粒球生成过程中没有充分利用标签信息，仍有进一步改进的空间。

### II-B 粒球计算

粒球计算是粒计算中的一个重要模型，其核心思想是自适应地构建大小不同的粒球来覆盖样本空间，从而通过基于粒球的表示来驱动学习过程。在效率方面，粒球的数量远小于样本数量，因此降低了计算开销；在鲁棒性方面，粒球的粗粒度特性使其对样本噪声不太敏感；在可解释性方面，粒球的拓扑结构提供了多粒度描述。

对于监督数据集，粒球生成通常设置为完全覆盖，即覆盖率为 1，而粒球的紧致性通常通过平均半径来保证。给定数据集 \(D=\{x_i \mid i=1,2,...,n\}\)，常用的监督粒球表示模型定义为：

\[
\begin{split}
&\min_{c_i,r_i,m} m\\
&s.t.\ \ quality(GB_i)\geq\phi\left(x_j\right),i=1,2,...,m,j=1,2,...,n.
\end{split}
\tag{1}
\]

其中 \(m\) 是粒球数量，\(c_i\) 和 \(r_i\) 分别表示第 \(i\) 个粒球的中心和半径。每个粒球的质量 \(quality(GB_i)\) 由约束函数 \(\phi_{x_j}\) 调节，从而防止表示退化为少数低质量的大粒球。因此，粒球生成的关键问题是在给定约束下，如何用尽可能少的粒球覆盖样本空间，同时保持较高的表示质量。该模型通常涉及粒球数量、中心、半径和质量约束的联合优化，这导致一个高度非凸的优化问题。直接求解其全局最优通常计算上不可行。因此，受“全局优先”策略的启发，该模型被高效地优化，并且一种