Interactive demo · Probabilistic Machine Learning · Chapter 16

The curse of dimensionality for nearest neighbours

Points are uniform in the unit cube; the class is 1 inside a disc in the plane of the first two coordinates and 0 outside (left). Every further coordinate is pure noise, but the Euclidean distance counts it as much as the informative ones. Adding nuisance coordinates pushes the nearest neighbours far away (right: the edge of the cube that must be grown around a point to capture K of the N training points is (K/N)1/D, which approaches 1) and the test error (middle, red) climbs from near zero towards the error of always guessing the larger class. A metric that only looks at the two informative coordinates (teal) is untouched: this is the remedy of Section 16.1.2, learning which dimensions matter (Section 16.2).

Nuisance coordinates

Training points N

Neighbours K

Try these

Data: 400 training and 400 test points, uniform in [0,1]30, simulated; the page uses the first N training points and the first 2 + (nuisance) coordinates. The class is 1 iff (x1 − 0.5)2 + (x2 − 0.5)2 < 0.1, so the Bayes error is 0 and about 31 percent of the points are in class 1. The distance is Euclidean in all used coordinates (red) or in the two informative ones (teal).

In the lecture notes