Adaptive $k$ Nearest Neighbors Classifier via Granular Ball Computing

# Adaptive k Nearest Neighbors Classifier via Granular Ball Computing
Source: [https://arxiv.org/html/2608.12903](https://arxiv.org/html/2608.12903)
Shuyin Xia\*Hongxuan HeLifeng ShenGuoyin WangXinbo GaoThanks:X\. Lian, S\. Xia, H\. He, L\. Shen and X\. Gao are with the Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, Sichuan\-Chongqing Co\-construction Key Laboratory of Digital Economy Intelligence and Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China\. E\-mail: lianxiaoyu724@qq\.com, xiasy@cqupt\.edu\.cn, hhxuan0726@163\.com, shenlf@cqupt\.edu\.cn, gaoxb@cqupt\.edu\.cn\.Thanks:G\. Wang are with the College of Computer and Information Science, the National Center for Applied Mathematics in Chongqing, Chongqing Normal University, Chongqing 401331, China\. E\-mail: wanggy@cqnu\.edu\.cn\.

###### Abstract

Thekk\-Nearest Neighbor \(KNN\) algorithm is widely used across various tasks\. The selection of thekkvalue is a key issue because it significantly impacts performance\. In this paper, an adaptive and efficient KNN approach via granular\-ball computing is proposed\. The method consists of two stages\.In the training stage, the dataset is first coarsely partitioned to reduce the complexity of data distributions within a granular ball, and then the Fisher criterion is introduced to control ball splitting and stopping, yielding a multi\-granularity granular ball representation\. In the prediction stage, the nearest granular ball is first located through a weighted distance mechanism, and an adaptive neighborhood is then constructed around the test sample\. The effectivekkvalue is dynamically determined by the actual number of samples contained in this neighborhood\. The neighborhood induced by the nearest granular ball provides more stable local group information, thereby improving robustness against noise and local perturbations\.Experimental results demonstrate that the proposed method outperforms existing KNN variants across multiple datasets in terms of both accuracy and efficiency\. The code has been open\-sourced for reproducibility: https://github\.com/lianxiaoyu724/Adaptive\-GBKNN\.

###### Index Terms:

KNN, Granular\-Ball Computing,Granular BallSplitting, Classification, Adaptivity\.

## IIntroduction

Thekk\-nearest neighbors \(KNN\) algorithm is a classic supervised learning algorithm\[[22](https://arxiv.org/html/2608.12903#bib.bib1)\]\. It computes Euclidean distances from the test instance to all training samples, subsequently identifying thekknearest neighbors for final classification through majority voting on their class labels\. It is widely applied in applications such as speech recognition\[[18](https://arxiv.org/html/2608.12903#bib.bib33)\], pattern recognition\[[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)\], classification and clustering tasks\[[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)\]\. However, the algorithm still has two limitations\. In high\-dimensional and large\-scale datasets, the cost of distance computation and sorting increases sharply, leading to unacceptable computational complexity\[[24](https://arxiv.org/html/2608.12903#bib.bib2)\]\. Moreover, the choice ofkkaffects classification accuracy: a smallkkmay cause overfitting, while a largekktends to include noisy samples, thereby compromising the robustness of the model\.

![Refer to caption](https://arxiv.org/html/2608.12903v1/KNN.png)Fig\. 1:The effectiveness of k selection on KNN classification, in which the test sample should be classified to Class 2\.The selection of thekkvalue of the KNN algorithm plays a critical role in determining classification accuracy\. As shown in Fig\.[1](https://arxiv.org/html/2608.12903#S1.F1)\(a\), within the local distribution of Class 2, a few Class 1 samples can be regarded as noise\. Settingk=3k=3may cause the test sample to be misclassified as “Class 1\.” Therefore, in the presence of noise, a largerkk\(e\.g\.,k=15k=15\) should be selected to enhance model robustness\. Conversely, when the test sample lies near the decision boundary, as shown in Fig\.[1](https://arxiv.org/html/2608.12903#S1.F1)\(b\), a smallerkkis preferable to better capture local structural characteristics and improve classification precision\. Currently, improved KNN algorithms that estimate the optimalkkvalue\[[7](https://arxiv.org/html/2608.12903#bib.bib24)\]or use distance metrics\[[6](https://arxiv.org/html/2608.12903#bib.bib25),[4](https://arxiv.org/html/2608.12903#bib.bib26)\]have been widely applied in various research fields\. The concept of neighborhood search has become a significant development direction for KNN\. In 2007, Yiu et al\. extended the traditional reverse nearest neighbor query by introducing the concept of reversekk\-nearest neighbor \(RKNN\) search\[[35](https://arxiv.org/html/2608.12903#bib.bib27)\]\. However, like traditional KNN, RKNN is also susceptible to the choice ofkk\. The core challenge lies in effectively detecting the neighborhood structure for different datasets, which is especially difficult when the data characteristics are unknown\.

Regarding this challenge, the natural neighbor of an interesting idea was proposed, which has triggered extensive research\[[20](https://arxiv.org/html/2608.12903#bib.bib29)\]\. Natural neighbors represent a scale\-free neighbor relationship that better reflects the true characteristics of the data\. Two data points,xxandyy, form a natural neighbor relationship ifxxconsidersyyas a neighbor andyylikewise considersxxas a neighbor\[[40](https://arxiv.org/html/2608.12903#bib.bib18)\]\. If each object in a dataset can find its natural neighbor, the dataset reaches a stable state\.The natural neighborhood provides an adaptive alternative to the presetkkin traditional kNN\. Nevertheless, methods built on natural neighborhoods tend to rely heavily on the local geometric structure of data points\[[34](https://arxiv.org/html/2608.12903#bib.bib19)\]\.When noise or outliers are present in the data, these anomalous points can significantly alter the neighborhood structure, leading to a decline in the stability and accuracy of the classification results\. Especially when the data exhibits high\-dimensional and complex distributions \(e\.g\., non\-convex shapes or multimodal distributions\), the discriminative power of distance metrics decreases, and natural neighbor relationships may fail to accurately capture the boundary features between classes, negatively impacting classification performance\.

In recent years, some studies have introduced granular\-ball computing into KNN classification\. By replacing original sample points with granular balls and making decisions based on the nearest granular ball, these methods improve classification efficiency and robustness to a certain extent\[[28](https://arxiv.org/html/2608.12903#bib.bib3),[26](https://arxiv.org/html/2608.12903#bib.bib9)\]\. However, existing methods mainly rely on purity\-related functions during granular ball generation, while purity is insufficient to fully characterize the geometric structure of samples within a granular ball\. In the classification stage, they usually make decisions directly based on a single nearest granular ball, lacking explicit modeling of the local neighborhood of the query sample\. Although a study has further combined granular\-ball computing with natural neighborhood methods \(MGKNN\)\[[32](https://arxiv.org/html/2608.12903#bib.bib4)\], their granular ball partitioning processes still mainly rely on unsupervised mechanisms and cannot fully exploit class supervision information\. Therefore, how to adaptively generate better supervised granular ball representations and, based on them, construct an adaptive neighborhood decision mechanism for query samples remains a worthwhile problem for further study\.

To address the above limitations, this paper proposes an efficient and adaptivegranular ballKNN \(GBKNN\) algorithm based on granular\-ball computing\. The algorithm initially simplifies the data distribution within eachgranular ballsby splitting the original dataset containingnnsamples inton\\sqrt\{n\}granular balls\.The Fisher criterion is jointly introduced to control the adaptive generation of granular balls\. Subsequently, an adaptive local neighborhood is constructed for the test sample according to its spatial relationship with the nearest granular ball, thereby adaptively determining the effectivekkvalue\.Specifically, the contributions of this study include:

- •A highly efficient and fully adaptive granular ball generation method is proposed\. The method first partitions the data at a coarse granularity to reduce the complexity of data distribution in a ball, and then uses the Fisher criterion to guide ball splitting, thereby establishing an adaptive generation framework of granular balls that range from coarse to fine\.
- •A KNN method that constructs adaptive neighborhood relationships based on granular ball structures is proposed\. Instead of classifying directly by the nearest granular ball, the method uses the nearest granular ball as a reference to build a local adaptive neighborhood for the test sample, and adaptively determineskkby the actual number of samples contained in that neighborhood\.
- •Experimental results on multiple benchmark datasets show that GBKNN achieves superior overall performance in terms of classification accuracy, robustness, and time efficiency compared with several competing methods\.

The remainder of this paper is organized as follows: Section[II](https://arxiv.org/html/2608.12903#S2)provides an overview of the evolution of KNN techniques, along with a discussion of relevant studies on granular\-ball computing\. In Section[IV](https://arxiv.org/html/2608.12903#S4), a fully adaptive method for generatinggranular ballsis introduced, followed by the design of an adaptive GBKNN algorithm built upon it\. Section[V](https://arxiv.org/html/2608.12903#S5)reports the experimental results and delivers a comprehensive analysis of the algorithm’s performance\. Finally, Section[VI](https://arxiv.org/html/2608.12903#S6)concludes the paper and highlights promising directions for future exploration\.

## IIRelated Work

### II\-AKNN Classification Method

Neighborhood\-based KNN algorithms have been extensively developed across various domains by integrating diverse strategies to overcome the limitations of traditional 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)\]\. These developments can be broadly categorized into three methodological directions\.

First, some methods aim to reconstruct neighborhood structures to better reflect the true data manifold\. To address the rigidity of fixed nearest\-neighbor definitions, Yiu et al\.\[[35](https://arxiv.org/html/2608.12903#bib.bib27)\]introduced the reverse KNN \(RKNN\) model, leveraging reverse nearest neighbor search to enhance query efficiency\. Similarly, Brito et al\.\[[5](https://arxiv.org/html/2608.12903#bib.bib28)\]proposed the mutualkk\-nearest neighbor \(MKNN\) model, which constructs mutual nearest neighbor graphs to improve robustness and reduce computational complexity for large datasets\. Further, Zhu et al\.\[[40](https://arxiv.org/html/2608.12903#bib.bib18)\]developed the natural neighbor \(NaNEKNN\) method, which eliminates the need for manually choosing thekkparameter by identifying neighbors based on mutual proximity in the dataset\. These methods redefine how neighborhoods are formed, providing a foundation for more adaptive KNN variants\.

Second, adaptive strategies are employed to determine neighborhood sizes based on local density or distribution\. Mullick et al\.\[[17](https://arxiv.org/html/2608.12903#bib.bib5)\]introduced the adaptive KNN \(AdaKNN\), which utilizes local density and distribution patterns, integrated with neural networks, to improve classification performance\. Similarly, OneStepKNN\[[39](https://arxiv.org/html/2608.12903#bib.bib17)\], parameterless KNN \(PLKNN\)\[[12](https://arxiv.org/html/2608.12903#bib.bib7)\], and Dr\.k\-NN\[[41](https://arxiv.org/html/2608.12903#bib.bib8)\]dynamically infer the optimal number of neighbors based on data characteristics, rather than relying on a pre\-specifiedkkvalue\. These methods effectively alleviate the sensitivity tokkand enhance KNN’s adaptability to complex data distributions\.

Third, at the representation level, coarse\-grained or structured approximations are used to enhance efficiency without significantly compromising accuracy\. To address this, Ayyad et al\.\[[3](https://arxiv.org/html/2608.12903#bib.bib6)\]proposed a strategy that defines circular weighted regions around test samples, incorporating SMKNN and LMKNN variants to boost classification accuracy, stability, and efficiency in gene expression data\. More recently, Xie et al\.\[[32](https://arxiv.org/html/2608.12903#bib.bib4)\]proposed the MGKNN algorithm, which leverages granular\-ball computing to construct multi\-granularity ball representations and neighborhood relationships while dynamically determining thekk\-value, thereby significantly improving the classification accuracy of KNN\. However, this method still relies on the traditional KNN algorithm and does not fully utilize label information during thegranular ballgeneration process, leaving room for further improvement\.

### II\-BGranular\-ball Computing

Granular\-ball computing is an important model in granular computing, whose core idea is to adaptively construct granular balls of varying sizes to cover the sample space, thereby driving the learning process through granular ball\-based representations\. In terms of efficiency, the number of granular balls is significantly smaller than the number of samples, thus reducing computational overhead; in terms of robustness, the coarse\-granularity nature of granular balls makes them less sensitive to sample noise; in terms of interpretability, the topological structure of granular balls provides multi\-granularity descriptions\.For supervised datasets, granular ball generation is usually set to full coverage, i\.e\., the coverage ratio is 1, while ball compactness is typically ensured by the average radius\. Given a datasetD=\{xi∣i=1,2,…,n\}D=\\\{x\_\{i\}\\mid i=1,2,…,n\\\}, a commonly used supervised granular ball representation model is defined as:

minci,ri,m⁡ms\.t\.q​u​a​l​i​t​y​\(G​Bi\)≥ϕ⁡\(xj\),i=1,2,…,m,j=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\}\(1\)wheremmis the number of granular balls, andcic\_\{i\}andrir\_\{i\}denote the center and radius of theii\-th granular ball, respectively\. The quality of each granular ball,q​u​a​l​i​t​y​\(G​Bi\)quality\(GB\_\{i\}\), is regulated by the constraint functionϕxj\\phi\_\{x\_\{j\}\}, thereby preventing the representation from degenerating into a few low\-quality large balls\. Hence, the key problem in granular ball generation is how to cover the sample space with as few granular balls as possible while maintaining high representation quality under the given constraints\.

This model usually involves the joint optimization of the number, centers, radii, and quality constraints of granular balls, which leads to a highly non\-convex optimization problem\. Directly obtaining its global optimum is often computationally intractable\. Therefore, inspired by the “global\-first” strategy, this model is efficiently optimized and approximately solved through a coarse\-to\-fine granular ball splitting process with quality control\.Initially,granular ballgeneration utilized the 2\-means algorithm\[[28](https://arxiv.org/html/2608.12903#bib.bib3)\]\. The purity threshold needs to be optimized within a specific range to adapt to different datasets and address label noise, but this process is computationally expensive\. To address this challenge, Xia et al\. proposed a novelgranular ballgeneration method by controlling the weighted purity sum of sub\-granular ballsand accelerating the splitting process using a division method\[[26](https://arxiv.org/html/2608.12903#bib.bib9)\]\. However, this method still requires improvements in stability and efficiency\. Subsequently, Xie et al\.\[[33](https://arxiv.org/html/2608.12903#bib.bib10)\]introduced the GBG \(GBG\+\+\) method, based on an attention mechanism, which significantly improves efficiency and robustness while achieving stability\. As a novel approach, granular\-ball computing has inspired various theoretical methods in machine learning, includinggranular ballclassifiers\[[27](https://arxiv.org/html/2608.12903#bib.bib11)\],granular ballclustering methods\[[31](https://arxiv.org/html/2608.12903#bib.bib12)\],granular ballneural networks\[[29](https://arxiv.org/html/2608.12903#bib.bib13)\],granular ballrough sets\[[30](https://arxiv.org/html/2608.12903#bib.bib14)\], andgranular ballreinforcement learning\[[16](https://arxiv.org/html/2608.12903#bib.bib15)\]\. Meanwhile, granular\-ball computing enhances efficiency and interpretability, bringing benefits that foster broader research and application potential\[[14](https://arxiv.org/html/2608.12903#bib.bib16)\]\.

\(a\)GBG\+\+ on the ‘Two Moons’ dataset\.\(b\)GBG\+\+ \(initialn\\sqrt\{n\}split\) on the ‘Two Moons’ dataset\.\(c\)GBG\+\+ on the ‘Circles’ dataset\.\(d\)GBG\+\+ \(initialn\\sqrt\{n\}split\) on the ‘Circles’ dataset\.
Fig\. 2:Comparison between GBG\+\+ and GBG\+\+ with initialn\\sqrt\{n\}granular ball splitting on two non\-linear datasets\.

## IIIPreliminaries

Granular\-ball computing takes granular balls as input units for learning\. Agranular ballis formally defined as follows\[[28](https://arxiv.org/html/2608.12903#bib.bib3)\]\.

###### Definition 1\.

Given a datasetD=\{xi,i=1,2,…,n\}D=\\\{x\_\{i\},i=1,2,\.\.\.,n\\\}, agranular ballG​BGBsplit fromDDis a spherical structure in the data space, represented by

GB=\{xi\|xi∈D,Δ\(xi−c\)≤r\},GB=\\\{x\_\{i\}\|x\_\{i\}\\in D,\\Delta\{\\color\[rgb\]\{0,0,0\}\\left\(x\_\{i\}\-c\\right\)\\leq r\\\}\},\(2\)whereΔ⁡\(xi−c\)\\Delta\\left\(x\_\{i\}\-c\\right\)denotes the distance between a samplexix\_\{i\}and the centercc\. In this study, we adopt the Euclidean distance for computation\. The centerccand radiusrrof thegranular ballare computed as follows:

c=1\|G​B\|​∑xi∈G​Bxi,r=1\|G​B\|​∑xi∈G​BΔ⁡\(xi−c\),c=\\frac\{1\}\{\\left\|GB\\right\|\}\\sum\_\{x\_\{i\}\\in GB\}x\_\{i\},\\ r=\\frac\{1\}\{\\left\|GB\\right\|\}\\sum\_\{x\_\{i\}\\in GB\}\\Delta\\left\(x\_\{i\}\-c\\right\),\(3\)where\|⋅\|\|\\cdot\|denotes the cardinality of the set, i\.e\., the number of elements in thegranular ball\.

In classification problems, eachgranular ball, similar to a sample point, is assigned a class label, as defined below\.

###### Definition 2\.

LetG​BGBbe agranular ball, and letL=\{lj,j=1,2,…,s\}L=\\\{l^\{j\},j=1,2,\\ldots,s\\\}denote the set of distinct class labels among its contained samples\. The label ofG​BGB, denoted bylG​Bl\_\{GB\}, is defined as the label with the highest frequency among its samples:

lG​B=arg⁡maxlj∈L​\|\{xi∈G​B∣lxi=lj\}\|,l\_\{GB\}=\\arg\\max\_\{l^\{j\}\\in L\}\\left\|\\\{x\_\{i\}\\in GB\\mid l\_\{x\_\{i\}\}=l^\{j\}\\\}\\right\|,\(4\)wherelxil\_\{x\_\{i\}\}is the label of samplexix\_\{i\}\.

According to Definition[2](https://arxiv.org/html/2608.12903#Thmdefinition2), the label of agranular ballis determined by the majority class of its contained samples, thus providing robustness to noise\. The quality of agranular ballcan be measured by its purity, defined as follows\.

###### Definition 3\.

The purity of agranular ballG​BGB, denoted byPP, measures the proportion of samples inG​BGBthat share thegranular ball’slabellG​Bl\_\{GB\}:

P=\|\{xi∈G​B∣lxi=lG​B\}\|\|G​B\|\.P=\\frac\{\\left\|\\\{x\_\{i\}\\in GB\\mid l\_\{x\_\{i\}\}=l\_\{GB\}\\\}\\right\|\}\{\\left\|GB\\right\|\}\.\(5\)

In subsequent work, Xie et al\.\[[33](https://arxiv.org/html/2608.12903#bib.bib10)\]introduced a splitting\-based mechanism forgranular ballgeneration, which begins with the entire dataset treated as a singlegranular ball\. Specifically, the entire dataset is initially regarded as agranular ball, denoted byG​BGB, which fails to meet the required quality criterion\. The splitting process proceeds as follows:

Step 1: Compute the majority class labell∗l^\{\\ast\}within thegranular ballG​BGB\.

l∗=a​r​g​max⁡∑i=1nlj∈L⁡𝕀⁡\(lx=lj\),l^\{\\ast\}=arg\\max\_\{l^\{j\}\\in L\}\\sum\_\{i=1\}^\{n\}\\mathbb\{I\}\(l\_\{x\}=l^\{j\}\),\(6\)where𝕀⁡\(⋅\)\\mathbb\{I\}\(\\cdot\)denotes the indicator function\.

Step 2: Calculate the corresponding centercl∗c\_\{l^\{\\ast\}\}and radiusrl∗r\_\{l^\{\\ast\}\}based on the majority class samples\. To characterize the majority class region within the granular ballG​BGB, first extract the subset of samples belonging to the majority classl∗l^\{\\ast\}and compute its size:

G​Bl∗=\{xi∈G​B∣lxi=l∗\},Nl∗=\|G​Bl∗\|\.GB\_\{l^\{\\ast\}\}=\\left\\\{x\_\{i\}\\in GB\\mid l\_\{x\_\{i\}\}=l^\{\\ast\}\\right\\\},\\quad N\_\{l^\{\\ast\}\}=\\left\|GB\_\{l^\{\\ast\}\}\\right\|\.\(7\)Then, calculate the centercl∗c\_\{l^\{\\ast\}\}and radiusrl∗r\_\{l^\{\\ast\}\}of the majority class samples:

cl∗=1Nl∗​∑xi∈G​Bl∗xi,rl∗=1Nl∗​∑xi∈G​Bl∗Δ⁡\(xi−cl∗\)\.c\_\{l^\{\\ast\}\}=\\frac\{1\}\{N\_\{l^\{\\ast\}\}\}\\sum\_\{x\_\{i\}\\in GB\_\{l^\{\\ast\}\}\}x\_\{i\},\\quad r\_\{l^\{\\ast\}\}=\\frac\{1\}\{N\_\{l^\{\\ast\}\}\}\\sum\_\{x\_\{i\}\\in GB\_\{l^\{\\ast\}\}\}\\Delta\\left\(x\_\{i\}\-c\_\{l^\{\\ast\}\}\\right\)\.\(8\)Here,Δ⁡\(⋅\)\\Delta\(\\cdot\)denotes the Euclidean distance\.

Step 3: Construct a sub\-granular ballusing points within the computed radius\.

G​Bk=\{xi∈G​B∣Δ⁡\(xi−cl∗\)≤rl∗\}\.GB\_\{k\}=\\left\\\{x\_\{i\}\\in GB\\mid\\Delta\\left\(x\_\{i\}\-c\_\{l^\{\\ast\}\}\\right\)\\leq r\_\{l^\{\\ast\}\}\\right\\\}\.\(9\)
The iterative execution of Steps 1 to 3 continues until the number of remaining samples equals the number of class labels\. This method has significantly improved the efficiency ofgranular ballgeneration\. However, it exhibits limitations when dealing with complex nonlinear data structures, such as ‘Two Moons’ or ‘Circles’ datasets\.

Specifically, the GBG\+\+ method constructs eachgranular ballby calculating the center and radius based solely on the majority class samples, resulting in an approximately spherical shape\. This geometric assumption implicitly presumes isotropic distributions, making it inadequate for fitting elongated or curved data structures\. As a result,granular ballsmay mistakenly include structurally dissimilar samples or exclude similar ones, leading to structural errors\. As illustrated in Fig\.[2](https://arxiv.org/html/2608.12903#S2.F2)\(a\) and Fig\.[2](https://arxiv.org/html/2608.12903#S2.F2)\(c\), such mismatches hinder the model’s ability to represent high\-dimensional, non\-uniform data spaces effectively\. To address this issue, we propose generatingn\\sqrt\{n\}granular ballsfrom the global dataset to enable a more appropriate partitioning at the global level, simplifying the internal distribution within each ball and mitigating errors caused by limited local fitting capacity\. Furthermore, existing methods typically require repeated tuning of the purity threshold to accommodate different datasets and label noise, which not only relies heavily on manual effort but also incurs considerable computational cost\.

![Refer to caption](https://arxiv.org/html/2608.12903v1/GBKNN_xin.png)Fig\. 3:The GBKNN, as illustrated in the overall flowchart, consists of two main modules: i\) granular ball generation; ii\) classification decision\.
## IVProposed method

### IV\-AMotivation

Although existing granular ball\-based KNN methods\[[28](https://arxiv.org/html/2608.12903#bib.bib3)\]have clear advantages over traditional KNN in classification efficiency and robustness, they still have limitations in both granular ball generation and decision making\. First, in supervised granular ball generation, existing methods usually rely on specified purity thresholds or purity\-related functions as the partition criterion\. As a result, they focus mainly on label information and cannot fully capture the geometric distribution of samples within each granular ball\. Second, in the prediction stage, these methods typically classify directly based on the nearest ball, lacking a mechanism to construct a local neighborhood around the test sample, and thus failing to reflect the true distribution near the test sample fully\. Although MGKNN\[[32](https://arxiv.org/html/2608.12903#bib.bib4)\]enhances neighborhood modeling through granular ball clustering and enables adaptive adjustment ofkk, its granular ball generation still mainly relies on unsupervised mechanisms, making it difficult to fully exploit class supervision information and limiting its ability to represent true class boundaries\. To address the above issues, this paper proposes a new supervised and fully adaptive granular ball generation method\. The method first obtains an initial granular ball representation throughn\\sqrt\{n\}\-based coarse division and then uses the Fisher criterion, which captures both distributional representation and class discrimination, to control the granular ball generation process\. The coarse\-grained granular ball representation can effectively reduce the influence of noise points, thereby improving model robustness\. In the decision stage, an adaptive local neighborhood is constructed for each test sample based on the nearest granular ball, and the value ofkkis automatically determined by the number of samples in the neighborhood\. This not only further reduces the influence of small noisy granular balls but also better matches the decision mechanism of KNN\.

The overall algorithm, as illustrated in Fig\.[3](https://arxiv.org/html/2608.12903#S3.F3), consists of two main modules: thegranular ballgeneration and classification decision\. First, the entire dataset is globally split inton\\sqrt\{n\}initialgranular ballsto simplify data distributions within each ball \(Fig\.[3](https://arxiv.org/html/2608.12903#S3.F3), Step 1\)\. A coarse\-to\-fine splitting procedure is then performed, guided bythe Fisher criterionthat adaptively controls the splits without relying on preset thresholds\. To further enhance decision boundary representation, a new purity lower bound based on label information is introduced, followed by a global overlap removal strategy to improve the structural clarity ofgranular balls\. In the classification decision stage \(Fig\.[3](https://arxiv.org/html/2608.12903#S3.F3), Module 2\), test samples are not granularized\.Instead, the nearest granular ball is located through a weighted distance mechanism, and the distance from the test sample to the farthest sample within that ball is used as the neighborhood radiusRk​N​NR\_\{kNN\}to construct an adaptive neighborhood centered on the test sample, thereby enabling efficient dynamic selection ofkk\.

### IV\-BAdaptiveGranular BallGeneration

Initial Partitioning\. In the generation ofgranular balls, directly splitting the entire dataset may be affected by the complexity of data distribution, particularly in the presence of nonlinear structures such as crescents or rings\. This is because GBG\+\+ determines the center and radius of eachgranular ballsolely based on majority\-class samples\. Such geometric assumptions fail to accommodate elongated or curved data regions, making it difficult to aligngranular ballswith the true shape of the data\. As a result, the generatedgranular ballsoften exhibit excessive overlaps or leave out relevant samples, as shown in Fig\.[2](https://arxiv.org/html/2608.12903#S2.F2)\(a\) and[2](https://arxiv.org/html/2608.12903#S2.F2)\(c\), ultimately degrading the model’s ability to represent intrinsic structures accurately\. To better handle complex data structures, the datasetD=\{xi∣i=1,2,…,n\}D=\\\{x\_\{i\}\\mid i=1,2,\\ldots,n\\\}is initially partitioned inton\\sqrt\{n\}granular ballsusing thekk\-means algorithm\. Assume that the dataset containsssclasses, andDlD^\{l\}denotes the subset of samples in thell\-th class\. The initial centero\(0\)o^\{\(0\)\}is randomly selected according to the proportion of each class, i\.e\.,

oj\(0\)=Random\(\{xi∈Dl\|l=1,2,\.\.,s\}\),j=1,2,…,n\.o\_\{j\}^\{\(0\)\}=\{\\rm Random\}\\left\(\\left\\\{x\_\{i\}\\in D^\{l\}\|l=1,2,\.\.,s\\right\\\}\\right\),j=1,2,\.\.\.,\\sqrt\{n\}\.\(10\)Each data pointxi∈Dx\_\{i\}\\in Dis assigned to the nearest centroidojo\_\{j\}usingkk\-means clustering:

G​Bj∗\(t\)=\{xi∈D\|j∗=a​r​g​minj​\{Δ⁡\(xi,oj\(t\)\)\}\},\{GB\_\{j^\{\*\}\}^\{\(t\)\}\}=\\left\\\{x\_\{i\}\\in D\|\{j^\{\*\}\}=arg\\min\_\{j\}\\left\\\{\\Delta\\left\(x\_\{i\},o\_\{j\}^\{\(t\)\}\\right\)\\right\\\}\\right\\\},\(11\)wherettis the iteration index\. The centroid is then updated as:

oj\(t\+1\)=1\|G​Bj\(t\)\|​∑xi∈G​Bjtxi\.\{o\_\{j\}^\{\(t\+1\)\}\}=\\frac\{1\}\{\\left\|GB\_\{j\}^\{\(t\)\}\\right\|\}\\sum\_\{x\_\{i\}\\in GB\_\{j\}^\{t\}\}x\_\{i\}\.\(12\)The alternating iteration follows Eq\. \([11](https://arxiv.org/html/2608.12903#S4.E11)\) and Eq\. \([12](https://arxiv.org/html/2608.12903#S4.E12)\) until the centroids converge, ultimately yieldingn\\sqrt\{n\}stablegranular ballsand completing the initial data split\.

To further validate the effectiveness of first performingn\\sqrt\{n\}splitting, we conducted experiments on the crescent and ring\-shaped datasets, and visualized the results using the GBG\+\+ method, as shown in Fig\.[2](https://arxiv.org/html/2608.12903#S2.F2)\(b\) and \(d\)\. Compared to directly applying the GBG\+\+ method for splitting, the proposed strategy yields a more accurate approximation of the data distribution and better preserves the intrinsic geometric structure of the data\. Specifically, on the crescent and ring\-shaped datasets, the GBG\+\+ method generated 109 and 85granular balls, respectively, whereas the number was significantly reduced to 21 and 62 when preceded byn\\sqrt\{n\}\-based splitting\. This reduction is due to the initialn\\sqrt\{n\}splitting, which effectively reduces the global mixing of data points, resulting in more stable subsequentgranular ballpartitioning and avoiding the computational overhead and overlap issues caused by excessive splitting\. Therefore, this approach not only improves the data fitting capability but also optimizes thegranular ballsplit efficiency, providing a better solution for applying thegranular ballmethod to complex data structures\.

Granular BallSplitting Method:After generatingn\\sqrt\{n\}initialgranular balls, we further refine the split\. As reviewed in Section II\-B, the GBG\+\+ method employs an attention\-based splitting strategy\[[33](https://arxiv.org/html/2608.12903#bib.bib10)\], which demonstrates superior performance in terms of computational efficiency and stability compared to traditional methods such askk\-means andkk\-partitioning\. Specifically, GBG\+\+ effectively focuses on key data regions, enabling more accurategranular ballsplitting while minimizing redundant computations and enhancing overall efficiency\. Therefore, we adopt the GBG\+\+ approach described in Eq\. \([6](https://arxiv.org/html/2608.12903#S3.E6)\), \([7](https://arxiv.org/html/2608.12903#S3.E7)\), \([8](https://arxiv.org/html/2608.12903#S3.E8)\) and \([9](https://arxiv.org/html/2608.12903#S3.E9)\) to further split the initialgranular balls, ensuring structural stability and optimizing computational costs\.

In classification tasks, the overlap between heterogeneousgranular ballscan lead to misclassification of samples in the overlapping regions, thereby affecting classification accuracy\. Traditional methods typically perform deduplication only after thegranular ballgeneration is complete\. In contrast, this paper innovatively integrates the deduplication strategy into thegranular ballgeneration process by executing deduplication after each split \(as shown in Fig\.[3](https://arxiv.org/html/2608.12903#S3.F3)\)\. Further splitting is performed to reduce their size for overlapping heterogeneousgranular balls, thereby optimizing subsequentgranular ballsplits\. This strategy not only actively suppresses the accumulation of overlap, preventing excessive overlap caused by multiple rounds of splitting and improving the stability ofgranular ballsplitting, but also gradually resolves the overlap issue during the splitting process, reducing the overall computational complexity of deduplication and improving computational efficiency\.

Stop Condition:In the process ofgranular ballgeneration, the purity threshold is commonly used to guide the splitting ofgranular balls\. However, due to the diverse characteristics of different datasets, the optimal value of the purity threshold often varies within a certain range, making it challenging to adaptively determine a fixed value in practice\.Existing supervised adaptive granular ball generation methods usually determine whether to split a ball according to whether the weighted sum of the purities of the resulting child balls increases\[[26](https://arxiv.org/html/2608.12903#bib.bib9)\]\. However, purity only measures the proportion of the dominant label within a granular ball and cannot fully characterize the geometric distribution of samples inside it\. To address this limitation, this paper introduces a new criterion to control the granular ball generation process, namely the Fisher criterion, which is defined as follows\. Suppose a granular ballG​BGBcontains samples fromLLclasses\. Letnln\_\{l\}denote the number of samples in thell\-th class,μl\\mu\_\{l\}the mean of thell\-th class, andμ\\muthe overall mean of all samples in the granular ball\. Then, the Fisher value of the granular ball is defined as:

F=∑l=1Lnl​‖μl−μ‖∑l=1Lnl​Sl,F=\\frac\{\\sum\_\{l=1\}^\{L\}\{n\_\{l\}\\left\\\|\{\\mu\_\{l\}\-\\mu\}\\right\\\|\}\}\{\\sum\_\{l=1\}^\{L\}\{n\_\{l\}S\_\{l\}\}\},\(13\)whereSlS\_\{l\}represents the intra\-class divergence of class l, defined as:

Sl=1nl​∑xi∈G​Bl‖xi−μl‖2\.S\_\{l\}=\\frac\{1\}\{n\_\{l\}\}\\sum\_\{x\_\{i\}\\in\{\{GB\}\_\{l\}\}\}\{\{\{\\left\\\|\{x\_\{i\}\-\\mu\_\{l\}\}\\right\\\|\}^\{2\}\}\}\.\(14\)Here,G​BlGB\_\{l\}represents the set of samples of classll\.

Unlike the stopping criterion based on the weighted sum of granular balls’ purities, the Fisher criterion is not limited to measuring label consistency within a granular ball\. Instead, it evaluates both inter\-class separability and intra\-class compactness from the perspective of feature distribution\. The weighted purity sum is essentially based on label proportions\. While it can reflect the degree of class mixing within a granular ball, it cannot adequately characterize the geometric structure of samples in the feature space\. In contrast, by jointly modeling between\-class scatter and within\-class scatter, the Fisher criterion can more comprehensively characterize a granular ball, thereby providing a finer and more robust basis for ball splitting and stopping\. A small Fisher value indicates insufficient class separation or excessive within\-class dispersion, suggesting that the granular ball remains mixed and should be further split\.

Since a granular ball with purity equal to 1 is directly treated as a terminal ball, we further adopt a Fisher\-based splitting criterion for non\-pure granular balls\. It should be noted that the Fisher criterion is not equivalent to purity, and therefore, we do not claim that it can theoretically guarantee a monotonic increase in purity\. Instead, it focuses on the change in local structure before and after splitting\. Specifically, when the weighted Fisher value of the sub\-ball set is higher than that of the parent ball, the split achieves a better balance between inter\-class separability and intra\-class compactness, thereby improving the representation of the granular ball, and the split is accepted; otherwise, it is rejected, and the parent ball is retained\.

Optimization ofGranular Balls’Quality:During granular ball partitioning, maintaining high purity within each granular ball is a key factor affecting classification performance\. Existing splitting criteria may mistakenly accept some low\-purity parent balls, which can negatively affect the final classification accuracy\. For example, the initial granular ball has a purity ofP=55/100=0\.55P=55/100=0\.55\. After splitting, two child balls are obtained with puritiesP1=28/50=0\.56P\_\{1\}=28/50=0\.56andP2=27/50=0\.54P\_\{2\}=27/50=0\.54, respectively\. In this case, although a split occurs, both child balls remain highly mixed, and neither inter\-class separability nor intra\-class compactness is substantially improved\. As a result, the weighted Fisher value of the child balls may be close to, or even lower than, that of the parent ball, so the Fisher criterion would judge the split as ineffective and stop further splitting\. However, because the purity is still low, such granular balls may reduce subsequent classification accuracy and weaken the overall quality of the granular ball representation\.To address the above issue, we propose a new category\-adaptive purity lower boundTLjT\_\{L\_\{j\}\}, which is defined as follows:

TLj=∑i=1N\|G​Bi∗\|\|Lj\|,T\_\{L\_\{j\}\}=\\frac\{\{\\textstyle\\sum\_\{i=1\}^\{N\}\}\\left\|GB^\{\*\}\_\{i\}\\right\|\}\{\\left\|L\_\{j\}\\right\|\},\(15\)whereLjL\_\{j\}denotes the set of thejj\-th classes in the datasetDDandNNis the total number ofgranular ballsset𝒢\\mathcal\{G\}generated after splitting\.

This strategy allows for a more accurate assessment of thegranular ballquality across different classes\. It adaptively adjusts the purity for each class, ensuring that the parentgranular ballstops splitting only after achieving sufficient quality\. Additionally, it prevents low\-qualitygranular ballsfrom terminating prematurely, as shown in the diagram, thereby improving the overallgranular balls’quality\. In addition, since the de\-overlapping operation is applied only locally within sub\-balls during the process, residual overlaps between different classes may persist\. Therefore, a final global de\-overlapping step is required to eliminate such inter\-class overlaps and ensure a clear decision boundary\.

### IV\-CClassification Decision

Existing granular ball\-based KNN methods usually classify directly according to the distance between the test sample and the nearest boundary granular ball, which can improve classification efficiency and robustness to some extent\. However, such methods essentially rely on only a single nearest granular ball for decision making and do not explicitly construct a local neighborhood around the test sample\. To address this issue, this paper proposes a novel neighborhood decision\-making mechanism based on granular balls\. Specifically, it first selects the granular ball whose boundary is closest to the test sample, and then uses the distance from the test sample to the farthest sample within that ball as the neighborhood radius, thereby constructing an adaptive neighborhood centered on the test sample\.To address this issue, this paper innovatively proposes a sample\-number\-based weighting method, which dynamically adjusts the confidence ofgranular ballsto mitigate the impact of noisygranular ballson classification decisions, thereby enhancing classification robustness\. Based on this, the weighted distance is defined as follows:

###### Definition 4\.

Let𝒢=\{GBi∣i=1,2,…,N\}\\mathcal\{G\}=\\\{GB\_\{i\}\\mid i=1,2,\.\.\.,N\\\}be agranular ballset\. The weighted distance between the test samplext​e​s​tx^\{test\}and the ballG​Bi∈𝒢GB\_\{i\}\\in\\mathcal\{G\}is defined as:

W​di​\(xt​e​s​t,G​Bi\)=\(1−\|G​Bi\|∑j=1N\|G​Bj\|\)⋅\(Δ⁡\(xt​e​s​t,oi\)−ri\),Wd\_\{i\}\\left\(x^\{test\},GB\_\{i\}\\right\)=\\left\(1\-\\frac\{\|GB\_\{i\}\|\}\{\\sum\_\{j=1\}^\{N\}\|GB\_\{j\}\|\}\\right\)\\cdot\\left\(\\Delta\\left\(x^\{test\},o\_\{i\}\\right\)\-r\_\{i\}\\right\),\(16\)where\|G​Bi\|\|GB\_\{i\}\|represents the number of samples contained in the ballG​BiGB\_\{i\}\.

The weighted distance enhances the reliability ofgranular balllabels by adjusting the boundary distance based on the proportion of sample counts, prioritizinggranular ballswith larger sample sizes and reducing the influence of noise or smallgranular ballson decision\-making\.

After obtaining the weighted nearest granular ball for the test sample, we further use the distance from the test sample to the farthest sample within that ball as the neighborhood radius, thereby constructing an adaptive neighborhood centered on the test sample\. Since a granular ball consists of multiple similar samples, it can effectively reduce noise interference and provide more stable and reliable local group information than a single nearest sample point\. The neighborhood induced by the nearest ball fully covers the samples within that ball while remaining compact\. In other words, it preserves the reliable local information represented by the nearest granular ball without unnecessarily expanding the neighborhood\.

Compared with existing KNN methods based on granular\-ball computing, this approach explicitly constructs a strict neighborhood relation around the test sample, thus preserving the basic idea that labels are determined by neighborhoods\. Compared with traditional KNN, the neighborhood here is first guided by the coarser granular ball, which gives the method advantages in both efficiency and robustness\. Moreover, the actual number of samples contained in the neighborhood naturally determines the correspondingkkvalue, so the neighborhood size no longer depends on manual setting but is adaptively determined by the local data distribution around the test sample\. Therefore, the proposed method not only retains the efficiency and robustness of multi\-granularity granular ball representation, but also preserves the essential KNN characteristic of making decisions based on local neighborhoods\.

### IV\-DAlgorithm Procedure

This paper proposes an improvedgranular ballKNN classification method, which consists of the generation ofgranular ballsand classification decision \(as illustrated in Fig\.[3](https://arxiv.org/html/2608.12903#S3.F3)\)\. To optimize the initialgranular ballpartitioning and reduce the number of iterations, this paper directly splits the entire dataset inton\\sqrt\{n\}granular ballsand designs a new evaluation index to select the optimal initialgranular balldivision scheme, thereby simplifying the data distribution within each ball\. Subsequently, the GBG\+\+ method is employed for fastgranular ballsplitting, introducing weighted purity of sub\-balls for dynamic control, achieving threshold\-free and adaptive splitting\.Considering that low\-quality granular balls may remain after splitting, this paper further introduces an optimization of the granular ball quality stage, which refines the granular ball set based on a new purity threshold to improve ball quality and provide more reliable granular ball representations for subsequent classification decisions\. In the classification stage, the proposed method first identifies the nearest granular ball of the test sample using a weighted distance measure, then constructs an adaptive neighborhood centered on the test sample based on that ball, and finally determines the label by using the sample information within the neighborhood\. The detailed procedure is given in Algorithm[1](https://arxiv.org/html/2608.12903#alg1)\.

Algorithm 1GBKNN algorithmInput: Noise training setDn​o​i​s​yD\_\{noisy\}, test setDt​e​s​tD\_\{test\}; Output: The accuracy of GBKNN;

1:Select

n\\sqrt\{n\}initial points randomly according to the label ratio multiple times to split

n\\sqrt\{n\}balls using

kk\-means, and evaluate according to Eq\. \([32](https://arxiv.org/html/2608.12903#S4.E32)\) to select the optimalgranular ballset

𝒢n\\mathcal\{G\}\_\{\\sqrt\{n\}\}\.

2:Initial

W=0W=0,

𝒢b​a​l​l=∅\\mathcal\{G\}\_\{ball\}=\\emptyset,

𝒢n​e​x​t=𝒢n\\mathcal\{G\}\_\{next\}=\\mathcal\{G\}\_\{\\sqrt\{n\}\};

3:while

𝒢n​e​x​t≠∅\\mathcal\{G\}\_\{next\}\\neq\\emptysetdo

4:Select one granular ball

G​BjGB\_\{j\}from

𝒢n​e​x​t\\mathcal\{G\}\_\{next\}, calculatethe Fisher valueWWofG​BjGB\_\{j\};

5:Split thegranular ball

G​BjGB\_\{j\}using the GBG\+\+ method;Calculate the sum of all sub\-balls’ Fisher valueFG​BjF\_\{GB\_\{j\}\};

6:if

W<FG​BjW<F\_\{GB\_\{j\}\}then

7:Delete

G​BjGB\_\{j\}from

𝒢n​e​x​t\\mathcal\{G\}\_\{next\}, de\-overlap heterogeneous balls in sub\-balls and add the resulting balls to

𝒢n​e​x​t\\mathcal\{G\}\_\{next\};

8:else

9:Add

G​BjGB\_\{j\}to

𝒢b​a​l​l\\mathcal\{G\}\_\{ball\}and remove it from

𝒢n​e​x​t\\mathcal\{G\}\_\{next\};

10:endif

11:Return to step 4\.

12:endwhile

13:Get

TLjT\_\{L\_\{j\}\}by the Eq\. \([15](https://arxiv.org/html/2608.12903#S4.E15)\), and then use the GBG\+\+ method to segment the balls with purity lower than

TLjT\_\{L\_\{j\}\};

14:De\-overlap heterogeneousgranular balls;

15:According to Eq\. \([16](https://arxiv.org/html/2608.12903#S4.E16)\), the weighted distanceWdW\_\{d\}from each test sample to all granular balls is first computed to identify the nearest granular ballG​B∗GB^\{\*\}\.

16:Then, the distance from the test sample to the farthest sample within that ball is taken as the radius

Rk​N​N​\(x\)=maxxi∈G​B∗⁡Δ⁡\(x,xi\)R\_\{kNN\}\(x\)=\\max\_\{x\_\{i\}\\in GB^\{\*\}\}\\Delta\\left\(x,x\_\{i\}\\right\)\. An adaptive neighborhood centered on the test sample can be constructed\.

17:It can get the label of the test sample can be obtained based on the neighborhood, and the final accuracy can be obtained\.

### IV\-ETheoretical Investigation

To further validate the effectiveness of the initial splitting method, a theorem is presented that proves directly that splittingn\\sqrt\{n\}granular ballsresults in balls with better density compared to the binary splitting method\. Specifically, the direct splitting method better maintains the density balance of the clusters during the division, leading to theoretically superior partition results, with thesegranular ballsexhibiting a clear advantage in terms of density distribution\.

###### Theorem 1\.

Let the dataset beD=\{x1,x2,…,xn\}⊂ℝdD=\\left\\\{x\_\{1\},x\_\{2\},\\dots,x\_\{n\}\\right\\\}\\subset\\mathbb\{R\}^\{d\}and assume it is splitted inton\\sqrt\{n\}granular balls\{G​Bi,i=1,2,…,n\}\\\{GB\_\{i\},i=1,2,\.\.\.,\\sqrt\{n\}\\\}, whererir\_\{i\}denotes the radius of theii\-th ball\.ΩG​Bi\\Omega\_\{GB\_\{i\}\}denotes the data space region that thegranular ballG​BiGB\_\{i\}covers\. The average densityρ¯\\bar\{\\rho\}is defined as:

ρ¯=1n​∑i=1nρi,ρi=1n​∑i=1nniVi,\\bar\{\\rho\}=\\frac\{1\}\{\\sqrt\{n\}\}\\sum\_\{i=1\}^\{\\sqrt\{n\}\}\\rho\_\{i\},\\ \\rho\_\{i\}=\\frac\{1\}\{\\sqrt\{n\}\}\\sum\_\{i=1\}^\{\\sqrt\{n\}\}\\frac\{n\_\{i\}\}\{V\_\{i\}\},\(17\)whereni=\|G​Bi\|n\_\{i\}=\\left\|GB\_\{i\}\\right\|denotes the number of samples inG​BiGB\_\{i\}, andViV\_\{i\}represents the volume ofG​BiGB\_\{i\}\. Consider the following two partitioning methods:

Method 1\(Global Partition\): Then\\sqrt\{n\}granular ballsare obtained by directly applying the k\-means algorithm over the entire dataset;

Method 2\(Recursive Partition\): Then\\sqrt\{n\}granular ballsare generated via recursive binary splitting using 2\-means\.

The following conclusions are satisfied:

\(i\) If the data are uniformly distributed, then the average densities of samples in granular balls produced by both methods are approximately equal;

\(ii\) Assuming that the data are drawn from a Lipschitz\-continuous probability density functionf⁡\(x\)f\(x\), the average density of sample points in thegranular ballsgenerated byMethod 1is higher than that ofMethod 2, i\.e\.,ρ¯\(1\)\>ρ¯\(2\)\\bar\{\\rho\}^\{\(1\)\}\>\\bar\{\\rho\}^\{\(2\)\}\.

###### Proof\.

\(i\) Uniform Distribution\.

Assume that the dataset is normalized to lie within the unit hypercube, so that all data pointsxi∼U⁡\(\[0,1\]d\)x\_\{i\}\\sim U\(\[0,1\]^\{d\}\)are drawn from a uniform distribution over the unit hypercube\. For Method 1, thekk\-means algorithm is directly applied to split the data inton\\sqrt\{n\}granular balls\. Since the data are uniformly distributed, eachgranular ballcovers approximately the same region, with volume denoted byVV, and the number of samples contained in each ball,\|G​Bi\|≈n\|GB\_\{i\}\|\\approx\\sqrt\{n\}, is roughly equal\. Inℝd\\mathbb\{R\}^\{d\}, the volume of a ball\[[15](https://arxiv.org/html/2608.12903#bib.bib40)\]with radiusrris given by

Vd​\(r\)=πd/2Γ⁡\(1\+d/2\)​rd=ξd​rd,V\_\{d\}\(r\)=\\frac\{\\pi^\{d/2\}\}\{\\Gamma\(1\+d/2\)\}\{r^\{d\}\}=\\xi\_\{d\}r^\{d\},\(18\)whereΓ\\Gammadenotes the gamma function andξd\\xi\_\{d\}is a constant\. Whend=1d=1, thusξ1=2\\xi\_\{1\}=2; hence,V⁡\(r\)=2​rV\(r\)=2r, which represents the length of a line segment\. Whend=2d=2, we haveξ2=π\\xi\_\{2\}=\\pi; therefore,V⁡\(r\)=π​r2V\(r\)=\\pi r^\{2\}, which represents the area of a circle\.

The average density of sample points in agranular ballis

ρ¯\(1\)≈nVd\.\\bar\{\\rho\}^\{\(1\)\}\\approx\\frac\{\\sqrt\{n\}\}\{V\_\{d\}\}\.\(19\)
For Method 2, under the assumption of uniform data distribution, the recursive splitting process is performed in a balanced manner, resulting ingranular ballswith equal volumes; similarly, we have

ρ¯\(2\)≈nVd\.\\bar\{\\rho\}^\{\(2\)\}\\approx\\frac\{\\sqrt\{n\}\}\{V\_\{d\}\}\.\(20\)
In summary, when the samplesxi∼U⁡\(\[0,1\]d\)x\_\{i\}\\sim U\(\[0,1\]^\{d\}\)are drawn from a uniform distribution over the unit hypercube, thegranular ballsgenerated by both methods have similar volumes and sample counts, and thus their densities tend to be approximately equal, i\.e\.,

ρ¯\(1\)≈ρ¯\(2\)\.\\bar\{\\rho\}^\{\(1\)\}\\approx\\bar\{\\rho\}^\{\(2\)\}\.\(21\)
\(ii\) Non\-uniform Distributions\.

Assume that the data samples are drawn from a probability density functionf⁡\(x\)f\(x\)\. On eachgranular ballG​BiGB\_\{i\}, the functionf⁡\(x\)f\(x\)has a bounded gradient and satisfies the Lipschitz condition; that is, there exists a constantLi\>0L\_\{i\}\>0such that\[[23](https://arxiv.org/html/2608.12903#bib.bib41)\]:

∀x,y∈G​Bi,\|f⁡\(x\)−f⁡\(y\)\|≤Li​‖x−y‖\.\\forall x,y\\in GB\_\{i\},\\left\|f\(x\)\-f\(y\)\\right\|\\leq L\_\{i\}\\left\\\|x\-y\\right\\\|\.\(22\)Since the samples follow the distributionf⁡\(x\)f\(x\), the expected number of samples inG​BiGB\_\{i\}is approximately

E⁡\[\|G​Bi\|\]≈n​∫ΩG​Bif⁡\(x\)​𝑑x\.E\\left\[\\left\|GB\_\{i\}\\right\|\\right\]\\approx n\\int\_\{\\Omega\_\{GB\_\{i\}\}\}f\\left\(x\\right\)dx\.\(23\)We rewrite the functionf⁡\(x\)f\(x\)onG​BiGB\_\{i\}as:

f⁡\(x\)=f⁡\(ci\)\+\(f⁡\(x\)−f⁡\(ci\)\)\.f\\left\(x\\right\)=f\\left\(c\_\{i\}\\right\)\+\\left\(f\\left\(x\\right\)\-f\\left\(c\_\{i\}\\right\)\\right\)\.\(24\)Substitute this approximation Eq\. \([24](https://arxiv.org/html/2608.12903#S4.E24)\) into the integral:

∫ΩG​Bif⁡\(x\)​𝑑x=∫ΩG​Bi\(f⁡\(ci\)\+\(f⁡\(x\)−f⁡\(ci\)\)\)​𝑑x=f⁡\(ci\)​Vi\+∫ΩG​Bi\(f⁡\(x\)−f⁡\(ci\)\)​dx\.\\begin\{split\}\\int\_\{\\Omega\_\{GB\_\{i\}\}\}f\\left\(x\\right\)dx&=\\int\_\{\\Omega\_\{GB\_\{i\}\}\}\\left\(f\\left\(c\_\{i\}\\right\)\+\\left\(f\\left\(x\\right\)\-f\\left\(c\_\{i\}\\right\)\\right\)\\right\)dx\\\\ &=f\\left\(c\_\{i\}\\right\)V\_\{i\}\+\\int\_\{\\Omega\_\{GB\_\{i\}\}\}\\left\(f\\left\(x\\right\)\-f\\left\(c\_\{i\}\\right\)\\right\)dx\.\\end\{split\}\(25\)By multiplying by the total number of samplesnn, the expected number of samples can be estimated as:

E⁡\[\|G​Bi\|\]≈n​∫ΩG​Bif⁡\(x\)​𝑑x=n​f​\(ci\)​Vi\+n​∫ΩG​Bi\(f⁡\(x\)−f⁡\(ci\)\)​𝑑x=n​f​\(ci\)​Vi\+ϵi\.\\begin\{split\}E\\left\[\\left\|GB\_\{i\}\\right\|\\right\]&\\approx n\\int\_\{\\Omega\_\{GB\_\{i\}\}\}f\\left\(x\\right\)dx\\\\ &=nf\\left\(c\_\{i\}\\right\)V\_\{i\}\+n\\int\_\{\\Omega\_\{GB\_\{i\}\}\}\\left\(f\\left\(x\\right\)\-f\\left\(c\_\{i\}\\right\)\\right\)dx\\\\ &=nf\\left\(c\_\{i\}\\right\)V\_\{i\}\+\\epsilon\_\{i\}\.\\end\{split\}\(26\)Therefore,ϵi\\epsilon\_\{i\}represents the error in estimatingE⁡\[\|G​Bi\|\]E\\left\[\\left\|GB\_\{i\}\\right\|\\right\]—that is, the error caused by usingf⁡\(ci\)​Vif\\left\(c\_\{i\}\\right\)V\_\{i\}instead of the integral∫ΩG​Bi\(f⁡\(x\)\)​𝑑x\\int\_\{\\Omega\_\{GB\_\{i\}\}\}\\left\(f\\left\(x\\right\)\\right\)dx\. Sincef⁡\(x\)f\(x\)is Lipschitz continuous onG​BiGB\_\{i\}, that is,

\|f⁡\(x\)−f⁡\(ci\)\|≤Li​‖x−ci‖≤Li​ri\.\\left\|f\\left\(x\\right\)\-f\\left\(c\_\{i\}\\right\)\\right\|\\leq L\_\{i\}\\left\\\|x\-c\_\{i\}\\right\\\|\\leq L\_\{i\}r\_\{i\}\.\(27\)
Then, the corresponding error term can be bounded as follows:

ϵi≤n​∫ΩG​Bi\(Li​ri\)​𝑑x≤n​Li​ri​Vi\.\\epsilon\_\{i\}\\leq n\\int\_\{\\Omega\_\{GB\_\{i\}\}\}\\left\(L\_\{i\}r\_\{i\}\\right\)dx\\leq nL\_\{i\}r\_\{i\}V\_\{i\}\.\(28\)So the densityρi\\rho\_\{i\}of samples ingranular ballG​BiGB\_\{i\}can be estimated as follows:

ρi=niVi=E⁡\[\|G​Bi\|\]Vi≈n​f​\(ci\)\+n​Li​ri,\\rho\_\{i\}=\\frac\{n\_\{i\}\}\{V\_\{i\}\}=\\frac\{E\\left\[\\left\|GB\_\{i\}\\right\|\\right\]\}\{V\_\{i\}\}\\approx nf\\left\(c\_\{i\}\\right\)\+nL\_\{i\}r\_\{i\},\(29\)wheref⁡\(ci\)f\(c\_\{i\}\)denotes the value of the density function at the centercic\_\{i\}of the ball\.For each granular ball, a largerf⁡\(ci\)f\\left\(c\_\{i\}\\right\)and a smaller error termn​Li​rinL\_\{i\}r\_\{i\}lead to a higher estimated density\.

Method 1 generatesn\\sqrt\{n\}granular ballsacross the entire data space\. The samples within each ball are as concentrated as possible, andrir\_\{i\}is small, which increases the concentration of samples within the clusters, i\.e\., largerf⁡\(ci\)f\(c\_\{i\}\)\. Since k\-means tends to generate balls with balanced sizes and smallrir\_\{i\}, the sample concentration within each ball is higher, leading to smaller error\. As a result, according to Eq\. \([29](https://arxiv.org/html/2608.12903#S4.E29)\), the estimated densityρi\\rho\_\{i\}for eachgranular ballis larger\. Therefore, Method 1 yieldsgranular ballswith higher individual densitiesρi\\rho\_\{i\}, and consequently achieves a larger average density:

ρ¯\(1\)=1n​∑i=1nρi\.\\bar\{\\rho\}^\{\(1\)\}=\\frac\{1\}\{\\sqrt\{n\}\}\\sum\_\{i=1\}^\{\\sqrt\{n\}\}\\rho\_\{i\}\.\(30\)
Method 2 uses recursive 2\-means splitting\. Since each round of division only focuses on local information, the final centerscic\_\{i\}are no longer globally optimal and may fall into regions with lower densityf⁡\(x\)f\(x\)\. This can result ingranular ballswith larger radii or uneven sample distributions, wheref⁡\(ci\)f\\left\(c\_\{i\}\\right\)is smaller,rir\_\{i\}is larger, andLiL\_\{i\}is unstable, leading to larger error terms\. Consequently, the average densityρ¯\(2\)\\bar\{\\rho\}^\{\(2\)\}tends to be lower\. Therefore,

ρ¯\(1\)\>ρ¯\(2\)\.\\bar\{\\rho\}^\{\(1\)\}\>\\bar\{\\rho\}^\{\(2\)\}\.\(31\)∎

Remark: In density estimation, then​Li​rinL\_\{i\}r\_\{i\}term represents an upper bound for the error, not the actual trend of density increasing with radiusrir\_\{i\}\. This is a consequence of using the Lipschitz continuity to estimate the bias introduced in the integral approximation\. As a result, the density approximation takes a form related to this argument\. In fact, the densityρi\\rho\_\{i\}does not necessarily increase with the radiusrir\_\{i\}, especially in non\-uniform distributions, where the sample density in regions farther from the center of the ball typically decreases\. Therefore, the main termn​f​\(ci\)nf\(c\_\{i\}\)should be considered the core estimate of the density, while the error termn​Li​rinL\_\{i\}r\_\{i\}is only used to quantify the bias and does not reflect the actual trend of density change\.

In the above method, the selection of initial points is crucial\. Initially, we randomly selected initial points based on the proportion of samples with different labels\. However, this random strategy does not guarantee the optimality ofgranular ballsplitting, often requiring multiple computations and validation to determine the best partitioning, leading to high computational costs\. Moreover, random initialization may result in an imbalanced distribution of initialgranular balls, which can affect the stability of subsequent splits and the overall quality of the finalgranular balls\.

To address the above issue, a heuristic criterion based on density evaluation is proposed to optimize the initial split ofn\\sqrt\{n\}granular balls\. Specifically, we first generaten\\sqrt\{n\}initialgranular balls, denoted as𝒢n\\mathcal\{G\}\_\{\\sqrt\{n\}\}, and introduce the sum ofgranular balls’densities as an evaluation metric to assess the quality of the partitioning\. This criterion enhances the separability of the initialgranular ballsand provides a more stable and effective foundation for subsequent refinement\. The mathematical definition is as follows:

S​u​mT=∑j=1nρj,Sum\_\{T\}=\\sum\_\{j=1\}^\{\\sqrt\{n\}\}\{\\rho\}\_\{j\},\(32\)whereρj\{\\rho\}\_\{j\}denotes the density estimate of thegranular ballG​Bj∈𝒢nGB\_\{j\}\\in\\mathcal\{G\}\_\{\\sqrt\{n\}\}, reflecting the compactness of the sample distribution within the ball\. A higher density indicates that the samples are more tightly clustered, suggesting stronger representational and discriminative capabilities of thegranular ball\. By introducing a density\-based evaluation criterion, a relatively optimal initialgranular ballsplit can be achieved with fewer random selections\. This approach effectively reduces uneven distributions caused by randomness, enhancing the stability and reproducibility of the splitting process\. Moreover, it promotes a more compact and balanced initial structure, providing a more robust foundation for subsequentgranular ballrefinement\. As a result, the overall computational cost is reduced, and generation efficiency is significantly improved\.

### IV\-FTime Complexity

The overall time complexity of the proposed algorithm can beconsideredfrom two stages: thegranular ballgeneration stage and the classification decision stage\. Thegranular ballgeneration stage primarily consists of the initial partitioning ofgranular ballsand the dynamic splitting process based on the GBG\+\+ method\.In contrast, the classification decision stage uses a weighted nearest ball to construct a neighborhood centered on the predicted point and completes the classification\.Next, we analyze the computational complexity of each stage separately\.

#### IV\-F1Granular Ball Generation Stage

First, we applykk\-means to obtain an initial division of the dataset inton\\sqrt\{n\}granular balls, which simplifies subsequent computations\. The time complexity ofkk\-means is typicallyO⁡\(n​k​Tk\)O\(nkT\_\{k\}\), whereTkT\_\{k\}denotes the number ofkk\-means iterations\. By settingk=nk=\\sqrt\{n\}, the time complexity of this initial division stage becomesO⁡\(n​n​Tk\)O\(n\\sqrt\{n\}T\_\{k\}\)\.Subsequently, during the GBG\+\+ iterative splitting stage,each ball is controlled based on the weighted Fisher sum of its split sub\-balls, ultimately formingGGgranular ballsSince the time complexity of GBG\+\+ is close to linear, i\.e\.,O⁡\(n\)O\(n\), andgranular ballstend to stabilize during the intermediate stages, the overall complexity forgranular ballsplitting can be approximated asO⁡\(n\)O\(n\)\[[33](https://arxiv.org/html/2608.12903#bib.bib10)\]\. Furthermore, the de\-overlapping operation is performed after each split, but it only affects a small number of adjacentgranular balls, thus the computational load is relatively low and can be neglected\. Therefore, the total time complexity for the entiregranular ballgeneration stage can be expressed asO⁡\(n​n​Tk\)\+O⁡\(n\)=O⁡\(n​n\)O\(n\\sqrt\{n\}T\_\{k\}\)\+O\(n\)=O\(n\\sqrt\{n\}\)\.

#### IV\-F2Classification Decision Stage

In the classification stage, for each test sample, the weighted distances to all granular balls are first computed to identify the weighted nearest ball and initialize the neighborhood radius\. Let the number of test samples beMM, and the final number of granular balls beNN\. The time complexity of this step isO⁡\(M​N\)O\(MN\)\. To avoid exhaustive search over all training samples, the proposed method further uses the geometric boundaries of granular balls to filter candidate neighborhoods\. Specifically, only those granular balls whose boundary distance to the test sample is no greater than the neighborhood radius are considered to potentially intersect the neighborhood\. Therefore, sample\-level distance computation is performed only within these candidate balls\. In this way, neighborhood construction consists of two levels: a coarse filtering at the granular ball level, followed by a fine filtering at the sample level within the candidate balls\. Letsis\_\{i\}denote the number of samples in the candidate granular balls of theii\-th test sample that require further distance computation\. Then, the total complexity of the sample\-level fine filtering over the whole test set isO⁡\(∑i=1Msi\)O\(\\sum\_\{i=1\}^\{M\}s\_\{i\}\)\. Accordingly, the total time complexity of the classification stage can be written asO⁡\(M​N\+∑i=1Msi\)O\\left\(\{MN\+\\sum\_\{i=1\}^\{M\}\{s\_\{i\}\}\}\\right\)\. Ifs¯\\bar\{s\}denotes the average number of samples that need to be further checked within the candidate granular balls for each test sample, the above complexity can be further simplified asO⁡\(M⁡\(N\+s¯\)\)O\\left\(\{M\\left\(N\+\\bar\{s\}\\right\)\}\\right\)\.

#### IV\-F3Overall Time Complexity Analysis

Traditional KNN is a lazy learning method, whose main computational cost is concentrated in the testing stage, with complexityO⁡\(M​n\)O\(Mn\)\. In contrast, the proposed method consists of two stages: a granular ball generation stage and a classification stage\. The complexity of the granular ball generation stage isO⁡\(n​n\)O\(n\\sqrt\{n\}\), while the complexity of the classification stage isO⁡\(M⁡\(N\+s¯\)\)O\(M\(N\+\\bar\{s\}\)\)\. Therefore, the total complexity of the proposed method isO⁡\(n​n\+M⁡\(N\+s¯\)\)\.O\\\!\\left\(n\\sqrt\{n\}\+M\(N\+\\bar\{s\}\)\\right\)\.When the number of test samples is large andN\+s¯≪nN\+\\bar\{s\}\\ll n, the additional cost introduced by preprocessing can be compensated by the efficiency gain in the subsequent classification stage, so that the proposed method achieves an overall computational advantage\.

## VExperiment details

This section conducts an experiment analysis from four main aspects: i\) comparing the classification accuracy of different methods across various datasets; ii\) analyzing the accuracy variation trends of each method under different noise conditions; iii\) evaluating the runtime performance of different methods;iv\) evaluating the classification accuracy and running time of GBKNN on large\-scale datasets; v\) verifying, through ablation studies, the effectiveness of then\\sqrt\{n\}\-based coarse partition, neighborhood construction, and purity lower\-bound mechanism in improving model performance\.

### V\-ASetup

TABLE I:Data informationBaselines:The proposed method is compared with several baseline algorithms, including KNN\[[22](https://arxiv.org/html/2608.12903#bib.bib1)\], NaNEKNN\[[40](https://arxiv.org/html/2608.12903#bib.bib18)\], adaKNN variants\[[17](https://arxiv.org/html/2608.12903#bib.bib5)\], SMKNN\[[3](https://arxiv.org/html/2608.12903#bib.bib6)\], LMKNN\[[3](https://arxiv.org/html/2608.12903#bib.bib6)\], OneStepKNN\[[39](https://arxiv.org/html/2608.12903#bib.bib17)\], PLKNN\[[12](https://arxiv.org/html/2608.12903#bib.bib7)\], MGNR\[[32](https://arxiv.org/html/2608.12903#bib.bib4)\],GBKNN\_2019\[[28](https://arxiv.org/html/2608.12903#bib.bib3)\]and the method based on sub\-balls weighted purity and control ball division, and using weighted nearest granular ball decision\-making, is denoted as GBKNN\_p\.

TABLE II:Average classification accuracy of different methods under various noise conditionsImplementation details:For the traditional KNN algorithm, the value ofkkis set within the range\[1,15\]\[1,15\]with a step size of 2, and the optimalkkis determined through hyperparameter tuning using the training set\. In the generation ofgranular balls, our method first randomly selects the initial point 10 times to splitn\\sqrt\{n\}balls and then selects the optimal splitting result for subsequent calculations based on the evaluation index\. To ensure the comparability of performance evaluation across different algorithms on the same dataset, classification accuracy \(ACC\) is adopted as the evaluation metric, which quantifies the consistency between classification results and ground truth labels\. A higher ACC value indicates better classification performance\. In the experiments, all datasets are randomly split into train and test sets in a8:28:2ratio to ensure fairness and robustness\. Each dataset is augmented by introducing noise at different proportions: 0%, 5%, 10%, 15%, 20%, 25%, and 30%\. It is important to note that noise is introduced only to the training set, while the validation and test sets remain free of noise, ensuring the reliability and validity of the results\. For all experiments, our hardware experimental environment is an AMD Ryzen Threadripper PRO 5975WX 32\-Cores 3\.60 GHz, and the software experiment environment is Python 3\.9\.

### V\-BMain Results

In Table[II](https://arxiv.org/html/2608.12903#S5.T2), the average accuracy results of different methods under 7 noise levels are presented, with the optimal results highlighted inboldand the second\-best results marked withunderline\. As shown in Table[II](https://arxiv.org/html/2608.12903#S5.T2), the GBKNN algorithm achieves the best or second\-best accuracy on most datasets, significantly outperforming the other13algorithms\. Particularly under various noise conditions,GBKNN and GBKNN\_p show notable improvementsin average accuracy compared to the latest multi\-granularity\-based MGNR method\.GBKNN further achieves better performance than GBKNN\_p\. For example, on the ‘heart1’ dataset, the accuracy of the MGNR method is 0\.6379, while the proposed GBKNN algorithm achieves an accuracy of0\.8030, surpassing MGNR by approximately25\.88%\. On all datasets, the GBKNN method reaches an average accuracy of0\.8736, outperforming other algorithms\.In comparison, the average accuracies of GBKNN\_2019 and GBKNN\_p are 0\.8195 and 0\.8622, respectively\. Therefore, GBKNN improves the average accuracy by approximately 6\.60% and 1\.32% compared with GBKNN\_2019 and GBKNN\_p, respectively\.

This result fully demonstrates the outstanding performance of the GBKNN algorithm in classification tasks, clearly surpassing existing methods\. The superior performance of GBKNN mainly comes from its adaptive granular ball representation and neighborhood construction mechanism\. Specifically, the initial partition inton\\sqrt\{n\}coarse granular balls preserves the overall distribution while simplifying local data structures, thereby reducing the effect of complex nonlinear distributions\. Compared with GBKNN\_p, GBKNN uses the Fisher criterion for granular ball partitioning\. Unlike purity, the Fisher criterion simultaneously captures inter\-class separability and intra\-class compactness, thus providing more reasonable guidance for granular ball generation\. Classifying based on coarse\-grained granular balls helps reduce the impact of noise points and enhances robustness\. In the decision stage, GBKNN first searches for the nearest granular ball by a weighted distance, and then uses the distance from the test sample to the farthest sample within that ball as the neighborhood radius to construct an adaptive neighborhood around the test sample\. Since a granular ball consists of multiple similar samples, it provides more reliable local group information than a single nearest neighbor\. Meanwhile, the neighborhood induced by the nearest granular ball can fully cover the reliable local sample group while remaining compact, which helps to enhance robustness and improve the overall classification accuracy\.

### V\-CEffect of varying noise levels\.

To evaluate the impact of different noise levels, multiple noise intensities were considered, with the results presented in Fig\.[4](https://arxiv.org/html/2608.12903#S5.F4)\. Overall, as the noise level increases, most algorithms exhibit varying degrees of performance degradation, highlighting the sensitivity of KNN\-based methods to noise interference\. Notably, OneStepKNN, adaKNNGHIS, and adaKNN2GHIS show the most significant fluctuations, particularly on datasets such as balance\-scale and phoneme, where their accuracy drops substantially, limited in robustness to noisy conditions\.

In contrast, GBKNN demonstrates notable stability and robustness\. Across all 12 datasets, GBKNN consistently maintains high accuracy under high\-noise conditions, with minimal performance decline\. For example, on the ‘haberman’, and ‘rssi’ datasets, GBKNN maintains an accuracy above 0\.75 even when noise reaches 30%\.On the ‘heart1’ dataset, GBKNN consistently outperforms all other compared methods across all noise levels\. This notable advantage is mainly attributed to the group\-based decision mechanism of GBKNN\. Unlike methods that rely on individual sample points, coarse\-grained granular balls reduce the impact of noise, thereby providing more reliable and robust local information\. Furthermore, the neighborhood radius is defined as the distance between the test sample and the farthest sample within the nearest granular ball, thus constructing an adaptive neighborhood centered at the test sample\. Such a neighborhood can fully cover the relevant samples within the nearest granular ball while maintaining good local compactness, thereby effectively enhancing the discriminative stability of the model in noisy environments\. This is also a key reason why GBKNN can maintain high accuracy and exhibit strong noise resistance even under high noise levels\.

In comparison, traditional methods such as KNN, LMKNN, and PLKNN perform reasonably well in low\-noise scenarios but degrade rapidly as noise increases, reflecting their lack of mechanisms to handle data perturbations\. NaNEKNN and SMKNN exhibit performance close to GBKNN on specific datasets such as ‘mushroom’ and ‘fourclass’, but are generally less stable\. Additionally, MGNR performs well on datasets like ‘heart1’ and ‘anneal’, suggesting that its natural neighbor strategy is effective in some tasks\. However, its performance still suffers under high noise due to susceptibility to false neighbors\. In summary, GBKNN exhibits strong adaptability and noise resilience across diverse data distributions and noise levels\. It stands out as a leading approach among existing KNN variants in terms of both stability and accuracy, making it particularly suitable for noise\-sensitive or structurally complex tasks\.

![Refer to caption](https://arxiv.org/html/2608.12903v1/noisyacc_1.png)
![Refer to caption](https://arxiv.org/html/2608.12903v1/noisyacc_2.png)

Fig\. 4:Accuracy of different methods on six datasets under different noise conditions\.TABLE III:Running time \(s\) of different methods under noise\-free conditions\.
### V\-DRuntime Analysis

As shown in Table[III](https://arxiv.org/html/2608.12903#S5.T3), the runtime comparison of various algorithms under noise\-free conditions is conducted on 12 datasets\. Overall, traditional KNN demonstrates relatively high computational efficiency on some small\-scale datasets, such as ‘heart1’, ‘cleveland’, and ‘haberman’, where it achieves relatively short runtimes\. Meanwhile, several improved KNN\-based methods also exhibit certain efficiency advantages on some datasets\. In contrast, GBKNN\_p and GBKNN incur slightly higher runtimes on small\-scale datasets, mainly due to the additional granular ball generation process before classification, which introduces extra preprocessing overhead\. However, as the data scale increases, the efficiency advantage of granular ball\-based methods becomes more evident\. On datasets such as ‘phoneme’, ‘Anuran’, ‘mushroom’, ‘anneal’, and ‘Skin NonSkin’, both GBKNN\_p and GBKNN achieve significantly lower runtimes than most competing algorithms\. For example, on the ‘anneal’ dataset, the runtime of GBKNN is only 0\.3576, which is much faster than 4\.2327 for GBKNN\_2019 and 30\.2779 for the traditional KNN\. Similarly, on ‘phoneme’, ‘mushroom’, and ‘Skin NonSkin’, GBKNN achieves runtimes of 2\.4616, 2\.4396, and 3\.2114, respectively, demonstrating strong computational efficiency\. Overall, the granular ball\-based representation effectively reduces the computational cost caused by sample\-wise operations, leading to better scalability on medium and large scale datasets\.

Further comparison among GBKNN\_2019, GBKNN\_p, and GBKNN shows that GBKNN\_p is generally slightly faster than GBKNN, while GBKNN consistently outperforms GBKNN\_2019 in terms of runtime\. This difference mainly stems from their distinct granular ball generation and decision mechanisms\. Specifically, GBKNN\_2019 improves efficiency by replacing sample points with granular balls, but its splitting strategy is relatively inefficient\. GBKNN\_p adopts a coarse division and controls granular ball splitting based on purity, and directly performs classification using the nearest granular ball, resulting in a simpler computational process\. In contrast, GBKNN employs the Fisher criterion to guide granular ball splitting and stopping, enabling more refined partitioning\. In the prediction stage, it constructs an adaptive neighborhood centered at the test sample based on the nearest granular ball rather than directly using it for classification\. Although this neighborhood construction introduces additional computational cost, it also enhances classification performance\.

In summary, the results in Table III indicate that both GBKNN\_p and GBKNN achieve favorable time efficiency while maintaining high classification performance\. GBKNN\_p is more efficient in terms of computational speed, whereas GBKNN achieves a better balance between efficiency and discriminative power, demonstrating strong practical value\.

### V\-EResults of large\-scale datasets

Furthermore, to further validate the applicability of the proposed method in large\-scale scenarios, experiments are conducted on five large\-scale datasets, including ‘Santander’, ‘creditcard’, ‘covertype’, ‘Higgs’, and ‘supersymmetry’, and the results are reported in the table\. Due to the large sample sizes and high computational cost of these datasets, some competing algorithms encounter issues such as excessive memory consumption or prohibitively long runtimes, making it difficult to complete the experiments within acceptable resource and time constraints\. Therefore, complete comparison results are not available on these datasets\. In this setting, the analysis primarily focuses on the classification performance and robustness of GBKNN on large\-scale datasets\.

TABLE IV:Accuracy and time performance of GBKNN on large\-scale datasets at different noise levels\.As shown in Table[IV](https://arxiv.org/html/2608.12903#S5.T4), GBKNN maintains relatively stable performance under different noise levels\. For example, on the ‘Santander’ dataset, the accuracy remains at 0\.8979 across the noise range from 0% to 30%; on the ‘creditcard’ dataset, the accuracy consistently stays above 0\.9980; and on the ‘Higgs’ dataset, the accuracy remains stable within the range of 0\.5117–0\.5220 with only minor fluctuations\. For the ‘covertype’ and ‘supersymmetry’ datasets, although accuracy declines as noise level increases, it remains stable overall\. These results indicate that GBKNN retains strong robustness and applicability when dealing with large\-scale and high\-complexity data\. Taken together with the average runtime of all noise observations, it can be seen that although the algorithm still requires a certain amount of computation time for ultra\-large datasets, it can complete the training and prediction processes under limited computational resources, demonstrating good scalability\. Overall, these findings further verify the effectiveness of GBKNN in large\-scale data scenarios and highlight the advantage of granular ball representation in reducing computational burden and improving algorithm feasibility for large datasets\.

### V\-FAblation Studies

TABLE V:Comparison of classification accuracy of GBKNN under different key modules\.As shown in Table[V](https://arxiv.org/html/2608.12903#S5.T5), all key designs improve the final performance, and the complete model integratingn\\sqrt\{n\}\-based coarse initialization, the Fisher criterion, the lower boundTLT\_\{L\}of quality, weighted boundary distanceWdW\_\{d\}, and neighborhood decision achieves the best average result of 0\.8217\. To ensure a fair comparison in the ablation study, we fixed then\\sqrt\{n\}initial cluster centers and analyzed the effect of different designs on model performance based on this setting\.Subsequently, according to the proportion of different class samples, the farthest sample from the already selected initial points was iteratively chosen untiln\\sqrt\{n\}initial points were selected\. By prioritizing the selection of majority\-class samples and incorporating a farthest\-point strategy based on global distribution, the initialgranular ballswere ensured to cover the entire data space, leading to a more balancedgranular balldivision and reducing initial partitioning imbalance\.

In the ablation study on then\\sqrt\{n\}\-based coarse division, we compared the traditional granular ball initialization method, which starts the iterative process from the whole dataset, with then\\sqrt\{n\}\-based coarse initialization strategy\. The results are shown in Table[V](https://arxiv.org/html/2608.12903#S5.T5)\(Rows 4 and 6\)\. It can be seen that introducing coarse division leads to higher classification accuracy on most datasets, with improvements exceeding 5%–10% on some datasets\. The reason is that dividing the whole dataset inton\\sqrt\{n\}coarse balls provides a simpler initial representation for the original complex distribution, which helps reduce the effect of nonlinear data distributions and avoids premature convergence to overly large granular balls, thereby providing a more reasonable basis for adaptive granular ball generation\.

The ablation experiment results for Purity and Fisher control of granular ball generation are shown in Table[V](https://arxiv.org/html/2608.12903#S5.T5)\(Rows 2 and 3\)\. The results show that replacing purity with the Fisher criterion as the control criterion for granular ball generation further improves the average performance of the model by 3\.7%\. This indicates that, compared with purity, which only considers the proportion of the dominant class, the Fisher criterion can simultaneously capture inter\-class separability and intra\-class compactness within a granular ball, thus enabling more accurate evaluation of ball quality and more effective guidance for adaptive granular ball division\.

As shown in Table[V](https://arxiv.org/html/2608.12903#S5.T5)\(Rows 5 and 6\), after introducing the quality lower\-bound mechanism \(i\.e\.,TLT\_\{L\}\), the classification accuracy improves on most datasets\. In particular, the accuracy increases by 2\.05% and 1\.32% on the ‘haberman’ and ‘rssi’ datasets, respectively\. This mechanism further refines those granular balls that do not satisfy the splitting condition but still have relatively low quality, thereby effectively improving the classification accuracy of GBKNN across different datasets\.

The effectiveness of the weighted boundary distance can be verified by comparing Rows 1 and 2 in Table[V](https://arxiv.org/html/2608.12903#S5.T5)\. Under the same purity\-based granular ball generation criterion, the average performance improves from 0\.8093 to 0\.8107\. Unlike the unweighted version, which treats all granular balls equally during prediction, the weighted boundary distance reduces the influence of small noisy balls and enhances the role of larger balls in nearest\-ball search\. Since larger granular balls usually contain more representative samples and are less likely to be dominated by local noise, this mechanism improves the reliability of nearest\-ball selection and thus enhances the robustness of the model in the presence of local noise and outliers\.

As shown in Rows 3 and 6 of Table[V](https://arxiv.org/html/2608.12903#S5.T5), the decision strategy based on constructing a neighborhood around the test point outperforms direct decision making based on the nearest granular ball\. Since this neighborhood is induced by the nearest granular ball, and its radius is defined as the distance from the test sample to the farthest sample within that ball, it can fully cover the reliable local sample group while remaining compact\. More importantly, this mechanism allowskkto be adaptively determined by the actual number of samples contained in the neighborhood, rather than being manually preset, which is more consistent with the basic KNN principle of making decisions based on local neighborhoods\.

## VIConclusion

This paper proposes a new adaptive granular\-ball k\-nearest neighbor model\. The method fits the original data distribution by generating granular balls\. It first simplifies local splitting throughn\\sqrt\{n\}coarse divisions, and then achieves full adaptivity by controlling the splitting process with the weighted sum of the Fisher values of child balls\. During coarse\-granular ball partitioning, a density\-based splitting criterion is introduced, and then\\sqrt\{n\}divisions strategy is optimized through rigorous mathematical analysis\. In the decision stage, GBKNN constructs an adaptive neighborhood for each test sample based on the weighted nearest granular ball, so that the value ofkkis dynamically determined by the actual number of samples in the neighborhood, avoiding the dependence of traditional KNN on a fixed parameter setting\. Extensive experiments on multiple benchmark datasets show that GBKNN outperforms traditional KNN and other competing methods in classification accuracy, time efficiency, and noise robustness, demonstrating strong overall advantages\. In future work, we will further explore more efficient granular ball partition strategies to continuously improve classification performance\. We will also extend GBKNN to broader application scenarios, such as imbalanced classification, open\-set recognition, and semi\-supervised learning\.

## References

- \[1\]M\. N\. Ab Wahab, A\. Nazir, A\. T\. Z\. Ren, M\. H\. M\. Noor, M\. F\. Akbar, and A\. S\. A\. Mohamed\(2021\)Efficientnet\-lite and hybrid cnn\-knn implementation for facial expression recognition on raspberry pi\.IEEE Access9,pp\. 134065–134080\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[2\]A\. A\. A\. Ali and S\. Mallaiah\(2022\)Intelligent handwritten recognition using hybrid cnn architectures based\-svm classifier with dropout\.Journal of King Saud University\-Computer and Information Sciences34\(6\),pp\. 3294–3300\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[3\]S\. M\. Ayyad, A\. I\. Saleh, and L\. M\. Labib\(2019\)Gene expression cancer classification using modified k\-nearest neighbors technique\.Biosystems176,pp\. 41–51\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p4.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[4\]G\. Bhattacharya, K\. Ghosh, and A\. S\. Chowdhury\(2012\)An affinity\-based new local distance function and similarity measure for knn algorithm\.Pattern Recognition Letters33\(3\),pp\. 356–363\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p2.1)\.
- \[5\]M\. R\. Brito, E\. L\. Chávez, A\. J\. Quiroz, and J\. E\. Yukich\(1997\)Connectivity of the mutual k\-nearest\-neighbor graph in clustering and outlier detection\.Statistics & Probability Letters35\(1\),pp\. 33–42\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p2.1)\.
- \[6\]C\. Domeniconi, J\. Peng, and D\. Gunopulos\(2002\)Locally adaptive metric nearest\-neighbor classification\.IEEE Transactions on Pattern Analysis and Machine Intelligence24\(9\),pp\. 1281–1285\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p2.1)\.
- \[7\]A\. K\. Ghosh\(2006\)On optimum choice of k in nearest neighbor classification\.Computational Statistics & Data Analysis50\(11\),pp\. 3113–3123\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p2.1)\.
- \[8\]J\. E\. Goin\(1984\)Classification bias of the k\-nearest neighbor algorithm\.IEEE Transactions on Pattern Analysis and Machine Intelligence\(3\),pp\. 379–381\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[9\]C\. Gong, Y\. Li, Y\. Liu, P\. Wang, and Y\. You\(2022\)Joint evidentialKK\-nearest neighbor classification\.In2022 IEEE 38th International Conference on Data Engineering \(ICDE\),pp\. 2113–2126\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p1.1)\.
- \[10\]J\. Heo, Z\. Lin, and S\. Yoon\(2018\)Distance encoded product quantization for approximate k\-nearest neighbor search in high\-dimensional space\.IEEE Transactions on Pattern Analysis and Machine Intelligence41\(9\),pp\. 2084–2097\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[11\]Q\. Huang and A\. K\. Tung\(2023\)Lightweight\-yet\-efficient: revitalizing ball\-tree for point\-to\-hyperplane nearest neighbor search\.In2023 IEEE 39th International Conference on Data Engineering \(ICDE\),pp\. 436–449\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p1.1)\.
- \[12\]D\. S\. Jodas, L\. A\. Passos, A\. Adeel, and J\. P\. Papa\(2022\)PL\-k nn: a parameterless nearest neighbors classifier\.In2022 29th International Conference on Systems, Signals and Image Processing \(IWSSIP\),pp\. 1–4\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p3.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[13\]B\. S\. Kim and S\. B\. Park\(1986\)A fast k nearest neighbor finding algorithm based on the ordered partition\.IEEE Transactions on Pattern Analysis and Machine Intelligence\(6\),pp\. 761–766\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[14\]H\. Kuai, J\. Chen, X\. Tao, L\. Cai, K\. Imamura, H\. Matsumoto, P\. Liang, and N\. Zhong\(2024\)Never\-ending learning for explainable brain computing\.Advanced Science11\(24\),pp\. 2307647\.Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1)\.
- \[15\]G\. Le Caër\(2017\)Circumspheres of sets of n\+1 random points in the d\-dimensional euclidean unit ball \(1≤n≤d1\\leq n\\leq d\)\.Journal of Mathematical Physics58\(5\)\.Cited by:[§IV\-E](https://arxiv.org/html/2608.12903#S4.SS5.p3.1.1)\.
- \[16\]J\. Liu, H\. Jianye, Y\. Ma, and S\. Xia\(2024\)Unlock the cognitive generalization of deep reinforcement learning via granular ball representation\.InForty\-first International Conference on Machine Learning,Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1)\.
- \[17\]S\. S\. Mullick, S\. Datta, and S\. Das\(2018\)Adaptive learning\-basedkk\-nearest neighbor classifiers with resilience to class imbalance\.IEEE Transactions on Neural Networks and Learning Systems29\(11\),pp\. 5713–5725\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p3.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[18\]K\. K\. Paliwal and P\. Rao\(1983\)Application of k\-nearest\-neighbor decision rule in vowel recognition\.IEEE Transactions on Pattern Analysis and Machine Intelligence\(2\),pp\. 229–231\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[19\]Y\. Peng, B\. Choi, T\. N\. Chan, and J\. Xu\(2022\)LAN: learning\-based approximate k\-nearest neighbor search in graph databases\.In2022 IEEE 38th International Conference on Data Engineering \(ICDE\),Vol\.,pp\. 2508–2521\.External Links:[Document](https://dx.doi.org/10.1109/ICDE53745.2022.00233)Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p1.1)\.
- \[20\]S\. Pourbahrami and M\. Hashemzadeh\(2022\)A geometric\-based clustering method using natural neighbors\.Information Sciences610,pp\. 694–706\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p3.1)\.
- \[21\]H\. Samet\(2007\)K\-nearest neighbor finding using maxnearestdist\.IEEE Transactions on Pattern Analysis and Machine Intelligence30\(2\),pp\. 243–252\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[22\]P\. Soucy and G\. W\. Mineau\(2001\)A simple knn algorithm for text categorization\.InProceedings 2001 IEEE International Conference on Data Mining,pp\. 647–648\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[23\]B\. K\. Sriperumbudur, A\. Gretton, K\. Fukumizu, B\. Schölkopf, and G\. R\. Lanckriet\(2010\)Hilbert space embeddings and metrics on probability measures\.The Journal of Machine Learning Research11,pp\. 1517–1561\.Cited by:[§IV\-E](https://arxiv.org/html/2608.12903#S4.SS5.p8.1.1)\.
- \[24\]N\. Ukey, Z\. Yang, B\. Li, G\. Zhang, Y\. Hu, and W\. Zhang\(2023\)Survey on exact knn queries over high\-dimensional data space\.Sensors23\(2\),pp\. 629\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[25\]U\. P\. Wani, Y\. Gatagat, and M\. Thalor\(2022\)Handwritten character recognition using cnn, knn and svm\.International Journal of Technology Engineering Arts Mathematics Science1\(2\),pp\. 2583–1224\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[26\]S\. Xia, X\. Dai, G\. Wang, X\. Gao, and E\. Giem\(2022\)An efficient and adaptive granular\-ball generation method in classification problem\.IEEE Transactions on Neural Networks and Learning Systems35\(4\),pp\. 5319–5331\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p4.1.1),[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1),[§IV\-B](https://arxiv.org/html/2608.12903#S4.SS2.p5.1.4)\.
- \[27\]S\. Xia, X\. Lian, G\. Wang, X\. Gao, J\. Chen, and X\. Peng\(2024\)Gbsvm: an efficient and robust support vector machine framework via granular\-ball computing\.IEEE Transactions on Neural Networks and Learning Systems\.Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1)\.
- \[28\]S\. Xia, Y\. Liu, X\. Ding, G\. Wang, H\. Yu, and Y\. Luo\(2019\)Granular ball computing classifiers for efficient, scalable and robust learning\.Information Sciences483,pp\. 136–152\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p4.1.1),[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1),[§III](https://arxiv.org/html/2608.12903#S3.p1.1),[§IV\-A](https://arxiv.org/html/2608.12903#S4.SS1.p1.1.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1.2)\.
- \[29\]S\. Xia, X\. Ma, Z\. Liu, C\. Liu, S\. Zhao, and G\. Wang\(2025\)Graph coarsening via supervised granular\-ball for scalable graph neural network training\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.39,pp\. 12872–12880\.Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1)\.
- \[30\]S\. Xia, C\. Wang, G\. Wang, X\. Gao, W\. Ding, J\. Yu, Y\. Zhai, and Z\. Chen\(2023\)GBRS: a unified granular\-ball learning model of pawlak rough set and neighborhood rough set\.IEEE Transactions on Neural Networks and Learning Systems\.Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1)\.
- \[31\]J\. Xie, C\. Hua, S\. Xia, Y\. Cheng, G\. Wang, and X\. Gao\(2024\)W\-gbc: an adaptive weighted clustering method based on granular\-ball structure\.In2024 IEEE 40th International Conference on Data Engineering \(ICDE\),pp\. 914–925\.Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1)\.
- \[32\]J\. Xie, X\. Xiang, S\. Xia, L\. Jiang, G\. Wang, and X\. Gao\(2024\)MGNR: a multi\-granularity neighbor relationship and its application in knn classification and clustering methods\.IEEE Transactions on Pattern Analysis and Machine Intelligence\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p4.1.1),[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p4.1),[§IV\-A](https://arxiv.org/html/2608.12903#S4.SS1.p1.1.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[33\]Q\. Xie, Q\. Zhang, S\. Xia, F\. Zhao, C\. Wu, G\. Wang, and W\. Ding\(2024\)Gbg\+\+: a fast and stable granular ball generation method for classification\.IEEE Transactions on Emerging Topics in Computational Intelligence\.Cited by:[§II\-B](https://arxiv.org/html/2608.12903#S2.SS2.p2.1),[§III](https://arxiv.org/html/2608.12903#S3.p4.1),[§IV\-B](https://arxiv.org/html/2608.12903#S4.SS2.p3.1),[§IV\-F1](https://arxiv.org/html/2608.12903#S4.SS6.SSS1.p1.1)\.
- \[34\]J\. Yang, L\. Yang, J\. Zhang, Q\. Liang, W\. Wang, D\. Tang, and T\. Liu\(2024\)GNaN: a natural neighbor search algorithm based on universal gravitation\.Pattern Recognition146,pp\. 110063\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p3.1.1)\.
- \[35\]M\. L\. Yiu and N\. Mamoulis\(2007\)Reverse nearest neighbors search in ad hoc subspaces\.IEEE Transactions on Knowledge and Data Engineering19\(3\),pp\. 412–426\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p2.1),[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p2.1)\.
- \[36\]B\. Zhang and S\. N\. Srihari\(2004\)Fast k\-nearest neighbor classification using cluster\-based trees\.IEEE Transactions on Pattern Analysis and Machine Intelligence26\(4\),pp\. 525–528\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[37\]F\. Zhang and J\. Feng\(2017\)High\-resolution mobile fingerprint matching via deep joint knn\-triplet embedding\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.31\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[38\]J\. Zhang, Y\. Li, F\. Shen, Y\. He, H\. Tan, and Y\. He\(2024\)Hierarchical text classification with multi\-label contrastive learning and knn\.Neurocomputing577,pp\. 127323\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p1.1)\.
- \[39\]S\. Zhang and J\. Li\(2021\)KNN classification with one\-step computation\.IEEE Transactions on Knowledge and Data Engineering35\(3\),pp\. 2711–2723\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p3.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[40\]Q\. Zhu, J\. Feng, and J\. Huang\(2016\)Natural neighbor: a self\-adaptive neighborhood method without parameter k\.Pattern Recognition Letters80,pp\. 30–36\.Cited by:[§I](https://arxiv.org/html/2608.12903#S1.p3.1),[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p2.1),[§V\-A](https://arxiv.org/html/2608.12903#S5.SS1.p2.1)\.
- \[41\]S\. Zhu, L\. Xie, M\. Zhang, R\. Gao, and Y\. Xie\(2022\)Distributionally robust weighted k\-nearest neighbors\.Advances in Neural Information Processing Systems35,pp\. 29088–29100\.Cited by:[§II\-A](https://arxiv.org/html/2608.12903#S2.SS1.p3.1)\.