Is the k-NN classifier in high dimensions affected by the curse of dimensionality?

DOI10.1016/J.CAMWA.2012.09.011zbMATH Open1362.68248arXiv1110.4347OpenAlexW2057074619MaRDI QIDQ2629451FDOQ2629451

Authors: Vladimir G. Pestov 

Publication date: 6 July 2016

Published in: Computers & Mathematics with Applications (Search for Journal in Brave)

Abstract: There is an increasing body of evidence suggesting that exact nearest neighbour search in high-dimensional spaces is affected by the curse of dimensionality at a fundamental level. Does it necessarily mean that the same is true for k nearest neighbours based learning algorithms such as the k-NN classifier? We analyse this question at a number of levels and show that the answer is different at each of them. As our first main observation, we show the consistency of a k approximate nearest neighbour classifier. However, the performance of the classifier in very high dimensions is provably unstable. As our second main observation, we point out that the existing model for statistical learning is oblivious of dimension of the domain and so every learning problem admits a universally consistent deterministic reduction to the one-dimensional case by means of a Borel isomorphism.

Full work available at URL: https://arxiv.org/abs/1110.4347

Recommendations

• When is `nearest neighbour' meaningful: A converse theorem and implications
• scientific article; zbMATH DE number 2065612
• On the finite sample performance of the nearest neighbor classifier
• Lower bounds for high dimensional nearest neighbor search and related problems
• On the performance of edited nearest neighbor rules in high dimensions

zbMATH Keywords

dimensionalitynearest neighbour searchapproximate \(k\)-NN classifierBorel dimensionality reduction

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Nearest neighbor pattern classification
• Consistent nonparametric regression. Discussion
• Title not available (Why is that?)
• On the almost everywhere convergence of nonparametric regression function estimates
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Nearest neighbor classification in infinite dimension
• Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points
• Learning and generalisation. With applications to neural networks.
• Title not available (Why is that?)
• Consistency and localizability
• Indexing schemes for similarity search: an illustrated paradigm
• An axiomatic approach to intrinsic dimension of a dataset
• Similarity search. The metric space approach.
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• Indexability, concentration, and VC theory
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Title not available (Why is that?)
• Covering, measure derivation and dimensions
• Title not available (Why is that?)
• Pattern recognition via projection-based \(k\)NN rules
• Higher lower bounds for near-neighbor and further rich problems

Cited In (8)

• On some transformations of high dimension, low sample size data for nearest neighbor classification
• Approximation with random bases: pro et contra
• New algorithms for efficient high-dimensional nonparametric classification
• Editorial: Grasping complexity
• A classification algorithm based on geometric and statistical information
• Blessing of dimensionality: mathematical foundations of the statistical physics of data
• Correction of AI systems by linear discriminants: probabilistic foundations
• Hubs in space: popular nearest neighbors in high-dimensional data

This page was built for publication: Is the \(k\)-NN classifier in high dimensions affected by the curse of dimensionality?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629451)