Optimal weighted nearest neighbour classifiers

By Richard J. Samworth. 2011

290 citations recorded by the source corpus.

We derive an asymptotic expansion for the excess risk (regret) of a weighted nearest-neighbour classifier. This allows us to find the asymptotically optimal vector of nonnegative weights, which has a rather simple form. We show that the ratio of the regret of this classifier to that of an unweighted k-nearest neighbour classifier depends asymptotically only on the dimension d of the feature vectors, and not on the underlying populations. The improvement is greatest when d=4, but thereafter decreases as $d\rightarrow\infty$. The popular bagged nearest neighbour classifier can also be regarded as a weighted nearest neighbour classifier, and we show that its corresponding weights are somewhat suboptimal when d is small (in particular, worse than those of the unweighted k-nearest neighbour classifier when d=1), but are close to optimal when d is large. Finally, we argue that improvements in the rate of convergence are possible under stronger smoothness assumptions, provided we allow negative weights. Our findings are supported by an empirical performance comparison on both simulated and real data sets.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

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 Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

FEMa: a finite element machine for fast learning (2019, methodology): “It is worth mentioning that FEMa is not a variation of the well-known k-nearest neighbors classifier and its variants such as the weighted nearest neighbor method [39]).”
DÏoT: A Federated Self-learning Anomaly Detection System for IoT (2018, methodology): “We implement automated device-type identification using a supervised k-Nearest Neighbors (kNN) classifier [22].”
A weighted k-nearest neighbor density estimate for geometric inference (2011, methodology): “Our approach is close in spirit to the one of Samworth [46], who derived asymptotic expansions for the excess risk of a weighted nearest neighbor classifier and found the asymptotically optimal vector of weights.”