Skip to Main content Skip to Navigation

Nearest neighbor classification in infinite dimension

Frédéric Cérou 1 Arnaud Guyader 1
1 ASPI - Applications of interacting particle systems to statistics
UR1 - Université de Rennes 1, Inria Rennes – Bretagne Atlantique , CNRS - Centre National de la Recherche Scientifique : UMR6074
Abstract : Let $X$ be a random element in a metric space $(\calF,d)$, and let $Y$ be a random variable with value $0$ or $1$. $Y$ is called the class, or the label, of $X$. Assume $n$ i.i.d. copies $(X_i,Y_i)_1\leqi\leqn$. The problem of classification is to predict the label of a new random element $X$. The $k$-nearest neighbor classifier consists in the simple following rule : look at the $k$ nearest neighbors of $X$ and choose $0$ or $1$ for its label according to the majority vote. If $(\calF,d)=(R^d,||.||)$, Stone has 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 more valid in general metric spaces. However, if $(\calF,d)$ is separable and if a regularity condition is assumed, then the $k$-nearest neighbor classifier is weakly consistent.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:35:52 PM
Last modification on : Wednesday, May 16, 2018 - 11:23:02 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:17:38 PM


  • HAL Id : inria-00070470, version 1


Frédéric Cérou, Arnaud Guyader. Nearest neighbor classification in infinite dimension. [Research Report] RR-5536, INRIA. 2005, pp.23. ⟨inria-00070470⟩



Record views


Files downloads