k-Nearest Neighbors

The algorithm

kNN is lazy learning: training is storing the data. To predict for a query $\mathbf{x}$, compute its distance to every stored point, take the $k$ closest — the neighbourhood $N_k(\mathbf{x})$ — and aggregate their labels:

The distance-weighted version gives nearer neighbours more say, with weights $w_i = 1/d(\mathbf{x},\mathbf{x}_i)$ (or $e^{-d^2/\tau}$), and predicts the weighted vote or weighted mean. Class probabilities are the vote fractions, which makes kNN a crude density estimator: it is asking "around here, which label is more common?" The model is the data plus a notion of "around here" — the distance.

Distances and scaling

Scaling is not optional. Suppose patients are described by age (20–80 years) and income (20,000–200,000). Euclidean distance between $(30, 50000)$ and $(60, 51000)$ is $\sqrt{30^2 + 1000^2} \approx 1000.4$: the thirty-year age gap contributes essentially nothing, and the "nearest" neighbours are chosen by income alone. Standardize each feature (zero mean, unit variance) or min–max scale it using training-set statistics before computing any distance. For one-hot categorical features, consider Hamming or Gower distance; for embeddings, normalize to unit length so Euclidean and cosine rankings coincide (1.1 Vectors, dot products and norms).

Choosing k

$k$ is the capacity knob of 3.1 What is learning? ERM, generalization and the ML workflow in reverse. With $k=1$ the training error is zero (every point is its own nearest neighbour), the decision boundary follows every noisy point, and the model has high variance. As $k$ grows the boundary smooths, outliers are outvoted, and eventually — at $k=n$ — every prediction is the majority class: high bias. The sweet spot depends on the data and is found by cross-validation (3.5 Evaluating models: metrics, validation and the bias–variance trade-off); $\sqrt{n}$ is a common starting point, odd $k$ avoids ties in binary problems, and distance weighting makes the choice less sensitive. The interactive demo shows this directly: place two classes of points, slide $k$ and watch the painted decision regions go from jagged islands to smooth blobs.

Worked example

Training points $(x_1, x_2, y)$: $A=(1,1,\text{red})$, $B=(2,1,\text{red})$, $C=(4,3,\text{blue})$, $D=(5,4,\text{blue})$, $E=(3,3,\text{red})$. Query $\mathbf{q}=(3,2)$. Squared Euclidean distances: $A: 4+1=5$, $B: 1+1=2$, $C: 1+1=2$, $D: 4+4=8$, $E: 0+1=1$.

• $k=1$: nearest is $E$ (distance $1$) → red.
• $k=3$: $E$ (1), then $B$ and $C$ tied at $\sqrt2$ → votes red, red, blue → red, with probability $2/3$.
• $k=5$: three red, two blue → red, probability $3/5$.
• Distance-weighted, $k=3$: weights $1/1, 1/\sqrt2, 1/\sqrt2$ → red $1.707$ vs blue $0.707$ → red with higher confidence than the plain vote.

Move the query to $(4, 2.5)$ and recompute: $C$ is now nearest, and $k=1$ flips to blue while $k=5$ still says red — the small-$k$ boundary is the one that moves.

The curse of dimensionality

kNN assumes neighbours are local — close in every feature. In high dimensions three facts conspire against that assumption.

1. Neighbourhoods are not local. Take $n$ points uniform in the unit cube $[0,1]^d$. To capture a fraction $f$ of the points in a sub-cube around a query, its edge must be $e_d(f) = f^{1/d}$. For $f = 1\%$: $e_{2} = 0.1$, $e_{10} = 0.63$, $e_{100} = 0.955$. In 100 dimensions, a "neighbourhood" containing 1% of the data spans 95% of the range of every feature. Nearest neighbours are not near.

