cs.LGNov 5, 2026

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

Abstract

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

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Adaptive kk Nearest Neighbors Classifier via Granular Ball Computing

    Aug 13, 2026Xiaoyu Lian, Shuyin Xia, Hongxuan He +3k-Nearest Neighbors

  2. Evolutionary Adaptive Metric Learning: A Multi-Objective Framework for Learning Local Distance Functions in Nearest Neighbor Classification

    Nov 5, 2026Isaac TouzaMetric Learningk-Nearest Neighbors

  3. Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification

    Aug 27, 2026Alexandre L. M. Levadak-Nearest Neighbors