Scatter some points in a box. The nearest pair is obviously close and the farthest pair
is obviously far. Now add dimensions. Every distance grows — but they grow together,
and the gap between nearest and farthest closes until asking which point is closest stops telling
you anything at all.
Every distance between every pair● nearest pair● farthest pair
nearest pair—farthest pair—farthest ÷ nearest—volume in the skin—
—
—
140 — near ≈ far300
20 a handful120 — default200 a crowd
1% thin5% — default25% thick rind
↳ your turn — drag
Dimensions to the right and watch the pile of distances lift off zero and close
into a spike
What you're seeing
The points are scattered once and then left alone. Moving the Dimensions slider does not
re-scatter them. It gives each point one more coordinate.
The histogram counts every distance between every pair. The axis always starts at zero, so you
can see how far the whole pile sits from the origin, not just how wide it is.
In one dimension the pile touches zero and sprawls: some pairs are almost on top of each other,
others are at opposite ends. That is what "near" and "far" mean.
Add dimensions and two things happen at once. The pile marches to the right, because each new
coordinate adds another difference to the total. And the pile narrows, because those differences
average out. Distance still exists. It just stops varying.
The second of those is the one that matters, and it is easy to watch the first instead. Things
getting further apart is not the problem — you could divide every distance by a hundred and
nothing would improve. The problem is that near and far stop being different kinds of
distance.
Watch the farthest ÷ nearest figure. In one dimension it is enormous. Somewhere
around forty dimensions it drops below two: the most distant point in your data is no longer even
twice as far away as the closest one.
The bar underneath tells the same story about volume. A sphere's outer skin is a sliver in three
dimensions and almost the whole fruit in three hundred. The sphere is not
shrinking. Its radius is 1 in every dimension. What moves is where the volume sits.
Then press Lay them on a line instead. Same three hundred dimensions, same points, but
arranged along a single straight line through the space — and the spread springs straight
back. This is the part that matters in practice. It is not the number of
columns in your data that does the damage; it is how many of them carry independent information.
Real measurements are usually tangled together, which is why nearest-neighbour methods still work
on photographs with a million pixels.
The rule, exactly. Squared distance between two points is a sum of
d independent per-coordinate terms:
D2= ∑i=1d (xi − yi)2
A sum of d independent terms has a mean growing like d and a standard
deviation growing like √d, so the pile's width relative to its centre
falls like 1⁄√d. For the volume bar, a ball of radius r has
volume proportional to rd, so an inner ball of radius
1−ε keeps only (1−ε)d of it.
Verified in node (improve/verify/113-curse-of-dimensionality.js, 25 checks):
The skin formula 1−(1−ε)d is confirmed
by sampling points inside a real d-ball, a completely different route to the
same number.
The relative spread falls monotonically from 10,986 at d=1 to 0.23 at
d=500, and the width-to-centre ratio halves each time d quadruples,
exactly as 1⁄√d requires.
For two random directions, the mean of cos2 of the angle between them is
1⁄d at every dimension tested; at d=100 two random directions
sit about six degrees from perpendicular.
The threshold quoted on this page is measured, not guessed: the median over nine
scatters. It also moves with how many points you draw — d=23 at 30 points,
41 at 120, 57 at 400 — so the slider's landmark is honest only alongside its sample
size.
Negative control. At d=1, 2 and 3 a 5% skin holds under 15% of
the volume. The formula does not simply return "nearly all" whatever you feed it.
Negative control. 120 points on a line inside 500 dimensions keep a
spread of 7,031 where a scattered cloud gives 0.23. Ambient dimension is not the cause.
Negative control. Rescaling every coordinate leaves the relative spread
identical to twelve decimal places, which refutes the tempting explanation that distances
merely got bigger.
The random generator is checked before it is used — mean, range and a
chi-square on its deciles.
What this leaves out: the points here are independent and uniform, which is
the worst case. Real data usually lies on a lower-dimensional surface inside its space, and the
line button is the extreme version of that.