Is the k-NN classifier in high dimensions affected by the curse of dimensionality?
From MaRDI portal
Publication:2629451
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.
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
Cites work
- scientific article; zbMATH DE number 3719441 (Why is no real title available?)
- scientific article; zbMATH DE number 3790697 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- scientific article; zbMATH DE number 2107521 (Why is no real title available?)
- scientific article; zbMATH DE number 2109363 (Why is no real title available?)
- scientific article; zbMATH DE number 893887 (Why is no real title available?)
- scientific article; zbMATH DE number 1421142 (Why is no real title available?)
- An axiomatic approach to intrinsic dimension of a dataset
- Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points
- Consistency and localizability
- Consistent nonparametric regression. Discussion
- Covering, measure derivation and dimensions
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Higher lower bounds for near-neighbor and further rich problems
- Indexability, concentration, and VC theory
- Indexing schemes for similarity search: an illustrated paradigm
- Learning and generalisation. With applications to neural networks.
- 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
- Nearest neighbor pattern classification
- On the almost everywhere convergence of nonparametric regression function estimates
- Pattern recognition via projection-based \(k\)NN rules
- Similarity search. The metric space approach.
- Tighter bounds for nearest neighbor search and related problems in the cell probe model
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
- Correction of AI systems by linear discriminants: probabilistic foundations
- Blessing of dimensionality: mathematical foundations of the statistical physics of data
- 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)
