module 03
k-Nearest Neighbours
Nearest Neighbor Pattern Classification
Thomas M. Cover & Peter E. Hart
The simplest classifier there is: give a new point the label of the closest example you've seen. The paper proves that with enough data this lazy rule makes at most twice as many mistakes as the best possible classifier.
the idea in one line
To label a new point, look at the training points closest to it and copy their answer. With k = 1 you copy the single closest point. With k = 5 the five closest points vote, and the majority wins.
There is no training step. The model is the stored data. All the work happens when you ask for a prediction.
what k does to the decision regions
● filled class · ○ hollow class · darker background = more confident it's the filled class
why such a simple rule works
Cover and Hart asked how good this lazy rule can be. Their answer: with enough data, 1-nearest-neighbour makes at most twice as many mistakes as the best possible classifier.
Here's the intuition. With lots of data, the closest training point sits almost on top of your new point. So its label is like a second coin flip from the same coin. Two flips of the same coin disagree some of the time, and that disagreement is the 1-NN error. It's never worse than double the best you could do.
Two things follow from that:
- More data doesn't make 1-NN perfect. One neighbour is always a noisy guess.
- Voting fixes it. Averaging over k neighbours cancels the noise. Let k grow as the data grows and k-NN gets as good as the best possible classifier.
choosing k
| k | what happens |
|---|---|
| 1 | every point gets its own island. Training accuracy is perfect, noise included. |
| middle | the border is smooth and follows the real shape of the data |
| very large | it starts ignoring the shape and leans toward whichever class is bigger |
Try the buttons in the figure above. Training accuracy is highest at k = 1, but test accuracy is best in the middle.
how the code works
| step | in knn.py |
|---|---|
| store the data | fit just keeps X_ and y_ |
| measure distance | pairwise_distances: Euclidean, Manhattan, Chebyshev, Minkowski or cosine |
| find the k closest | kneighbors: a partial sort, so it's fast even with lots of data |
| vote | _votes; with weights="distance", closer points count more |
| break ties | the tied class that has the closest neighbour wins |
| regression | the average of the neighbours' values instead of a vote |
Three small details that matter:
- Fast distances.
|a − b|² = |a|² + |b|² − 2a·bturns all distances into one matrix multiply. Rounding can make a tiny distance slightly negative, so it's clipped at 0. - Fair ties. With an even k the vote can tie. Picking the lowest label would quietly favour class 0, so the closest neighbour decides instead.
- Exact matches. With distance weighting, a weight of 1/0 would break things. If a new point sits exactly on a training point, that point simply decides.
what the demo checks
Run uv run python examples/03_knn.py. It uses two overlapping bell curves, where
the best possible error is known exactly, so the theory can be tested.
- The best possible error is 0.159, the 1-NN limit is 0.225, and Cover & Hart's bound is 0.267.
- Measured 1-NN error settles at about 0.218 and stops improving even with 10,000 points, exactly as the theory says.
- Raising k to 501 brings the error down to the best possible.
- One extra feature of pure noise, measured in big units, pushes the error to 0.425. Rescaling the features brings it back to 0.07.
- In 1000 dimensions, the nearest point is 90% as far away as the farthest one, so "nearest" stops meaning much.
when it goes wrong
- k too small: islands around noisy points.
- k too large: everything becomes the majority class.
- features on different scales: the feature with the biggest numbers decides every distance. Rescale first.
- many dimensions: all points start to look equally far apart.
- slow predictions: every prediction measures the distance to every stored point.