k-Nearest Neighbours and the Curse of Dimensionality

Suppose your data are spread uniformly in a unit cube and you want a neighbourhood that holds 1% of the points. In two dimensions a square of side 0.1 does it. In ten dimensions the cube needs side \(0.01^{1/10} \approx 0.63\), covering nearly two thirds of the range of every feature. In a hundred dimensions it needs side \(0.955\). The "nearest" neighbours are no longer near anything, and the method that depends on locality has quietly lost it.

The method and its guarantee

Given training pairs \((x_i, y_i)\), a distance \(d\), and a query \(x\), k-nearest neighbours finds the \(k\) training points closest to \(x\) and predicts their majority label (classification) or their mean (regression). There is no training step and no parameters beyond \(k\) and the metric. All the modelling lives in the choice of \(d\).

The method has a remarkable asymptotic guarantee. For the 1-nearest-neighbour rule with \(M\) classes, as the training set grows its error \(R\) satisfies

where \(R^*\) is the Bayes error, the lowest achievable by any classifier (Cover & Hart, 1967, Nearest Neighbor Pattern Classification, IEEE Trans. Inf. Theory 13(1)). For two classes this is at most \(2R^*(1-R^*)\): with a Bayes error of 5%, one neighbour eventually gets at most 9.5%, using no knowledge of the distribution at all. Letting \(k \to \infty\) while \(k/n \to 0\) makes k-NN consistent, converging to the Bayes error itself (Stone, 1977, Consistent Nonparametric Regression, Ann. Statist. 5(4)).

The choice of \(k\) is a bias-variance dial. For regression with noise variance \(\sigma^2\), averaging \(k\) neighbours cuts variance to roughly \(\sigma^2/k\), while a larger \(k\) reaches further from the query and averages over points where the true function differs. Small \(k\) gives jagged boundaries; large \(k\) over-smooths toward the class prior.

Two faces of the curse

The guarantee above is asymptotic, and the price of reaching the asymptote grows exponentially with dimension. This has two separate mechanisms that are often run together.

Neighbourhoods stop being local. The cube calculation is the first. To keep the neighbourhood small you need exponentially more data. For a Lipschitz regression function, the classical nonparametric error rate is of order \(n^{-2/(2+d)}\), so the sample needed for a fixed error \(\varepsilon\) scales like \(\varepsilon^{-(2+d)/2}\). Ignoring constants, at \(\varepsilon = 0.1\) that is on the order of 100 points in two dimensions and a million in ten.

Distances stop discriminating. The second mechanism is concentration of distances. Beyer and colleagues showed that under broad conditions, including i.i.d. features, the ratio of the farthest to the nearest distance from a query tends to 1 as dimension grows (Beyer et al., 1999, When Is "Nearest Neighbor" Meaningful?, ICDT, LNCS 1540). If every point sits at nearly the same distance, the ranking is decided by noise. The choice of norm matters here: Aggarwal, Hinneburg and Keim found that the relative contrast between nearest and farthest decays faster for higher-order \(L_p\) norms, so \(L_1\) keeps more contrast than Euclidean distance, and fractional norms more still (Aggarwal et al., 2001, On the Surprising Behavior of Distance Metrics in High Dimensional Space, ICDT).

A related symptom, hubness, makes a few points appear in almost every neighbour list.

Why it still works on real data

If the curse were the full story, nearest-neighbour search over 768-dimensional embeddings would be useless, and it plainly is not. Real data usually lie near a low-dimensional structure inside the ambient space, and the relevant rate depends on that intrinsic dimension, not on the column count. The concentration results need assumptions, such as independent, identically distributed coordinates, that structured data violate.

This is where practitioners disagree. One camp treats the curse as mostly a theoretical warning that learned representations have already defeated. The other points out that tabular feature sets with many weakly related columns behave much more like the i.i.d. case, and that k-NN on raw tabular features in dozens of dimensions is routinely beaten by trees for exactly this reason. Both are right about different data.

When it breaks

The metric is a model, and scaling decides it. Euclidean distance on unscaled features lets income in dollars dominate age in years by five orders of magnitude. Standardising is not a neutral preprocessing step, it asserts that one standard deviation of every feature matters equally. Irrelevant features add distance noise with no signal, and k-NN has no mechanism to ignore them.

Prediction cost moves to query time. Brute force costs \(O(nd)\) per query: ten million stored vectors at 768 dimensions is about \(7.7 \times 10^9\) floating-point operations for a single lookup. Tree indexes such as k-d trees degrade toward brute force above roughly a few dozen dimensions, and graph-based approximate indexes trade exact neighbours for speed, returning some fraction of the true top \(k\).

Majority vote ignores imbalance. With 1% positives, a positive query in any region where the classes overlap usually finds a majority of negative neighbours. Distance-weighted votes or adjusting the decision threshold on the neighbour fraction help; the raw vote does not produce calibrated probabilities either, since with \(k = 5\) the only possible outputs are multiples of 0.2.

The whole training set is the model. Storing it raises memory and privacy costs, and every correction to a mislabelled training point changes predictions directly around it, which is both a strength for editing and a weakness for poisoning.