Nearest neighbours

The validation note gave a way to measure any model honestly; so far the only models were thought experiments. The memorizer of the opening note answers correctly for the objects it has seen and has nothing to say about the others. The smallest change that makes it useful is to answer a new question with the answers to the most similar questions seen before. That is the nearest-neighbour method (Fix and Hodges, 1951). It needs no training beyond storing the data, works for any target, and is consistent when the number of neighbours grows with the size of the training set (but more slowly): with enough data it then approaches the best possible predictor, while a single neighbour tends to at most twice the best possible error. It also fails in a characteristic way when the number of features grows, and that failure motivates the rest of the course.

Notation. A distance $\rho(x, z) \ge 0$ between objects. For a query $u$, the training objects ordered by distance are $x_{(1)}(u), x_{(2)}(u), \dots$ with targets $y_{(1)}(u), \dots$; $N_k(u)$ is the set of the $k$ nearest. For two classes, $\eta(x) = P(Y = 1 \mid X = x)$, and $R^*$ is the Bayes error of the opening note.

The rule#

Classification: predict the class most frequent among the $k$ nearest neighbours,

$$\hat f(u) = \arg\max_{c} \sum_{i \in N_k(u)} [y_i = c] .$$

Regression: predict the mean of their targets, $\hat f(u) = \frac1k \sum_{i \in N_k(u)} y_i$. This is a local estimate of the conditional expectation $E[Y \mid X = u]$, the best predictor for squared loss: the average of $Y$ over the training points whose $X$ is close to $u$. In the same way, the vote shares estimate the class probabilities $P(Y = c \mid X = u)$.

Worked example. A query $u = (0, 0)$ and five training points: $A = (1, 0)$ and $C = (-2, 0)$ of class $+$, and $B = (0, 2)$, $D = (2, 2)$, $E = (0, -3)$ of class $-$. The distances are $1$, $2$, $2$, $2.83$ and $3$ for $A, B, C, D, E$. With $k = 1$ the prediction is $+$ (the neighbour $A$); with $k = 3$ it is $+$ ($A$, $B$, $C$: two votes to one); with $k = 5$ it is $-$ (three votes to two). The answer depends on $k$, and so does its quality.

Choosing k: bias against variance#

Small $k$ follows the data closely; large $k$ averages over a wide neighbourhood. For regression with noise variance $\sigma^2$, the average of $k$ independent noisy targets has variance $\sigma^2/k$, so a larger $k$ lowers the variance; but the $k$-th neighbour lies farther away, where $E[Y \mid X]$ differs from its value at $u$, so a larger $k$ raises the bias. With $k = 1$ every training point is its own nearest neighbour and the training error is zero; with $k = n$ every query gets the overall majority class. The figure shows the three regimes on data where the best rule is known:

Figure

The k-nearest-neighbour boundary for three values of k

At $k = 1$ the boundary encircles individual points of the wrong colour: training error 0, risk 0.188. At $k = 15$ the boundary follows the Bayes boundary closely, and the risk, 0.141, is near the Bayes error of 0.135. At $k = 101$ the vote averages over half of the training set, the boundary is too smooth, and the risk rises to 0.204. The best $k$ is chosen by cross-validation, and since cross-validation then reports the best of many candidates, the nested scheme estimates the result honestly: on the breast-cancer data bundled with scikit-learn, a grid over $k$ selects $k = 5$, with a cross-validated accuracy of 0.965 and a nested estimate of 0.968 for standardized features (the Code section).

Weighted votes and kernel regression#

A plain vote ignores how near the neighbours are: in the worked example, $A$ at distance 1 counts as much as $E$ at distance 3. Weighted kNN gives each neighbour a weight that decreases with distance. With weights $1/\rho$ and $k = 5$, class $+$ gets $1 + 0.5 = 1.5$ and class $-$ gets $0.5 + 0.354 + 0.333 = 1.187$, so the prediction returns to $+$.

Taking the weights from a kernel $K$ with a bandwidth $h$ gives the Nadaraya–Watson estimator (Nadaraya, 1964; Watson, 1964):

