If the nearest neighbor rule (NNR) is used to classify unknown samples, then Cover and Hart [1] have shown that the average probability of error using n known samples (denoted by R_n ) converges to a number R as n tends to infinity, where R^ {\ast} \leq R \leq 2R^ {\ast} (1 - R^ {\ast}) , and R^ {\ast} is the Bayes probability of error. Here it is shown that when the samples lie in n -dimensional Euclidean space, the probability of error for the NNR conditioned on the n known samples (denoted by L_n . so that EL_n = R_n) converges to R with probability 1 for mild continuity and moment assumptions on the class densities. Two estimates of R from the n known samples are shown to be consistent. Rates of convergence of L_n to R are also given.
['Terry J. Wagner']
Convergence of the nearest neighbor rule