k-NN and the Curse of Dimensionality

k-nearest neighbors predicts from stored examples: it finds nearby training points and combines their targets. Fitting can still involve scaling features or building a search index, but basic k-NN does not optimize a coefficient vector. Its usefulness depends on whether the chosen distance brings together examples with similar outcomes. Adding many irrelevant coordinates can change those neighbors even when the useful features stay the same.

The algorithm, and what it assumes

For uniform k-NN classification, find the \(k\) closest training points and return their majority label. For regression, return their mean target. If the three nearest labels are 1, 0, and 1, the predicted class is 1 and the estimated class-1 probability is \(2/3\); targets 8, 10, and 15 would instead give a regression prediction of 11. A useful local relationship is that the conditional mean or class probabilities vary little among nearby points. Noisy individual targets need not agree. Coverage of the query region and representative training data also matter.

Euclidean distance is \(\sqrt{\sum_j(x_j-q_j)^2}\), where \(x\) is a stored point and \(q\) the query. It gives equal coefficients to squared coordinate differences; it does not explicitly weight features by their variance. Changing a length from meters to centimeters multiplies its contribution to squared distance by 10,000. Standardization divides by a training-set scale and can prevent units from dominating, but does not identify which features are relevant. Fit that preprocessing inside each training fold. Manhattan distance sums absolute differences, so one large difference has less dominance relative to the other coordinates than in the sum of squares; this is not a guarantee of better performance in high dimensions. Cosine similarity compares directions of nonzero vectors and is unchanged by positive rescaling. Zero vectors need a separate convention.

Choosing k

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score

rng = np.random.default_rng(1)
n = 600
X = rng.normal(size=(n, 2))
y = (X[:, 0] * X[:, 1] > 0).astype(int)
flip = rng.random(n) < 0.15                    # each label flips with probability 0.15
y[flip] = 1 - y[flip]

for k in (1, 3, 9, 27, 81, 243):
    m = KNeighborsClassifier(k)
    print(f"k={k:4d}  train {m.fit(X, y).score(X, y):.4f}"
          f"  cv {cross_val_score(m, X, y, cv=5).mean():.4f}")
# k=   1  train 1.0000  cv 0.7317
# k=   3  train 0.8700  cv 0.7767
# k=   9  train 0.8267  cv 0.7950
# k=  27  train 0.8267  cv 0.7933
# k=  81  train 0.8050  cv 0.7783
# k= 243  train 0.7033  cv 0.5317

Here the two coordinates define four quadrants: the clean label is 1 when their signs agree. Each label is then flipped independently with probability 0.15. At \(k=1\), calling score(X, y) on the training rows gives 1.0 because each distinct point retrieves itself, including its noisy label. Conflicting labels at identical inputs would prevent this guarantee. Five-fold cross-validation evaluates held-out rows and gives 0.7317. Among the six tested values, \(k=9\) has the highest CV score, 0.7950; its small lead over 27 does not establish a precise optimum. At \(k=243\), each validation prediction uses 243 of the fold’s 480 training rows, about 51%, and accuracy falls to 0.5317. The training-score neighborhood uses 243 of 600 rows, about 41%. A separate test set or nested evaluation is needed to assess the procedure after selecting \(k\).

Increasing \(k\) averages over more labels but reaches farther from the query. This often trades reduced sensitivity to individual noisy labels for more smoothing across changes in the target. The familiar \(1/k\) variance formula has a narrower meaning: in regression with fixed neighbor locations and independent errors of common variance \(\sigma^2\), the noise contribution to the variance of their uniform average is \(\sigma^2/k\). Random training locations contribute additional variation, and a classification majority vote is not that average. Neither its variance nor its bias must change monotonically with \(k\) on every problem.

An odd \(k\) avoids equal class counts in uniform binary voting, but does not settle ties in neighbor distances or weighted votes. Distance weighting gives closer points more influence; it still requires choosing \(k\) and a meaningful distance.

Relative distance contrast

The next experiment isolates the geometry of independent standard-normal coordinates. For each dimension it draws 1,000 stored points and one independent query. axis=1 computes one distance per stored row. The last columns measure the range relative to the nearest distance and the standard deviation relative to the mean; there are no targets here, so this experiment cannot measure predictive accuracy.

import numpy as np

rng = np.random.default_rng(0)
print(f"{'dim':>6} {'min d':>9} {'max d':>9} {'(max-min)/min':>15} {'sd/mean':>9}")
for d in (1, 2, 5, 20, 100, 1000):
    X = rng.normal(size=(1000, d))
    q = rng.normal(size=d)
    dist = np.linalg.norm(X - q, axis=1)
    print(f"{d:6d} {dist.min():9.3f} {dist.max():9.3f}"
          f" {(dist.max() - dist.min()) / dist.min():15.4f} {dist.std() / dist.mean():9.4f}")
