Why does KNN degrade badly in high dimensions?
mediumAnswer
- In high dimensions, pairwise distances between random points concentrate — the ratio (max - min) / min distance approaches 0.
- Every point becomes roughly the same distance from every other, so the concept of 'nearest' loses meaning and KNN votes become dominated by noise.
- Remedies: apply dimensionality reduction (PCA, autoencoder) first, use domain-specific distance metrics, or switch to a model with stronger inductive bias (tree ensembles).
Check yourself — multiple choice
- Distances become more discriminative in high dimensions
- Pairwise distances concentrate — the nearest neighbour is not much closer than the farthest
- KNN can only run on GPUs
- It just needs more training data
Distance concentration in high dimensions kills the notion of a meaningful 'nearest' neighbour.
#knn#theory
Practise Supervised Learning
215 interview questions in this topic.
Related questions
- Generative vs discriminative classifier — what's the difference?
- What is the curse of dimensionality?
- Parametric vs non-parametric models — what's the difference?
- Why do we prefer simpler models when performance is equal?
- What does the no free lunch theorem say for ML?
- In one sentence, what is PAC learning?