Mohammad Mahmoud Interactive lessons

Lesson 2 of 4Supervised learning11 exercises

Nearest Neighbours

A new point arrives with no label, and we want to classify it: Sand or Sea. The laziest sensible rule is to find the labelled point closest to it and copy that label. That rule is 1-NN. We could also ask a small crowd instead of a single point: take the k closest labelled points and copy the majority label. That is k-NN. In the playground below you can drag the ◆, change k, and watch the map redraw.

Playground

SandSeaUnlabelled queryBoundaryTies go to the closer class
Drag ◆ or any point · arrow keys move ◆
Neighbours
Distance
Dataset
Tap on the map to

The idea

You are given a few dozen labelled examples. Each one is a dot in the plane, coloured Sand or Sea. Then a new dot shows up with no colour. What should the computer say?

k-nearest neighbours answers with a vote: find the k labelled dots nearest to the newcomer, count colours, and go with the majority. There is no training step worth the name. The model is the data.

On the playground, the dashed shape around the ◆ is the neighbourhood: the smallest ball (for Manhattan distance, a diamond) that captures exactly k points. The shading behind everything is the map of what the rule would answer at every location, and the dark string is the boundary: every place where the vote flips.

Exercise bank

Four kinds of exercise, checked on the spot. Once a card is solved it stays solved, but everything on it keeps working, so try the other options, other values of k, or other spots on the map and see what happens. Progress is saved in this browser.

PredictParameter playBreak itQuiz
Progress 0 of 11

Why k matters

k = 1 trusts whichever point happens to be nearest. One stray point then gets its own little island on the map, and the boundary zigzags around every single point. Raise k and each spot on the map asks a bigger crowd. Single points stop mattering, the islands close up, and the zigzag relaxes into a few long, calm curves. Push k further still and the crowd gets so big that it is nearly the same crowd everywhere: a small group of one class, even a perfectly real one, is outvoted by its surroundings and disappears from the map.

Picture the boundary as a string pulled between the two classes. Small k pulls the string tight around every point, noise included; that is overfitting. Large k lets it hang slack and ignore real detail; that is underfitting. The right tension is a judgement call, but it does not have to be a guess.

k = 1Overfit
Leave-one-out mistakes –
k = 5About right
Leave-one-out mistakes –
k = 21Underfit
Leave-one-out mistakes –
The same 49 points three times. Four stray points, two of each colour, sit in the wrong territory, and a small, real group of Sea points lives in the bottom-left corner. At k = 1 the string wraps the strays and carves islands. At k = 5 the strays are outvoted but the corner group keeps its territory. At k = 21 the corner group is outvoted too, and the map forgets it.

One honest way to choose: leave one out. Hide a point, predict it from the others, and check. Repeat for every point and count the mistakes. Do this for each k and pick the one that embarrasses the rule least. The counts under the three panels come from exactly this.

The boundary in 3D

With three measurements per example, the dots float inside a cube and the string becomes a sheet: a surface that splits the cube into Sand territory and Sea territory. The tension story is the same. 1-NN crumples the sheet around every stray point and blows bubbles around outliers; a larger k irons it flat.

Drag either cube to turn both. Scroll or pinch to zoom, and keep zooming to step inside and look at the sheet from within. Zones fills the cube with the rule's answer at every spot. Sheet keeps only the spots where the answer flips, so you see the boundary itself. The ◆ sits on a disputed spot: 1-NN and 3-NN disagree about it.

Show
Right cube k
View
Looking from outside
1-NNTight
3-NNSmoother

44 training points, 22 of each class, with the two groups overlapping in the middle of the cube. Drag to turn, scroll or pinch to zoom, arrow keys and + / − work too.

Breaking it

Since the data is the model, changing the data changes the answer. Three well-placed points can flip a vote. That is a feature when the points are honest examples and a bug when they are noise or a typo in a spreadsheet.

Ties are possible too: with two classes and even k, 2–2 is a real outcome. This page hands ties to the class of the closer neighbour. Notice how arbitrary that is. Every implementation picks some rule, and few mention it.

The catch: more dimensions

In the plane, “nearest” means something. A few neighbours really are close, and the vote is informed. Add features, and this quietly stops being true.

Here is the geometry. Take a box with sides of length 1 and shave 5% off every face, leaving an inner box with sides of 0.9. In one dimension the inner part is 90% of the whole. In two, 81%. In three, 72.9%. Each new dimension multiplies by 0.9 again, because the volume of a box is always the product of its side lengths, however many sides it has. By 50 dimensions the inside is half a percent, and 99.5% of the box is a thin skin near its faces.

d = 1Line
Inside: 90% of the length ·
d = 2Square
Inside: 81% of the area ·
d = 3Cube · drag, pinch
Inside: 72.9% of the volume ·
Share of the box that is inside (0.9d)Nearest ÷ farthest distance, 200 random points
200 random points in each box, coloured Sand when they land inside and Sea when they land in the skin. The chart continues the story to 50 dimensions, and adds the part that hurts k-NN: as d grows, the nearest of 200 random points is almost as far away as the farthest one.

Points scattered in a high-dimensional box are therefore almost all “far out”, and the gap between the nearest and the farthest neighbour shrinks until “nearest” is a technicality. This is the curse of dimensionality, and it is why k-NN wants few, carefully chosen features.