Evolutionary Adaptive Neighborhood Learning: A Genetic Algorithm for Instance-Dependent k Optimization in Nearest Neighbor Classification

Isaac Touza, Kaladzavi Guidedi, Kolyang

Submitted by Isaac Touza

Published November 6, 2026 · Version v1, November 6, 2026 · DOI 10.66977/xsci.2611.000t

Machine Learning, Artificial Intelligence, Algorithms

Abstract

The number of neighbours $k$ is the central hyper-parameter of the $k$-nearest
neighbour ($k$-NN) classifier, and it is almost always chosen globally, by cross-validation or, increasingly, by evolutionary search. Yet the bias--variance trade-off that governs $k$ is local: dense, noise-free regions favour small neighbourhoods, whereas sparse or label-noisy regions favour large ones. Because the global-$k$ search space is one-dimensional, replacing exhaustive search by a genetic algorithm (GA) cannot improve on it. We therefore change the object being optimised. We propose EANK (Evolutionary Adaptive Neighborhood $K$), which evolves a low-dimensional policy $g_\theta$ mapping a description of the local neighbourhood of a point (density, label entropy at two scales, vote margin, concentration, relative density) to an instance-dependent number of neighbours $k(x)\in\{1,\dots,K\}$. A real-coded elitist GA maximises the leave-one-out accuracy of the induced adaptive rule, penalised by a neighbourhood-smoothness term. A pre-computed vote table reduces each fitness evaluation to $O(n)$ look-ups. We prove that (i)~a seeded EANK never does worse than the best global $k$ on its training criterion, (ii)~the GA converges almost surely to the essential supremum of the fitness, (iii)~the learned neighbourhood size is Lipschitz in the meta-features, and (iv)~the policy class has a growth function polynomial in the sample size with exponent $d+2$. This yields a uniform generalisation bound that does not depend on $n$, which per-instance
encodings do not enjoy. On a controlled benchmark with spatially heterogeneous structure, EANK recovers small neighbourhoods in the fine-grained region and large ones in the noisy region, and it improves accuracy over the best global $k$ at every noise level. In a nested, $5\times5$-fold evaluation on twelve public datasets, EANK obtains the best average rank among six $k$-NN variants. Its accuracy is statistically indistinguishable from the tuned global-$k$ baselines, and it is significantly better than the default $k=5$. We document the gap between in-sample and out-of-sample gains, and we identify it as the main obstacle for adaptive-neighbourhood methods.

View PDF