k-Nearest Neighbours & the Curse of Dimensionality

k-nearest neighbours (kNN) delays learning until prediction. It stores training examples, finds the $k$ closest to a query under a chosen metric, then votes for a class or averages a response. The apparent simplicity exposes a fundamental principle: the representation and distance function are the model.

The local estimate #

For regression with neighbour set $N_k(x)$,

$$\hat f(x)=\frac1k\sum_{i\in N_k(x)}y_i.$$

For classification, estimate local class probability by the fraction of neighbours in each class and choose according to the decision rule. Distance weighting, such as weights $1/(d_i+\epsilon)$, gives closer observations more influence but can let a mislabeled near-duplicate dominate.

Small $k$ creates a flexible, low-bias, high-variance boundary. Large $k$ smooths noise but can erase local structure and eventually predicts the global majority. Choose $k$, metric, scaling, and weighting together inside validation.

Worked one-dimensional example #

Training positions and classes are

For query $x=3$, the nearest points are 2 (A), 4 (B), and 1 (A). With $k=1$, the tie in distance between 2 and 4 needs a deterministic rule and prediction can flip between A and B. With $k=3$, A wins 2–1. With $k=5$, the global majority B wins. None is intrinsically correct; each imposes a neighbourhood scale.

If observations have unequal relevance, a domain metric may be more important than tuning $k$. Geographic straight-line distance, edit distance, cosine distance, and learned embedding distance encode different notions of “near.”

Scaling and irrelevant dimensions #

Euclidean distance is

$$d(x,z)=\sqrt{\sum_{j=1}^{p}(x_j-z_j)^2}.$$

A high-range coordinate dominates. Standardization fixes units, not relevance: adding 100 independent noise features still injects 100 noise contributions into every squared distance. Feature selection, a task-trained representation, or an appropriate metric may be necessary.

Categorical variables need a meaningful dissimilarity. Integer codes create fictional order and spacing. Mixed numeric/categorical records often need a composite metric with justified weights, not blind one-hot Euclidean distance.

Why high dimension breaks locality #

In $p$ dimensions, a ball's volume scales as $r^p$. To capture a fixed fraction $q$ of roughly uniform data in a unit hypercube, radius scales like $r\approx q^{1/p}$ (up to geometry constants). As $p$ grows, even a small fraction requires a radius close to the full data range. “Local” neighbours become far away.

Distances also concentrate: the nearest and farthest points become similar relative to their absolute distance under many high-dimensional distributions. Then neighbour ranking is sensitive to noise and enormous sample sizes are needed to populate local regions. This is the curse of dimensionality; faster search indexing does not solve the statistical emptiness.

Computation and indexing #

Brute-force prediction compares a query with all $n$ training points, costing roughly $O(np)$ per query and storing the full training set. KD-trees and ball trees can prune searches in low/moderate dimension, but their advantage deteriorates as dimension grows. Approximate nearest-neighbour indexes trade exactness for latency and memory; the approximation itself must be evaluated on downstream loss.

Distance calculation, preprocessing, and index construction must be identical in training and serving. Deleting a training record may require index updates, which makes data-retention semantics operationally significant.

Class imbalance and density #

Majority voting estimates the local class distribution present in training. If sampling altered class prevalence, neighbour proportions are not deployment posteriors. Dense majority regions can engulf sparse minority structure. Class-weighted voting can adjust decisions, but only with a defensible sampling/prevalence model.

Rejecting a query when its nearest distance is too large is often safer than extrapolating. A kNN prediction outside training support is merely the label of the least distant remote examples.

Misconceptions and limits #

• kNN does “train”: it selects representation, scaling, metric, $k$, index, and tie policy from data.
• A small neighbour distance is not semantic similarity unless the representation makes it so.
• PCA before kNN may remove noise, but it can also discard a low-variance discriminative direction.
• Leave-one-out performance can be optimistic when near-duplicates or repeated entities remain.
• $k=1$ does not reveal the true class boundary; it reproduces individual labels and noise.

kNN is strongest when the dataset is moderately sized, the metric has real task meaning, dimension is controlled, and local examples are themselves useful evidence.