Choice of neighbor order in nearest-neighbor classification

By Peter Hall, Byeong U. Park, Richard J. Samworth. 2008

330 citations recorded by the source corpus.

The kth-nearest neighbor rule is arguably the simplest and most intuitively appealing nonparametric classification procedure. However, application of this method is inhibited by lack of knowledge about its properties, in particular, about the manner in which it is influenced by the value of k; and by the absence of techniques for empirical choice of k. In the present paper we detail the way in which the value of k determines the misclassification error. We consider two models, Poisson and Binomial, for the training samples. Under the first model, data are recorded in a Poisson stream and are "assigned" to one or other of the two populations in accordance with the prior probabilities. In particular, the total number of data in both training samples is a Poisson-distributed random variable. Under the Binomial model, however, the total number of data in the training samples is fixed, although again each data value is assigned in a random way. Although the values of risk and regret associated with the Poisson and Binomial models are different, they are asymptotically equivalent to first order, and also to the risks associated with kernel-based classifiers that are tailored to the case of two derivatives. These properties motivate new methods for choosing the value of k.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fe5a6a37a7bd474ed4c561fd43e09a8fefae314c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Reducto: On-Camera Filtering for Resource-Efficient Real-Time Video Analytics (2020, background): “…the overhead of the clustering algorithm and robustness of the resulting clusters to noisy inputs; we empirically observe that setting a target of 5 clusters strikes the best balance between these factors, and we leave an exploration of more adaptive tuning strategies to future work [31, 32].”
Optimal weighted nearest neighbour classifiers (2011, background): “Another consequence of Theorem 1 is that, provided (A.1)–(A.4) hold andB2 > 0, the quantity k∗ defined in (2.4) is larger by a factor of {2(d+4) d+2 }d/(d+4) (up to an unimportant rounding error) than the asymptotically optimal choice of kopt for Ĉnnn,k; see also Hall et al. (2008).”
A Selective Overview of Variable Selection in High Dimensional Feature Space (2009, background): “See also Tibshirani et al. (2002), Donoho and Jin (2008), Hall, Park and Samworth (2008), Hall, Pittelkow and Ghosh (2008), Hall and Chan (2009), Hall and Miller (2009b), and Jin (2009) for some recent developments in high dimensional classiﬁcations.”