Definition
k-nearest neighbors (k-NN) classifies a new point by finding the training points closest to it under a distance metric and letting them vote: the predicted class is the one most common among those neighbours, and the vote shares are its class probabilities. Nothing is fitted. The stored training set is the model.
At a glance
- Task
- Classification (this article); the same recipe with an average instead of a vote gives KNN regression
- Input → output
- query → class probabilities = (weighted) share of the neighbours in class , and
- Learns
- nothing: it memorises all labelled pairs (a lazy, instance-based learner)
- Training cost
- to store; if you build a KD-tree or ball tree for faster search
- Prediction cost
- per query by brute force (plus to select the smallest); roughly with a tree index in low dimension
- Hyperparameters
n_neighborsk,weights(uniform or distance), the metric (pfor Minkowski, or any custom distance), the searchalgorithm- Assumes
- points that are close under your metric tend to share a label; all features are on comparable scales and actually relevant
The problem
Most classifiers commit to a shape for the decision boundary before they see data. Logistic regression draws a straight line (a hyperplane); a decision tree draws axis-aligned boxes; Naive Bayes assumes features are independent within each class. When the true boundary is curved, wiggly, or made of several disconnected islands, these shapes fit it badly unless you hand-engineer features.
There is a much weaker assumption that holds for an enormous range of problems: similar inputs have similar labels. Two emails with almost the same words are probably both spam or both not; two tumours with nearly identical measurements probably share a diagnosis. k-NN turns that single assumption into a classifier with no parameters to fit and no boundary shape to choose. The price is paid at prediction time, and in the need for a distance that genuinely captures "similar".
The idea
To label a new point, look at the training points around it and copy the local majority. Picture the data as coloured dots on a map. Drop the query on the map, draw the smallest circle around it that contains dots, and count colours. The circle's radius adapts automatically: in dense regions it is small and the prediction is very local; in sparse regions it grows until it has gathered enough evidence.
controls how much evidence you demand. With you copy the single nearest point, so every training point owns a little territory around it (its Voronoi cell) and the boundary bends around every outlier. With large the vote averages over a wide neighbourhood: the boundary becomes smooth, but small or minority regions get out-voted. At the extreme , every query sees the whole dataset and k-NN predicts the majority class everywhere.
Vocabulary
- Query point q
- the unlabelled input you want a prediction for
- Neighbourhood N_k(q)
- the indices of the training points with the smallest distance to
- k-th neighbour distance
- , the distance to the farthest member of : the radius of the smallest ball around holding points
- Metric
- the distance function ; Euclidean (), Manhattan () and cosine are the usual choices
- Uniform vs distance weighting
- each neighbour casts one vote, or a vote of weight so that closer neighbours count more
- Voronoi cell
- the region of space closer to one training point than to any other; the 1-NN decision regions are unions of these cells
- Lazy learner
- a method that defers all work to prediction time; the opposite (eager) learners compress data into parameters during training
- Leave-one-out (LOO)
- predict each training point from all the others; for k-NN it is cheap and the standard way to pick k on small data
The math
Everything depends on the distance. The Minkowski family covers the common cases:
- the query and a training point, both in
- their -th features
- Euclidean (straight-line), Manhattan (sum of absolute differences), the largest single difference
The unit "ball" of changes shape with : a circle for , a diamond for , a square for . is less dominated by one large coordinate difference than , which squares it. Given a metric, the classifier is a vote over the neighbourhood:
- the training indices nearest to
- 1 if neighbour has class , else 0
- vote weight: (uniform) or (distance weighting)
- estimated probability of class at : the (weighted) fraction of neighbours in class
With uniform weights, , where is the number of neighbours in class . With these probabilities can only be : k-NN probabilities are coarse, and you need a larger for smoother ones.
Why voting is the right thing: k-NN as density estimation
The vote is not an ad-hoc rule; it falls out of Bayes' rule with a local density estimate. Grow a ball of volume around until it contains points, of them from class . If class has training points in total, the fraction of them inside the ball estimates its probability mass there, so the class-conditional density is about
- volume of the smallest ball around holding training points (radius )
- training points in class , and in total
- neighbours of that belong to class
Plug these into Bayes' rule . The volume and the counts , all cancel:
So majority voting is the Bayes classifier applied to a nearest-neighbour density estimate, and the vote shares are genuine (if noisy) posterior estimates. It also explains the bias–variance trade-off of . The estimate is a proportion over samples, so its variance is about : small gives noisy probabilities. But the ball must grow to hold points, and the larger it is, the more it averages over regions where differs from : large gives biased, over-smoothed probabilities. Consistency theory makes this precise: k-NN converges to the Bayes-optimal classifier as provided and .
Distance weighting replaces with . It makes the prediction depend continuously on how close each neighbour is, reduces the sensitivity to the exact choice of (far neighbours barely count), and breaks ties. If coincides with a training point, and that point takes all the weight (scikit-learn's convention), so distance-weighted k-NN, like 1-NN, always reproduces its training labels.
Scale. Every metric above adds up raw feature differences, so a feature measured in large units dominates. The standard fix is to standardise each feature, , which is the same as using a diagonal Mahalanobis distance:
- a positive-definite matrix; is Euclidean, (inverse covariance) is the full Mahalanobis distance
- standard deviation of feature on the training set
Learning from labels (so that same-class points end up close) is called metric learning; NCA and LMNN are the classical methods. In deep learning the same idea appears as training an embedding network and running k-NN on its outputs.
Worked example: is a tomato a fruit?
Fourteen foods, scored 0–10 for sweetness and crunchiness (both features already on the same scale, so no standardisation is needed), and labelled fruit or vegetable. The query is a tomato: sweetness 6, crunchiness 4. Botanists and cooks disagree about tomatoes, and so, it turns out, do different values of .
| # | Food | Sweetness | Crunchiness | Class |
|---|---|---|---|---|
| 1 | peach | 7 | 4.5 | fruit |
| 2 | orange | 8 | 3 | fruit |
| 3 | pear | 7.5 | 6 | fruit |
| 4 | apple | 9 | 8 | fruit |
| 5 | banana | 10 | 1.5 | fruit |
| 6 | grape | 8.5 | 5 | fruit |
| 7 | bell pepper | 5 | 5 | vegetable |
| 8 | sweet potato | 6.5 | 2.5 | vegetable |
| 9 | carrot | 3 | 9 | vegetable |
| 10 | celery | 2 | 8 | vegetable |
| 11 | lettuce | 1 | 6 | vegetable |
| 12 | cucumber | 2 | 4 | vegetable |
| 13 | onion | 3 | 2 | vegetable |
| 14 | green bean | 3.5 | 6.5 | vegetable |
Classifying the tomato q = (6, 4) by hand
- 1Distances. For every food compute . Peach: . Bell pepper: . Sweet potato: . Orange: . Pear: . The other nine are all farther (next: grape 2.693, green bean 3.536; the farthest is the carrot at 5.831).
- 2Sort the 14 distances ascending (table below). There is no "training": this ranking is computed fresh for this query.
- 3k = 1. The single nearest food is the peach, a fruit. → fruit.
- 4k = 3. Peach (fruit), bell pepper (veg), sweet potato (veg). Votes 1 to 2, → vegetable.
- 5k = 5. Add orange and pear, both fruit. Votes 3 to 2, → fruit.
- 6k = 3 with 1/d weights. Fruit: . Vegetable: . → still vegetable: two moderately close vegetables outweigh one closer fruit.
- 7k = 5 with 1/d weights. Fruit gains , reaching ; vegetable stays . → fruit, slightly less confident than the uniform 0.600 because the two added fruits are the farthest neighbours.
| Rank | Food | Δ sweet | Δ crunch | d² | d | Class | Votes so far (fruit : veg) |
|---|---|---|---|---|---|---|---|
| 1 | peach | 1 | 0.5 | 1.25 | 1.118 | fruit | 1 : 0 |
| 2 | bell pepper | −1 | 1 | 2.00 | 1.414 | vegetable | 1 : 1 |
| 3 | sweet potato | 0.5 | −1.5 | 2.50 | 1.581 | vegetable | 1 : 2 |
| 4 | orange | 2 | −1 | 5.00 | 2.236 | fruit | 2 : 2 |
| 5 | pear | 1.5 | 2 | 6.25 | 2.500 | fruit | 3 : 2 |
| 6 | grape | 2.5 | 1 | 7.25 | 2.693 | fruit | 4 : 2 |
| 7 | green bean | −2.5 | 2.5 | 12.50 | 3.536 | vegetable | 4 : 3 |
Three values of , two different answers. Which should we trust? Use the data itself: leave-one-out predicts each of the 14 foods from the other 13 and counts the hits.
| k | 1 | 3 | 5 | 7 | 9 | 11 | 13 |
|---|---|---|---|---|---|---|---|
| Uniform vote | 11/14 = 0.786 | 12/14 = 0.857 | 13/14 = 0.929 | 12/14 = 0.857 | 13/14 = 0.929 | 7/14 = 0.500 | 8/14 = 0.571 |
| 1/d weights | 0.786 | 0.857 | 0.929 | 0.857 | 0.929 | 0.929 | 0.929 |
The table tells the whole bias–variance story. At three foods are misclassified: orange (its nearest other food is the sweet potato), bell pepper and sweet potato (each sits next to fruit). At only the sweet potato, a genuinely fruit-like vegetable, is still wrong. At the uniform vote collapses to 7/14: leaving out a fruit leaves only 5 fruits among the 13 remaining foods, so an 11-point neighbourhood is always mostly vegetable, and every fruit is misclassified. Distance weighting rescues large because the far-away vegetables barely count.
Explore it
The algorithm, step by step
fit(X, y) and predict(q)
- 1Fit. Standardise the features (store each ), then store the scaled rows and their labels. Optionally build a KD-tree or ball tree over them.
- 2Distances. For a query (scaled with the training ), compute for every stored point, or let the tree prune whole regions that cannot contain a nearer point.
- 3Select the smallest. A partial selection (quickselect / "argpartition") does this in ; a full sort costs .
- 4Weight each neighbour: , or (an exact match takes all the weight).
- 5Vote. Sum the weights per class, divide by the total to get , and return the arg-max. Break remaining ties consistently (scikit-learn picks the class that comes first in its sorted class list), or avoid them with an odd on two classes.
- 1store all (xᵢ, yᵢ) # no training
- 2given query q:
- 3 dᵢ ← ‖q − xᵢ‖ for all i
- 4 sort points by dᵢ
- 5 N ← k nearest
- 6 ŷ ← majority class in N
Training is just storing all 36 labelled points — nothing is fitted or computed.
Complexity
- Fit
- (brute force) or (KD-tree / ball tree build); memory either way: you keep every training point
- Predict, brute force
- distances + selection per query; vectorises perfectly on GPUs, so it is often the fastest exact choice for moderate n
- Predict, KD-tree
- about per query when is small, degrading towards as grows, because the pruning test rarely succeeds
- Predict, approximate (HNSW, IVF-PQ)
- sub-linear search over millions to billions of vectors, trading a small loss in recall for orders-of-magnitude speed; this is what vector databases do
Choosing k and the other knobs
| Knob | Small / off | Large / on | Practical default |
|---|---|---|---|
n_neighbors k | jagged boundary, Voronoi islands around outliers, high variance, coarse probabilities | smooth boundary, minority classes out-voted, high bias; k = n predicts the majority | tune by cross-validation over odd k; √n is a common starting point |
weights | uniform: every neighbour counts the same, sensitive to k | distance: close neighbours dominate, robust to large k, ties vanish | try both in the grid search |
| metric | L2: rotation-invariant, dominated by the largest difference | L1: more robust to one extreme coordinate; cosine: compares direction only (text, embeddings) | L2 on standardised numeric features; cosine on embeddings |
| feature scaling | unscaled: the feature with the biggest units decides | standardised or min-max scaled: features contribute comparably | always scale, inside a Pipeline |
algorithm | brute: exact, simple, GPU-friendly | kd_tree / ball_tree: fast in low d; ANN libraries for huge n | auto lets scikit-learn choose |
The curse of dimensionality
k-NN's one assumption, that near means similar, quietly breaks in high dimensions, for two reasons. First, neighbourhoods stop being local. To capture 1% of points spread uniformly in a unit hypercube, a sub-cube needs edge length : 0.1 of each axis in 2-D, but 0.631 in 10-D and 0.955 in 100-D. Your "nearest" neighbours then span almost the whole range of every feature.
Second, distances concentrate. With 1,000 uniform random points and 100 random queries, the average ratio of nearest to farthest distance is 0.017 in 2-D, 0.275 in 10-D, 0.694 in 100-D and 0.894 in 1000-D. When every point is about equally far away, "nearest" carries little information. Real data usually lives near a much lower-dimensional surface, which is why k-NN still works on images and embeddings, but irrelevant features hurt: each one adds noise to every distance. Select features, or reduce dimension with PCA or a learned embedding first.
In code
1import numpy as np23def knn_predict_proba(X_train, y_train, Q, k=5, weights="uniform", p=2, n_classes=None):4 """Class probabilities for each query row: (weighted) share of the k nearest neighbours."""5 n_classes = n_classes or y_train.max() + 16 D = (np.abs(Q[:, None, :] - X_train[None, :, :]) ** p).sum(-1) ** (1 / p) # (m, n) Minkowski7 idx = np.argsort(D, axis=1, kind="stable")[:, :k] # k nearest, ties by index8 d = np.take_along_axis(D, idx, axis=1)9 if weights == "distance":10 w = np.where(d == 0, 1e12, 1 / np.maximum(d, 1e-12)) # exact match dominates11 else:12 w = np.ones_like(d)13 P = np.zeros((len(Q), n_classes))14 for c in range(n_classes):15 P[:, c] = (w * (y_train[idx] == c)).sum(1)16 return P / P.sum(1, keepdims=True), idx, d1718def loo_accuracy(X, y, k, **kw):19 hits = 020 for i in range(len(X)):21 keep = np.arange(len(X)) != i22 P, _, _ = knn_predict_proba(X[keep], y[keep], X[i:i + 1], k, n_classes=2, **kw)23 hits += P.argmax() == y[i]24 return hits / len(X)2526names = ["peach", "orange", "pear", "apple", "banana", "grape", "bell pepper",27 "sweet potato", "carrot", "celery", "lettuce", "cucumber", "onion", "green bean"]28X = np.array([[7, 4.5], [8, 3], [7.5, 6], [9, 8], [10, 1.5], [8.5, 5], [5, 5],29 [6.5, 2.5], [3, 9], [2, 8], [1, 6], [2, 4], [3, 2], [3.5, 6.5]])30y = np.array([0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]) # 0 = fruit, 1 = vegetable31tomato = np.array([[6, 4]])3233for k in (1, 3, 5):34 P, idx, d = knn_predict_proba(X, y, tomato, k)35 print(f"k={k}: P(fruit)={P[0, 0]:.3f} ->", ["fruit", "vegetable"][P.argmax()],36 "| neighbours:", [f"{names[i]} {dist:.3f}" for i, dist in zip(idx[0], d[0])])37P, _, _ = knn_predict_proba(X, y, tomato, 3, weights="distance")38print(f"k=3, 1/d weights: P(fruit)={P[0, 0]:.3f}")39for k in (1, 3, 5, 7, 9, 11, 13):40 print(f"LOO k={k:2d}: uniform {loo_accuracy(X, y, k):.3f} distance {loo_accuracy(X, y, k, weights='distance'):.3f}")4142# k=1: P(fruit)=1.000 -> fruit | neighbours: ['peach 1.118']43# k=3: P(fruit)=0.333 -> vegetable | neighbours: ['peach 1.118', 'bell pepper 1.414', 'sweet potato 1.581']44# k=5: P(fruit)=0.600 -> fruit | neighbours: [... 'orange 2.236', 'pear 2.500']45# k=3, 1/d weights: P(fruit)=0.40046# LOO k= 1: uniform 0.786 ... k= 5: uniform 0.929 ... k=11: uniform 0.500 distance 0.9291import numpy as np2from sklearn.neighbors import KNeighborsClassifier3from sklearn.model_selection import GridSearchCV, LeaveOneOut45X = np.array([[7, 4.5], [8, 3], [7.5, 6], [9, 8], [10, 1.5], [8.5, 5], [5, 5],6 [6.5, 2.5], [3, 9], [2, 8], [1, 6], [2, 4], [3, 2], [3.5, 6.5]])7y = np.array(["fruit"] * 6 + ["vegetable"] * 8)8tomato = [[6, 4]]910for k in (1, 3, 5):11 knn = KNeighborsClassifier(n_neighbors=k).fit(X, y)12 dist, idx = knn.kneighbors(tomato)13 print(k, knn.predict(tomato)[0], knn.predict_proba(tomato).round(3)[0], dist.round(3)[0], idx[0])1415search = GridSearchCV(KNeighborsClassifier(),16 {"n_neighbors": [1, 3, 5, 7, 9, 11, 13], "weights": ["uniform", "distance"]},17 cv=LeaveOneOut()).fit(X, y)18print("best:", search.best_params_, round(search.best_score_, 3))1920# 1 fruit [1. 0.] [1.118] [0]21# 3 vegetable [0.333 0.667] [1.118 1.414 1.581] [0 6 7]22# 5 fruit [0.6 0.4] [1.118 1.414 1.581 2.236 2.5 ] [0 6 7 1 2]23# best: {'n_neighbors': 5, 'weights': 'uniform'} 0.929Use when
- +You want a strong, assumption-light baseline in minutes: no training, any boundary shape, any number of classes.
- +Data is low-dimensional or lives in a good embedding space where distance means similarity.
- +Data arrives continuously: learning a new example is appending a row, and forgetting one is deleting it.
- +You want explanations by example: "classified as fraud because these 5 past transactions were most similar".
Avoid when
- −Many raw, irrelevant or differently-scaled features: distances concentrate and noise drowns the signal.
- −Large n with tight latency or memory budgets, unless you can use an approximate-NN index.
- −Classes are heavily imbalanced: the majority class wins most neighbourhoods unless you weight votes or rebalance.
- −You need calibrated probabilities or extrapolation far from the training data: k-NN only knows what is near.
Where it's used
Retrieval and RAG
Vector databases return the k nearest document embeddings to a query embedding; k-NN classification on top gives zero-training text and image classifiers.
Recommendation
Neighbourhood collaborative filtering: recommend what the k most similar users liked, or items similar to ones you bought.
Handwriting and face recognition
k-NN on raw pixels is a classic strong baseline for MNIST digits; on face embeddings from a deep network it identifies people from a handful of examples.
Imputation and anomaly detection
Fill a missing value from the k most similar rows (KNNImputer); flag a point whose k-th neighbour distance is unusually large (the idea behind LOF).
Check yourself
A query's three nearest neighbours are at distances 1 (class A), 2 (class B) and 4 (class B). What do a uniform vote and a 1/d-weighted vote predict?
Check yourself
In the worked example, why does leave-one-out accuracy with a uniform vote drop to 7/14 at k = 11?
Check yourself
Points are uniform in a 10-dimensional unit cube. A sub-cube that holds 1% of them must have an edge length of about…
Check yourself
Features are [annual salary in dollars, years of experience], unscaled. Euclidean neighbours are chosen almost entirely by…
Remember
- ✓k-NN stores the data and predicts by a (weighted) vote of the nearest points; the vote shares are Bayes-rule posteriors from a local density estimate.
- ✓ is the bias–variance dial: gives Voronoi islands and 100% training accuracy; large smooths and lets the majority class win. Pick it by cross-validation or leave-one-out.
- ✓Distance weighting (1/d) makes predictions robust to large k and removes most ties.
- ✓Everything depends on the metric: standardise features, drop irrelevant ones, and use cosine or learned embeddings for text and images.
- ✓Prediction costs O(nd) per query by brute force; KD-trees help in low dimension, approximate-NN indexes at scale. High dimensions make all distances look alike.