Every other model on this site learns parameters. k-nearest neighbours learns nothing. It memorises the training set and answers new questions by looking things up — and it still works remarkably well.
How k-nearest neighbours works
Three steps, and that is the whole algorithm:
Distance is usually Euclidean — the straight-line distance you get from Pythagoras, generalised to any number of dimensions:
$$d(p,q) = \sqrt{\sum_{i=1}^{n}(p_i – q_i)^2}$$
That is exactly the L2 norm of the difference between two vectors. If your features are text or high-dimensional, cosine similarity is often a better distance measure.
Why k-nearest neighbours breaks without feature scaling
⚠️ This is the mistake that ruins most first attempts
Because k-nearest neighbours is defined by distance, any feature with a larger numeric range silently takes over. Always scale your features first. This is not optional here.
Choosing k
k is the only real decision you make, and it directly controls the bias–variance tradeoff.
| Value of k | Behaviour | Failure mode |
|---|---|---|
| k = 1 | Copies the single nearest point | Overfits — one mislabelled point creates a wrong pocket |
| k ≈ √n | A sensible starting guess | Tune properly with cross-validation |
| k = n | Every point votes | Underfits — always predicts the most common class |
Two practical tips: use an odd k for two-class problems so votes cannot tie, and choose k with cross-validation rather than by eye.
The unusual thing about training
The consequence is a real one. With 100,000 training rows, every single prediction requires 100,000 distance calculations. k-nearest neighbours is therefore a poor choice when predictions must be fast or the dataset is large — though structures like KD-trees and ball trees speed it up considerably in low dimensions.
The curse of dimensionality
k-nearest neighbours degrades badly as you add features, for a reason that is genuinely counter-intuitive: in high dimensions, everything is far from everything else, and roughly equally far.
🧪 Why distance stops meaning anything
Scatter the same 100 points in 100 dimensions and the nearest and furthest points end up at almost the same distance from you. “Nearest” stops carrying information, and a vote among neighbours becomes a vote among effectively random points.
Practical rule: with more than about 20 features, either reduce dimensions with PCA first, or use a different algorithm.
When to reach for it
Use k-nearest neighbours when your dataset is small to medium, you have few features, the decision boundary is irregular, and you want a strong baseline in five minutes. Recommendation systems built on “people similar to you” are k-nearest neighbours in spirit.
Avoid it for large datasets, high-dimensional data, or anywhere prediction latency matters.
🔑 Key Takeaways
- k-nearest neighbours predicts by voting among the k closest training points.
- There is no training — the model just stores the data, so prediction is the slow part.
- Feature scaling is mandatory, because the algorithm is built entirely on distance.
- Small k overfits, large k underfits; pick k with cross-validation and keep it odd for two classes.
- It degrades badly beyond roughly 20 features — the curse of dimensionality.
Further reading
scikit-learn’s nearest neighbours guide documents the distance metrics and the tree structures used to speed up search, and Wikipedia on the curse of dimensionality gives the mathematics behind the effect described above.
Where to go next
- k-means clustering — the next algorithm, and unsupervised
- Decision trees — the previous one, which needs no scaling at all
- Feature scaling — mandatory before you run this
- Start Here — the full learning path
Free guides to the mathematics behind machine learning — derived in full, written for people who never did a maths degree.