k-Nearest Neighbours

A new observation arrives without a label. We have examples whose labels are known. A simple approach is to find the examples most like the new one and let their answers guide us.

Before a formula, follow which observations are consulted and how their answers become one prediction.

Move the ringed query point, then change k. Watch which stored points are selected and how their votes produce the label.

The dots in the box above are people we have already measured and labelled, amber for children and indigo for adults, placed by height and weight. The ringed point is someone new, measured but not yet labelled, and the question is which group they belong to.

The method answers the way a person would. Look at whoever the new arrival most resembles. The dashed lines reach out to the k stored people nearest the query, those neighbours each vote their own label, and the majority wins. Drag the ringed point around and watch the lines grab different neighbours and the answer follow.

This model stores the examples and their labels instead of solving for regression coefficients. Fitting may also build an index that makes neighbour searches faster. Most of the prediction work happens when a new query arrives: find nearby examples, then combine their answers. The choice of distance and the number of neighbours still need to be selected and evaluated.

The whole method is three steps, and the first is the linear algebra primer’s distance. Each person is a vector of measurements, and the distance between two people is the length of their difference.

distance = √((height₁ − height₂)² + (weight₁ − weight₂)²)

Compute that distance from the query to every stored person, keep the k smallest, and let those k labels vote, majority rules. That is the entire mechanism, which is itself the lesson. Where regression compressed the data into a few fitted numbers and then discarded it, this method keeps every example and compresses nothing.

The number k is the one dial, and it is kept odd here so a two-class vote cannot tie. What it trades is the subject of a later section, though the short version is that k sets how local the decision is, one neighbour listens to a single nearby voice, fifteen neighbours poll the whole neighbourhood.

Press the borderline case button, which places the query at a height of 150 cm and a weight of 45 kg, and work the distances by hand to the five people nearest it. Each difference below lands on a Pythagorean triple, four of them multiples of the linear algebra primer’s 3-4-5 triangle and one the 5-12-13, so every root comes out clean.

child at (147, 41)   difference (3, 4)     distance  5
adult at (156, 53)   difference (6, 8)     distance 10
child at (145, 57)   difference (5, 12)    distance 13
adult at (159, 57)   difference (9, 12)    distance 15
adult at (162, 61)   difference (12, 16)   distance 20

Now read the votes at each k, checking against the widget as you go. At k of 1 only the child at distance 5 is consulted, and the answer is child. At k of 3 the voters are two children and one adult, two to one, child again. At k of 5 the two adults at distances 15 and 20 join, the vote is three adults to two children, and the answer flips to adult.

Slide k from 3 to 5 above and watch that flip happen. Not one point moved and not one label changed, yet the answer reversed, because k decides how wide a circle of opinion is consulted, and this query sits close to a few children inside a neighbourhood that leans adult.

The shaded regions show the model’s answer at every spot on the plane, and sliding k redraws them in a way worth staring at. At k of 1 the map is jagged. Every stored person commands their own island of territory, including any point that sits oddly among the other class, so one mislabelled or unusual person creates a local prediction region around that example. That is memorising, the same failure the polynomial page met at degree 9, wearing a different costume.

Raise k and the islands dissolve. Each decision now polls a wider circle, stray voices are outvoted by their surroundings, and the frontier between amber and indigo smooths out. Push k toward the size of the whole dataset, though, and the poll stops being local at all, every query consults nearly everyone, and the answer drifts toward whichever class simply has more members.

Small k trusts each example too much, large k trusts the crowd too much, and the honest choice again needs data held out from the decision, the same open thread the penalty page left hanging.

One quiet assumption is doing load-bearing work in every distance above, and it is the method’s best-known trap. The distance formula adds the two squared differences as though a centimetre of height and a kilogram of weight were the same size of thing. Here that happens to be roughly fair, since the heights span about 65 units and the weights about 60, so both measurements get a real say.

Now imagine that height is recorded in millimetres. Height differences become numerically larger, so they contribute much more to the squared distance and can change which people count as nearest. This may help or hurt predictions depending on the dataset. The unit conversion alone gives us no reason to prefer the new weighting.

Here it does. Redo the worked example with every height multiplied by ten. The weight differences are what they were, the height differences are ten times larger and their squares a hundred times larger, so weight has almost no say left.

child at (1470, 41)   difference (30, 4)     distance ≈  30.27
child at (1450, 57)   difference (50, 12)    distance ≈  51.42
adult at (1560, 53)   difference (60, 8)     distance ≈  60.53
adult at (1590, 57)   difference (90, 12)    distance ≈  90.80
adult at (1620, 61)   difference (120, 16)   distance ≈ 121.06

The child at (145, 57) has overtaken the adult at (156, 53) for second nearest. In centimetres the adult was closer, since the child is twelve kilograms from the query in weight and the adult only eight, and that outweighed the child being one centimetre nearer in height. In millimetres the height differences are fifty and sixty, their squares dwarf anything the kilograms add, and the child’s one-centimetre edge decides it. The vote happens to survive, two children to one adult at k of 3 and three adults to two children at k of 5, but the ranking it rests on was reshuffled by a choice of unit that said nothing about anybody.

Scaling by each feature’s training standard deviation puts differences on a comparable numerical scale. This is a useful starting point, not proof that the features deserve equal predictive importance. Choose the scaling and distance with the task in mind, then evaluate them on held-out data.

On these eleven people that spread is about 22.8 cm for height and about 20.8 kg for weight, so dividing each difference by its own spread hands the two measurements a roughly equal say. The five neighbours then sit at these distances, measured in spreads rather than in any unit.

child at (147, 41)   ≈ 0.23
adult at (156, 53)   ≈ 0.47
child at (145, 57)   ≈ 0.62
adult at (159, 57)   ≈ 0.70
adult at (162, 61)   ≈ 0.93

That is the centimetre order back again, and the same five numbers come out whether the fit started from centimetres or from millimetres, because a difference ten times larger is divided by a spread ten times larger. The unit has been cancelled, which is all that standardising promises.

A method with no objective would seem to leave nothing to derive, though one piece of it can be earned rather than assumed, the vote itself. Why should the majority of the neighbours decide, rather than the single nearest one, or some fancier weighting?

Treat the k neighbours as a small poll of the query’s neighbourhood. If a fraction p̂ of them are adults, that fraction is our estimate of the chance that a person standing at the query’s spot is an adult, the statistics primer’s sampling idea pointed at a neighbourhood instead of a population. Now weigh the two possible answers against that estimate. Guess adult and the expected chance of being wrong is 1 − p̂. Guess child and it is p̂.

guess adult   when  1 − p̂ < p̂,   that is, when  p̂ > ½

If both kinds of mistake have the same cost, choose the class with the larger estimated local probability. With equally weighted neighbours, that gives a majority vote. This is optimal for the local estimate we just made; it does not prove the estimate matches the true population probability.

Read the worked example through this lens. At k of 3 one voter in three is an adult, at k of 5 three in five are, and the flip between them is the estimate crossing one half.

k = 3   p̂ = 1/3 < ½   guess child
k = 5   p̂ = 3/5 > ½   guess adult

An even number of neighbours can produce a tied two-class vote, which needs a stated tie rule. An odd count avoids that particular tie. It does not resolve equally distant candidates at the edge of the neighbourhood, and multiclass votes can tie even with an odd count.