$$\hat f(u) = \frac{\sum_i K\big(\rho(u, x_i)/h\big)\, y_i}{\sum_i K\big(\rho(u, x_i)/h\big)} ,$$

the weighted mean that minimizes $\sum_i K(\rho(u, x_i)/h)\,(c - y_i)^2$ over the constant $c$. With the Gaussian kernel $K(t) = e^{-t^2/2}$ and $h = 1$, the five points of the example get weights $0.607, 0.135, 0.135, 0.018, 0.011$, and the share of class $+$ is $(0.607 + 0.135)/0.906 = 0.818$. The bandwidth plays the role of $k$: small $h$ is local and noisy, large $h$ smooth and biased. Kernels return later in this course as similarity functions in support vector machines, and the word then means something else. Here a kernel is a smoothing weight: a non-negative function of a distance that decreases away from zero. There it is a positive semidefinite similarity, an inner product of feature maps. The Gaussian is an example of both.

Distances and scaling#

Everything rests on the distance. The common choices:

Distance	Formula	Typical use
Euclidean	$\sqrt{\sum_j (x_j - z_j)^2}$	numeric features on comparable scales
Manhattan	$\sum_j \lvert x_j - z_j \rvert$	less dominated by one large coordinate difference
Cosine	$1 - \frac{x^\top z}{\lVert x \rVert\, \lVert z \rVert}$	word counts, embeddings: direction matters, length does not
Hamming, Jaccard	share of differing coordinates; $1 - \frac{\lvert A \cap B \rvert}{\lvert A \cup B \rvert}$	binary features, sets of tags

The Euclidean distance adds squared differences of features in their own units, so the feature with the largest spread decides who is a neighbour. On the wine data, kNN on raw columns is dominated by one feature with standard deviation 314 and reaches 0.663 accuracy, against 0.961 on standardized columns, as the data note showed. Standardization is not automatically right either: on the digits data, where every feature is a pixel intensity on the same scale, 1-NN reaches 0.988 on raw pixels and 0.973 after standardizing, which inflates the noise of nearly constant border pixels. Irrelevant features are worse than badly scaled ones, since each adds noise to every distance; feature selection, or a distance learned from the data, helps. For text, the cosine between bag-of-words vectors is the classical choice, and the NLP course builds those vectors.

The curse of dimensionality#

Nearest neighbours rely on there being training points close to the query. In many dimensions there are not (Hastie, Tibshirani and Friedman, 2009, Section 2.5):

• Neighbourhoods stop being local. With data uniform in the unit cube $[0, 1]^d$, a sub-cube that holds 1% of the data has edge $0.01^{1/d}$: 0.1 for $d = 2$, but 0.63 for $d = 10$ and 0.95 for $d = 100$. A “neighbourhood” with 1% of the data spans most of the range of every feature.
• Volume sits near the surface. The share of the volume of a $d$-dimensional ball within 5% of its radius from the surface is $1 - 0.95^d$: 0.098 for $d = 2$, 0.401 for $d = 10$, 0.994 for $d = 100$. The same concentration puts Gaussian samples on a thin shell far from the centre of the distribution.
• All distances become alike. Beyer et al. (1999), Theorem 1, show that for a fixed number of points, if the relative variance of the distance from the query to a data point vanishes as the dimension grows, which holds for independent identically distributed coordinates, then the ratio of the farthest to the nearest distance tends to 1 in probability. The nearest neighbour is then hardly nearer than any other point.

Figure

In high dimension every point is far, and equally far

With 1,000 uniform points, the nearest point is 50 times closer than the farthest in two dimensions (ratio 0.02) and only 1.1 times closer in a thousand (ratio 0.89). The number of points needed to keep neighbours local grows exponentially with $d$.

