EANK：用遗传算法优化最近邻分类中逐样本自适应 k 值
Evolutionary Adaptive Neighborhood Learning: A Genetic Algorithm for Instance-Dependent k Optimization in Nearest Neighbor Classification
AI 导读
arXiv 论文提出 EANK（Evolutionary Adaptive Neighborhood K），用低维策略将局部邻域描述子（密度、标签熵、投票边际、集中度）映射为逐样本自适应邻居数 k(x)，并以实数编码精英遗传算法结合留一法精度与邻域平滑性惩罚优化该策略。在嵌套交叉验证下，EANK 相对调优的全局 k 基线表现具竞争力，并优于默认 k=5，实验覆盖合成数据与十二个公开数据集。
正文 · 原文
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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.07257 [cs.LG] |
| (or arXiv:2611.07257v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.07257 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Isaac Touza [view email]
[v1]
Thu, 5 Nov 2026 00:14:13 UTC (624 KB)
来源：arXiv cs.AI · arxiv.org