ML Explorer · Level 3 · Classic ML
k-nearest neighbours
To label a new case, look at the cases most like it and let them vote.
Overview
So far every model has predicted a number. This lesson predicts a label instead: which of two classes a case belongs to.
The method is about as simple as machine learning gets. Keep the training cases, and when a new case arrives, let the k closest ones vote. We watch the vote, shade the whole plot by its answer, turn k up and down, and then change the units of one feature to see why that matters.
The points are made up. See "About the data" at the end.
You'll learn
- how k-nearest neighbours (k-NN) labels a new case, and what accuracy measures
- why k = 1 is perfect on the training data and why that means little, and how to choose k
- why the units of the features change k-NN's answer, and how standardising fixes that
-
Labels, not numbers
Each case belongs to one of two classes. The model's job is to say which. That is classification.
Each point is one case, described by two measurements, feature 1 and feature 2. They are made up and have no units. Each case also has a label, class 0 or class 1. We write the label y, so y is 0 or 1.
Class 0 is a cyan circle and class 1 a violet triangle, so the shape alone tells them apart.
There are 40 training cases, 20 of each class. The two clouds overlap: some circles sit among the triangles, and some triangles among the circles.
To score a classifier we use its accuracy: the fraction of cases it labels correctly. Get 45 of 50 right and the accuracy is 45 ÷ 50 = 90%. As in Lesson 9, the score that matters is on test cases the model never saw. Here there are 300 of them, 150 of each class, from the same source.
The maths
Case has a feature vector and a label . A classifier gives a predicted label . Over cases,
where is 1 when the statement inside is true and 0 when it is false. The labels are names for the classes: 1 is not "more" than 0, so an error like has no useful meaning here.
-
A new case: ask the neighbours
Find the k training cases closest to the new case and let them vote. The majority wins.
The hollow diamond is a new case with no label. Drag it, or tab to it and use the arrow keys.
Here k = 3. Lines join the new case to its 3 nearest training cases, which are ringed. The dashed circle passes through the third nearest; the other two lie inside it.
At the start, at feature 1 = and feature 2 = , the vote is circles to triangle, so k-NN predicts class .
Closest means the ordinary straight-line distance on the plot, the one Lesson 2 used to compare fruit. With two classes and an odd k, the vote can never be a tie.
There is no training step. The model is the training data itself, kept until a new case arrives.
The maths
The distance from a new case to training case is
Let be the training cases with the smallest distances. If two are exactly as far away, the one made first wins the place. The vote is a majority:
The sum counts the class-1 votes. With odd it can never equal , so there is no tie. With more than two classes, the most common class among the wins, and ties can happen even for odd (three neighbours from three classes), so a tie rule is needed.
The cost sits at prediction time: each new case needs its distance to all training cases, so twice the training data means twice as many distances to compute for every prediction.
-
The decision boundary
Ask the same question at every spot on the plot and shade the spot by the answer. Where the answer changes is the decision boundary.
Here k = 1: each spot takes the label of its single nearest training case. The cyan-tinted area is predicted class 0, the violet-tinted area class 1, and a line marks where they meet.
The boundary is jagged, and it draws small islands around lone cases sitting among the other class.
Training accuracy is 100%. Each training case is its own nearest neighbour, at distance 0, so its vote is always its own label.
That says nothing about new cases. On the test cases, accuracy at k = 1 is .
The maths
With , training case has distance to itself, so it is its own nearest neighbour and . The only exception would be two training cases at exactly the same spot with different labels; that does not happen here.
For the plot splits into cells, one per training case, each holding the spots closer to that case than to any other. The shading is a simplification: it is worked out on a grid of 60 × 56 small squares, each coloured by the prediction at its centre, so the drawn boundary follows the grid.
-
Turning k
Move the k slider. A small k follows every case. A large k listens to many cases at once, and the boundary smooths out.
The slider takes the odd values of k from 1 to 25. The chart shows training accuracy (solid line, dots) and test accuracy (dashed line, squares) for each one.
Training accuracy is 100% only at k = 1. At k = 3 it is already : once other cases join the vote, a case surrounded by the other class gets outvoted. Each training case still counts in its own vote here.
Test accuracy goes the other way at first: at k = 1, higher for every larger k on the slider. At k = 25 it is .
This is Lesson 10 again, with the knob turned the other way. k = 1 is the most flexible model, like the degree-12 curve: it learns the noise. A very large k is like the straight line: it smooths away real shape.
The maths
Training accuracy here lets each training case vote for itself, which flatters it, most of all for small . It is shown to compare with the test accuracy, not to choose .
At the far end, , every case would get the same 40 votes, 20 for each class: a tie everywhere, and no use at all. Long before that, the boundary loses the shape of the data.
-
Choosing k on unseen data
Pick the k that does best on cases the model did not learn from.
On the test cases, accuracy peaks at k = , with . That is neither the smallest k on the slider nor the largest. Its training accuracy, , is not the highest, and that does not matter.
The peak is not sharp: several other values of k score within one percentage point of it. With a different sample of data, a nearby k could win.
We pick k with the test set here only to show the idea. In practice, as Lesson 9 said, you choose k on a validation set and use the test set once, at the end.
The maths
The chosen value is
with a tie going to the smaller . Because was picked for these test cases, its score on them is likely to be a little higher than it would be on fresh cases. That is why the choice belongs on a validation set.
-
Units matter
k-NN adds up the differences in every feature. Change one feature's units and you change which cases count as near.
Press "Feature 2 × 100". It is as if feature 2 had been written in centimetres instead of metres. The points do not move; only the axis labels change. But a gap of 1 in feature 2 now counts as 100, so feature 1 hardly matters.
The dashed neighbourhood flattens into a thin band: the nearest cases are the ones with almost the same feature 2, wherever they sit in feature 1. The boundary runs almost flat across the plot.
With k = , test accuracy falls from to , and of the test predictions change. For the new case at its starting spot, only of its neighbours stay the same, and the prediction changes from class to class .
Press "Standardised". Each feature becomes a z-score, as in Lesson 2: subtract the training mean, then divide by the training standard deviation. Now the units drop out. Standardising the original data or the × 100 copy gives exactly the same predictions.
Test accuracy is , a little below the in the original units. Standardising does not promise a better score: the two features already had spreads of a similar size, so it changed little, and here it happened to cost a few cases. What it does promise is that the units someone happened to record in do not decide the answer.
The maths
Multiply feature 2 by and the squared distance becomes
With the second term is times as heavy, so it decides the order unless two feature-2 values are almost equal. Points within a fixed distance now form an ellipse 100 times as wide as it is tall, which is the band on the plot.
Standardising feature uses the mean and the population standard deviation (dividing by ) of the 40 training cases:
Test cases and the new case use the same training and . Multiplying a feature by multiplies its mean and standard deviation by too, so
and the z-scores, the distances and the votes are unchanged. On a computer the two routes can differ in the last digit; on this data every prediction agrees.
Quick check
Lesson complete
- Classification predicts a label. Accuracy is the fraction of cases labelled correctly, and the one that counts is on unseen cases.
- k-NN labels a new case by a majority vote of its k nearest training cases. An odd k avoids ties with two classes.
- k = 1 is 100% right on the training data and overfits. A larger k smooths the boundary; too large a k underfits. Choose k on a validation set.
- Distances depend on units. Standardise the features, using the training mean and standard deviation, before k-NN.
Common misconceptions
- "k-NN learns a rule from the data." It stores the training cases; all the work happens when a new case arrives.
- "100% training accuracy means a great model." With k = 1 it comes almost for free, whatever the data (the only exception is two identical cases with different labels).
- "Standardising always improves accuracy." It removes the effect of the units. Whether the score goes up depends on the data.
Further reading
- James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 2.2.3, "The Classification Setting", which introduces k-NN and shows the training error at K = 1 falling to zero while the test error does not. The book writes K for the number of neighbours, where this course writes k.
- The same book, Section 4.7.6, "K-Nearest Neighbors", a worked example that explains why the scale of the variables matters and standardises them first.
About the data. The cases are made up. Each class is a round cloud: feature 1 = m₁ + 1.1 z₁ and feature 2 = m₂ + 1.1 z₂, where z₁ and z₂ are independent draws from a normal distribution with mean 0 and SD 1, made with mulberry32. Class 0 has centre (m₁, m₂) = (2, 2) and class 1 has centre (4, 3.4). The 40 training cases (20 per class, class 0 first) use seed 41; the 300 test cases (150 per class) use seed 42. The starting spot of the new case, (3.5, 2.5), was chosen so the vote there is not one-sided. Distances are straight-line distances; when two training cases are exactly as far away, the one made first counts as nearer. Standardising uses the training cases' mean and population SD. Displayed values are rounded; the calculations are not.
If this helped, you can .