Two things soften the curse in practice. Real data are rarely uniform in all their dimensions: images, text embeddings and sensor readings lie near low-dimensional structures, and what matters is that intrinsic dimension rather than the number of columns. And a good representation changes the distances: kNN on raw pixels is mediocre, kNN on the embeddings of a trained network is the basis of modern retrieval. Still, for generic tabular features the curse is real, and it is the failure the next notes answer with global models that do not need a neighbour nearby.

Optimality: twice the Bayes error#

How good can such a simple rule be? Cover and Hart (1967) answered for the 1-nearest-neighbour rule as the training set grows. As $n \to \infty$ the nearest neighbour of $u$ converges to $u$, so its label becomes an independent draw from the same conditional distribution as the label of $u$. For two classes the rule then errs at $u$ with probability $\eta(u)(1 - \eta(u)) + (1 - \eta(u))\eta(u) = 2\eta(u)(1 - \eta(u))$. Writing $r(u) = \min(\eta(u), 1 - \eta(u))$ for the conditional Bayes error, the large-sample 1-NN error is $R_{1\mathrm{NN}} = E[2 r(X)(1 - r(X))]$, and since $E[r(X)^2] \ge (E\,r(X))^2 = (R^*)^2$,

$$R^* \le R_{1\mathrm{NN}} \le 2R^*(1 - R^*) \le 2R^* .$$

For $K$ classes the bound is $R^*\big(2 - \frac{K}{K-1}R^*\big)$ (Cover and Hart, 1967, Section VI). The statement is precise in three ways. It is a limit as $n \to \infty$ of the expected error, not a guarantee for finite samples, where 1-NN can be much worse (the figure’s $k = 1$ panel: 0.188 against a Bayes error of 0.135 with 200 points). It needs mild conditions: a separable metric space, and, with probability one, either continuity of the class-conditional densities at the query point or positive probability of the point itself. And the upper bound is tight: it is reached exactly when $r(x)$ is constant. Worked example. On $[0, 1]$ with $\eta = 0.1$ on the left half and $0.7$ on the right half, $R^* = \frac12(0.1 + 0.3) = 0.2$, $R_{1\mathrm{NN}} = \frac12(2 \cdot 0.1 \cdot 0.9 + 2 \cdot 0.3 \cdot 0.7) = 0.30$, and the bound is $2 \cdot 0.2 \cdot 0.8 = 0.32$. Trained on 20,000 points, 1-NN has a test error of 0.306 (the Code section).

Half the information in an infinite sample is in the single nearest neighbour, in Cover and Hart’s phrase. The other half needs a growing neighbourhood: if $k \to \infty$ and $k/n \to 0$, the $k$-NN rule converges to the Bayes error for every distribution of $(X, Y)$ with $X \in \mathbb R^d$ and the Euclidean distance (with ties between equidistant points broken at random), a universal consistency result due to Stone (1977). For regression the $k$-NN mean converges in mean square whenever $E\,Y^2 \lt \infty$. The result is about finite-dimensional inputs; for an arbitrary metric space it needs extra conditions. In the example, 101-NN on the same 20,000 points errs 0.206 of the time, close to $R^* = 0.2$.

Finding neighbours fast#

Prediction is where kNN pays: a brute-force search computes $n$ distances in $d$ dimensions per query, $O(nd)$, which is too slow for millions of objects and thousands of queries per second.

• Space-partitioning trees. A kd-tree (Bentley, 1975) splits the space along one coordinate at a time and prunes branches that cannot contain a closer point. In a few dimensions a query costs about $O(\log n)$; in high dimension the pruning stops working, and the search degrades towards checking every point, another face of the curse.
• Locality-sensitive hashing (Indyk and Motwani, 1998) hashes objects so that near objects collide with high probability and far ones rarely, and searches only the query’s buckets.
• Graph indexes. HNSW (Malkov and Yashunin, 2020) links every stored vector to a few near neighbours, forming a proximity graph, and builds several such layers on nested subsets, like a skip list: each vector enters the layers up to a random maximum level drawn from an exponentially decaying distribution, so the top layers are sparse and their links long. A search starts at the top, walks greedily to the stored vector closest to the query, descends one layer, and repeats; in the bottom layer it keeps a candidate list of size $ef$, and a larger $ef$ trades speed for recall. The number of steps grows roughly logarithmically with $n$ in the authors’ experiments, and the search returns the true nearest neighbours most of the time rather than always.

