Home / Learn / Data & AI / ML foundations / Lesson 4.7
All lessons

Module 4: Classification and logistic regression · Lesson 4.7 · about 20 min

k-nearest neighbours

The simplest classifier of all: to label a new point, find the k closest examples and let them vote. No training, flexible boundaries, and one dial, k, that runs from overfitting to underfitting. Change k on the two-moons data.

Key points, meanings and formulas on one page: choose "Save as PDF" in the print box.

Module 4 · about 20 minutes · read first: 2.4, 3.7. You’ll be able to classify a point with k-NN by hand, choose k, and explain the method’s strengths and its weakness with many features.

To guess the label of something new, find the most similar things you have already seen and go with what most of them were.

1. Why this matters

k-nearest neighbours (k-NN) is the plainest form of “learning from examples”: things that are alike tend to have the same label. It needs no training, draws borders of any shape, and is easy to explain (“these five similar past cases were approved”). The same “find the nearest” idea powers recommendation systems and the document search behind many AI assistants, where the “points” are embeddings (Lesson 10.2).

2. The method

To classify a new point:

  1. Measure its distance to every stored example. Usually this is straight-line (Euclidean) distance, the kind you’d measure with a ruler, on scaled features.
  2. Keep the k closest. (k is just a number you choose, such as 3 or 9.)
  3. Let them vote: predict the most common class. The share of votes is a rough probability.

For regression, predict the average of the k neighbours’ values instead.

There is no training step: the model is the stored data. That makes it quick to set up and slow to use, because every prediction compares the new point with every stored example. Smart index structures help. Because it puts off all the work until a question arrives, k-NN is called a lazy learner.

A new point arrives at (3, 3). Five stored points: two of class A, three of class B.

Measure every distance. For (2, 2): √((3−2)² + (3−2)²) = √2 ≈ 1.41. The others: 2.83, 1.41, 2.24 and 2.83.

Keep the 3 nearest. (2, 2) at 1.41, (4, 4) at 1.41 and (5, 4) at 2.24. The two far corners drop out.

Vote. One A, two B. The new point is labelled B, with a rough probability of 2/3.

d(a, b)
The straight-line distance between two rows: square each feature's difference, add them up, take the square root.
k
How many neighbours get a vote.
Nk(x)
The set of the k stored examples closest to the new point x.
Physical meaning
Asking the neighbours. To guess how a new family on the street will vote, ask the five nearest houses. Ask only one and you may get the odd one out; ask the whole town and you lose what is special about the street.

A popular version weights each vote by 1/d, so closer neighbours count more.

3. The one dial: k

Try it: change k
training accuracy
test accuracy (new points)
vote at the tapped spot

Tap the plot to see the k neighbours of that spot.

k-nearest neighbours does no training at all: it keeps every example and, for a new point, lets the k closest ones vote. With k = 1 the regions hug every point, including the noisy ones (overfitting: perfect on training, worse on test). With a very large k the vote is swamped by the bigger picture and the boundary goes too smooth (underfitting). Odd k avoids tied votes.
  • k = 1: the border wraps round every single point, including noisy ones on the wrong side. Training accuracy is 100 %, test accuracy is lower. Overfitting.
  • Middle k (say 9 to 21 here): smooth borders that follow the two moons. The best test accuracy.
  • Very large k: far-away points swamp the vote; the border flattens out and then becomes “always the majority class”. Underfitting.

Choose k with a validation set or cross-validation (Lesson 7.2). With two classes, an odd k avoids ties.

4. The curse of dimensionality

k-NN works beautifully in 2 or 3 dimensions and can fail in 300. With many features, points spread out so thinly that every point is far from every other, and the “nearest” neighbours are barely nearer than the rest. Picture friends who live on one street: easy to find the closest. Now give every friend a house in a 300-storey building on a 300-street grid: everyone is far from everyone. Irrelevant features make it worse, because they add noise to every distance. Use a handful of good features, or reduce the dimensions first (PCA, Lesson 8.4).

“k-NN has no settings, so there is nothing to get wrong.” It has two big ones hiding in plain sight: the value of k, and how distance is measured. Forget to scale your features and a column in dollars (thousands) drowns out a column in years (tens), so the “nearest” neighbours are just the ones with similar incomes.

Maths and principle

Principle: similar inputs should get similar outputs. k-NN estimates the class probability as the share of each class among the nearest examples.

Equations: Euclidean distance between rows 𝐚 and 𝐛, and the estimate for a new point 𝐱 with neighbour set Nk(𝐱):

d(𝐚,𝐛)=∑j=1d(aj−bj)2,Pˆ(y=c|𝐱)=1k∑i∈Nk(𝐱)[yi=c]

The curse in one number: in d dimensions, to capture 1 % of points spread evenly in a unit cube, a smaller cube must have side 0.011/d: 0.1 in 2 dimensions, but 0.63 in 10 and 0.95 in 100. “Local” stops being local.

Try it: training points (1, 1) class A, (2, 2) class A, (4, 4) class B, (5, 4) class B, (5, 5) class B. Classify (3, 3) with k = 3. (Distances: 2.83, 1.41, 1.41, 2.24, 2.83. Nearest three: (2, 2) A, (4, 4) B, (5, 4) B. Vote: B.)

5. Worked example

Made-up numbers. A library guesses whether a new member will like a book club, using two scaled features: books read last year and average book length. For a new member at (0.4, −0.2), the 5 nearest past members are at distances 0.15, 0.22, 0.30, 0.31 and 0.45; three of them joined and liked it, two didn’t. Plain vote: 3 to 2, “will like it”, with a probability of 0.6. Distance-weighted vote: if the two closest (1/0.15 = 6.7 and 1/0.22 = 4.5) are the ones who liked it, along with the fourth (3.2), the weights are 14.4 for “like” against 3.3 + 2.2 = 5.5 for “not”: about 0.72.

6. Practice

  1. Why does k-NN have “no training”, and what is the cost of that?
  2. With 3 classes and k = 4, how could a tie happen, and how might you break it?
  3. Would k-NN work well on raw pixel values of photos? Why or why not?
Answers
  1. It just stores the data. The cost is that each prediction compares against every stored example, which is slow and needs all the data kept.
  2. Two classes get 2 votes each. Break ties by the closest neighbour, by distance weighting, or by using a different k.
  3. Poorly: thousands of dimensions, and pixel distance doesn’t match meaning (the same cat shifted a little is “far” in pixels). Use learned features (embeddings) instead.
  • k-NN labels a new point by a vote of its k nearest stored examples; there is no training step.
  • Small k overfits (jagged borders), large k underfits (everything becomes the majority class); choose k by validation.
  • Features must be scaled, or the one with the biggest numbers decides every distance.
  • With many features, “nearest” loses its meaning: the curse of dimensionality.

Try it on your own data: the small model trainer runs k-NN on your CSV and shows test accuracy as you change k.

New words: k-nearest neighbours, Euclidean distance, distance weighting, lazy learning (no training step), curse of dimensionality.

Check yourself

1With k = 1, what is the training accuracy of k-NN (when no two identical points have different labels)?
2What happens as k grows very large?
3Why must inputs be scaled for k-NN?

Sources

Your ticks stay in this browser. Save them as a file on the course home.

Updated 2026-11-22. Numbers in the examples are made up to show the idea unless a source is given. Simulations run in your browser; nothing you type is sent anywhere.