Nearest neighbours

A new point has no label. Who are its nearest neighbours, and what do they say? Before the clip plays, a question: $k=1$ makes no mistakes on the training dots; will it also do best on new dots?

Asking the nearest examples

Each example here is a point whose two coordinates are its two measurements, its features; Data as points in space builds that picture slowly. Its class, A or B, is its label. There are $m=100$ examples. Statistics writes $n$ for a sample size; on these pages $m$ counts examples.

To label the grey point, I look for the 7 training dots closest to it and count their labels. Four are B and three are A, so I call it B. That is the whole method: ask the $k$ nearest training examples, and take their vote.

“Nearest” needs a distance. Write example $i$ as the vector $\mathbf{x}_i$, with $q$-th feature $x_{iq}$, and the new point as $\mathbf{x}$, with features $x_q$. With $d$ features, the distance between them is the length of their difference, as in Length and the dot product:

Here $d=2$. Sort the training examples by this distance and keep the first $k$. I call their indices $I_k(\mathbf{x})$. If two examples sit at exactly the same distance, the one with the lower index $i$ goes first. With labels $y_i$, the prediction $\hat y$ (the hat marks a guess) is

With two classes and an odd $k$, the vote can never tie. That is why the slider takes odd values only.

Distance treats every feature alike, so the units matter: a feature in millimetres outweighs one in metres. Data as points in space shows how to put features on one scale.

Decision regions and the boundary

Nothing stops me from asking the vote for every point of the plane, not only for the grey one. The instrument does that on a grid of 120 by 90 cells and tints each cell with the winning class. The cells that vote A form the decision region of A, the rest form the region of B, and the line where the two meet is the decision boundary.

Drag $k$ from 1 up to 29 and watch the regions. At $k=1$ each training dot claims the space nearest to it, so a stray dot inside the other crescent owns an island of its own. On these dots there are four. At $k=3$ two are left, from $k=7$ none, and by 29 the boundary is a smooth curve between the crescents.

A small $k$ follows every stray dot. A large $k$ averages over many dots and draws a smoother boundary, but past some size it starts to miss real detail in the shape. The number of neighbours asked is a choice the data do not make for me.

Why k = 1 makes no training mistakes

Now the question from the top of the page. Ask a training dot for its own label with $k=1$, and its nearest training example is itself, at distance 0. So it always gets its own label back, and the training readout shows 0 mistakes. At $k=3$ the same readout shows 7. Judged on the training dots, $k=1$ looks perfect.

That proves nothing, because the method has seen those dots. The honest test is the second readout: 100 new dots from the same two crescents, which the method never saw. There $k=1$ makes 14 mistakes, the most of any $k$ on the slider; the clip’s other stops, 3, 7, 15 and 29, make 7 to 9. Some of those mistakes fall inside the islands that made the training count perfect: 5 of the 14.

A hundred new dots are too few to name a best $k$: the counts for the larger $k$ differ by only a few dots, and a different hundred could put them in a different order. Bias and variance of a model explains why $k=1$ sits at the jumpy end, and Validation and cross-validation shows how to choose $k$.

Predicting a number

The labels need not be classes. If each example carries a number, say a temperature, the $k$ nearest examples give their average instead of a vote:

The same choice of $k$ applies: a small $k$ follows each nearby reading, a large one smooths over many.

The cost of a prediction

There is no training step. The method keeps all the examples, and that is all it keeps: there is no formula inside it. The work comes at prediction time. To label one new point it computes $m$ distances, each a sum of $d$ squares, and finds the $k$ smallest. With a million examples, every single prediction means a million distances. Practical systems store the examples in search structures that skip most of them, but the data still have to be kept.

There is a second cost, in many features. Suppose the examples are spread evenly through a cube whose edges run from 0 to 1, one edge per feature. A smaller cube that holds 1 % of them needs edges of length $0.01^{1/d}$, and that edge grows quickly with the number of features $d$:

With 100 features, the “neighbourhood” of 1 % spans almost the whole range of every feature. The nearest examples are then not near in any useful sense, and the vote says little.

Worked example

Six training dots: class A at $(2,3)$, $(1,2)$ and $(5,1)$; class B at $(4,2)$, $(3,5)$ and $(6,3)$. The new point is $\mathbf{x}=(3,3)$. I list the dots by distance from it:

No two distances are equal, so the tie rule is not needed.

• $k=1$: the nearest dot, $(2,3)$, is A, so the answer is A.
• $k=3$: the first three are A, B, B. B wins 2 to 1, so the answer is B.
• $k=5$: add $(1,2)$ and $(5,1)$, both A. A wins 3 to 2, so the answer is A.

One point, three answers.

Predicting a number. Three weather stations are nearest to a farm, and they read 10, 14 and 12 °C. With $k=3$ the prediction for the farm is their average, $(10+14+12)/3=12$ °C.

The cost. With $m=1\,000\,000$ examples and $d=2$ features, one prediction computes a million distances of two squared differences each.

Where you’ll meet this

Recommendations. “People whose ratings are nearest to yours liked this” is a nearest-neighbour vote, with each person a point whose features are their ratings.

Matching faults. A machine’s vibration is summarised as a few numbers and compared with records of past faults; the nearest past records name the likely fault.

Reading handwriting. Matching a scanned digit to its nearest stored examples is a common first method, a baseline that other methods must beat.

Reference card