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

  1. Store all the training points. That is the whole "training".
  2. For a new point, measure its distance to every training point, usually straight-line (Euclidean) distance.
  3. Sort, and take the k nearest.
  4. Classification: majority vote among those k labels. Regression: the average of their values.
  5. Choose k with validation data. k = 1 follows every quirk of the data (high variance); a large k smooths everything out (high bias).
  6. Scale the features first, or the feature with the largest units decides every distance.

Key points

Common mistakes

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.