Last updated: 2026-10-07

U
Undergraduate level
FDN
Foundational — Knowledge that endures for decades — core principles

Nearest-Neighbour and Instance-Based Learning

Every model in this section so far distils the training data into something smaller than the data itself — weights, a tree, a set of support vectors, a grid of prototypes. A k-nearest-neighbour (k-NN) classifier, formalised by Cover and Hart in 1967, refuses that step entirely1: it simply keeps every training example, and answers a new query by finding whichever stored examples are closest to it.

The Rule Itself FoundationalKnowledge that endures for decades — core principles

Classifying a new point means measuring its distance to every stored training example, taking the \(k\) closest, and letting them vote — the new point gets whichever label is most common among its \(k\) nearest neighbours. Run against this section's shared dataset with \(k=1\): a new point at (1.2, 1.3) lands closest to the "round" cluster's nearest member and is classified round; a new point at (4.2, 4.3) lands closest to the "square" cluster instead. There is, in the usual sense, no training phase at all — "training" an instance-based model just means storing the data, with essentially no computation until a query actually arrives.

Choosing k, and What Distance Means FoundationalKnowledge that endures for decades — core principles

A small \(k\) (especially \(k=1\)) produces a decision boundary that can wiggle around every individual training point, including mislabelled or noisy ones — high variance, low bias. A large \(k\) averages over many more neighbours, smoothing the boundary at the cost of blurring genuinely sharp distinctions that exist in the real data — low variance, higher bias. Which distance measure counts as "closest" is a real design choice, not a detail: Euclidean distance (straight-line) is the default, Manhattan distance (sum of absolute coordinate differences) is less sensitive to a single feature with an unusually large difference, and whichever is used, features measured on very different scales — age in years next to income in whole currency units — need to be rescaled first, or the larger-scale feature will dominate the distance calculation regardless of which one actually matters more.k=1 memorises noise; large k blurs real boundaries

Note well. Nearest-neighbour distance is meaningless across features measured on very different scales until they're rescaled. A feature ranging 0–1,000,000 will dominate a straight-line distance calculation over one ranging 0–1, whether or not it's actually more informative.

The Cost Moves to Inference Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

Every other model in this section pays its computational cost up front, during training, and answers a query cheaply afterward. Instance-based learning inverts that trade: training is nearly free, but every single query has to measure its distance to every stored training example (or rely on a spatial index structure to avoid checking all of them), which gets slower as the stored dataset grows, not faster. This is the opposite cost profile from a trained neural network or decision tree, whose inference cost is fixed regardless of how large the original training set was.

The Curse of Dimensionality Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

Nearest" stops being a meaningful idea as the number of features grows large. In high-dimensional spaces, the distance between the closest and the farthest point in a random dataset tends to shrink toward being nearly the same — every point ends up roughly equally far from every other point — which is the curse of dimensionality as it applies specifically to distance-based methods: the entire premise of "vote among whichever points are closest" weakens exactly when there are enough features for genuinely distinguishing structure to exist in principle.

  • Weightless Neural Networks and RAM Networks — another model that stores something other than weights, worth contrasting exact tuple-address matching against continuous distance matching.
  • Radial Basis Function Networks — a smoothed, weighted version of the same "nearby things are similar" assumption, rather than a hard vote among the k closest.
  • Support Vector Machines — another model whose prediction depends on a subset of stored points, chosen by margin rather than by raw proximity.

References

  1. Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21–27. ↩