k-nearest neighbours

Step 1 Understand it

The problem it solves. 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.

Watch it happen

The idea

To classify a new point, find the k closest training points and take a vote. There is no training step at all.

How it works, step by step

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.

Picture it

flowchart LR
  N["new point"] --> D["measure the distance<br/>to every training point"]
  D --> K["take the k = 3 nearest"]
  K --> V["their labels: A, A, B"]
  V --> W["majority vote → A"]

Analogy

New in a town? Ask your 5 nearest neighbours which restaurant is best, and go with the majority.

Where the analogy breaks

In very high dimensions, all points are almost equally far apart (the 'curse of dimensionality'), so 'nearest' stops meaning much.

Worked example

Class A sits at (1, 1) and (2, 1); class B at (3.5, 2) and (4, 4). The new point (2.5, 2) is 1.0 from (3.5, 2), 1.12 from (2, 1) and 1.80 from (1, 1). With k = 1 the answer is B; with k = 3 the vote is A, A, B, so the answer is A. The choice of k changes the prediction.

d = np.linalg.norm(X_train - x_new, axis=1)   # distance to every training point
nearest = np.argsort(d)[:k]
pred = np.bincount(y_train[nearest]).argmax()

Must-know 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.
• Curse of dimensionality: with hundreds of features, all points are nearly the same distance apart.
• Fast approximate nearest-neighbour search (Phase 5) makes this idea work at the scale of millions of vectors.

Common mistakes

• Forgetting to scale features.
• Choosing k on the test set.
• Using it with many irrelevant features: noise dimensions swamp the useful ones.
• Expecting fast predictions on millions of rows without an index.

Step 2 Go further (optional)

Optional. The lesson above is written to be enough on its own. If you want a second explanation, start with the one marked Worth it.

• Watch

  K-nearest neighbors, Clearly Explained

  StatQuest (Josh Starmer)

• Watch

  k-nearest neighbours and the curse of dimensionality

  Kilian Weinberger, Cornell CS4780

• Read

  ISLP, Ch 2 and Ch 4 (k-nearest neighbours)

  free book

Step 3 Practise

Try each exercise yourself first: on paper, out loud or in code. Then open the answer and compare it with yours.

1. ExplainSay it in plain words, with no notes.

   Explain k-NN with the neighbours-and-restaurants picture.

   Show answer

   You are new in town and want a good restaurant. You ask your 5 nearest neighbours where they eat, and go with the most popular answer. That is k-nearest neighbours with k = 5: to label something new, find the k most similar examples you already know, and take a vote.

   There is no training at all: the model is the whole set of examples. The work happens when you ask: measure the distance to everything and find the closest. Ask just 1 neighbour and you may get one odd opinion; ask the whole town and you just get the most popular place overall.

2. DeriveWrite the maths, or the steps, from memory.

   Class A at (2, 3) and (0, 0). Class B at (5, 3) and (3, 5.5). Classify the point (3, 3) by hand with k = 1 and with k = 3.

   Show answer

   Distances from the new point (3, 3):
   A (2, 3): √(1² + 0²) = 1.0
   A (0, 0): √(3² + 3²) ≈ 4.24
   B (5, 3): √(2² + 0²) = 2.0
   B (3, 5.5): √(0² + 2.5²) = 2.5

   k = 1: the single nearest is A at (2, 3), distance 1.0. Answer: A.
   k = 3: the three nearest are A (1.0), B (2.0) and B (2.5). The vote is 2 to 1 for B. Answer: B.

   The choice of k changed the answer. Small k follows the closest point exactly, so it is sensitive to noise; larger k smooths things out.

3. BuildCode it from scratch in NumPy, with no ML library.

   Implement k-NN with vectorised distances. Plot validation accuracy for k = 1 to 30 on a real dataset.

   Show answer

   Vectorised distances use the same trick as the toolkit phase: ‖a − b‖² = ‖a‖² + ‖b‖² − 2a·b for all pairs at once. Then sort each row, take the k nearest labels, and vote.

   On the standardised breast-cancer data, validation accuracy stays around 94 to 97% across most k, so the curve is fairly flat. When it is this flat, prefer a moderate k (say 5 to 10) over a lucky peak at k = 1: small k follows single noisy points, and very large k gets too smooth. Pick k from the validation curve, never from the test set.

   pythonCopy

   import numpy as np
   import matplotlib.pyplot as plt
   from sklearn.datasets import load_breast_cancer     # only to load the data
   
   data = load_breast_cancer()
   order = np.random.default_rng(0).permutation(len(data.target))
   X, y = data.data[order], data.target[order]
   tr, va = slice(0, 400), slice(400, None)
   mean, std = X[tr].mean(axis=0), X[tr].std(axis=0)
   X = (X - mean) / std
   
   def knn_predict(X_train, y_train, X_new, k):
       d = (X_new**2).sum(1)[:, None] + (X_train**2).sum(1)[None, :] - 2 * X_new @ X_train.T
       nearest = np.argsort(d, axis=1)[:, :k]
       return (y_train[nearest].mean(axis=1) > 0.5).astype(int)
   
   ks = range(1, 31)
   acc = [(knn_predict(X[tr], y[tr], X[va], k) == y[va]).mean() for k in ks]
   print("best k:", ks[int(np.argmax(acc))], "accuracy:", round(max(acc), 3))
   plt.plot(ks, acc, marker="o"); plt.xlabel("k"); plt.ylabel("validation accuracy"); plt.show()

4. BreakShow when it fails, and why.

   Add 50 random noise features to the data and run it again. What happens to accuracy? Connect this to the curse of dimensionality.

   Show answer

   With 50 extra columns of random noise, accuracy drops clearly (on this run from about 96% to the low 90s or below). The neighbours are no longer the truly similar patients.

   Why: distance adds up differences across every feature. 30 useful features and 50 noise features means most of the distance is now noise, so "nearest" mostly means "luckiest noise". That is the curse of dimensionality: in many dimensions, every point is roughly as far from every other point, so nearest neighbours stop being meaningfully near. k-NN needs a few relevant, scaled features; feature selection or a learned embedding helps.

   pythonCopy

   import numpy as np
   from sklearn.datasets import load_breast_cancer     # only to load the data
   
   data = load_breast_cancer()
   rng = np.random.default_rng(0)
   order = rng.permutation(len(data.target))
   X, y = data.data[order], data.target[order]
   X = (X - X[:400].mean(axis=0)) / X[:400].std(axis=0)
   
   def accuracy(X, k=7):
       d = ((X[400:][:, None, :] - X[:400][None, :, :]) ** 2).sum(-1)
       pred = (y[:400][np.argsort(d, axis=1)[:, :k]].mean(axis=1) > 0.5)
       return (pred == y[400:]).mean()
   
   noisy = np.column_stack([X, rng.normal(size=(len(X), 50))])
   print(f"30 real features: {accuracy(X):.1%}, plus 50 noise features: {accuracy(noisy):.1%}")

Step 4 Prove it

Check you understood

Tick each check when you can do it without notes