2. Distances concentrate. If coordinates are i.i.d. with variance $s^2$, then $\|\mathbf{x}-\mathbf{x}'\|^2 = \sum_{j=1}^d (x_j - x'_j)^2$ is a sum of $d$ i.i.d. terms: its mean grows like $d$ and its standard deviation like $\sqrt d$, so the relative spread of distances shrinks like $1/\sqrt d$. The ratio $(d_{\max} - d_{\min})/d_{\min}$ from a query to the dataset tends to zero: everyone is roughly equally far away, and "nearest" becomes a statement about noise (1.1 Vectors, dot products and norms made the same point with cosines).

3. Everything is on the edge. The fraction of the unit cube's volume within $\varepsilon$ of its boundary is $1 - (1-2\varepsilon)^d$; for $\varepsilon = 0.05$ this is $19\%$ at $d=2$ and $99.997\%$ at $d=100$. Almost every point is near the boundary, so predictions extrapolate rather than interpolate.

Yet kNN on 768-dimensional sentence embeddings works superbly (9.2 Embeddings deep dive). The resolution is that real data lie near a low-dimensional manifold — images of digits, sentences about cooking — and a good embedding maps that manifold to a space where Euclidean distance tracks semantic similarity. The curse applies to the ambient dimension of raw pixels or one-hot words, not to the intrinsic dimension of meaningful representations. This is the deepest reason representation learning (4.10 Autoencoders, embeddings and representation learning, 5.8 Self-supervised and contrastive learning) matters: it makes kNN's assumption true.

Cost, trees and approximate search

A brute-force query costs $O(nd)$ — compute $n$ distances in $d$ dimensions — which is the whole pairwise-distance trick of 2.2 NumPy and vectorized thinking in one row. For $n$ in the millions and thousands of queries per second that is too slow. KD-trees and ball trees partition space recursively and answer exact queries in roughly $O(\log n)$ when $d \lesssim 20$; above that the partitions stop pruning anything (distance concentration again) and they degrade to brute force. The modern answer is approximate nearest neighbour (ANN) search: locality-sensitive hashing, inverted-file indexes with product quantization, and graph-based HNSW, which navigates a hierarchy of small-world graphs greedily and finds the true nearest neighbour 95–99% of the time, 100–1000× faster than brute force. This is exactly what a vector database does (9.3 Vector search and indexes); scikit-learn's KNeighborsClassifier(algorithm="auto") picks a tree or brute force for you, and FAISS/HNSW libraries take over at scale.

Beyond classification

kNN regression (KNeighborsRegressor) averages neighbours' targets; KNNImputer fills missing values from similar rows (3.13 Feature engineering, data quality and data-centric ML); the distance to the $k$-th neighbour is an anomaly score; user–user collaborative filtering recommends what your nearest users liked; and few-shot classification on top of a pretrained encoder is kNN in embedding space — label ten examples, embed everything, vote. Against logistic regression (3.3 Logistic regression and softmax classification), kNN wins when the boundary is complex and data are dense, loses when data are scarce, high-dimensional and raw, and is always slower at prediction time — the opposite trade-off of a parametric model, which is slow to train and instant to query.

Where this shows up later

• Distance on embeddings is retrieval: vector search, ANN indexes and RAG — 9.2 Embeddings deep dive, 9.3 Vector search and indexes, 9.5 Retrieval quality: hybrid search, reranking, query transforms and metrics.
• k-means uses the same distances to assign points to centroids — 3.11 Clustering: k-means, GMMs/EM, DBSCAN and hierarchical; KNNImputer and anomaly scores appear in 3.13 Feature engineering, data quality and data-centric ML.
• The curse of dimensionality motivates dimensionality reduction — 3.12 Dimensionality reduction: PCA, t-SNE and UMAP — and representation learning — 4.10 Autoencoders, embeddings and representation learning, 5.8 Self-supervised and contrastive learning.
• kNN's bias–variance behaviour in $k$ is the clean case for the decomposition in 3.5 Evaluating models: metrics, validation and the bias–variance trade-off.