Module 13 · Neighbors & structure
Nearest neighbors — the training set is the model
k-NN has no training step, no parameters, no fitted object — it is its training data. To classify a new point, find the k closest training points and let them vote. Everything interesting hides in two innocuous words: closest(which distance? features must be scaled comparably, or one wide-ranged feature silently decides everything) and k (the entire bias-variance dial, as the U-curve of Module 2 showed).
This module's lab shows the thing curves can't: the decision map. Every pixel is colored by the vote it would receive, so you see the classifier's entire personality at once — and how it changes as k grows.
Despite its simplicity, k-NN has a serious theoretical credential: with unlimited data, 1-NN's error is at most twice the best achievable (Bayes) error, no matter how gnarly the problem. Its real limitations are practical — prediction cost grows with the training set, and high dimensions break the notion of “near” entirely.
🎛 Decision-region lab
Training error
7.3%
neighbors vote, majority wins
Test error
15.0%
on 400 fresh points
Every pixel is colored by asking: which class wins a vote among the k nearest training points? At k=1 the map shatters into islands — a private region around every noisy point. Raising k merges the islands into smooth territories; the stray specks disappear and test error usually improves. The catch that limits this idea: in high dimensions “nearest” stops meaning “near” — with many features all points are almost equally far apart, so the vote turns into noise (the curse of dimensionality, revisited in chapter 18). Educational tool.
Prototype methods — compressing the memory
If lugging the whole training set around is the problem, keep a few well-placed prototypes per class instead and classify by nearest prototype. Run k-means (Module 14) within each class to place them, or better, LVQ: iteratively attract each prototype toward points it classifies correctly and repel it from ones it gets wrong, so prototypes drift toward the contested frontier — a nearest-neighbor cousin of the support vectors from Module 12. A few dozen prototypes often match the full dataset's accuracy at a fraction of the cost.
Things to try
- • At k=1, find the little islands of one color deep inside the other's territory — each is a single noisy point that owns real estate. Raise k to 9 and watch them dissolve.
- • Push k to 51: the map goes nearly flat and test error climbs back up — oversmoothed. The best map is usually the moderately chunky one.
- • Raise the overlap and watch the boundary region grow ragged at every k: where classes truly mix, no vote can be confident, and the map shows you exactly where that is.