Evolutionary Adaptive Neighborhood Learning: A Genetic Algorithm for Instance-Dependent k Optimization in Nearest Neighbor Classification
Authors: Isaac Touza, Kaladzavi Guidedi, Kolyang
Organizations: Department of Mathematics and Computer Science, Faculty of Science, University of Maroua, P.O. Box 814, Maroua, Cameroon · Laboratoire de Recherche en Informatique (LaRI), University of Maroua, Maroua, Cameroon · Department of Computer Science and Telecommunications, National Advanced School of Engineering, University of Maroua, P.O. Box 46, Maroua, Cameroon · Higher Teacher’s Training College, University of Maroua, P.O. Box 46, Maroua, Cameroon
The number of neighbours k is the central hyperparameter of the k-nearest neighbour (k-NN) classifier and is usually selected globally through cross-validation or evolutionary search. However, the bias-variance trade-off is inherently local: dense and noise-free regions may favour small neighbourhoods, whereas sparse or noisy regions may require larger ones. Since global-k optimization is one-dimensional, replacing exhaustive search with a genetic algorithm offers little computational advantage. We therefore optimize an instance-dependent neighbourhood policy instead. We propose EANK (Evolutionary Adaptive Neighborhood K), which uses a low-dimensional policy to map local neighbourhood descriptors, including density, label entropy, vote margin, and concentration, to an adaptive number of neighbours k(x). A real-coded elitist genetic algorithm optimizes this policy using leave-one-out accuracy with a neighbourhood-smoothness penalty. Precomputed neighbour votes reduce fitness evaluation costs. We investigate theoretical properties of the method, including dominance over global-k solutions on the training criterion, evolutionary convergence, policy regularity, and generalization guarantees. Experiments on synthetic data with spatially heterogeneous structure and twelve public datasets evaluate predictive performance, robustness, and computational cost. Under nested cross-validation, EANK achieves competitive performance relative to tuned global-k baselines and improves upon the default k=5. We also examine the gap between training and test performance to assess the practical value of adaptive neighbourhood selection.
Figures & tables
Dataset
n
p
C
Imb. ratio
Iris
150
4
3
1.0
Wine
178
13
3
1.5
Breast cancer
569
30
2
1.7
Digits
1797
61
10
1.1
Sonar
208
60
2
1.1
Ionosphere
351
33
2
1.8
Table 1: Datasets: number of instances n , features p (after removing constant ones), classes C , and imbalance ratio (largest / smallest class).
Figure 1: Synthetic heterogeneous benchmark ( η=0.3 ). (a) Training sample: noiseless checkerboard on the left, linear boundary with 30% label noise on the right. (b) Neighbourhood size k(x) chosen by the learned EANK policy over the input space. The policy selects small neighbourhoods in the fine-grained checkerboard and large ones in the noisy smooth region. The best single global value found by exhaustive LOO search is a compromise between the two.
η
kNN-LOO
LocalK
EANK
p
k (global)
k EANK (L / R)
0.0
95.18
95.17
95.42
0.055
4.4
1.4 / 1.5
0.1
89.81
89.85
90.49
0.004
9.5
4.3 / 20.0
0.2
84.04
84.05
84.76
0.016
16.0
8.8 / 23.8
0.3
78.73
78.39
79.33
0.084
18.6
6.2 / 32.8
0.4
73.05
72.92
73.84
0.010
14.9
2.6 / 22.9
Table 2: Synthetic benchmark: test accuracy (%, mean over 10 replications) as a function of the label-noise rate η in the smooth region. p : two-sided Wilcoxon signed-rank test, EANK vs. kNN-LOO. Last two columns: global k selected by kNN-LOO, and median k used by EANK in the left / right regions.
Figure 2: Synthetic benchmark. Left: test-accuracy gain over the best global k (kNN-LOO) versus noise rate (mean ± s.d. over 10 paired replications). Right: median neighbourhood size in each region.
Dataset
kNN ( k =5)
kNN-LOO
wkNN-LOO
GA-k
LocalK
EANK
Iris
95.20 ± 4.2
96.27 ± 3.5
95.87 ± 3.9
95.73 ± 3.8
96.27 ± 3.5
95.73 ± 3.8
Wine
95.75 ± 3.6
96.29 ± 3.0
96.86 ± 2.7
96.52 ± 2.5
96.29 ± 3.0
95.83 ± 2.6
Breast cancer
96.59 ± 1.7
96.63 ± 1.5
96.49 ± 1.5
96.70 ± 1.5
96.63 ± 1.5
96.63 ± 1.4
Digits
97.66 ± 0.5
97.58 ± 0.5
97.64 ± 0.5
97.58 ± 0.5
97.58 ± 0.5
97.70 ± 0.6
Sonar
80.96 ± 5.8
84.89 ± 5.1
84.79 ± 5.2
84.89 ± 5.1
84.79 ± 5.1
84.89 ± 4.0
Ionosphere
84.67 ± 4.1
85.69 ± 3.7
85.69 ± 3.7
85.69 ± 3.7
85.69 ± 3.7
86.61 ± 4.0
Table 3: Test accuracy (%, mean ± s.d. over 25 nested splits). Bold: best per row. An arrow on EANK would mark a significant difference with kNN-LOO (corrected resampled t -test, α=0.05 ); none was observed. Mean rank: average Friedman rank over the 12 datasets (lower is better).
Baseline
W/T/L
p
pHolm
sig. better/worse
kNN (k=5)
11/0/1
0.001
0.005
0/0
kNN-LOO
8/0/4
0.569
1.000
0/0
wkNN-LOO
6/1/5
0.820
1.000
0/0
GA-k
6/1/5
0.820
1.000
0/0
LocalK
7/0/5
0.850
1.000
0/0
Table 4: Pairwise comparison of EANK with each baseline over the 12 datasets (mean accuracy): wins/ties/losses, Wilcoxon signed-rank p -value, Holm-adjusted p -value, and number of datasets on which EANK is significantly better/worse according to the corrected resampled t -test.
kNN ( k =5)
kNN-LOO
wkNN-LOO
GA-k
LocalK
EANK
Macro-F1 (mean)
82.94
84.25
84.44
84.24
84.45
84.14
Macro-F1 (rank)
4.92
3.71
2.88
3.08
3.50
2.92
Balanced acc. (mean)
83.05
84.30
84.38
84.28
84.47
84.08
Balanced acc. (rank)
5.00
3.67
2.92
2.96
3.38
3.08
Fit time (ms)
3.2
9.1
8.1
10.2
7.8
113.8
Predict time (ms)
1.4
2.6
2.8
2.6
2.8
3.6
Table 5: Other metrics, averaged over the 12 datasets (ranks: lower is better), and mean wall-clock time per training fold on one CPU core.
Figure 3: GA convergence on four datasets: fitness gain over the best global k (LOO, points), mean and 10–90% band over 25 folds. The dashed line marks the seeded starting point ( Proposition 2 ).
Figure 4: Distribution of the neighbourhood sizes ki assigned by EANK to training points, pooled over folds. Dashed: median global k chosen by kNN-LOO.
Variant
Acc.
Rank
LOO gain
s.d.( k )
#eval
Time
EANK
87.95
2.25
+1.52
5.24
2092
114
EANK ( λ =0)
87.64
4.46
+1.84
12.56
1829
68
EANK (random search)
87.81
3.42
+0.36
4.21
1297
59
EANK (no seeding)
87.68
3.79
+1.53
7.18
2410
131
EANK (density feats)
87.71
3.88
+1.14
4.44
2051
111
EANK (label feats)
87.91
3.21
+0.98
3.02
1901
101
Table 6: Ablations over the 12 datasets: mean test accuracy (%), mean rank among the six variants, mean LOO fitness gain over the best global k (points), mean within-fold standard deviation of test-time k , mean number of fitness evaluations, and mean training time (ms).
Figure 5: Mean policy weights wj per dataset (25 folds). Positive weights increase k .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Symbol
Value
Symbol
Value
K (max. neighbours)
50
P (population)
40
m , M (feature scales)
10 , 30
G (generations)
60 (patience 25 )
λ , q (smoothness)
0.05 , 5
tournament size
3
Bw , Bb (box)
4 , 6
SBX pc , η
0.9 , 15
elites
2
mutation σ0→σmin
0.5→0.02 (annealed)
Appendix
Table 7: Default hyper-parameters of EANK (identical for all datasets).
k-Nearest Neighbors (k-NN) predicts or retrieves from nearby data points using local similarity for classification, regression, clustering, and uncertainty.
The k-Nearest Neighbor~(KNN) algorithm is widely used across various tasks. The selection of the k value 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. \textcolor{black}{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 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.} 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.
Xiaoyu Lian, Shuyin Xia, Hongxuan He +3
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 · College of Computer and Information Science, the National Center for Applied Mathematics in Chongqing, Chongqing Normal University, Chongqing 401331, China
Nearest neighbour classifiers inherit the geometry of their distance function. Fixed distances and globally learned metrics apply the same geometry throughout the input space, although relevant feature directions may vary across regions. We propose EAML (Evolutionary Adaptive Metric Learning), a framework that learns instance-dependent positive-definite metrics through a low-dimensional parameterization. Each local metric combines an input-dependent diagonal scaling, generated by softmax interpolation between anchor points, with a global low-rank correlation component. A real-coded elitist genetic algorithm optimizes the parameters using a scalar objective combining leave-one-out prediction error, robustness, metric smoothness, and regularization. We establish positive definiteness, metric equivalence, existence of an optimal solution, and Lipschitz continuity of the metric field. We further investigate prediction stability, generalization bounds, and evolutionary convergence under explicit assumptions. Experiments on synthetic data with region-dependent feature relevance show that EAML can recover local metric variations and outperform global metrics. Evaluation on thirteen public datasets using nested 5-fold cross-validation reveals a more nuanced picture: EAML improves performance on selected datasets but does not significantly outperform global metric baselines overall. Additional experiments show that global diagonal metrics can be preferable under nuisance features and test-time noise. These findings identify the conditions under which evolutionary local metric learning is beneficial and highlight its practical limitations.
Isaac Touza
Department of Mathematics and Computer Science, Faculty of Science, University of Maroua, P.O. Box 814, Maroua, Cameroon · Laboratoire de Recherche en Informatique (LaRI), University of Maroua, Maroua, Cameroon
Nearest neighbor classification relies fundamentally on how locality is defined, yet conventional k-NN imposes the same neighborhood cardinality throughout the feature space. This assumption can be inadequate for data whose local geometry varies substantially across the underlying manifold. We introduce Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification (CARSANN), a geometry-driven framework that adapts the spatial support of each neighborhood according to local geometric complexity. CARSANN first estimates intrinsic dimensionality using TwoNN and constructs an intrinsic representation through principal component analysis. Local mean curvature is then estimated using a shape-operator-based formulation and controls neighborhood scale: highly curved regions receive stronger radius shrinkage, whereas approximately flat regions retain broader spatial support. Unlike methods that modify only the number of neighbors or the local metric, CARSANN explicitly adapts the spatial extent of local evidence. Experiments on more than 70 real-world OpenML datasets show that CARSANN consistently improves upon standard k-NN and is competitive with adaptive nearest-neighbor methods. In a controlled comparison using the same base neighborhood size, CARSANN achieves higher balanced accuracy on 40 of 45 datasets, increasing mean balanced accuracy from 0.6506 to 0.7528. The advantage also persists against k-NN with fixed k=5. Friedman and Nemenyi tests confirm that the improvements are statistically significant. These results indicate that local manifold curvature can serve as an effective geometric control variable for adapting neighborhood support, providing a complementary paradigm to cardinality-based nearest-neighbor adaptation.
Alexandre L. M. Levada
Computing Department Federal University of São Carlos 13565-905, São Carlos-SP, Brazil