Analysis of Rate of Convergence of k-Nearest Neighbors Classification Rule
k-Nearest Neighbor rule; Classification rules; Rates of convergence; Binary classification
The main objective of this work is to analyze the velocity of convergence of k-Nearest Neighbor (kNN) classification rule. Thus the binary classification problem is approached. The main theoretical results are developed, overall Stone Theorem, which guarantees the universal consistency of classification rules with some properties. Specifically the kNN rule is analyzed, mainly its universal consistency. Then restrictive conditions which allow uniform rates of convergence for a family of distributions are presented. Finally, under the mentioned restrictive conditions the order of magnitude of rate of convergence of kNN rule is obtained such that it cross out the need of a bounded space of observations.