k-nearest neighbours
k-nearest neighbours predicts by finding the k training points closest to a new point and letting them vote (or averaging their values, for regression).
Why it matters
Sometimes the simplest idea is enough: things that are close together tend to be alike. k-NN needs no training, adapts to any shape of boundary, and makes a strong baseline. Learning it also teaches you why distances, scaling and the curse of dimensionality matter for every method that compares points, including vector search for LLMs.
The idea
To classify a new point, find the k closest training points and take a vote. There is no training step at all.
New in a town? Ask your 5 nearest neighbours which restaurant is best, and go with the majority.
In very high dimensions, all points are almost equally far apart (the 'curse of dimensionality'), so 'nearest' stops meaning much.
How it works
- Store all the training points. That is the whole "training".
- For a new point, measure its distance to every training point, usually straight-line (Euclidean) distance.
- Sort, and take the k nearest.
- Classification: majority vote among those k labels. Regression: the average of their values.
- Choose k with validation data. k = 1 follows every quirk of the data (high variance); a large k smooths everything out (high bias).
- Scale the features first, or the feature with the largest units decides every distance.
Key points
- No training step; all the work happens at prediction time, so prediction is slow on big data.
- Small k: wiggly boundaries, overfits. Large k: smooth boundaries, underfits.
- Use an odd k for two classes, to avoid ties.
- Feature scaling is essential for k-NN: without it, the feature with the biggest numbers decides every distance.
- Curse of dimensionality: with hundreds of features, all points are nearly the same distance apart.
- Fast approximate nearest-neighbour search (Unit 5) makes this idea work at the scale of millions of vectors.
Common mistakes
- Forgetting to scale features, so one feature with large numbers decides which neighbours count as nearest.
- Choosing k on the test set. Choose it on validation data, and keep the test set for the final score.
- Using it with many irrelevant features: noise dimensions outweigh the useful ones.
- Expecting fast predictions on millions of rows without an index.
Not true: k-nearest neighbours improves as you add more features, even irrelevant ones.
In fact: Irrelevant features add noise to every distance, and with many of them the useful features hardly count: the curse of dimensionality.
Not true: k-NN has no training step: so it also predicts quickly on millions of rows.
In fact: No training means all the work happens at prediction time: each prediction compares the new point with the stored rows. Large data needs an index.
Part of Unit 2: Classical ML, built by you in the free ML Foundations course.