5.8 k-nearest neighbours and distance methods

What this is and why it exists

Nearest neighbours is the simplest thing that can honestly be called learning: store everything, and to predict, look at what happened to the most similar cases. It costs nothing to train and everything to use, which is unusual and instructive. It also teaches two lessons that outlive it entirely — that distance depends on units, and that geometric intuition stops working in high dimensions.

The vocabulary

• Instance-based (lazy) learning — no model is built; the data is the model.
• k — how many neighbours vote.
• Distance metric — how similarity is measured: straight-line, city-block, cosine.
• Cosine similarity — the angle between two vectors, ignoring their lengths.
• Curse of dimensionality — the failure of distance to distinguish anything as dimensions grow.
• KD-tree and ball tree — structures that make exact neighbour search faster in modest dimensions.
• Approximate nearest neighbour — trading exactness for speed at large scale.

The mental model

Training is storing. Prediction is finding the k closest stored points and taking a vote, or an average for regression. That inversion is the interesting part: every other model in this module pays at training time and is cheap to use, and this one is the reverse — instant to fit, and every prediction is a search through the whole dataset. For a small dataset that is fine; for a million rows and a latency budget it is the whole problem, which is what the search structures address.

Scaling is not optional here, it is the entire behaviour. Distance sums contributions from every feature, so a feature measured in millimetres contributes a thousand times more than the same quantity in metres. Without scaling, the neighbours you find are decided by your choice of units, which is not a modelling decision anybody meant to make. Scale every feature to a comparable range first, and be aware that this makes every feature equally important — which is itself an assumption, and the reason nearest neighbours does badly when many features are irrelevant.

The choice of k is a bias-variance dial in its plainest form. k of one memorises: the decision boundary wraps around every individual point, and one mislabelled example creates its own little region. Large k smooths: the boundary becomes broad and the model approaches predicting the overall majority. Choose it by cross-validation, and prefer an odd number for binary classification so that votes cannot tie.

The metric matters too, and matching it to the data is often worth more than tuning k. Straight-line distance is the default and assumes every direction is comparable. City-block distance sums absolute differences and is less swayed by one large discrepancy. Cosine similarity ignores magnitude entirely and compares direction, which is why it is the standard for text and for embeddings — where two documents about the same subject should count as similar whether one is a paragraph or a page.

Then the curse of dimensionality, which is the lesson that outlives the algorithm. As the number of dimensions grows, points spread out and the distances between them become increasingly similar: the nearest neighbour and the farthest one end up nearly the same distance away, so "nearest" stops meaning anything. Two consequences follow. Nearest neighbours degrades in high dimensions unless the data really lies on a lower-dimensional surface inside them. And your geometric intuition — built in three dimensions — is actively misleading about high-dimensional spaces, which is worth remembering every time somebody draws a two-dimensional picture of a hundred-dimensional problem.

The search structures address the cost, within limits. Tree structures partition the space so a search need not touch every point, and they help substantially in low dimensions and progressively less as dimensions grow — for the reason above, since partitioning stops separating anything useful. Beyond that, approximate methods give up the guarantee of finding the true nearest neighbour in exchange for speed, and they are what makes vector search practical at scale. That is not a detour: it is exactly the machinery underneath retrieval in the language-model modules, and this topic is where the idea belongs.

So where does it still win? When the decision boundary is genuinely irregular and there is enough data to describe it. When you need a strong baseline in five minutes. When new classes appear constantly and retraining is impractical — adding a class means adding examples. And as the retrieval step in a larger system, which is its most common modern role by far.

What you should now be able to explain or do

Say what training and prediction cost, and why that is the opposite of every other model here. Explain why scaling decides the behaviour, with the millimetres example. Say what small and large k each do to the boundary. Choose a distance metric for text and say why. State the curse of dimensionality in one sentence and give two consequences. Say why tree structures stop helping in high dimensions. Name a modern system that is nearest neighbours at its centre.

Check yourself