1 · The curse of dimensionality
Why high-dimensional spaces break distance-based models — and how feature selection vs extraction fight back.
One idea, one try. At your own pace.
LEARN BY DOINGPut your intuition to work3 steps
1 · The curse of dimensionality
Use the lesson’s examples and explanation to check your idea.
Personal reflection. Nothing is sent to an AI service.As dimensionality grows, distances concentrate, neighbourhoods empty out, and 'similar' loses meaning — dimensionality reduction fights back.
Without this:
Without grasping the curse, you'd dump every feature into every model and wonder why KNN, distance-based clustering, and density estimation silently fail.
Dimensionality refers to the number of input features in your dataset. A house might be described by 5 features (area, rooms, floors, age, zip code). A genome might use 500,000 SNP markers. A raw 64×64 image has 4,096 pixel dimensions. As d grows, something deeply counterintuitive happens: the geometry of space breaks down.
The curse of dimensionality is a family of related phenomena that make statistical estimation hard in high dimensions:
-
Volume concentrates at the edges — In a d-dimensional unit cube, the fraction of volume that lies within a distance ε of any face grows to 1 as d → ∞. Most of the mass of a high-dimensional cube lives in its corners, not its interior.
-
Distances concentrate — In high dimensions, the ratio of the maximum to minimum pairwise distance between random points converges to 1. Every point is roughly the same distance from every other point — "nearest neighbour" becomes meaningless.
-
Data density collapses — To maintain the same sample density as you had in d dimensions, you need exponentially more points. Going from 2D to 20D requires roughly 10¹⁸ times more data for equivalent coverage.
Two strategies to fight the curse:
| Strategy | Idea | Examples | |---|---|---| | Feature selection | Keep a subset of original features | SelectKBest, Lasso (L1), mutual information | | Feature extraction | Build new compressed features | PCA, t-SNE, autoencoders |
Selection keeps interpretability (you can name the chosen features). Extraction sacrifices interpretability for compression power — it combines information across all features, potentially capturing structure selection misses.
Python (in browser)
Pairwise distance histograms across dimensionalities — by d=1000 the spread has all but vanished.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
The unit ball collapses to near-zero volume relative to the unit cube.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Selection vs extraction — PCA usually wins slightly because it captures shared variance across all features.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Decision guide: when to select vs extract features.
3-D lab: clusters hiding in 10-D
Six clusters live in 10 dimensions behind two noisy ones: a linear projection stacks them, while t-SNE follows each point's nearest neighbours and pulls them apart.
In a 100-dimensional unit cube, where do most randomly sampled points live?
- As d grows, pairwise distances concentrate around a single value — nearest-neighbour and density-based algorithms silently degrade.
- The volume of a unit ball relative to a unit cube collapses to zero by d≈20 — high-dimensional spherical neighbourhoods capture almost no data.
- Feature selection keeps interpretable original features; feature extraction (PCA, autoencoders) builds new compressed axes — both reduce the effective dimensionality.
- PCA typically outperforms SelectKBest slightly on correlated data because it captures shared variance rather than ranking individual features.
- Always reduce dimensionality before applying KNN, RBF SVM, or GMM to datasets with d > 50.
Image classification (raw pixels are high-D), genomics (millions of SNPs per patient), NLP (word embeddings as a compression of vocabulary size 50k+ to 300-D). All start with some form of dimensionality reduction.
If you remove it: You'd train models in the original feature space and pay the curse on every prediction — poor generalisation, slow inference, and misleadingly small training errors.