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.
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.
code/ch02_overview_supervised_learning.py (edge_length, nn_median_distance, nn_mean_distance, one_nn_origin_mc, one_nn_bump_exact, Figures 2.6 to 2.8).