Curse of Dimensionality
As the number of features grows, data becomes sparse and distances lose meaning, so methods that rely on 'nearby' examples need exponentially more data.
Also high-dimensional data · dimensionality
Find a friend on a 100 meter line: easy. On a 100 by 100 meter field: harder. In a 100 meter cube: much harder. Every new direction gives your friend more room to hide.
Where it fits
+All relationships as a list
Is a kind of / part of
Siblings
How it works
Adding features sounds like it should always help: more information, better predictions. In practice, every extra dimension makes the space much bigger, and your data does not grow with it.
Two surprising effects:
- Sparsity. To cover a unit line with points spaced 0.1 apart you need 10 points. A square needs 100, a 10-dimensional cube needs 10 billion. Your dataset is almost always tiny compared with the space.
- Distances flatten out. In high dimensions, the nearest and farthest neighbors of a point can be almost the same distance away. Methods built on “closeness”, like k-nearest neighbors and k-means, become less reliable.
The way out: real data is rarely spread evenly. Faces, sentences and sensor readings lie near much lower-dimensional surfaces. That is why these tools work:
- PCA and t-SNE / UMAP find the few directions that matter.
- Regularization and feature selection ignore useless features.
- Neural networks learn compact embeddings where distance means similarity.
Everyday use cases
- Case 01
Genomics
Thousands of gene measurements per patient but only hundreds of patients, so models overfit easily without dimensionality reduction or strong regularization.
- Case 02
Nearest-neighbor search
Why plain kNN on raw pixels works poorly, while kNN on learned embeddings works well.
Strengths, weaknesses and when to use it
Strengths
- Explains why feature selection, PCA and embeddings matter.
Weaknesses
- The worst-case picture is often too pessimistic, because real data has structure.
When to use itKeep it in mind whenever you have many features relative to examples, or use distance-based methods.
Compare with
Check yourself
- Q01
Why does kNN struggle with many raw features?
Show answer
A: Distances between points become nearly equal
- Q02
Which helps against the curse of dimensionality?
Show answer
B: Dimensionality reduction such as PCA