Interactive demo · Statistical Learning: Theory and Methods · Chapter 2

The curse of dimensionality: neighbourhoods that are not local

Nearest-neighbour methods estimate f(x0) by averaging the responses of training points near x0. In many dimensions there are no near points. A cube that holds a fraction r of uniform data must have edge r1/p (top left); the nearest of N points in the unit ball is typically more than half-way to the boundary once p is about 10 (top right, formula 2.24); and so the 1-nearest-neighbour estimate of f(0) is badly biased, or very variable, depending on f (bottom, Figures 2.7 and 2.8). The simulations use a seeded generator, so the same settings always give the same numbers.

Dimension p

Fraction of the data r (log scale)

Training points N

True function (bottom panel)

Try these

Top right: the dots are medians over 500 simulated training sets of N points uniform in the unit ball. Bottom: N points uniform on [−1, 1]p without noise, the 1-NN prediction at x0 = 0, averaged over 200 simulated training sets for each p; for the bump the thin line is the exact value, computed from the distribution of the nearest-neighbour distance.

In the lecture notes