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

DOI10.1016/j.camwa.2012.09.011zbMath1362.68248arXiv1110.4347OpenAlexW2057074619MaRDI QIDQ2629451

Vladimir G. Pestov

Publication date: 6 July 2016

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

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

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)

Related Items (5)

Editorial: Grasping complexity ⋮ Correction of AI systems by linear discriminants: probabilistic foundations ⋮ A classification algorithm based on geometric and statistical information ⋮ Blessing of dimensionality: mathematical foundations of the statistical physics of data ⋮ Approximation with random bases: pro et contra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Indexability, concentration, and VC theory
• Covering, measure derivation and dimensions
• Pattern recognition via projection-based \(k\)NN rules
• On the almost everywhere convergence of nonparametric regression function estimates
• Consistent nonparametric regression. Discussion
• Balls in \(\mathbb{R}^k\) do not cut all subsets of \(k+2\) points
• Learning and generalisation. With applications to neural networks.
• 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
• Higher Lower Bounds for Near-Neighbor and Further Rich Problems
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Nearest neighbor classification in infinite dimension
• Nearest neighbor pattern classification
• 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

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