I used to reach for "just add more features" as a free win. It isn't — past a point it quietly destroys any model built on distances, and the reasons are pure geometry, not folklore. The curse of dimensionality is the collection of ways high-dimensional space refuses to behave like the plane in your head. So I built a demo that samples real random points and computes the real Euclidean distances and volume integrals live — drag the dimension from 1 to 100 and watch the numbers break. No faked curves. Three things go wrong at once, and each is a one-line fact you can measure.
Distances concentrate — "nearest" stops meaning anything
Drop N random points into the d-dimensional unit cube and measure every pairwise distance. In 2-D the nearest pair is far closer than the farthest — huge contrast. Crank d up and every distance piles onto the same value:
def pairwise_dists(n, d):
X = np.random.random((n, d))
diff = X[:, None, :] - X[None, :, :]
return np.sqrt((diff**2).sum(-1))[np.triu_indices(n, k=1)]
# mean distance grows like √d, but the spread barely moves —
# so std/mean → 0 and Dmax/Dmin → 1
Beyer et al. (1999) proved it: under broad conditions the farthest/nearest ratio converges to 1 as d→∞, and the relative contrast (Dmax−Dmin)/Dmin goes to 0. When "the nearest neighbor" is barely nearer than the farthest, kNN, k-means and DBSCAN lose their entire basis — every point looks equidistant, so there's nothing for them to discriminate on. In the demo the histogram of distances starts broad and clenches into a narrow spike — that spike is the curse, and it's computed from the real coordinates, not asserted.
Volume flees to a thin outer shell
A d-ball's volume scales as R^d, so the inner ball of radius 1−ε holds only (1−ε)^d of it. Everything else lives in the outer rim:
def shell_fraction(d, eps): return 1 - (1 - eps)**d # exact
def shell_fraction_mc(d, eps, m=100_000):
r = np.random.random(m) ** (1/d) # true radial law
return np.mean(r > 1 - eps) # Monte-Carlo check
# d=50, eps=0.1 → 0.9948: ~99.5% of the volume sits in the outer 10%
The demo plots the exact formula and confirms it with a live Monte-Carlo count — they track. At a few dozen dimensions almost all of a ball's volume is in a paper-thin shell, the interior is empty, and the ball inscribed in a cube shrinks toward zero volume while the corners take over. "Central tendency" barely describes high-D data.
Space gets exponentially sparse — "local" isn't local
To capture a fraction r of uniformly-spread data with a box neighborhood, the box must span an edge of r^(1/d) on every axis:
neighborhood_edge = r ** (1/d) # r=0.01, d=100 → 0.955
samples_for_grid = k ** d # k bins per axis
A "1% neighborhood" in 100-D reaches across 95% of each axis — nothing is local anymore. And filling even a modest k-per-axis grid needs k^d points, which blows past the number of atoms in the universe within a few dozen dimensions. You never have enough data.
The escape: real data lives on a manifold
The reason ML works at all is that real high-D data rarely fills its dimensions — a page of 1000 pixel features really lives on a much smaller surface, clustered near a low-dimensional manifold. So the fix is to get back to that smaller space: project with PCA or UMAP, keep only the informative columns with feature selection, regularize so useless dimensions are ignored, and prefer cosine or Manhattan over Euclidean when d is large. Do that and the distance ratio recovers, the shell stops swallowing everything, and kNN works again — the two curves in the demo snap back toward their low-D shapes.
The takeaway I now carry into every model: in high dimensions geometry is not on your side. Fewer, better dimensions usually win — before you throw 500 features at a model, remember what the ratio and the shell are doing.
Drag the dimension slider and watch the distance ratio crawl to 1 and the shell hit 100%:
https://dev48v.infy.uk/ml/day46-curse-of-dimensionality.html
Top comments (0)