k-Nearest Neighbours

You've probably heard some version of the saying: "you are the average of the five people you spend the most time with." It's a folk theory of personality — to guess what someone is like, just look at who they hang around with and take the majority view.

k-nearest neighbours (k-NN) is that folk theory turned into an algorithm, and it might be the simplest classifier there is. To label a brand-new example, k-NN doesn't build a model of the data at all. It just finds the k training examples that are closest to it, and lets them vote. Whichever label the majority of those neighbours have, the new point gets too.

"Closest" means smallest distance in feature space — the length of the difference between two feature vectors, the same idea behind the dot product. Once your data is a list of numbers (a vector), "closest" has a precise meaning, and k-NN is almost free to describe.

The recipe

There is no fitting, no equation to solve, no gradient to descend. Given a new point x, k-NN does exactly three things:

Compute the distance from x to every point in the training set (commonly the Euclidean distance, d = \sqrt{(x_1-p_1)^2 + (x_2-p_2)^2 + \cdots}).
Keep the k training points with the smallest distance — the "nearest neighbours."
Predict the label that appears most often among those k neighbours (a majority vote).

That's the whole algorithm. There's no separate "learning" step that happens beforehand — which, as we'll see, is both k-NN's charm and its biggest drawback.

Euclidean distance — "as the crow flies" — is the usual default, but it isn't the only choice. Some versions of k-NN instead add up the distance along each feature separately (called Manhattan distance, like counting city blocks instead of cutting diagonally across them). The vote-counting step never changes; only the ruler used to decide "closest" does.

Worked example: will the new student pass?

Ten students have already sat an exam. For each one we recorded how many hours they studied and their score on a practice test out of ten, plus whether they went on to Pass or Fail the real exam:

Student	Hours studied	Practice score	Result
F1	2	2	Fail
F2	3	3	Fail
F3	2	4	Fail
F4	4	3	Fail
F5	8	3	Fail (was ill on the day!)
P1	7	7	Pass
P2	8	8	Pass
P3	9	7	Pass
P4	7	9	Pass
P5	8	6	Pass

A new student studied 7 hours and scored 4 on the practice test: the query point (7, 4). Will they pass? Compute the distance from (7,4) to every training point using d = \sqrt{(\Delta\text{hours})^2 + (\Delta\text{score})^2} and sort:

Rank	Student	Distance	Result
1	F5 (8, 3)	1.41	Fail
2	P5 (8, 6)	2.24	Pass
3	P1 (7, 7)	3.00	Pass
4	F4 (4, 3)	3.16	Fail
5	P3 (9, 7)	3.61	Pass
…	(five more, all farther away)	≥ 4.12	—

With k=3, the three closest students are F5 (Fail), P5 (Pass), P1 (Pass) — two Pass votes beat one Fail vote, so k-NN predicts Pass.

Now watch what happens at the extremes. With k=1, the single nearest neighbour is F5 — the student who studied plenty but happened to fail (bad luck on exam day). k-NN copies that one neighbour exactly and predicts Fail. With k=5, the vote is F5 (Fail), P5 (Pass), P1 (Pass), F4 (Fail), P3 (Pass) — three Pass to two Fail — so the prediction flips back to Pass. Same student, same data, different answer — purely because of how many neighbours were allowed to vote.

Try it yourself

Move the grey query point through the data below and choose how many neighbours k get a vote. The k nearest examples light up, and the query is coloured by their majority. Drag the query near the boundary between the two clouds and watch the prediction flip as you cross it — or leave the query still and just change k instead. A single stray point near the border can behave just like F5 did above: enough to swing a small-k vote, but outvoted once k grows.

The "lazy learner"

Compare this with something like logistic regression. Logistic regression spends effort up front: it churns through the training data once, fits a set of weights, and then throws the training data away — a new prediction is just a quick calculation with those weights.

k-NN does the opposite. There is no fitting stage at all — "training" a k-NN model means nothing more than filing the training data away unchanged. All of the real work is deferred until someone actually asks for a prediction, at which point k-NN must measure the distance from the query to every single stored training point, sort them, and count votes. That's why k-NN is often called a lazy learner: it puts off all its effort until the last possible moment, and pays for that laziness at prediction time instead of at training time. With a training set of a few hundred points this is instant; with millions of points, every single prediction gets slow.

The algorithm is simple, but that simplicity hides some sharp edges:

Too small a k is jumpy. With k=1, a single noisy or mislabelled point — like F5 above, who studied hard but failed anyway — can single-handedly flip a prediction. Small k chases every little bump in the data.
Too large a k blurs everything together. Push k all the way up and the vote starts pulling in points from far outside the query's real neighbourhood, washing out genuine local patterns until every prediction just echoes the overall majority class. This is one face of the general underfitting and overfitting trade-off you'll meet again and again in machine learning: tiny k overfits to noise, huge k underfits and ignores structure.
Raw feature scales can silently take over. If one feature is measured in the thousands (say, a house's price) and another ranges from 0–10 (say, its number of bedrooms), the distance formula is almost entirely determined by whichever feature happens to have bigger numbers — regardless of which feature actually matters. This is exactly why feature scaling matters so much for distance-based methods like k-NN.

Because k-NN never "trains" in the usual sense, it's a natural fit for systems where new data keeps arriving — like a shop's "customers similar to you also bought…" recommendations. The moment a new customer's purchases are recorded, they're simply another point sitting in the data; the very next recommendation query can already treat them as a potential neighbour. A model like logistic regression would need to be re-fitted from scratch to take the new data into account; k-NN just quietly has more neighbours to search through.

There's no formula that hands you the "correct" k for a given dataset — it depends on how noisy the data is and how the classes are shaped. In practice, people usually just try several values (say, 1, 3, 5, 7, 11 …) and check which one predicts best on data the model hasn't seen before. Compared with more "theoretical" methods that derive their settings from calculus or probability, choosing k for k-NN is refreshingly — almost suspiciously — hands-on: try it, measure it, and see.