k-Nearest Neighbours
Classify a point by asking its closest neighbours to vote.
How it works
k-nearest neighbours (k-NN) is probably the most intuitive classification algorithm there is. Its underlying idea is something people do every day: to guess something about a new case, look at the most similar cases you have already seen and go with what they say.
Unusually, k-NN has no real training phase. "Training" consists of simply storing all the training examples. For this reason it is called a lazy or instance-based learner: all the work is postponed until a prediction is needed. To classify a new point, the algorithm goes through three steps. First, it measures the distance from the new point to every stored training point. Second, it picks out the training points with the smallest distances, the "nearest neighbours". Third, it lets those neighbours vote, and predicts whichever class is most common among them. For regression, the third step instead averages the neighbours' target values.
The result depends on how "distance" is measured. The default is the ordinary straight-line Euclidean distance, . An alternative is the Manhattan distance, , which adds up the differences along each axis like a taxi driving on a grid of streets. For text and embeddings, cosine similarity, which compares directions rather than positions (see the vectors topic), usually works best. A common refinement is to give closer neighbours a bigger say, for example by weighting each vote by one over its distance.
One practical point is essential: the features must be scaled. Distances add up contributions from every feature, so a feature with large numbers dominates. If one feature is annual salary (tens of thousands of dollars) and another is age (tens of years), a difference of $1,000 in salary would count a thousand times more than a difference of one year in age, and age would effectively be ignored. Standardising every feature to a similar range before computing distances fixes this.
Interactive: this part runs in your browser.
Watch it: k-nearest neighbours: ask the closest examples
A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.
Interactive: this part runs in your browser.
Try it: choose k
Shaded regions show what k-NN would predict anywhere on the plane. Click to drop a test point.
Interactive: this part runs in your browser.
Strengths and weaknesses
k-NN has real strengths. It is simple to understand and explain; it needs no training; it naturally handles any number of classes; and because it makes no assumption about the shape of the decision boundary, it can follow curved and irregular boundaries that would defeat a linear model. Adding new data is trivial, since you just store the new examples.
Its weaknesses are equally real. Prediction is slow, because a naive implementation must compute the distance to every training point for every prediction; with millions of examples this becomes expensive. Clever data structures such as KD-trees and ball trees speed up the search when there are few features, and for large-scale problems, approximate nearest-neighbour libraries such as FAISS find neighbours that are almost always the true nearest ones at a fraction of the cost. k-NN is also sensitive to feature scaling (as discussed above) and to irrelevant features, which add noise to every distance without adding information.
Its most fundamental weakness is the curse of dimensionality. As the number of features grows, the space they define becomes so vast that the data are spread extremely thinly, and the distances from a point to its nearest and farthest neighbours become almost the same. When every point is roughly equally far away, "nearest" stops meaning "most similar", and k-NN loses its basis. The Advanced section quantifies this effect.
Two practical guidelines help when using k-NN. Choose with cross-validation rather than guessing; as the demo showed, small overfits and large underfits. And for two-class problems, use an odd value of , so that the vote can never be a tie.
Interactive: this part runs in your browser.
k-NN formally, and how good can it be?
k-NN estimates "what's the probability of each class here?" by simply looking at the nearby training points and counting. With more and more data, this local vote becomes almost as good as knowing the true probabilities. Even the crudest version (k = 1) is at most twice as bad as the best possible classifier.
🔤 Symbols in this section
| the k nearest training points to x | |
| Minkowski distance (p = 1 Manhattan, p = 2 Euclidean) | |
| 1 if neighbour i is class c | |
| Bayes error: lowest achievable error | |
| error rate of 1-nearest-neighbour |
This section states k-NN precisely and then looks at a classic result about how good it can be.
Let be the set of the training points closest to a query point . Closeness is measured with a distance function; a general family is the Minkowski distance, , where gives the Euclidean distance and the Manhattan distance. The predictions are then
The indicator equals 1 when neighbour belongs to class and 0 otherwise, so the classification formula is simply the fraction of neighbours in class .
This reveals what k-NN is really doing. The best possible classifier, called the Bayes classifier, would know the true probability of each class at every point and always predict the most probable class; its error rate, the Bayes error , is the lowest error achievable on that problem, because some cases are genuinely ambiguous. k-NN imitates the Bayes classifier by estimating those class probabilities locally, from the labels of nearby examples, and then predicting the most probable class.
How well can such a simple method do? In 1967, Cover and Hart proved a remarkable result for the simplest version, 1-nearest-neighbour. As the amount of training data grows without limit, its error rate satisfies
In words, the crudest possible nearest-neighbour rule is never more than twice as bad as the best possible classifier, given enough data. If is allowed to grow with the amount of data, but more slowly (so that while ), k-NN becomes consistent: its error converges all the way down to the Bayes error.
The choice of is a bias–variance trade-off that can be seen directly in the regression formula. Averaging noisy labels reduces the variance of the prediction to about , so larger gives smoother, more stable predictions. But the more neighbours we include, the farther away the most distant ones are, and the less they resemble the query point, so the prediction becomes biased towards the general average. Small means low bias and high variance; large means the reverse.
The curse of dimensionality, quantified
In high dimensions, space is enormous and mostly empty. To include even a few neighbours you have to reach so far that they're no longer similar, and all points end up roughly the same distance apart. So "nearest" stops meaning "similar", unless the data actually lives on a lower-dimensional structure, as real data often does.
🔤 Symbols in this section
| number of dimensions (features) | |
| fraction of the data to capture | |
| edge length of the cube needed | |
| cost grows with examples × dimensions |
The curse of dimensionality is the reason k-NN, and distance-based methods generally, struggle with many features. Two simple calculations show why.
Neighbourhoods stop being local. Suppose the data are spread uniformly through a unit hypercube in dimensions, and we want a small cube around a point that contains a fraction of all the data. A cube with edge length has volume , so we need , which gives
In one dimension, capturing 10% of the data needs an interval covering 10% of the range, as you would expect. But in ten dimensions, capturing just 1% of the data needs , a cube spanning 63% of the range of every feature, and capturing 10% needs . So in ten dimensions, a point's "neighbourhood" stretches across most of the space, and its nearest neighbours can differ from it substantially in most features. They are no longer genuinely similar.
Distances concentrate. A related effect is that, for many data distributions, the distances from a point to all the others become nearly equal as the dimension grows. Formally, the relative gap between the farthest and the nearest neighbour shrinks towards zero:
When the nearest point is barely nearer than the farthest, ranking points by distance carries almost no information.
Fortunately, real data rarely fill high-dimensional space uniformly. Images, text and sounds usually lie close to a much lower-dimensional surface, or manifold, within the full space: the set of realistic faces, for instance, is a tiny, structured subset of all possible pixel arrays. That is why k-NN works well on good embeddings, learned representations in which similar items are close together, even when those embeddings have hundreds of dimensions. Reducing dimensionality with PCA before running k-NN can also help.
Computational cost. A brute-force search compares the query with every training point, costing time proportional to per prediction. Tree-based indexes (KD-trees and ball trees) partition the space so that most points can be ruled out without being examined, giving roughly logarithmic search time when the dimension is low, but their advantage fades above about 20 dimensions, again because of the curse of dimensionality. For large collections of high-dimensional vectors, approximate nearest-neighbour (ANN) methods, such as graph-based HNSW indexes and the product-quantisation techniques in the FAISS library, trade a tiny amount of accuracy for enormous speed-ups. They are the engines behind vector databases and the retrieval step of retrieval-augmented language models.
Code: vectorised k-NN and a tuned scikit-learn model
The from-scratch version computes all distances at once using .
import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
X, y = load_wine(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)
mu, sd = Xtr.mean(0), Xtr.std(0) # scale using TRAIN statistics only
Xtr, Xte = (Xtr - mu) / sd, (Xte - mu) / sd
def knn_predict(Xtr, ytr, Xq, k=5):
# squared Euclidean distances, shape (n_query, n_train), no Python loops
d2 = (Xq ** 2).sum(1)[:, None] + (Xtr ** 2).sum(1)[None, :] - 2 * Xq @ Xtr.T
nn = np.argpartition(d2, k, axis=1)[:, :k] # indices of k nearest (unordered)
votes = ytr[nn]
return np.array([np.bincount(v).argmax() for v in votes])
for k in [1, 5, 15]:
print(f"k={k:2d} accuracy:", np.mean(knn_predict(Xtr, ytr, Xte, k) == yte).round(3))from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV
X, y = load_wine(return_X_y=True)
pipe = make_pipeline(StandardScaler(), KNeighborsClassifier())
grid = GridSearchCV(pipe, {
"kneighborsclassifier__n_neighbors": range(1, 31, 2),
"kneighborsclassifier__weights": ["uniform", "distance"],
"kneighborsclassifier__p": [1, 2], # Manhattan vs Euclidean
}, cv=5).fit(X, y)
print(grid.best_params_, round(grid.best_score_, 3))Quiz
1. k = 1 in k-NN tends to…
2. Why must features be scaled for k-NN?
3. k-NN is called a "lazy" learner because…
4. Cover & Hart: asymptotically, 1-NN error is at most…
5. In 10-D, a cube capturing 10% of uniform data needs edge length about…
📚 Further reading
Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.
- scikit-learn: Nearest neighbours ↗ Official guide
- An Introduction to Statistical Learning (free book) ↗ James, Witten, Hastie, Tibshirani (Python edition available)