HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:35:52 PM
Last modification on : Thursday, January 20, 2022 - 4:14:56 PM
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