k-Nearest Neighbours

Here is the whole algorithm. Keep every example you were given. When a new case arrives, find the handful most similar to it, and answer whatever they answered.

That is it. There is no equation, no slope to find, no bowl to roll down. Training consists of writing the data to disk. People call it a lazy learner, which is accurate rather than rude: it defers all the work to the moment you ask it something.

The consequences are immediate. It costs nothing to train and a great deal to use, which is the opposite of every model you have met. It can express a wildly complicated boundary without anybody designing one. And it cannot tell you why it answered — the justification is a list of neighbours, not a rule.

Below are fifty-four students, placed by how long they revised and what they scored on the previous exam. The cross is somebody new. The lines run to the students the model considers nearest, and those students vote.

Start on Ten hours in. Every neighbour agrees, the vote is lopsided, and moving k changes nothing. Most predictions look like this, which is exactly why a model that gets the easy cases right has told you almost nothing.

Now switch to On the fence and walk k upward. At k=1 the answer is fail. At k=5 it is pass. At k=7 it is fail again. The student has not moved. The data has not changed. The only thing you altered was how many opinions to collect.

k is the one dial this model has, and it is the same dial you met two lessons ago wearing a different coat. At k=1 every training point gets its own little island of territory, and the model reproduces the training data perfectly — including its mistakes. That is overfitting, arrived at by a completely different route. Push k toward fifty-four and every query returns the majority class no matter where it sits. That is underfitting.

The strip under the scatter plots accuracy at every k. The rescaled line climbs from 83% at k=1 to about 91% by k=15. The raw line does the opposite: it starts at 78% and sags to 63%. Twenty-eight of these fifty-four students failed, so a rule that ignores the data entirely and says “fail” every time already scores 52%. At k=15 the raw model is worth eleven points over knowing nothing.

The raw line falling apart is not a quirk of this dataset. It is the flaw that makes this model worth teaching.

“Nearest” means nearest by some measurement, and the obvious measurement is straight-line distance. Revision hours run from 0 to 12. Previous scores run from 20 to 100. A gap of ten points on the previous exam and a gap of ten hours of revision count the same in that sum — and since the score axis is roughly eight times wider, it contributes roughly eight times as much. The model is not weighing your features. Your units are.

Select Coasting on a good record: two hours of revision, a previous score of 80. In raw units the five nearest are whoever else scored around 80, three of whom passed, so the answer is pass. Rescale both features to run 0 to 1 and the neighbours become people who also barely revised. Five of five failed. Same data, same k, opposite answer.

Grinding with a bad record is the mirror image and the more expensive error. Nine hours of revision, a weak previous score. Raw distance writes the student off three votes to two, on the strength of a number they have already done the work to overturn.

One caution that will matter later: work out the scaling from the training data alone. If you compute the minimum and maximum across the whole dataset before splitting, the test set has already influenced how the training set is represented. That is a small leak, and leaks get a chapter of their own in Part 4.