Adaptive k Nearest Neighbors Classifier via Granular Ball Computing

The paper proposes an adaptive and efficient k-Nearest Neighbor (KNN) approach via granular-ball computing, called GBKNN, to address two key limitations of traditional KNN: the computational cost in high-dimensional and large-scale datasets, and the sensitivity to the choice of the k value. The method consists of two stages: a training stage and a prediction stage.

In the training stage, the dataset is first coarsely partitioned to reduce the complexity of data distributions within a granular ball. Specifically, the dataset is initially split into √n granular balls using k-means, where n is the number of samples. This initial partitioning simplifies the data distribution within each ball and mitigates errors caused by limited local fitting capacity, particularly for complex nonlinear data structures such as 'Two Moons' or 'Circles' datasets. The paper proves through a theorem that this direct √n splitting results in balls with better density compared to recursive binary splitting, especially for non-uniform distributions.

After the initial partitioning, the Fisher criterion is introduced to control ball splitting and stopping. The Fisher value of a granular ball is defined as:

F = (Σ l=1 L n l ∥μ l − μ∥) / (Σ l=1 L n l S l),

where n l is the number of samples in class l, μ l is the mean of class l, μ is the overall mean, and S l is the intra-class divergence of class l. Unlike purity, which only measures label consistency, the Fisher criterion evaluates both inter-class separability and intra-class compactness from the perspective of feature distribution. When the weighted Fisher value of the sub-ball set is higher than that of the parent ball, the split is accepted; otherwise, it is rejected.

The method also introduces a category-adaptive purity lower bound TLj, defined as:

TLj = (Σ i=1 N GBi*) / Lj,

where Lj denotes the set of the j-th classes in the dataset and N is the total number of granular balls. This strategy ensures that the parent granular ball stops splitting only after achieving sufficient quality and prevents low-quality granular balls from terminating prematurely.

Additionally, the method integrates a de-overlapping strategy into the granular ball generation process, executing deduplication after each split to actively suppress the accumulation of overlap between heterogeneous granular balls.

In the prediction stage, the nearest granular ball is first located through a weighted distance mechanism. The weighted distance between the test sample xtest and a granular ball GBi is defined as:

Wd(xtest, GBi) = (1 − GBi / Σ j=1 N GBj) · Δ(xtest, oi − ri),

where GBi represents the number of samples contained in the ball. This weighting adjusts the confidence of granular balls based on sample counts, prioritizing larger balls and reducing the influence of noise or small granular balls.

After identifying the nearest granular ball, an adaptive neighborhood is constructed around the test sample. The distance from the test sample to the farthest sample within that ball is used as the neighborhood radius RkNN(x) = max xi ∈ GB* Δ(x, xi). The effective k value 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.

The overall time complexity of the proposed method is O(n√n + M(N + s̄)), where n is the number of training samples, M is the number of test samples, N is the number of granular balls, and s̄ is the average number of samples that need to be further checked within candidate granular balls for each test sample. When N + s̄ ≪ n, the additional cost introduced by preprocessing is compensated by the efficiency gain in the classification stage.

Experimental results on 17 real-world datasets (ranging from 169 to 1,048,575 samples) demonstrate that the proposed method outperforms existing KNN variants across multiple datasets in terms of both accuracy and efficiency. Under various noise conditions (0% to 30%), GBKNN achieves an average accuracy of 0.8736, outperforming GBKNN 2019 (0.8195) and GBKNN p (0.8622) by approximately 6.60% and 1.32%, respectively. The method also shows strong robustness, maintaining high accuracy even under 30% noise levels. On large-scale datasets, GBKNN maintains relatively stable performance under different noise levels, with accuracy remaining at 0.8979 on the 'Santander' dataset across all noise levels.

Ablation studies confirm that all key designs improve the final performance: the √n-based coarse initialization, the Fisher criterion, the purity lower bound TL, the weighted boundary distance Wd, and the neighborhood decision mechanism. The complete model achieves the best average result of 0.8217. The code has been open-sourced for reproducibility at https://github.com/lianxiaoyu724/Adaptive-GBKNN.

Improvements to AI Systems:

1. Adaptive k-Nearest Neighbor Classification with Noise Robustness

• Replace fixed-k KNN in existing classifiers with GBKNN’s dynamic neighborhood radius (based on the nearest granular ball’s farthest sample). This eliminates the need to pre-tune k, making the system self-adaptive to local data density and robust to label noise up to 30%, as shown in experiments.

• What it can do: Automatically classify high-dimensional, large-scale datasets (e.g., 1M+ samples) without manual hyperparameter selection, maintaining accuracy even when up to 30% of labels are corrupted.

2. Efficient Granular-Ball Indexing for Real-Time Prediction

• Integrate the two-stage training (√n coarse partition + Fisher-criterion-controlled splitting) as a pre-processing index for any distance-based model (e.g., anomaly detection, clustering, or regression). The weighted boundary distance (Wd) prioritizes larger, more reliable balls, reducing the search space from O(n) to O(√n + N + s̄).

• What it can do: Enable real-time inference on streaming or embedded systems (e.g., IoT sensors, mobile devices) where traditional KNN is computationally prohibitive, while preserving accuracy on non-linear structures like Two Moons or Circles.

3. Category-Adaptive Purity Threshold for Imbalanced Data

• Adopt the TLj lower bound (based on per-class granular-ball size) to stop splitting only when each class’s balls reach sufficient quality. This prevents premature termination on minority classes and over-splitting on majority classes.

• What it can do: Improve classification on imbalanced datasets (e.g., fraud detection, rare disease diagnosis) by ensuring that small classes are not under-represented, leading to higher recall for minority classes without sacrificing overall accuracy.

4. De-overlapping Strategy for Cleaner Decision Boundaries

• Apply the deduplication step after each granular-ball split to actively remove overlapping samples between heterogeneous balls. This reduces boundary ambiguity and improves the stability of the nearest-ball selection.

• What it can do: Produce more interpretable and separable decision regions in multi-class problems, reducing misclassifications near class boundaries (e.g., in image segmentation or speech recognition where classes overlap in feature space).

5. Fisher-Criterion-Driven Hierarchical Partitioning for Complex Distributions

• Use the Fisher value (inter-class separability / intra-class compactness) as a general splitting criterion in any tree-based or ball-based model (e.g., decision trees, random forests, or DBSCAN). This replaces purity-only measures, which ignore feature distribution.

• What it can do: Build more accurate hierarchical models for non-linearly separable data, such as satellite imagery or medical imaging, where class clusters are elongated or intertwined, leading to better generalization on unseen test samples.

6. Noise-Agnostic Large-Scale Learning

• Leverage the method’s proven stability under noise (accuracy remains 0.8979 on 'Santander' across 0–30% noise) to create a drop-in replacement for KNN in production systems where data quality is uncertain (e.g., user-generated content, sensor logs).

• What it can do: Maintain high performance in real-world noisy environments without requiring separate noise-filtering preprocessing, saving computational resources and reducing pipeline complexity.