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. In this class, two students typically sit about 19 points apart on previous score but under 4 hours apart on revision, so the score gap is about five times bigger, and it dominates the distance. 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.

Run the same comparison on a fresh class of 120 generated students: once in raw units, once with both features squashed onto 0 to 1.

import numpy as npfrom sklearn.model_selection import train_test_splitfrom sklearn.neighbors import KNeighborsClassifier rng = np.random.default_rng(4)n = 120hours = rng.uniform(0, 12, n)        # what actually predicts passingprevious = rng.uniform(20, 100, n)   # weakly useful, numerically hugepassed = hours * 7 + (previous - 60) * 0.2 + rng.normal(0, 6, n) > 42 X_raw = np.column_stack([hours, previous])X_scaled = np.column_stack([hours / 12, (previous - 20) / 80])   # both onto 0-1 for k in [1, 3, 7, 15, 31]:   # try your own k (odd, so votes cannot tie)    scores = []    for X in [X_raw, X_scaled]:        X_train, X_test, y_train, y_test = train_test_split(            X, passed, test_size=0.3, random_state=0)        model = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train)        scores.append(model.score(X_test, y_test))    print(f"k={k:2}   raw units {scores[0]:.0%}   scaled 0-1 {scores[1]:.0%}")

At k = 1 and 3 the two are close. From k = 7 the raw version falls apart, to 67%, then 58% and 56%, because a bigger vote reaches further and in raw units further means along the score axis. The scaled version holds at 92% to 94%.

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.