Start learning

Curse of Dimensionality

Lesson 46. About 6 minutes.

As the number of features grows, the space they live in grows explosively. Data becomes sparse, distances between points become nearly equal, and many models need far more data to work well. This is the curse of dimensionality.

Your Path Through This Lesson

0 of 5 done

By the End of This Lesson You Can
  • Explain why high-dimensional space is mostly empty.
  • See distances lose their meaning as dimensions grow.
  • Know the main remedies: feature selection and dimensionality reduction.

Space Grows Fast

Suppose you want at least one data point in every "cell" of your feature space, with each feature split into 10 ranges:

Features Cells Points needed for one per cell
1 10 10
2 10 × 10 100
3 10³ 1,000
10 10¹⁰ 10 billion

With 10 features, even a million rows leaves almost every cell empty. The data becomes sparse: every point is far from every other.

Distances Stop Being Informative

Many methods rely on distance: KNN, K-means, DBSCAN, SVMs with an RBF kernel. They assume "near" means "similar". In many dimensions, though, the nearest and furthest points end up at almost the same distance.

python
import numpy as np

rng = np.random.default_rng(0)
for d in [2, 10, 100, 1000]:
    points = rng.random((500, d))
    query = rng.random(d)
    dist = np.linalg.norm(points - query, axis=1)
    print(f"{d:>4} dims: nearest {dist.min():6.2f}   furthest {dist.max():6.2f}   ratio {dist.max() / dist.min():5.2f}")
Output
   2 dims: nearest   0.03   furthest   1.27   ratio 41.73
  10 dims: nearest   0.34   furthest   1.91   ratio  5.65
 100 dims: nearest   3.39   furthest   4.60   ratio  1.36
1000 dims: nearest  12.32   furthest  13.63   ratio  1.11

In 2 dimensions, the furthest point is many times further away than the nearest. In 1,000 dimensions, the ratio is close to 1: every point is roughly equally far. "Nearest neighbour" no longer means much.

Irrelevant Features Hurt

Adding features that carry no information doesn't just waste time; it adds noise to every distance and gives the model more ways to overfit.

python
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_breast_cancer(return_X_y=True)
model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5))

for extra in [0, 30, 100, 300]:
    noise = rng.normal(size=(len(X), extra))
    X_big = np.hstack([X, noise])
    print(f"30 real + {extra:>3} random features: CV accuracy {cross_val_score(model, X_big, y, cv=5).mean():.3f}")
Output
30 real +   0 random features: CV accuracy 0.965
30 real +  30 random features: CV accuracy 0.935
30 real + 100 random features: CV accuracy 0.910
30 real + 300 random features: CV accuracy 0.900

The same 30 useful features, with more and more random columns mixed in: KNN's accuracy falls steadily, because the random dimensions swamp the real distances.

Remedies

Remedy Idea Examples
Feature selection Keep only useful features Domain knowledge, Lasso, tree feature importances, SelectKBest
Dimensionality reduction Combine features into fewer new ones PCA (next lesson)
More data Fill the space more densely Often expensive or impossible
Regularisation Discourage the model from using every feature Ridge, Lasso, limiting tree depth
Choose robust models Some models suffer less Tree ensembles and linear models usually cope better than KNN
Note

Real data is usually kinder than random data: features are correlated, so the points lie near a lower-dimensional surface within the big space. That's exactly what dimensionality reduction exploits.

Try It Yourself
  1. Rerun the noise experiment with RandomForestClassifier instead of KNN. Does it suffer as much?
  2. In the distance experiment, try 5,000 dimensions. What does the ratio approach?
The Key Idea

More features make the space emptier and distances less meaningful. Remove useless features or reduce dimensions, especially for distance-based models.

Summary

  • Space grows exponentially with the number of features; data becomes sparse.
  • In high dimensions, distances become similar, so "nearest" loses meaning.
  • Irrelevant features add noise and overfitting risk.
  • Fix it with feature selection, dimensionality reduction, regularisation or more data.
  • Next: the classic dimensionality reduction method, PCA.