k-Nearest Neighbors

The k-nearest-neighbour rule (k-NN) predicts the label of a new example from the $k$ stored training examples that are most similar to it: the most common class among them for classification, their average target for regression. It has no training step beyond storing the data, makes no assumption about the form of the decision boundary, and in the limit of infinite data the error of its one-neighbour version is at most twice the best possible. In computer vision it is the classifier behind systems that recognize an image by finding similar images: image retrieval, face identification against a gallery, the evaluation of learned embeddings, and nonparametric scene parsing that copies labels from similar annotated photographs. It is also called the nearest-neighbour classifier (for $k = 1$), a memory-based or instance-based method, or an exemplar-based model (Hastie, Tibshirani & Friedman, 2009, §13.3; Murphy, 2022, §16).

Its two design choices are the number of neighbours $k$ and the distance that decides which examples count as near. Finding the neighbours quickly in a large collection is the separate problem of approximate nearest neighbor search, and learning the distance from labelled pairs is metric learning; this article covers the rule itself.

Problem

Supervised learning asks for a function from inputs to labels that does well on new inputs (see machine learning). Parametric models, such as logistic regression or a neural network, choose a fixed family of functions and fit its parameters; the training data can then be discarded. k-NN takes the opposite route. It assumes only that examples that are close in the chosen distance tend to share a label, or at least have similar class probabilities, the heuristic that Cover and Hart (1967) start from when nothing is known about the underlying distribution beyond the samples, and lets the training set itself be the model. Its number of effective parameters grows with the data: Hastie and colleagues (§2.3.2) argue that k-NN has about $n/k$ of them, one mean per neighbourhood if the neighbourhoods did not overlap.

Inputs and Outputs

