k-nearest neighbours (k-NN)
k-nearest neighbours labels a new example by finding the k most similar stored examples and taking their majority vote, or their average for numbers.
k-nearest neighbours, or k-NN, is a supervised method that predicts from the stored examples closest to a new one. It fits no general formula during training and simply keeps the labelled examples. To classify a new point, it finds the k closest examples and picks the class most of them share. For regression, it averages their values instead. In scikit-learn, k is set by n_neighbors, which defaults to 5. Despite the similar name, k-means is a different algorithm. It splits unlabelled data into k groups, so its k counts clusters rather than neighbours.
The rule is old. A 1967 paper by Cover and Hart credits Fix and Hodges, in a 1951 report, with the first rule of this kind. Cover and Hart then showed that, with enough data, using only the single nearest neighbour errs at most twice as often as the best possible rule.
Close needs a distance measure. In scikit-learn, one setting, p, gives Euclidean distance at 2 and Manhattan distance at 1. Closer neighbours can also get a bigger say, with each vote weighted by the inverse of its distance. Features should share a scale first, because the one measured in the biggest numbers dominates every distance. In scikit-learn’s wine example, proline runs from 0 to 1,000 while hue stays between 1 and 10. Unscaled distances then mostly ignore hue. The value of k is chosen by testing. Training error cannot choose it, but cross-validation error bottoms out very close to the best k.
All the work happens when a prediction is asked for. A brute-force search compares the new point with every stored example, so its cost grows with the number of examples and features. KD trees cut that cost when there are fewer than about 20 features, but lose their edge as the count grows. With many features, even the nearest examples can be far away. This is called the curse of dimensionality. The same search sits behind embeddings, where a short distance between two vectors means two similar items. For millions of vectors, the Faiss library builds an index that can trade some accuracy for speed. Its wiki gives the example of a wrong answer 10% of the time from a method 10 times faster. A GPU design from the Faiss authors built a k-nearest-neighbour graph over 95 million images in 35 minutes.
A model with a fixed shape can miss a pattern that has no simple shape.
Follow one new point through a k = 3 vote.
- 1 · storeTraining only keeps the labelled examples, sometimes inside a search structure such as a KD tree or ball tree.
- 2 · measureFor a new point, work out its distance to the stored examples, most often the straight-line Euclidean distance.
- 3 · sortRank the examples by that distance and keep the k closest.
- 4 · voteReturn the class most of those k share, or the average of their values for regression.
The main choice is k. A small k follows every quirk in the data, and a large k smooths the boundary toward a straight line.
| Who | What they ask | What it works with |
|---|---|---|
| Handwriting recognition | “Which digit is this scanned character closest to?” | Labelled images of handwritten digits |
| Search engineers | “Which stored passages sit closest to this query vector?” | Text embeddings held in a vector index |
| Fraud analysts | “Were past transactions that look like this one fraudulent?” | Scaled features of labelled past transactions |
| Shop recommendations | “Which products are most like the one this shopper just viewed?” | Product embedding vectors |
- Training is only storage, so there is no formula to fit before predicting.
- It can follow very irregular class boundaries.
- The same idea covers classification, by vote, and regression, by averaging.
- With enough data, even the single nearest neighbour errs at most twice as often as the best possible rule.
- It does not say which features matter, since there are no coefficients to read.
- Unscaled features distort it, because a feature with large numbers dominates every distance.
- Prediction is the slow part. A brute-force search grows with the number of stored examples times the number of features.
- With many features, even the nearest examples can be far away, and accuracy tends to fall.
Sources used
This explainer is written in original language. The links below support its factual claims.
- docs1.6. Nearest Neighbors (User Guide), scikit-learn · read 27 Sept 2026
- docsKNeighborsClassifier, scikit-learn · read 27 Sept 2026
- docsImportance of Feature Scaling, scikit-learn · read 27 Sept 2026
- paperAn Introduction to Statistical Learning (seventh printing), James, Witten, Hastie and Tibshirani (Springer) · read 27 Sept 2026
- paperNearest Neighbor Pattern Classification, Cover and Hart, IEEE Transactions on Information Theory (1967) · read 27 Sept 2026
- repoFaiss wiki, Meta (Faiss) · read 27 Sept 2026
- paperBillion-scale similarity search with GPUs, Johnson, Douze and Jégou (arXiv) · read 27 Sept 2026
- docsEmbeddings: Embedding space and static embeddings (Machine Learning Crash Course), Google for Developers · read 27 Sept 2026