Approximate search is what makes nearest neighbours the core of modern retrieval: the semantic search note of the NLP course embeds passages with a neural encoder and finds the passages nearest to a query in such an index, and the Generative Models course uses $k$-nearest-neighbour balls to estimate the support of a distribution in its precision and recall metric.

What changed#

	Memorizer	$k$ nearest neighbours
Unseen object	a default answer	the answers of the $k$ most similar objects
Training	store the data	store the data
Prediction cost	a lookup	$O(nd)$ brute force; a tree or a graph index
Complexity control	none	$k$ (or a bandwidth $h$), chosen by cross-validation
Large-sample error	that of the default	1-NN at most $2R^*(1 - R^*)$; $k \to \infty$, $k/n \to 0$ reaches $R^*$
Weak point	everything new	many dimensions, scaling, irrelevant features

Limitations#

• The distance is the model. Bad scaling or irrelevant features make neighbours meaningless, and kNN has no mechanism to learn which features matter.
• High dimension. Without low intrinsic dimension or a learned representation, the data needed to keep neighbourhoods local grow exponentially with $d$.
• Cost at prediction time. The whole training set must be stored and searched; approximate indexes trade exactness for speed.
• No extrapolation and no summary. Far from the data the prediction is that of whatever points happen to be nearest, and there are no coefficients to inspect.
• Class imbalance. A rare class that overlaps the others is outvoted wherever it is locally outnumbered, unless votes are weighted or $k$ is small. The vote depends on the local share of the class among the neighbours, not on its global rarity: a rare class that forms a dense, well-separated cluster still wins inside that cluster as long as $k$ does not exceed its size.

What you should remember#

• kNN predicts by the majority class or the mean target of the $k$ nearest training objects; it is a local estimate of $E[Y \mid X]$ or of the class probabilities.
• Small $k$: low bias, high variance (1-NN has zero training error); large $k$: the opposite. Choose $k$ by cross-validation, report with nested cross-validation.
• Weighted votes and kernel (Nadaraya–Watson) regression replace the hard neighbourhood by weights; the bandwidth plays the role of $k$.
• Scale features before computing Euclidean distances, unless they already share a unit; prefer cosine for counts and embeddings.
• Curse of dimensionality: a 1% neighbourhood in $d = 10$ spans 63% of each axis; nearest and farthest distances become alike.
• As $n \to \infty$, $R^* \le R_{1\mathrm{NN}} \le 2R^*(1 - R^*)$ for two classes; $k$-NN with $k \to \infty$, $k/n \to 0$ is universally consistent in $\mathbb R^d$.
• Large-scale search uses approximate indexes such as HNSW, the engine behind semantic search.

Code#

Choosing $k$, scaling, distance concentration, the shell, and the Cover–Hart limit by simulation:

import numpy as np
from sklearn.datasets import load_breast_cancer, load_digits
from sklearn.model_selection import GridSearchCV, StratifiedKFold, cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(0)
cv = StratifiedKFold(5, shuffle=True, random_state=0)

# choosing k by cross-validation on the breast-cancer data (30 features on very different scales)
X, y = load_breast_cancer(return_X_y=True)
for name, model in [('raw', KNeighborsClassifier()), ('scaled', make_pipeline(StandardScaler(), KNeighborsClassifier()))]:
    key = 'n_neighbors' if name == 'raw' else 'kneighborsclassifier__n_neighbors'
    search = GridSearchCV(model, {key: list(range(1, 50, 4))}, cv=cv).fit(X, y)
    nested = cross_val_score(search, X, y, cv=StratifiedKFold(5, shuffle=True, random_state=1)).mean()
    print(name, search.best_params_[key], round(search.best_score_, 3), round(nested, 3))
