k-Nearest Neighbors
Predicts for a new point by finding the k most similar training examples and letting them vote. No real training step at all.
Also kNN · k-NN · nearest neighbor
Fix and Hodges, 1951; Cover and Hart, 1967
To guess whether you will like a movie, find the five people whose taste is most like yours and see what they thought of it.
Where it fits
+All relationships as a list
Is a kind of / part of
How it works
kNN is the “lazy” learner: it does nothing until you ask it something. Then:
- Measure the distance from the new point to every training point.
- Take the k closest ones.
- Classification: majority vote. Regression: average their values.
The choice of k controls smoothness. With k = 1 the model follows every individual point, noise included (overfitting). With a large k it averages over a big neighborhood and may blur real boundaries.
Do not confuse it with k-means: the “k” there is the number of clusters, and k-means is unsupervised. kNN is supervised and the k is the number of neighbors.
The idea is more alive than ever: modern similarity search over embeddings, including the retrieval step in RAG, is nearest-neighbor search at scale.
Everyday use cases
- Case 01
"People who liked this also liked"
Recommend items liked by the users most similar to you.
- Case 02
Similar-image search
Find the nearest neighbors of a photo's embedding to show look-alike pictures.
Strengths, weaknesses and when to use it
Strengths
- Trivial to understand and implement.
- No training time; new data is added by just storing it.
Weaknesses
- Slow predictions on big datasets without special indexes.
- Struggles in high dimensions, where everything is roughly equally far away.
- Sensitive to feature scaling.
When to use itFor small to medium datasets with meaningful distances, and as the core idea behind similarity search with embeddings.
Compare with
Check yourself
- Q01
What happens during kNN "training"?
Show answer
B: It just stores the training data
- Q02
Why should features be scaled before using kNN?
Show answer
A: Otherwise features with large ranges dominate the distance