Nearest neighbor classification in infinite dimension - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

Nearest neighbor classification in infinite dimension

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5536.pdf (289.71 Ko) Télécharger le fichier

Dates et versions

inria-00070470 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070470 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More