# raw 5 0.932 0.937 | scaled 5 0.965 0.968: best k, its CV accuracy, the nested estimate

# when every feature already has the same unit (pixel intensities 0-16), standardizing can hurt
Xd, yd = load_digits(return_X_y=True)
print(round(cross_val_score(KNeighborsClassifier(1), Xd, yd, cv=cv).mean(), 3),
      round(cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(1)), Xd, yd, cv=cv).mean(), 3))   # 0.988 0.973

# distance concentration: 1,000 uniform points in [0, 1]^d, 100 queries; mean of nearest / farthest distance
for d in (2, 10, 100, 1000):
    P, Q = rng.random((1000, d)), rng.random((100, d))
    D = np.sqrt(np.maximum((Q ** 2).sum(1)[:, None] + (P ** 2).sum(1)[None] - 2 * Q @ P.T, 0))
    print(d, round(float((D.min(1) / D.max(1)).mean()), 2))
# 2 0.02 | 10 0.27 | 100 0.69 | 1000 0.89
# volume within 5% of the surface of a d-ball, and the edge of a cube holding 1% of uniform data
print([round(1 - 0.95 ** d, 3) for d in (2, 10, 100)], [round(0.01 ** (1 / d), 2) for d in (1, 2, 10, 100)])
# [0.098, 0.401, 0.994] [0.01, 0.1, 0.63, 0.95]

# Cover and Hart: eta = P(Y = 1 | x) is 0.1 on [0, 0.5) and 0.7 on [0.5, 1]; Bayes error 0.2
eta = lambda x: np.where(x < 0.5, 0.1, 0.7)
r = np.minimum(eta(np.array([0.25, 0.75])), 1 - eta(np.array([0.25, 0.75])))
print(round(r.mean(), 3), round((2 * r * (1 - r)).mean(), 3), round(2 * r.mean() * (1 - r.mean()), 3))   # 0.2 0.3 0.32: R*, the 1-NN limit, the bound
x, xt = rng.random((20_000, 1)), rng.random((20_000, 1))
yy, yt = rng.random(20_000) < eta(x[:, 0]), rng.random(20_000) < eta(xt[:, 0])
for k in (1, 101):
    print(k, round(float((KNeighborsClassifier(k).fit(x, yy).predict(xt) != yt).mean()), 3))
# 1 0.306 | 101 0.206: test error of 1-NN and 101-NN trained on 20,000 points

Next#

Nearest neighbours vote locally: each prediction uses a handful of training points, and nothing is learned about the shape of the relationship as a whole. That is why the method needs points nearby and fails in many dimensions. The next note goes to the other extreme, a global model with one coefficient per feature fitted to all the data at once: linear regression by least squares, its closed-form solution, and its reading as maximum likelihood under Gaussian noise.

References#

• E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture on metric methods: nearest neighbours, kernel regression, the optimality of kNN, fast neighbour search.
• E. Fix, J. L. Hodges. Discriminatory analysis. Nonparametric discrimination: consistency properties. USAF School of Aviation Medicine, report 4, 1951; reprinted in International Statistical Review, 57(3), 1989.
• T. M. Cover, P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 1967. Section VI (the theorem for two categories and its extension to $M$ categories).
• C. J. Stone. Consistent nonparametric regression. Annals of Statistics, 5(4), 1977.
• K. Beyer, J. Goldstein, R. Ramakrishnan, U. Shaft. When is “nearest neighbor” meaningful? ICDT, 1999. Section 3.4, Theorem 1.
• E. A. Nadaraya. On estimating regression. Theory of Probability and Its Applications, 9(1), 1964.
• G. S. Watson. Smooth regression analysis. Sankhyā A, 26(4), 1964.
• J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 1975.
• P. Indyk, R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. STOC, 1998.
• Yu. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 2020. Section 4 (the algorithm).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Section 2.5 (local methods in high dimensions), Section 13.3 ($k$-nearest-neighbour classifiers).
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Section 1.4 (the curse of dimensionality), Section 2.5.2 (nearest-neighbour methods).