• Training data: $n$ examples stored as a data matrix $X \in \mathbb{R}^{n \times d}$, one example per row (as scikit-learn stores it), with labels $y_i \in \{1, \dots, C\}$ for classification or real targets $y_i$ for regression. In vision a row is a vector of pixel values, a hand-designed descriptor or a learned embedding of an image or patch.
• Hyperparameters: the number of neighbours $k$, the distance $d(\mathbf{x}, \mathbf{x}')$, the voting weights, and any preprocessing such as feature scaling.
• Query: a new vector $\mathbf{x}$ in the same space.
• Output: a class label, or a vector of class proportions among the neighbours that serves as a rough estimate of $P(y = c \mid \mathbf{x})$; for regression, a real value.

Intuition

To label an unknown image patch, look at the labelled patches that resemble it most and go with the majority. With one neighbour the answer copies whatever the single closest patch says, including its noise and any labelling mistake. With many neighbours the vote averages those accidents away, but the neighbours are drawn from farther afield and some of them come from regions where the answer is different. The best $k$ balances the two and depends on how much data there is: with more examples, more of them lie close to any query, so a larger $k$ can be used without reaching far.

The rule is only as good as its notion of closeness. Two photographs of the same striped texture shifted by half a stripe differ in nearly every pixel and are far apart in raw-pixel distance, while a description of the patch that ignores position puts them together. The first example below shows this gap; choosing a representation in which the distance reflects the task is most of the work of using k-NN on images.

Algorithm

k-NN classification

1. Store the training set $\{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$.
2. For a query $\mathbf{x}$, compute $d(\mathbf{x}, \mathbf{x}_i)$ for every training example.
3. Take the index set $N_k(\mathbf{x})$ of the $k$ smallest distances.
4. Return the class with the most votes among $\{y_i : i \in N_k(\mathbf{x})\}$, breaking ties by a fixed rule.

k-NN regression replaces step 4 by the average $\frac{1}{k}\sum_{i \in N_k(\mathbf{x})} y_i$ (Hastie et al., §2.3.2, eq. 2.8).

Ties arise in two places. Two neighbours can be at exactly the same distance with different labels; Cover and Hart (footnote 1) suggest taking the most popular class among the tied points, and scikit-learn’s documentation warns that its result then depends on the order of the training data. Two classes can also receive the same number of votes. Hastie and colleagues (§13.3) and Bishop (2006, §2.5.2) break vote ties at random. scikit-learn 1.7.2, as its source and a small test show, returns the first of the tied classes in sorted label order, whatever their distances, with every search algorithm. With two classes an odd $k$ avoids vote ties altogether (our observation).

Weighted voting. Giving nearer neighbours more say reduces the dependence on $k$. scikit-learn’s weights="distance" weights each neighbour by the inverse of its distance; training points at distance zero then take the whole vote. Any decreasing function of distance can be used, which turns the vote into a kernel-weighted average (see Variants).

Mathematical Formulation

The vote as a density estimate

Bishop (§2.5.2) derives the rule from nonparametric density estimation. Grow a ball around $\mathbf{x}$ until it holds exactly $K$ training points, and let its volume be $V$ and the number of points from class $c$ inside it be $K_c$. With $n_c$ training points in class $c$, the local estimates of the class-conditional density, the overall density and the prior are

$$p(\mathbf{x} \mid c) = \frac{K_c}{n_c V}, \qquad p(\mathbf{x}) = \frac{K}{nV}, \qquad P(c) = \frac{n_c}{n},$$

and Bayes’ rule gives the posterior estimate

$$\hat{P}(c \mid \mathbf{x}) = \frac{K_c}{K}.$$

Assigning $\mathbf{x}$ to the class with the largest estimated posterior, the decision that minimizes the probability of error, is exactly the majority vote. Murphy (§16.1, eq. 16.1) writes the same vote fraction as the predictive distribution $p(y = c \mid \mathbf{x}, \mathcal{D})$. Kernel density estimation does the converse: it fixes the size of the neighbourhood, the kernel width, and counts the points in it, while k-NN fixes the count and lets the volume adapt, wide where data are sparse and narrow where they are dense (Bishop, §2.5.2).

Geometry of the decision regions

With $k = 1$ each training point owns the cell of space that is closer to it than to any other point, a Voronoi tessellation, and every query in a cell receives that point’s label (Hastie et al., §2.3.2; Murphy, §16.1.1). Under the Euclidean distance the boundary between two classes is made of pieces of the perpendicular bisectors of pairs of points from different classes (Bishop, Figure 2.27). The training error of 1-NN is therefore zero, which says nothing about its error on new data; larger $k$ gives smoother boundaries and a training error that grows with $k$ (Hastie et al., §2.3.2).

Bias and variance in the choice of k

For k-NN regression with $y = f(\mathbf{x}) + \varepsilon$, noise variance $\sigma_\varepsilon^2$, and the training inputs held fixed, the expected squared error at a query $\mathbf{x}_0$ splits as (Hastie et al., §7.3, eq. 7.10)

$$\operatorname{Err}(\mathbf{x}_0) = \sigma_\varepsilon^2 + \Big[f(\mathbf{x}_0) - \frac{1}{k}\sum_{\ell=1}^{k} f(\mathbf{x}_{(\ell)})\Big]^2 + \frac{\sigma_\varepsilon^2}{k},$$

where $\mathbf{x}_{(\ell)}$ is the $\ell$-th nearest training input. The variance term falls as $1/k$; the squared bias, the gap between the true value and the average of $f$ over the neighbours, typically grows with $k$ as the neighbours spread out. $k$ is inversely related to model complexity. This is the k-NN case of the bias–variance decomposition summarized in machine learning. The same trade-off governs classification, which is why the test error as a function of $k$ is usually U-shaped and why $k$ is chosen on held-out data (Hastie et al., §13.3, Figure 13.4; Murphy, §16.1.1).

The Cover–Hart bound

The best possible classifier, the Bayes classifier, assigns $\mathbf{x}$ to its most probable class and has the smallest achievable error $R^*$, the Bayes error (see probability and statistics for Bayes’ rule). Let $\eta_c(\mathbf{x}) = P(y = c \mid \mathbf{x})$, so that the conditional Bayes risk is $r^*(\mathbf{x}) = 1 - \max_c \eta_c(\mathbf{x})$ and $R^* = \mathbb{E}[r^*(\mathbf{x})]$.

As the training set grows, the nearest neighbour of $\mathbf{x}$ converges to $\mathbf{x}$ with probability one, in any separable metric space (Cover & Hart, 1967). In the limit the query’s label and its neighbour’s label are therefore independent draws from the same posterior, and 1-NN errs when they differ (Hastie et al., §13.3, eq. 13.3):

$$r(\mathbf{x}) = \sum_{i \ne j} \eta_i(\mathbf{x})\, \eta_j(\mathbf{x}) = 1 - \sum_{c=1}^{C} \eta_c(\mathbf{x})^2 .$$

The large-sample 1-NN error is $R = \mathbb{E}[r(\mathbf{x})]$. Cover and Hart proved that for $C$ classes ($M$ in their notation), whenever $\mathbf{x}$ is, with probability one, either a continuity point of the class densities or a point of positive probability,

$$R^* \;\le\; R \;\le\; R^*\Big(2 - \frac{C}{C - 1}\, R^*\Big),$$

their eq. (29), and that these bounds are as tight as possible. For two classes the upper bound is $2R^*(1 - R^*)$. Since the right-hand side never exceeds $2R^*$, the large-sample 1-NN error is at most twice the Bayes error, whatever the distribution: in Cover and Hart’s words, “half the classification information in an infinite sample set” is contained in the nearest neighbour. Hastie and colleagues (§13.3, eq. 13.5) give the same bound; Murphy (§16.1) states the factor of two.

The bound is asymptotic. Hastie and colleagues (§13.3) note that it assumes the bias of the nearest-neighbour rule has vanished, while in real problems the bias can be substantial, and Murphy (§16.1) warns that the convergence can be slow for the reasons given under the curse of dimensionality below. It also concerns $k = 1$ only. Letting $k$ grow removes the factor of two: Fix and Hodges had established the consistency of the $k_n$-NN rule, its convergence to the Bayes rule’s error, for sequences with $k_n \to \infty$ and $k_n/n \to 0$ (as Cover and Hart summarize it).

The bound can also be read backward. Hastie and colleagues (§13.3) point out that if 1-NN has 10% error on a large data set, then, asymptotically, the Bayes error is at least 5%.

Parameters

• $k$. At the extreme $k = n$ the rule predicts the majority class everywhere. The training error cannot choose $k$, since it always favours $k = 1$ (Hastie et al., §2.3.2). Choose it by cross-validation or on a validation set. Because k-NN has no training step, leave-one-out cross-validation costs no more than one pass over the data: classify each training example by its neighbours among the others (our observation; the first example does this). Hastie and colleagues (§13.3.1) found that the best $k$ is strongly problem-dependent: in one simulation 25 neighbours beat one by 70%, in another one neighbour was best by 18%.
• Distance. Euclidean by default; Manhattan, cosine, Hamming, χ² and the others in similarity and distance measures suit other representations, and a Mahalanobis distance $\sqrt{(\mathbf{x} - \mathbf{x}')^\top M (\mathbf{x} - \mathbf{x}')}$ with $M$ learned from labels is the subject of metric learning (Murphy, §16.1, eq. 16.2). Cover and Hart (§V) note that their large-sample bounds do not depend on the metric; the error with a finite training set does, as the examples below show.
• Feature scaling. A distance adds up coordinates, so a feature measured in larger units dominates it. Hastie and colleagues (§13.3) typically standardize each feature to mean zero and variance one first, since features may be measured in different units. Standardization is not automatically right either: it gives equal weight to every feature, including uninformative ones, as the second example shows.
• Representation. For images the largest decision is what vector to compare: raw pixels, a descriptor such as SIFT or HOG, a bag of visual words histogram, or a learned embedding. Reducing the dimension with principal component analysis before the search is common.

In scikit-learn 1.7.2, KNeighborsClassifier defaults to n_neighbors=5, weights="uniform", algorithm="auto", leaf_size=30, metric="minkowski" and p=2, the Euclidean distance; KNeighborsRegressor has the same defaults. With algorithm="auto" and dense data, the 1.7.2 source uses brute-force search when the data have more than 15 features, when $k$ is at least half the number of training points (rounded down), or when the distances are precomputed, and otherwise a k-d tree or ball tree, depending on the metric.

Complexity

Training stores the data: $O(nd)$ memory and no computation, unless an index is built.

Prediction by brute force computes $n$ distances in $d$ dimensions, $O(nd)$ operations per query (Hastie et al., §13.5), plus $O(n)$ to select the $k$ smallest with a partial sort. For $q$ queries the squared Euclidean distances form one matrix product, $\lVert \mathbf{a} - \mathbf{b} \rVert^2 = \lVert \mathbf{a} \rVert^2 - 2\mathbf{a}^\top\mathbf{b} + \lVert \mathbf{b} \rVert^2$, which is how the code below computes them. The cost is the price of having no training. Bishop (§2.5.2) notes that tree-based search structures can find approximate neighbours without an exhaustive search; for high-dimensional image descriptors that is the territory of approximate nearest neighbor search, whose indexes trade a small loss of recall for orders of magnitude in speed.

Reducing storage. Editing and condensing keep a subset of the training set that suffices for the nearest-neighbour decisions (Hastie et al., §13.5). Multi-editing, which Hastie and colleagues attribute to Devijver and Kittler (1982), repeatedly splits the data, classifies one part by the other, and deletes the misclassified points, leaving homogeneous clusters. Hart’s (1968) condensed nearest-neighbour rule goes further and tries to keep only the important exterior points of the class clusters: starting from one randomly chosen example, it processes the others one at a time and adds an example to the stored set only if the current stored set misclassifies it. Hastie and colleagues add that they have little practical experience with such methods and know of no systematic comparison of them.

Implementation

The examples use synthetic image patches with exactly known ground truth. The outputs came from NumPy 2.3.5, SciPy 1.16.3 and scikit-learn 1.7.2.

Classification and regression from raw pixels and from features

The first block renders $16 \times 16$ grayscale patches of a sinusoidal grating in one of four orientations (0°, 45°, 90° and 135°, each jittered by up to 15°), with random frequency, phase, contrast and mean brightness, plus Gaussian pixel noise of standard deviation 0.45. Each patch is classified by its orientation in two representations: the 256 raw pixel values, and a 32-number feature, the patch’s power spectrum pooled into 8 orientation and 4 frequency bins and normalized to sum 1. Apart from the noise, the feature ignores phase, so a shifted grating has the same feature, and it ignores contrast and brightness. For 5 random datasets of 400 training and 2,000 test patches, the block prints the test error for $k$ from 1 to 201, the leave-one-out error on the training set, and the $k$ that leave-one-out picks. It then checks the NumPy implementation against scikit-learn and uses k-NN regression to predict each patch’s grating frequency from the same feature.

import numpy as np

S = 16                                            # patch size (pixels)
yy, xx = np.mgrid[0:S, 0:S].astype(float)

def gratings(n, rng, noise=0.45):
    """n 16x16 grayscale patches of a sinusoidal grating, one row per patch. Class c
    (0-3) has orientation 45c degrees, jittered by up to 15 degrees; frequency
    (0.08-0.20 cycles/pixel), phase, contrast and mean brightness are random."""
    y = rng.integers(0, 4, n)
    theta = np.deg2rad(45 * y + rng.uniform(-15, 15, n))
    freq = rng.uniform(0.08, 0.20, n)
    phase = rng.uniform(0, 2 * np.pi, n)
    contrast, mean = rng.uniform(0.15, 0.4, n), rng.uniform(0.3, 0.7, n)
    u = np.cos(theta)[:, None, None] * xx + np.sin(theta)[:, None, None] * yy
    img = mean[:, None, None] + contrast[:, None, None] * np.sin(
        2 * np.pi * freq[:, None, None] * u + phase[:, None, None])
    img += rng.normal(0, noise, img.shape)
    return img.reshape(n, -1), y, freq

fy, fx = np.meshgrid(np.fft.fftfreq(S), np.fft.fftfreq(S), indexing="ij")
ori_bin = (np.mod(np.arctan2(fy, fx) + np.pi / 16, np.pi) / np.pi * 8).astype(int) % 8
rad_bin = np.digitize(np.hypot(fx, fy), [0.05, 0.14, 0.22, 0.36])   # 0 = DC and lowest
keep = rad_bin >= 1

def spectrum_features(X):
    """Power spectrum of each mean-removed patch pooled into 8 orientation x 4 frequency
    bins and normalized to sum 1: invariant to phase (position), contrast and brightness."""
    P = np.abs(np.fft.fft2((X - X.mean(1, keepdims=True)).reshape(-1, S, S))) ** 2
    idx = (ori_bin * 4 + rad_bin - 1)[keep]
    F = np.stack([np.bincount(idx, weights=p[keep], minlength=32) for p in P])
    return F / F.sum(1, keepdims=True)

def sq_dists(A, B):
    """Squared Euclidean distances between the rows of A and the rows of B."""
    return (A**2).sum(1)[:, None] - 2 * A @ B.T + (B**2).sum(1)[None, :]

def knn_predict(D, y_train, k, n_classes=4):
    """Majority vote among the k nearest training rows (D: query-by-train squared
    distances). Ties go to the smallest class label, as np.argmax returns the first."""
    nn = np.argsort(D, axis=1, kind="stable")[:, :k]
    votes = np.stack([(y_train[nn] == c).sum(1) for c in range(n_classes)], axis=1)
    return votes.argmax(1)

def loo_errors(D, y, ks):
    """Leave-one-out error for each k: each training patch is classified by the others."""
    D = D.copy(); np.fill_diagonal(D, np.inf)
    return np.array([np.mean(knn_predict(D, y, k) != y) for k in ks])

ks = [1, 3, 5, 9, 15, 25, 51, 101, 201]
res = {"raw pixels": [], "spectrum": []}
for seed in range(5):
    rng = np.random.default_rng(seed)
    X_tr, y_tr, _ = gratings(400, rng)
    X_te, y_te, _ = gratings(2000, rng)
    for name, f in (("raw pixels", lambda X: X), ("spectrum", spectrum_features)):
        A, B = f(X_tr), f(X_te)
        D_te = sq_dists(B, A)
        test = np.array([np.mean(knn_predict(D_te, y_tr, k) != y_te) for k in ks])
        loo = loo_errors(sq_dists(A, A), y_tr, ks)
        best = int(np.argmin(loo))
        res[name].append((test, loo, ks[best], test[best]))

print("k:                 " + "".join(f"{k:>7}" for k in ks))
for name, r in res.items():
    test = np.array([t for t, _, _, _ in r]); loo = np.array([l for _, l, _, _ in r])
    print(f"{name:<11} test   " + "".join(f"{e:7.3f}" for e in test.mean(0)))
    print(f"{'':<11} LOO    " + "".join(f"{e:7.3f}" for e in loo.mean(0)))
    print(f"{'':<11} k chosen by LOO per seed: {[c for _, _, c, _ in r]}, its test error "
          f"{min(e for *_, e in r):.3f} to {max(e for *_, e in r):.3f}")

# Cross-check against scikit-learn 1.7.2 on seed 0, then k-NN regression:
# predict each test patch's grating frequency (cycles/pixel) from its spectrum features.
import sklearn
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
rng = np.random.default_rng(0)
X_tr, y_tr, f_tr = gratings(400, rng)
X_te, y_te, f_te = gratings(2000, rng)
A, B = spectrum_features(X_tr), spectrum_features(X_te)
D_te = sq_dists(B, A)
same = all(np.array_equal(knn_predict(D_te, y_tr, k),
                          KNeighborsClassifier(n_neighbors=k).fit(A, y_tr).predict(B)) for k in ks)
print(f"\nscikit-learn {sklearn.__version__}: same class predictions for every k: {same}")
print("frequency regression, RMSE (cycles/pixel); predicting the training mean gives "
      f"{np.sqrt(np.mean((f_te - f_tr.mean())**2)):.4f}")
nn = np.argsort(D_te, axis=1)
for k in (1, 5, 15, 51):
    ours = f_tr[nn[:, :k]].mean(1)                     # average of the k neighbours' targets
    sk = KNeighborsRegressor(n_neighbors=k).fit(A, f_tr).predict(B)
    print(f"  k = {k:>2}: RMSE {np.sqrt(np.mean((ours - f_te)**2)):.4f}, "
          f"max |ours - scikit-learn| = {np.abs(ours - sk).max():.1e}")

Output:

k:                       1      3      5      9     15     25     51    101    201
raw pixels  test     0.494  0.475  0.446  0.432  0.426  0.436  0.484  0.601  0.739
            LOO      0.499  0.493  0.458  0.424  0.451  0.454  0.499  0.611  0.722
            k chosen by LOO per seed: [9, 25, 9, 9, 9], its test error 0.417 to 0.445
spectrum    test     0.144  0.124  0.115  0.106  0.102  0.097  0.100  0.112  0.165
            LOO      0.137  0.133  0.111  0.102  0.088  0.086  0.100  0.112  0.173
            k chosen by LOO per seed: [25, 25, 9, 15, 15], its test error 0.088 to 0.107

scikit-learn 1.7.2: same class predictions for every k: True
frequency regression, RMSE (cycles/pixel); predicting the training mean gives 0.0346
  k =  1: RMSE 0.0282, max |ours - scikit-learn| = 0.0e+00
  k =  5: RMSE 0.0214, max |ours - scikit-learn| = 0.0e+00
  k = 15: RMSE 0.0214, max |ours - scikit-learn| = 0.0e+00
  k = 51: RMSE 0.0248, max |ours - scikit-learn| = 0.0e+00

Both representations show the U-shaped error curve of the bias–variance trade-off, with the minimum at a few dozen neighbours or fewer. At $k = 201$, half the training set, the raw-pixel classifier is close to chance, an error of 0.75 for four balanced classes, while the spectrum classifier, whose same-class neighbours are packed more tightly, has lost only part of its accuracy. Leave-one-out on the 400 training patches traces the test curve closely enough to land near its minimum on every seed, at no extra cost. The representation matters far more than $k$: the best raw-pixel classifier errs on more than four patches in ten, the spectrum feature on about one in ten. In our reading, raw pixels fail because two gratings of the same orientation with different phases are far apart, even anti-correlated, in pixel space, so the nearest raw neighbours share position and brightness more than orientation; the spectrum discards exactly those differences. The NumPy vote, including its tie rule, matches scikit-learn’s predictions for every $k$, and the regression averages agree exactly. Regression shows the same trade-off: one neighbour lowers the error of a constant prediction by about a fifth, five to fifteen neighbours by about 40%, and 51 neighbours give some of that back by averaging over gratings of different frequency.

Feature scaling

The second block, which continues from the first, appends two features that carry no class information to the 32 spectrum features: the patch’s mean brightness and its standard deviation, both in 8-bit grey levels (0–255). It compares four versions at $k = 15$ over the same five seeds: the spectrum alone, the spectrum with the two extra features in their natural units, the same 34 features standardized with the training set’s means and standard deviations, and the spectrum alone, standardized.

def standardize(A, B):
    """Scale every feature to mean 0 and standard deviation 1 using training statistics."""
    mu, sd = A.mean(0), A.std(0)
    return (A - mu) / sd, (B - mu) / sd

k = 15
rows = {"spectrum only": [], "spectrum + 8-bit brightness, contrast": [],
        "  same, standardized": [], "spectrum only, standardized": []}
for seed in range(5):
    rng = np.random.default_rng(seed)
    X_tr, y_tr, _ = gratings(400, rng)
    X_te, y_te, _ = gratings(2000, rng)
    F_tr, F_te = spectrum_features(X_tr), spectrum_features(X_te)
    # two features that carry no class information, in 8-bit grey levels
    N_tr = 255 * np.c_[X_tr.mean(1), X_tr.std(1)]
    N_te = 255 * np.c_[X_te.mean(1), X_te.std(1)]
    sets = [(F_tr, F_te), (np.c_[F_tr, N_tr], np.c_[F_te, N_te]),
            standardize(np.c_[F_tr, N_tr], np.c_[F_te, N_te]), standardize(F_tr, F_te)]
    for (name, r), (A, B) in zip(rows.items(), sets):
        r.append(np.mean(knn_predict(sq_dists(B, A), y_tr, k) != y_te))
print(f"test error at k = {k}, 5 seeds")
for name, r in rows.items():
    print(f"  {name:<40} {np.mean(r):.3f}  ({min(r):.3f} to {max(r):.3f})")

Output:

test error at k = 15, 5 seeds
  spectrum only                            0.102  (0.092 to 0.111)
  spectrum + 8-bit brightness, contrast    0.750  (0.734 to 0.759)
    same, standardized                     0.194  (0.168 to 0.215)
  spectrum only, standardized              0.181  (0.159 to 0.208)

The spectrum features each lie between 0 and 1, while brightness in grey levels varies by tens of units between patches, so the two irrelevant features decide every distance and the classifier falls to chance, an error of 0.75 for four balanced classes. Standardizing restores most of the accuracy, as Hastie and colleagues’ advice predicts. It does not restore all of it, and standardizing the spectrum alone hurts by about the same amount. In our reading, the features with little energy, the frequency bins far from any grating, carry mostly noise, and standardizing raises their weight to that of the informative bins. Scaling decides how much each feature counts; it cannot tell which features matter. That is the job of the representation, of feature selection, or of a learned metric.

Distances in high dimensions

The curse of dimensionality (a phrase Hastie and colleagues, §2.5, trace to Bellman, 1961) is the main statistical weakness of k-NN (Murphy, §16.1.2). Hastie and colleagues (§2.5) give several forms of it for points spread uniformly in a $p$-dimensional unit cube. A cube-shaped neighbourhood that captures a fraction $r$ of the data has edge length $r^{1/p}$, so in ten dimensions capturing 1% or 10% of the data takes 63% or 80% of the range of every coordinate: such neighbourhoods are no longer local. For 500 points uniform in a ten-dimensional ball, the median distance from the centre to the nearest point is about 0.52, more than halfway to the boundary. And the sample size needed to keep the same sampling density grows exponentially with the dimension.

A related effect concerns the distances themselves. Beyer, Goldstein, Ramakrishnan and Shaft (technical report version, 1998, Theorem 1) proved that if the relative spread of the distance from a query to a data point vanishes as the dimension $m$ grows, formally $\operatorname{Var}\big(d_m^p / \mathbb{E}[d_m^p]\big) \to 0$ for some $p > 0$, then for every $\varepsilon > 0$ the probability that the farthest point is within $(1 + \varepsilon)$ times the distance of the nearest tends to one. Under such conditions, which they show are much broader than independent and identically distributed coordinates, “nearest” stops meaning much; their experiments on real and synthetic data showed that the effect can occur with as few as 10–15 dimensions. They stress that it does not occur for every workload. The embeddings article describes this distance concentration and the related emergence of hubs for learned embeddings.

The third block, which continues from the first, measures the relative contrast $(d_{\max} - d_{\min})/d_{\min}$ between 100 query patches and a database of 1,000 patches as the patch size grows from $4 \times 4$ to $64 \times 64$ pixels ($d = 16$ to $4{,}096$), for three kinds of patch: independent uniform noise, noise-free gratings drawn as above but sampled on a finer grid over the same area, so that $d$ grows while each patch is still described by five parameters, and the same gratings with pixel noise of standard deviation 0.45.

def grating_patches(n, s, rng, noise):
    """Gratings drawn as in gratings() over the same 16x16-pixel area, but sampled on
    an s x s grid, so d = s*s grows while the pattern's 5 parameters stay the same."""
    y_, x_ = np.mgrid[0:s, 0:s] * (16 / s)
    theta = np.deg2rad(45 * rng.integers(0, 4, n) + rng.uniform(-15, 15, n))[:, None, None]
    freq = rng.uniform(0.08, 0.20, n)[:, None, None]
    phase = rng.uniform(0, 2 * np.pi, n)[:, None, None]
    contrast, mean = (rng.uniform(a, b, n)[:, None, None] for a, b in ((0.15, 0.4), (0.3, 0.7)))
    img = mean + contrast * np.sin(2 * np.pi * freq * (np.cos(theta) * x_ + np.sin(theta) * y_) + phase)
    return (img + rng.normal(0, noise, img.shape)).reshape(n, -1)

def relative_contrast(db, queries):
    """Mean over queries of (farthest - nearest) / nearest Euclidean distance."""
    d = np.sqrt(np.maximum(sq_dists(queries, db), 0))
    return np.mean((d.max(1) - d.min(1)) / d.min(1))

rng = np.random.default_rng(0)
print("patch     d    uniform noise   gratings, no noise   gratings + noise 0.45")
for s in (4, 8, 16, 32, 64):
    sets = [rng.uniform(0, 1, (1100, s * s)),
            grating_patches(1100, s, rng, 0.0), grating_patches(1100, s, rng, 0.45)]
    rc = [relative_contrast(X[:1000], X[1000:]) for X in sets]
    print(f"{s:>2}x{s:<2} {s*s:>6}{rc[0]:>15.3f}{rc[1]:>21.3f}{rc[2]:>24.3f}")

Output:

patch     d    uniform noise   gratings, no noise   gratings + noise 0.45
 4x4      16          1.751                5.583                   1.967
 8x8      64          0.574                3.787                   0.741
16x16    256          0.251                4.039                   0.398
32x32   1024          0.118                4.219                   0.299
64x64   4096          0.057                4.081                   0.277

For independent noise pixels the contrast roughly halves each time $d$ quadruples, as a $1/\sqrt{d}$ law would give: at 4,096 dimensions the farthest of 1,000 patches is only 6% farther than the nearest. The noise-free gratings keep a contrast near 4 from $8 \times 8$ on, because adding pixels samples the same five-parameter pattern more finely without adding directions of variation; what matters is the intrinsic dimension of the data, not the length of the vector, the point the approximate-search article makes for real descriptors. The noisy gratings fall at first and then level off near 0.3. By our reasoning, independent noise adds about the same amount, $2\sigma^2$ per pixel, to every squared distance, while the differences between gratings also grow in proportion to the number of pixels, so the contrast settles at a value set by the signal-to-noise ratio rather than going to zero. If natural images, like the gratings, lie near sets of much lower dimension than their pixel count, the manifold hypothesis summarized in the machine learning article, nearest neighbours in a good representation can stay meaningful; in this example, pixel noise is what erodes them.

The Cover–Hart bound, checked

The fourth block, which is self-contained, builds a problem whose Bayes error is known exactly. Two materials are imaged as $4 \times 4$ grey patches: every pixel is the material’s brightness, 0.45 or 0.55, plus independent Gaussian noise of standard deviation 0.2, and the two classes are equally likely. The patch mean then follows a Gaussian with standard deviation $0.2/4 = 0.05$ around the material’s brightness, and, by our reasoning, it carries all the information the 16 pixels hold about the class (it is a sufficient statistic), so the Bayes error is the same for the 16 pixels and for their mean: $R^* = \Phi(-0.05/0.05) = \Phi(-1)$. The block computes $R^*$, the asymptotic 1-NN error $\mathbb{E}[2\eta(1 - \eta)]$ by numerical integration, and the bound $2R^*(1 - R^*)$, then measures the test error of 1-NN on the raw 16 pixels, 1-NN on the patch mean, and k-NN on the patch mean with $k$ near $\sqrt{n}$, for training sets of 100 to 100,000 patches, on 4,000 test patches and 3 seeds each. It takes about 20 seconds.

import numpy as np
from scipy.stats import norm
from scipy.integrate import quad

# Two materials photographed as 4x4 grey patches: each pixel is the material's
# brightness (0.45 or 0.55) plus independent Gaussian noise of standard deviation 0.2.
MU, SIGMA, PIX = np.array([0.45, 0.55]), 0.2, 16
s = SIGMA / np.sqrt(PIX)          # the patch mean is N(MU[c], s^2): a sufficient statistic

def patches(n, rng):
    y = rng.integers(0, 2, n)
    return MU[y][:, None] + rng.normal(0, SIGMA, (n, PIX)), y

# Exact quantities from the known densities (equal priors).
bayes = norm.cdf(-(MU[1] - MU[0]) / (2 * s))                     # R*
def eta(m):                                                      # P(class 1 | patch mean m)
    a, b = norm.pdf(m, MU[0], s), norm.pdf(m, MU[1], s)
    return b / (a + b)
density = lambda m: 0.5 * (norm.pdf(m, MU[0], s) + norm.pdf(m, MU[1], s))
r_inf = quad(lambda m: 2 * eta(m) * (1 - eta(m)) * density(m), -1, 2)[0]   # E[2 eta (1 - eta)]
print(f"Bayes error R* = {bayes:.4f}; asymptotic 1-NN error E[2 eta(1 - eta)] = {r_inf:.4f}; "
      f"Cover-Hart bound 2R*(1 - R*) = {2 * bayes * (1 - bayes):.4f}")

def nn_labels(A, B, y, k):
    """Labels predicted by a k-NN majority vote (k odd, two classes), brute force in chunks."""
    out = []
    for i in range(0, len(B), 250):
        Q = B[i:i + 250]
        D = (Q**2).sum(1)[:, None] - 2 * Q @ A.T + (A**2).sum(1)[None, :]
        nn = np.argpartition(D, k - 1, axis=1)[:, :k] if k > 1 else D.argmin(1)[:, None]
        out.append((y[nn].mean(1) > 0.5).astype(int))
    return np.concatenate(out)

print("     n   1-NN, 16 pixels   1-NN, patch mean   k-NN, patch mean (k ~ sqrt n)")
for n in (100, 1000, 10000, 100000):
    k = int(np.sqrt(n)) | 1                                      # an odd k near sqrt(n)
    errs = np.zeros((3, 3))
    for seed in range(3):
        rng = np.random.default_rng(seed)
        X, y = patches(n, rng)
        Xt, yt = patches(4000, rng)
        m, mt = X.mean(1, keepdims=True), Xt.mean(1, keepdims=True)
        errs[seed] = [np.mean(nn_labels(X, Xt, y, 1) != yt), np.mean(nn_labels(m, mt, y, 1) != yt),
                      np.mean(nn_labels(m, mt, y, k) != yt)]
    print(f"{n:>6}" + "".join(f"   {e.mean():.3f} ({e.min():.3f}-{e.max():.3f})" for e in errs.T)
          + f"  k = {k}")

Output:

Bayes error R* = 0.1587; asymptotic 1-NN error E[2 eta(1 - eta)] = 0.2248; Cover-Hart bound 2R*(1 - R*) = 0.2670
     n   1-NN, 16 pixels   1-NN, patch mean   k-NN, patch mean (k ~ sqrt n)
   100   0.306 (0.283-0.327)   0.237 (0.220-0.253)   0.170 (0.150-0.191)  k = 11
  1000   0.293 (0.287-0.303)   0.228 (0.220-0.233)   0.161 (0.157-0.166)  k = 31
 10000   0.265 (0.262-0.267)   0.224 (0.221-0.225)   0.158 (0.151-0.163)  k = 101
100000   0.253 (0.243-0.260)   0.225 (0.222-0.229)   0.163 (0.159-0.169)  k = 317

The asymptotic 1-NN error, 0.225, lies between $R^*$ and the Cover–Hart bound. In one dimension 1-NN reaches it by about 1,000 training patches and stays there: more data no longer helps, because the nearest neighbour is already close and its label is still an independent draw from the posterior. The same 1-NN rule on the 16 raw pixels sees the same information but is far from its limit: its error exceeds the asymptotic bound at 100 and 1,000 patches and is still above 0.225 at 100,000. The bound says nothing about finite samples, and in 16 dimensions the neighbour is far from the query long after it would be close in one, the curse of dimensionality in miniature. Letting $k$ grow with $n$ removes the factor between 1-NN and Bayes: with $k$ near $\sqrt{n}$, so that $k \to \infty$ and $k/n \to 0$ as in Fix and Hodges’ consistency condition, the error falls to within about half a point of $R^*$ from 1,000 patches on, inside the seed-to-seed spread of a 4,000-patch test set.

Properties and Behavior

• Local and adaptive. The decision boundary can take any shape, and it adapts to local density, since the neighbourhood is wide where data are sparse. Hastie and colleagues (§13.3) note that k-NN often succeeds where each class has many prototypes and the boundary is very irregular.
• Probability estimates are coarse. The vote fraction takes only the values $0, 1/k, \dots, 1$ and is noisy for small $k$.
• Incremental. Adding a labelled example, or a new class, means storing it; nothing is retrained. Murphy (§16.1.4) points to this as what makes nearest-neighbour classifiers suited to open-set problems such as face recognition, where new identities keep being enrolled and a query too far from every stored example can be declared novel.

Limitations

• Cost at test time. Every prediction touches the whole training set, or an index over it, and the whole training set must be kept; Hastie and colleagues (§13.5) call this computational load one drawback of nearest-neighbour rules in general.
• Dependence on the representation. Every coordinate counts under the chosen metric, so irrelevant features, unscaled units and pixel noise distort the neighbours, and in high dimensions neighbourhoods stop being local; raw pixel vectors make poor inputs unless the distance is adapted, learned or applied to a better representation.
• Class imbalance. A majority vote favours the frequent classes in regions where several overlap, since they supply more of the neighbours (our observation, from the $K_c/K$ posterior estimate, which includes the class prior).

Variants

• Kernel density classification replaces the $k$-neighbour ball by a fixed-width kernel around the query: it estimates each class density with a Parzen (kernel density) estimate and applies Bayes’ rule (Hastie et al., §6.6.2). k-NN is the variant whose window adapts to the local density.
• Invariant distances. Simard and colleagues’ tangent distance, which Hastie and colleagues (§13.3.3) describe, compares two handwritten digits by the shortest distance between the sets of their transformed versions (rotations, translations, scalings, shear and changes of stroke thickness), each approximated by its tangent plane at the image, building invariance into the metric rather than into the features. On the U.S. Postal Service digits (7,291 training and 2,007 test images), 1-NN with tangent distance had a test error of 0.026, against 0.055 with the Euclidean distance and 0.049 for a carefully constructed neural network (their Table 13.1); nearest neighbours then proved too slow for online use in that application, and neural networks were trained to mimic the classifier.
• Adaptive and learned metrics. Discriminant adaptive nearest neighbours (Hastie and Tibshirani, 1996, as described by Hastie et al., §13.4) adapts the metric at each query so that the neighbourhood stretches out in directions in which the class probabilities change little; Neighbourhood Components Analysis and large-margin nearest neighbour learn a Mahalanobis distance for k-NN directly, as the metric learning article describes, and deep metric learning learns an embedding for it.
• Prototype methods replace the training set by a few representatives per class, for example the centres found by k-means clustering within each class or learning vector quantization (Hastie et al., §13.2).

Use in Computer Vision

Retrieval and identification. Content-based image retrieval ranks a database by distance to a query’s descriptor or embedding, and face identification searches a gallery of enrolled people for the nearest embedding (face recognition), both nearest-neighbour searches at scale. Descriptor feature matching between two views is a 1-NN search per keypoint, often filtered by the ratio of the first to the second neighbour’s distance. A k-NN vote on frozen embeddings is also used to evaluate self-supervised representations, and adds no trained parameters of its own.

Pixel and region classification. Hastie and colleagues (§13.3.2) describe the STATLOG benchmark of classifying the land use of each pixel in a LANDSAT satellite image ($82 \times 100$ pixels, seven classes). A five-nearest-neighbour rule on 36 features per pixel, the pixel and its eight neighbours in each of four spectral bands, reached a test error of about 9.5% and performed best of all the methods in the project, from decision trees and neural networks to linear discriminant analysis, which they take as a sign that the class boundaries in that 36-dimensional space are highly irregular.

Recognition with very large datasets. Torralba, Fergus and Freeman (2008) collected 79,302,017 web images, each downsampled to $32 \times 32$ colour pixels and loosely labelled with one of 75,062 nouns from the WordNet lexical database, and recognized objects and scenes with nearest neighbours instead of trained classifiers. Images were compared by the sum of squared differences between normalized images, or after aligning one to the other by a mirror flip, translation and scaling and then shifting each pixel within a $5 \times 5$ window; to make search feasible they first retrieved 16,000 candidates using the first 19 principal components and then computed exact distances among them. Each neighbour voted for its noun’s branch of the WordNet tree, and the votes were accumulated across semantic levels, so that labelling noise averaged out over many neighbours. The quality of the retrieved neighbours improved markedly as the database grew from $10^5$ to $10^8$ images, though the authors note that the size has to grow on a logarithmic scale to have an effect (their Fig. 6), and for frequent classes such as people they reported recognition comparable to class-specific Viola–Jones style detectors.

Nonparametric scene parsing. Liu, Yuen and Torralba (2011) labelled every pixel of a query photograph by label transfer: retrieve its nearest neighbours in a database of densely annotated images using a global scene descriptor (GIST), align each retrieved image to the query with SIFT flow, a dense correspondence between SIFT descriptor images, warp the neighbours’ annotations onto the query, and combine them in a Markov random field. The authors argue that, unlike learning-based methods, the system needs no new models trained when categories are added. On a LabelMe outdoor database of 2,688 images with 33 categories, their system labelled 76.67% of the annotated pixels of 200 test images correctly, against 51.67% for a trained TextonBoost classifier on the same data with its Markov random field turned off; turning off their own Markov random field and spatial priors for a fair comparison still left their system ahead (their Fig. 12). The approach is a k-NN regression from images to label maps, with the distance replaced by retrieval and dense alignment; see semantic segmentation for the task.

Image-to-class distances. Boiman, Shechtman and Irani (2008) argued that nearest-neighbour image classifiers had been undervalued because of two common practices: quantizing local descriptors into a codebook, as in the bag of visual words, which discards discriminative information, and comparing a query with individual training images, which generalizes poorly for diverse classes. Their naive-Bayes nearest-neighbour (NBNN) classifier computes the descriptors $\mathbf{d}_1, \dots, \mathbf{d}_m$ of the query image and picks the class $C$ that minimizes $\sum_i \lVert \mathbf{d}_i - \mathrm{NN}_C(\mathbf{d}_i) \rVert^2$, where $\mathrm{NN}_C(\mathbf{d}_i)$ is the nearest descriptor to $\mathbf{d}_i$ among all descriptors of all training images of class $C$; they derive it as an approximation of the optimal classifier under a naive-Bayes assumption that descriptors are independent given the class. On Caltech-101 with 15 labelled images per class, NBNN with SIFT descriptors reached a mean per-class recognition rate of 65.0%, and 72.8% with five descriptor types, against 42.1% to 45.2% for nearest-neighbour image classifiers and 59.1% for SVM-KNN (their Table 1). With 30 labelled images per class, replacing the image-to-class distance with an image-to-image one lowered NBNN’s rate from 70.4% to 58.4%, and quantizing SIFT into a 1,000-word codebook lowered it to 50.4% (their Table 3).

History

Cover and Hart (1967) write that the first formulation of a nearest-neighbour type rule appears to have been made by Fix and Hodges, in a 1951 report for the US Air Force School of Aviation Medicine that studied the $k_n$-NN rule and proved the consistency result above; the report was reprinted in 1989. Hastie and colleagues similarly date the method back at least to Fix and Hodges. Several authors had suggested the rule for pattern recognition by the time Cover and Hart’s paper supplied the large-sample bound for $k = 1$.