What is the curse of dimensionality, and how does it affect distance-based algorithms like KNN?
Classic MLLevel: FoundationClassical machine learning
What is the curse of dimensionality, and how does it affect distance-based algorithms like KNN?
Hints
- Which information should a lower-dimensional representation preserve?
- Check centering, scaling and the difference between projection and feature selection.
Answer
As the number of features grows, the volume of the feature space grows exponentially, so data points become sparse and the ratio between the nearest and farthest neighbor distances tends toward 1 — meaning "nearest neighbor" becomes less meaningful. This hurts algorithms that rely on distance metrics (KNN, K-Means, clustering) and increases the risk of overfitting for any model given fixed sample size. Mitigations: dimensionality reduction (PCA, feature selection), or using tree-based/regularized models that are less distance-sensitive.
Source and licence: Ishan Dutta — Awesome Data Science Interview Q&A · MIT