Nearest neighbor classification in infinite dimension

Cérou, Frédéric ; Guyader, Arnaud

ESAIM: Probability and Statistics, Tome 10 (2006), pp. 340-355

Résumé

Let $X$ be a random element in a metric space $(ℱ,d)$, and let $Y$ be a random variable with value $0$ or $1$. $Y$ is called the class, or the label, of $X$. Let ${(X_i,Y_i)}_{1\le i\le n}$ be an observed i.i.d. sample having the same law as $(X,Y)$. The problem of classification is to predict the label of a new random element $X$. The $k$-nearest neighbor classifier is the simple following rule: look at the $k$ nearest neighbors of $X$ in the trial sample and choose $0$ or $1$ for its label according to the majority vote. When $(ℱ,d)=({ℝ}^d,||.|\left|\right)$, Stone (1977) proved in 1977 the universal consistency of this classifier: its probability of error converges to the Bayes error, whatever the distribution of $(X,Y)$. We show in this paper that this result is no longer valid in general metric spaces. However, if $(ℱ,d)$ is separable and if some regularity condition is assumed, then the $k$-nearest neighbor classifier is weakly consistent.

Détail

DOI : 10.1051/ps:2006014

Classification : 62H30
Keywords: classification, consistency, non parametric statistics