k=1
2,000 new houses the town’s own 240

Who are yourneighbours?

The Line That Leans’ two crowds, as a town: 120 navy houses and 120 white. A new house goes up where they meet. To choose its colour it asks the 5 houses nearest to it, and takes their vote: 3 navy, 2 white. Navy.

navy housewhite housethe new house

Nearest meansa ruler.

distance = √(east² + north²)

“The square root of the east gap squared plus the north gap squared.” Pythagoras: as the crow flies, not along the streets.

The fifth neighbour is 0.11 m east and 0.22 m north: √(0.11² + 0.22²) ≈ 0.25 m. The nearest is 0.09 m away.

Any numberof directions.

distance = √( Σ (aj − bj)² )

“Square the gap in every feature, add them all up, take the square root.”

Two features make a map. A house could also be described by 10 features, or 1,000, and the formula does not change. Hold on to that: it comes back.

One neighbour,one lot.

Ask only the single nearest house, k = 1, and the map splits into lots: every spot belongs to the house it is closest to. The lines are where two houses are exactly as far away. Mathematicians call this a Voronoi diagram.

Perfect at home.

Paint each lot its house’s colour. Ask about the town’s own houses and each one finds itself: 100% right. Ask about 2,000 new houses the town has never seen and it gets 82.0%; the misses flash in their true colour. It did not learn the crowds. It memorised the town.

The townvotes.

Every spot on the plan asks the new house’s question. Your graphics card runs 3.69 million votes, one per point, each measuring the distance to all 240 houses. Navy ground rises and white ground sinks, as far as the vote was lopsided. An even vote is sea level, so the border is the coastline.

Turn the dial.

At k = 1 every lot is all or nothing, and stray houses keep islands of their own. Ask more neighbours and the steps wear down into hills. The dashed line scores the town’s own houses: 100% at k = 1. The solid line scores the 2,000 new houses: 82.0% at k = 1, 86.6% at k = 11.

A long flat top.

The best on this draw is k = 145: 88.8% of the new houses right. Every k from 31 to 239 lands within one point of it. These two crowds really are split by a near-straight line, so smooth hills cost little here.

At 239, thetown sinks.

Now every house but one votes on every question, so every vote is 120 to 119 and the whole plan lies a hair from sea level. No answer is sure. The border survives because the one house left out, the farthest, usually belongs to the other crowd: still 87.9% right.

Now measure northin millimetres.

Same houses, same places. Only the second number changes: it is now written in millimetres, 1,000 times bigger, while east stays in metres. This is our construction, to show what units do. Here is the plan in metres, at k = 5.

North decideseverything.

One millimetre north now counts as much as a whole metre east, so a house’s neighbours are whoever stands at almost the same northing. The plan turns to stripes. The new house’s five nearest change: 3 white, 2 navy, and it turns white. 1,997 of the 2,000 new houses get a different five, and the score falls from 84.5% to 74.5%.

Give every featurean equal say.

z = (x − mean) ÷ spread

Standardise: subtract each feature’s mean, divide by its spread. Then metres or millimetres make no difference at all: all 2,000 neighbour sets are identical either way, the new house gets its five back, and the score is 84.8%. Downhill’s ravine was the same problem: one feature on a bigger scale bent the bowl out of shape.

d = 2its nearest house is 2.3% of the way to its farthest

Everyone is far.

Give every house, and the new one, up to 998 more features of pure noise. On the plan the new house’s nearest neighbour is 2.3% as far away as its farthest. With 1,000 features it is 90.2% as far: every house is nearly the same distance away, and its five neighbours melt into the crowd.

Nearest stops meaning much.

Give each house 998 extra features of pure noise and the vote fades: at k = 145, 88.8% right with the 2 real features, 67.4% with the noise beside them. The noise features are our construction, added to show the effect.

Swap the votefor an average.

Give every house a number instead of a colour: a price, in thousands (ours is invented: higher to the north-east, plus noise). Every spot now stands at the mean price of its five nearest, and the new house comes out at 522. Same ruler, same k, same neighbours. That is nearest-neighbour regression.

Same ruler,same traps.

Measure north in millimetres and the new house’s five change: its price jumps to 556. Standardise, and it is 522 again. The features still need an equal say. The price itself needs no scaling: the average of five prices is already a price.

Parametric:three numbers.

Where is the model? Episode 1 fitted a line and could then throw its data away: two numbers were the model. For prices that is this sheet, price = 508 + 74 × east + 65 × north, fitted once to all 240 houses. Three numbers are the whole model.

Non-parametric:every house.

Nearest neighbours has no numbers to keep. The 240 houses are the model, kept whole and searched at every question, and their shape can be anything the town is. The hills are back. For the new house the sheet says 518; its five nearest say 522.

Your town.

Turn k, switch north to millimetres, or tap the plan to build houses. Every question searches the whole town, which is why real systems use indexes such as k-d trees. Try the two moons, where the border curves: k = 1 gets 92.5% of 200 new points, k = 5 gets 93.5%, and k = 199 only 66.5%.

One neighbourmemorised the town.

Two hundred and thirty-nine shrugged. Somewhere between is the trade every model makes, and the only way to find it is an exam the town has never seen. Next: The Trade. Then how to set that exam without cheating: The Honest Exam.