k-Nearest Neighbours

The k-NN algorithm for classification and regression, distance metrics (Euclidean, Manhattan, Minkowski, cosine, Hamming), why feature scaling matters, choosing k and its bias–variance effect, distance-weighted voting, computational cost and speed-ups (k-d trees, approximate search), the curse of dimensionality, and the 1-NN error guarantee.

The algorithm

k-NN makes predictions directly from the stored training data:

Compute the distance from the query $\mathbf x$ to every training point.
Take the $k$ nearest.
Classification: majority vote of their labels. Regression: average (or median) of their targets.

Python

import numpy as np
from collections import Counter

def knn_predict(X_train, y_train, x, k=3):
    d = np.linalg.norm(X_train - x, axis=1)       # Euclidean distances
    idx = np.argsort(d)[:k]                       # k nearest
    return Counter(y_train[idx]).most_common(1)[0][0]

k-NN is non-parametric (no fixed set of parameters), instance-based and lazy (all work happens at prediction time).

The prediction can change with k: the nearest point is green, but most of the five nearest are blue.

Distance metrics

Metric	Formula	Use
Euclidean (L2)	$\sqrt{\sum(x_i - y_i)^2}$	default for continuous features
Manhattan (L1)	$\sum\lvert x_i - y_i\rvert$	grid-like movement, robust to outliers
Minkowski ( $L_p$ )	$\left(\sum\lvert x_i - y_i\rvert^p\right)^{1/p}$	$p = 1, 2$ special cases; $p \to \infty$ : Chebyshev $\max\lvert x_i - y_i\rvert$
Cosine distance	$1 - \frac{\mathbf x^\top\mathbf y}{\lVert\mathbf x\rVert\lVert\mathbf y\rVert}$	text, embeddings (direction matters, not length)
Hamming	number of differing positions	categorical/binary features

Choosing k

$k$	Boundary	Bias	Variance
1	very jagged, follows noise	low	high
moderate	smoother	moderate	moderate
$n$	constant (majority class everywhere)	high	low

Choose $k$ by cross-validation; a common heuristic starting point is $k \approx \sqrt n$ . Use odd $k$ for binary problems.

Distance-weighted voting gives closer neighbours more say (weights $1/d$ or $1/d^2$ ), reducing sensitivity to $k$ .

Cost and speed-ups

Training: $O(1)$ (store the data) — but memory $O(nd)$ .
Prediction: $O(nd)$ distances plus selecting the $k$ smallest.
Speed-ups: k-d trees and ball trees (effective in low dimensions), locality-sensitive hashing and graph-based approximate nearest neighbour search (high dimensions, used in vector databases).

The curse of dimensionality

In high dimensions, data becomes sparse and distances concentrate — the nearest and farthest points are almost equally distant, so neighbourhoods are no longer "local". To keep the same density of samples, the data needed grows exponentially with $d$ . Mitigate with PCA, feature selection or learned embeddings.

A theoretical guarantee

As $n \to \infty$ , the error rate of 1-NN is at most twice the Bayes error (the lowest achievable error) — a remarkable result for such a simple method (Cover and Hart, 1967). With $k \to \infty$ and $k/n \to 0$ , k-NN converges to the Bayes classifier itself.

The algorithm

Distance metrics

Choosing k

Cost and speed-ups

The curse of dimensionality

A theoretical guarantee

Quick revision

Practice questions