K-NN classifiers: Investigating the k = k(n) relationship

The paper proposes a theory-based method for estimating the optimal value of k in k-NN classifiers based on a n-sized training set As expected, experiments show that the suggested k is such that k/n →0 when both k and n tend to infinity, as required by the asymptotical consistency condition. Interestingly, it appears that the generalization error is robust w.r.t. to k when n becomes large (probably as a consequence of the k/n→0 relationship); the immediate consequence is that there is no need to provide an accurate estimate for the optimal k and an approximated coarser value, e.g., provided with cross validation, I-fold cross validation or leave one out is more than adequate.