k-Nearest Neighbors

What you are looking at

Two classes of labelled examples, and one diamond that has no label. The question is what class the diamond should be, and k-nearest-neighbors answers it in one sentence: look at the nearest few examples and take whichever label most of them have.

That is the whole algorithm. There is no line to fit and no weights to solve for.

Training does nothing

Every other model in this section has a training step that produces something — a slope and an intercept, a set of weights, a set of centroids. k-NN produces nothing. Training is store the data.

All the work moves to prediction time instead. That is a real tradeoff, not a curiosity: free to train, expensive to answer. A model with a million examples has to consult a million distances for every single query, which is why the practical versions of this algorithm are mostly clever data structures for avoiding that.

Asking the neighbours

You move into a street and want to know which bin day it is. You could look up the council schedule, or you could ask the nearest few houses and go with the majority.

Ask one house and you inherit whatever mistake that one household makes. Ask everyone on the street and you get the answer for the street as a whole, which may be wrong for your end of it. Ask five nearby, and you have smoothed out the individual errors without losing the local pattern.

That number — how many neighbours to ask — is the only decision this model has, and nobody can make it for you from the data alone.

The boundary is not drawn

Turn to the third stage and the plot fills with shading. Nothing about that shading was computed as a boundary. Every cell was asked the same question the diamond was asked — "what do your nearest neighbours say?" — and shaded by the answer.

The frontier that appears between the two colours is the set of positions where the vote happens to flip. It is a consequence, not a definition. That is worth sitting with, because it explains the shape: k-NN boundaries are jagged and locally irregular in a way a fitted line never is, and no amount of tuning makes them smooth.

Notice the shading is not uniform. Where a region is washed out, the vote is close — a position that was nearly classified the other way. The boundary is a zone, not a line, and a model that reported only its final answer would hide that entirely.

The one dial, and both ways it fails

$k$ controls how far the model looks, and both extremes are broken in opposite ways.

At $k = 1$ every training point owns the territory closest to itself. The boundary threads between individual examples, so one mislabelled point carves out its own little island of wrong answers. The model has memorised the data, including its noise.

At $k = n$ every query consults every example, so every query gets the same answer. The boundary is gone. The model has stopped looking at the query at all.

Everything useful is in between, and where exactly is a property of your data rather than of the algorithm.

Accuracy on the training set is meaningless here

Score k-NN on its own training data with $k = 1$ and you get 100%, every time, on any dataset. Each point is its own nearest neighbour, so each point predicts its own label.

This is not a good model. It is a lookup table reporting that it can look things up. The readout in this lab uses leave-one-out instead — each point classified by all the others — which is the cheapest honest alternative and which drops sharply at $k = 1$, exactly as it should.

Ties are real

Set $k$ to an even number and watch for the callout. With two classes and an even $k$, the vote can split exactly, and at that point the rule has no answer.

Something still has to be returned, so implementations impose a tiebreak — this one gives it to whichever tied class owns the single closest point. That is deterministic and defensible, and it is still a decision made outside the data. An odd $k$ makes the situation impossible, which is the entire reason odd values are conventional.

Distance is a modelling choice

The lab uses straight-line distance, which quietly assumes both axes mean comparable things. They rarely do. Measure one feature in metres and another in kilometres and the metres will dominate every distance calculation, so the model will effectively ignore the second feature — not because it is uninformative, but because of the units it was recorded in.

This is why k-NN is normally preceded by scaling the features, and why it degrades badly in high dimensions: as you add axes, the distances between all pairs of points converge toward each other, and "nearest" stops meaning much.

What to take away

There is no fitted model here, only a rule and a dataset. The boundary is emergent, so it is shaped by where the examples happen to be. $k$ trades sensitivity to local structure against sensitivity to noise, and both ends of that trade are visible on the plot rather than something to take on trust.