#    dim     min d     max d   (max-min)/min   sd/mean
#      1     0.001     5.083       4571.2016    0.6354
#      2     0.093     4.166         43.6939    0.4804
#      5     0.764     6.758          7.8499    0.2512
#     20     3.627     9.411          1.5950    0.1399
#    100    11.145    16.556          0.4855    0.0591
#   1000    41.443    47.084          0.1361    0.0194

The range column is \((D_{\max}-D_{\min})/D_{\min}\), so the farthest-to-nearest ratio is one plus the printed value: about 4,572 in one dimension and 1.136 in 1,000 dimensions. Across the same rows, the relative standard deviation falls from 0.6354 to 0.0194. Absolute distances grow in this setup, while their relative differences shrink.

The sum is the squared distance, \(D^2=\sum_j(X_j-q_j)^2\). For one independent standard-normal pair, each difference has variance 2, giving \(\mathbb E[D^2]=2d\) and \(\operatorname{Var}(D^2)=8d\). Thus the relative standard deviation of squared distance is \(\sqrt{2/d}\). Taking the square root gives distances of scale \(\sqrt{2d}\) with relative fluctuations of order \(1/\sqrt d\). The table conditions on one shared query in each row, so its spread is not a direct estimate over independent random pairs. Finite-sample extreme distances also depend on the number of stored points. These calculations explain this Gaussian setup, not every distribution with many columns.

Low relative distance contrast can make neighbor rankings sensitive to irrelevant features. Related difficulties arise for clustering and kernel methods when their distance is poorly matched to the data. High-dimensional embeddings can still have useful neighborhoods, however, and data may lie near a much lower-dimensional structure. Feature selection, dimensionality reduction, and a learned metric are options to validate, not compulsory preprocessing for every distance-based method. An unsupervised projection can also remove low-variance directions that matter for prediction.

How much data fits in a local region

A related geometric calculation concerns how many points a small region can contain. Suppose data are uniform in the unit cube \([0,1]^d\). An axis-aligned sub-cube lying entirely inside it, with side length \(a\), has volume and probability mass \(a^d\). To cover a fraction \(r\), solve \(a^d=r\), giving \(a=r^{1/d}\). In two dimensions, a square of side 0.1 covers \(0.1^2=0.01\), or 1%, of the area.

print(f"{'dim':>6} {'edge for 1% of the volume':>26} {'edge for 10%':>14}")
for d in (1, 2, 10, 50, 100):
    print(f"{d:6d} {0.01 ** (1 / d):26.4f} {0.10 ** (1 / d):14.4f}")
#    dim  edge for 1% of the volume   edge for 10%
#      1                     0.0100         0.1000
#      2                     0.1000         0.3162
#     10                     0.6310         0.7943
#     50                     0.9120         0.9550
#    100                     0.9550         0.9772

At 100 dimensions, such a cube needs side length 0.955 to contain 1% of the uniform distribution’s mass. It spans most of each coordinate range while still containing only a small fraction of all points. The calculation concerns expected mass, not an exact finite-sample count, and uses cubes rather than the Euclidean balls used by k-NN. It illustrates how demanding local coverage can become; averaging 1% of the data is not literally a global average.

For a fixed side length \(0<a<1\), the expected number of uniform observations in this cube is \(na^d\). Maintaining an expected count of \(k\) therefore requires \(n=k/a^d\), exponential in dimension. This full-dimensional uniform model differs from data concentrated near a curve or surface. What matters in practice is how many directions the data occupy locally and which of them affect the target, not the column count alone.

Cost

With \(n\) stored rows and \(d\) coordinates, a brute-force scan takes \(O(nd)\) work to compute distances per query; selecting neighbors and combining their targets adds work. Storing dense training features takes \(O(nd)\) memory. KD-trees and ball trees pay an index-building cost to avoid some distance calculations. They can give roughly logarithmic search behavior in favorable low-dimensional settings, but do not guarantee \(O(d\log n)\) per query. Performance depends on data geometry, \(k\), index settings, and implementation.

Approximate methods such as locality-sensitive hashing, HNSW graphs, and product quantization can trade retrieval accuracy for speed or memory. Whether a missed neighbor is acceptable depends on the application: two nearly equal distances can still have different labels or relevance. Compare recall against an exact-search baseline, latency, memory, and downstream prediction or retrieval quality. Exact brute-force search can remain suitable for smaller collections or efficient batched computation.

References

• scikit-learn documentation. Nearest Neighbors