On the Optimality of k=n in k-Nearest Neighbor Classification: Sub-Optimality Rates, Dimension-Aware Selection, and Hassanat Distance Comparison
Mathematics · 29.07.2026 · 14 (15) · 2707
DOI: 10.3390/math14152707 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 29.07.2026. Verfasst von Ahmad B. Hassanat und 8 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The k-nearest neighbor (KNN) algorithm remains one of the most fundamental and widely-used methods in machine learning. A common rule of thumb sets the number of neighbors as k=n, where n is the size of the training set. Despite its widespread adoption, the theoretical justification for this choice has remained obscure. We provide a comprehensive rate-based analysis. First, we derive the minimax-optimal exponent β*=4/(d+4) for k=nβ under standard Hölder-smoothness assumptions, recovering as a special case Theorem 1: under these second-order Hölder-smoothness assumptions, k=n attains the asymptotic minimax-optimal exponent if and only if the feature space has dimensionality d=4; this concerns the asymptotic rate exponent, not the finite-sample optimal value of k. Second, Theorem 2 quantifies the sub-optimality of any fixed β as Rn(nβ)=Θ(n−r(β,d)) with r(β,d)=min{β,4(1−β)/d}, yielding an asymmetric penalty for the classical rule when d≠4 that we make precise in Corollary 1. The predicted rate is empirically verified across d∈{2,…,20} on controlled synthetic data. On 48 datasets from the OpenML-CC18 benchmark suite, the dimension-aware rule k=⌊n4/(d+4)⌋ outperforms the classical n rule in 32 of 48 head-to-head comparisons (paired Wilcoxon p=4.6×10−4, mean accuracy gain +2.5 percentage points), demonstrating that the theoretical improvement translates to a practical one. We further test the Hassanat distance metric against Euclidean across all KNN variants on the same 48 datasets, finding that Hassanat outperforms Euclidean in five of six configurations (paired Wilcoxon p
Zitieren
APA
Hassanat, A. B., Alkasasbeh, A. A., Alkafaween, E., Lasassmeh, O., Almohammadi, K., Alrashidi, M., Alzahrani, A., Alamri, M., & Tarawneh, A. S. (2026). On the Optimality of k=n in k-Nearest Neighbor Classification: Sub-Optimality Rates, Dimension-Aware Selection, and Hassanat Distance Comparison. Mathematics, 14(15), 2707. https://doi.org/10.3390/math14152707
Vancouver
Hassanat AB, Alkasasbeh AA, Alkafaween E, Lasassmeh O, Almohammadi K, Alrashidi M, et al. On the Optimality of k=n in k-Nearest Neighbor Classification: Sub-Optimality Rates, Dimension-Aware Selection, and Hassanat Distance Comparison. Mathematics. 2026;14(15):2707. doi:10.3390/math14152707
BibTeX
@article{Hassanat2026,
author = {Hassanat, Ahmad B. and Alkasasbeh, Anas A. and Alkafaween, Esra’a and Lasassmeh, Omar and Almohammadi, Khalid and Alrashidi, Malek and Alzahrani, Abdulkareem and Alamri, Maha and Tarawneh, Ahmad S.},
title = {On the Optimality of k=n in k-Nearest Neighbor Classification: Sub-Optimality Rates, Dimension-Aware Selection, and Hassanat Distance Comparison},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {15},
pages = {2707},
doi = {10.3390/math14152707}
}
EUVIMED