k-Nearest neighbors

Predict by vote or average of the k closest training points — there is no training step.

17 min read1871 wordscore10 viewsupdated 2026-10-07

Definition

k-nearest neighbors (k-NN) classifies a new point qq by finding the kk 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 q∈Rdq\in\mathbb{R}^d → class probabilities p^(c∣q)\hat p(c\mid q) = (weighted) share of the kk neighbours in class cc, and y^=arg⁡max⁡cp^(c∣q)\hat y=\arg\max_c \hat p(c\mid q)
Learns
nothing: it memorises all nn labelled pairs (xi,yi)(x_i,y_i) (a lazy, instance-based learner)
Training cost
O(1)O(1) to store; O(dnlog⁡n)O(dn\log n) if you build a KD-tree or ball tree for faster search
Prediction cost
O(nd)O(nd) per query by brute force (plus O(n)O(n) to select the kk smallest); roughly O(log⁡n)O(\log n) with a tree index in low dimension
Hyperparameters
n_neighbors k, weights (uniform or distance), the metric (p for Minkowski, or any custom distance), the search algorithm
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 kk 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.

kk controls how much evidence you demand. With k=1k=1 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 kk the vote averages over a wide neighbourhood: the boundary becomes smooth, but small or minority regions get out-voted. At the extreme k=nk=n, 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 kk training points with the smallest distance to qq
k-th neighbour distance
rk(q)r_k(q), the distance to the farthest member of Nk(q)N_k(q): the radius of the smallest ball around qq holding kk points
Metric
the distance function d(⋅,⋅)d(\cdot,\cdot); Euclidean (L2L_2), Manhattan (L1L_1) and cosine are the usual choices
Uniform vs distance weighting
each neighbour casts one vote, or a vote of weight 1/d(q,xi)1/d(q,x_i) 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:

dp(q,x)=(∑j=1d∣qj−xj∣p)1/pd_p(q,x)=\Big(\sum_{j=1}^{d}\lvert q_j-x_j\rvert^{p}\Big)^{1/p}
q,  xq,\;x
the query and a training point, both in Rd\mathbb{R}^d
qj,  xjq_j,\;x_j
their jj-th features
pp
p=2p=2 Euclidean (straight-line), p=1p=1 Manhattan (sum of absolute differences), p→∞p\to\infty the largest single difference

The unit "ball" of dpd_p changes shape with pp: a circle for p=2p=2, a diamond for p=1p=1, a square for p=∞p=\infty. L1L_1 is less dominated by one large coordinate difference than L2L_2, which squares it. Given a metric, the classifier is a vote over the neighbourhood:

p^(c∣q)=∑i∈Nk(q)wi [ yi=c ]∑i∈Nk(q)wi,y^(q)=arg⁡max⁡c p^(c∣q)\hat p(c\mid q)=\frac{\sum_{i\in N_k(q)} w_i\,[\,y_i=c\,]}{\sum_{i\in N_k(q)} w_i},\qquad \hat y(q)=\arg\max_c\,\hat p(c\mid q)
Nk(q)N_k(q)
the kk training indices nearest to qq
[ yi=c ][\,y_i=c\,]
1 if neighbour ii has class cc, else 0
wiw_i
vote weight: wi=1w_i=1 (uniform) or wi=1/d(q,xi)w_i=1/d(q,x_i) (distance weighting)
p^(c∣q)\hat p(c\mid q)
estimated probability of class cc at qq: the (weighted) fraction of neighbours in class cc

With uniform weights, p^(c∣q)=kc/k\hat p(c\mid q)=k_c/k, where kck_c is the number of neighbours in class cc. With k=5k=5 these probabilities can only be 0,0.2,0.4,…,10, 0.2, 0.4,\dots,1: k-NN probabilities are coarse, and you need a larger kk 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 VV around qq until it contains kk points, kck_c of them from class cc. If class cc has ncn_c training points in total, the fraction of them inside the ball estimates its probability mass there, so the class-conditional density is about

p^(q∣c)=kcncV,p^(c)=ncn,p^(q)=knV\hat p(q\mid c)=\frac{k_c}{n_c V},\qquad \hat p(c)=\frac{n_c}{n},\qquad \hat p(q)=\frac{k}{nV}
VV
volume of the smallest ball around qq holding kk training points (radius rk(q)r_k(q))
nc,  nn_c,\;n
training points in class cc, and in total
kck_c
neighbours of qq that belong to class cc

Plug these into Bayes' rule p(c∣q)=p(q∣c) p(c)/p(q)p(c\mid q)=p(q\mid c)\,p(c)/p(q). The volume VV and the counts nn, ncn_c all cancel:

p^(c∣q)=kcncV⋅ncnknV=kck\hat p(c\mid q)=\frac{\dfrac{k_c}{n_cV}\cdot\dfrac{n_c}{n}}{\dfrac{k}{nV}}=\frac{k_c}{k}

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 kk. The estimate kc/kk_c/k is a proportion over kk samples, so its variance is about p(1−p)/kp(1-p)/k: small kk gives noisy probabilities. But the ball must grow to hold kk points, and the larger it is, the more it averages over regions where p(c∣x)p(c\mid x) differs from p(c∣q)p(c\mid q): large kk gives biased, over-smoothed probabilities. Consistency theory makes this precise: k-NN converges to the Bayes-optimal classifier as n→∞n\to\infty provided k→∞k\to\infty and k/n→0k/n\to 0.

Distance weighting replaces wi=1w_i=1 with wi=1/d(q,xi)w_i=1/d(q,x_i). It makes the prediction depend continuously on how close each neighbour is, reduces the sensitivity to the exact choice of kk (far neighbours barely count), and breaks ties. If qq coincides with a training point, d=0d=0 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, xj↦(xj−μj)/σjx_j\mapsto (x_j-\mu_j)/\sigma_j, which is the same as using a diagonal Mahalanobis distance:

dM(q,x)=(q−x)⊤M (q−x),M=diag⁡(1/σ12,…,1/σd2)d_M(q,x)=\sqrt{(q-x)^\top M\,(q-x)},\qquad M=\operatorname{diag}(1/\sigma_1^2,\dots,1/\sigma_d^2)
MM
a positive-definite matrix; M=IM=I is Euclidean, M=Σ−1M=\Sigma^{-1} (inverse covariance) is the full Mahalanobis distance
σj\sigma_j
standard deviation of feature jj on the training set

Learning MM 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 kk.

#FoodSweetnessCrunchinessClass
1peach74.5fruit
2orange83fruit
3pear7.56fruit
4apple98fruit
5banana101.5fruit
6grape8.55fruit
7bell pepper55vegetable
8sweet potato6.52.5vegetable
9carrot39vegetable
10celery28vegetable
11lettuce16vegetable
12cucumber24vegetable
13onion32vegetable
14green bean3.56.5vegetable
Training data: 6 fruits and 8 vegetables. Highlighted: the 5 foods nearest the tomato at (6, 4).

Classifying the tomato q = (6, 4) by hand

  1. 1Distances. For every food compute d=(x1−6)2+(x2−4)2d=\sqrt{(x_1-6)^2+(x_2-4)^2}. Peach: 12+0.52=1.25=1.118\sqrt{1^2+0.5^2}=\sqrt{1.25}=1.118. Bell pepper: (−1)2+12=2=1.414\sqrt{(-1)^2+1^2}=\sqrt{2}=1.414. Sweet potato: 0.52+(−1.5)2=2.5=1.581\sqrt{0.5^2+(-1.5)^2}=\sqrt{2.5}=1.581. Orange: 22+(−1)2=5=2.236\sqrt{2^2+(-1)^2}=\sqrt5=2.236. Pear: 1.52+22=6.25=2.500\sqrt{1.5^2+2^2}=\sqrt{6.25}=2.500. The other nine are all farther (next: grape 2.693, green bean 3.536; the farthest is the carrot at 5.831).
  2. 2Sort the 14 distances ascending (table below). There is no "training": this ranking is computed fresh for this query.
  3. 3k = 1. The single nearest food is the peach, a fruit. p^(fruit)=1/1=1.0\hat p(\text{fruit})=1/1=1.0 → fruit.
  4. 4k = 3. Peach (fruit), bell pepper (veg), sweet potato (veg). Votes 1 to 2, p^(fruit)=1/3=0.333\hat p(\text{fruit})=1/3=0.333 → vegetable.
  5. 5k = 5. Add orange and pear, both fruit. Votes 3 to 2, p^(fruit)=3/5=0.600\hat p(\text{fruit})=3/5=0.600 → fruit.
  6. 6k = 3 with 1/d weights. Fruit: 1/1.118=0.8941/1.118=0.894. Vegetable: 1/1.414+1/1.581=0.707+0.632=1.3401/1.414+1/1.581=0.707+0.632=1.340. p^(fruit)=0.894/(0.894+1.340)=0.400\hat p(\text{fruit})=0.894/(0.894+1.340)=0.400 → still vegetable: two moderately close vegetables outweigh one closer fruit.
  7. 7k = 5 with 1/d weights. Fruit gains 1/2.236+1/2.5=0.447+0.4001/2.236+1/2.5=0.447+0.400, reaching 1.7421.742; vegetable stays 1.3401.340. p^(fruit)=0.565\hat p(\text{fruit})=0.565 → fruit, slightly less confident than the uniform 0.600 because the two added fruits are the farthest neighbours.
RankFoodΔ sweetΔ crunchd²dClassVotes so far (fruit : veg)
1peach10.51.251.118fruit1 : 0
2bell pepper−112.001.414vegetable1 : 1
3sweet potato0.5−1.52.501.581vegetable1 : 2
4orange2−15.002.236fruit2 : 2
5pear1.526.252.500fruit3 : 2
6grape2.517.252.693fruit4 : 2
7green bean−2.52.512.503.536vegetable4 : 3
The seven nearest foods to the tomato, with the running vote. The prediction flips fruit → vegetable → fruit as k goes 1 → 3 → 5.

Three values of kk, 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.

k135791113
Uniform vote11/14 = 0.78612/14 = 0.85713/14 = 0.92912/14 = 0.85713/14 = 0.9297/14 = 0.5008/14 = 0.571
1/d weights0.7860.8570.9290.8570.9290.9290.929
Leave-one-out accuracy on the 14 foods (Euclidean). k = 5 is the smallest k with the best score, so it is the one we choose, and the tomato is a fruit.

The table tells the whole bias–variance story. At k=1k=1 three foods are misclassified: orange (its nearest other food is the sweet potato), bell pepper and sweet potato (each sits next to fruit). At k=5k=5 only the sweet potato, a genuinely fruit-like vegetable, is still wrong. At k=11k=11 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 kk because the far-away vegetables barely count.

Explore it

● fruit ● vegetable · drag ✚01234567891011012345678910sweetness →crunchiness →1·peach4·orange5·pearapplebananagrape2·bell pepper3·sweet potatocarrotcelerylettucecucumberoniongreen beantomato (6.0, 4.0)rank · food · L2 dist● 1 peach1.118● 2 bell pepper1.414● 3 sweet potato1.581● 4 orange2.236● 5 pear2.500● 6 grape2.693● 7 green bean3.536● 8 onion3.606● 9 cucumber4.000● 10 banana4.717● 11 apple5.000● 12 lettuce5.385● 13 celery5.657● 14 carrot5.831leave-one-out hits /14111123135127139711813k →
5 nearest: fruit 3 · vegetable 2
P(fruit)0.600→ fruit
radius to 5th neighbour = 2.500 · LOO accuracy at k = 5: 13/14 = 0.929
k
fig.The 14 foods from the worked example. Drag the tomato (✚); the dashed ball passes through the k-th neighbour, the lines show who votes, and the background shading is the prediction everywhere. At (6, 4) with Euclidean distance: k = 1 → fruit, k = 3 → vegetable (P(fruit) = 0.333, 0.400 with 1/d weights), k = 5 → fruit (0.600). Toggle Manhattan to see the ball become a diamond. The bars on the right are leave-one-out hits for every odd k: 11, 12, 13, 12, 13, 7, 8 with a uniform vote. Switch to 1/d weights and the k = 11 and 13 bars jump to 13. At k = 1 the boundary is made of Voronoi-cell edges and bends around the sweet potato; at k = 13 with a uniform vote the tomato becomes a vegetable (P(fruit) = 0.462).

The algorithm, step by step

fit(X, y) and predict(q)

  1. 1Fit. Standardise the features (store each μj,σj\mu_j,\sigma_j), then store the nn scaled rows and their labels. Optionally build a KD-tree or ball tree over them.
  2. 2Distances. For a query qq (scaled with the training μ,σ\mu,\sigma), compute d(q,xi)d(q,x_i) for every stored point, or let the tree prune whole regions that cannot contain a nearer point.
  3. 3Select the kk smallest. A partial selection (quickselect / "argpartition") does this in O(n)O(n); a full sort costs O(nlog⁡n)O(n\log n).
  4. 4Weight each neighbour: wi=1w_i=1, or wi=1/diw_i=1/d_i (an exact match takes all the weight).
  5. 5Vote. Sum the weights per class, divide by the total to get p^(c∣q)\hat p(c\mid q), 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 kk on two classes.
▸ k-nearest neighbours · k = 5step 1/15
votes000
k = 5neighbours 0/5votes 0 0 0
  1. 1store all (xᵢ, yᵢ) # no training
  2. 2given query q:
  3. 3 dᵢ ← ‖q − xᵢ‖ for all i
  4. 4 sort points by dᵢ
  5. 5 N ← k nearest
  6. 6 ŷ ← majority class in N

Training is just storing all 36 labelled points — nothing is fitted or computed.

fig.The same procedure on three classes: store, measure every distance, sort, take the k = 5 nearest, vote. The circle grows to the k-th neighbour; two queries give two different answers.

Complexity

Fit
O(1)O(1) (brute force) or O(dnlog⁡n)O(dn\log n) (KD-tree / ball tree build); memory O(nd)O(nd) either way: you keep every training point
Predict, brute force
O(nd)O(nd) distances + O(n)O(n) selection per query; vectorises perfectly on GPUs, so it is often the fastest exact choice for moderate n
Predict, KD-tree
about O(log⁡n)O(\log n) per query when dd is small, degrading towards O(n)O(n) as dd 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

q
q → orange (1 of 1 votes)train acc 100%test acc 67%click the plot to move q
50%75%100%159131721accuracy vs k: train · test (200 held-out) · best test k = 19
fig.A larger noisy two-class dataset. Slide k and click to move the query: k = 1 scores perfectly on the training points it memorised but worse on fresh test points; moderate k trades a little training accuracy for better test accuracy.
KnobSmall / offLarge / onPractical default
n_neighbors kjagged boundary, Voronoi islands around outliers, high variance, coarse probabilitiessmooth boundary, minority classes out-voted, high bias; k = n predicts the majoritytune by cross-validation over odd k; √n is a common starting point
weightsuniform: every neighbour counts the same, sensitive to kdistance: close neighbours dominate, robust to large k, ties vanishtry both in the grid search
metricL2: rotation-invariant, dominated by the largest differenceL1: more robust to one extreme coordinate; cosine: compares direction only (text, embeddings)L2 on standardised numeric features; cosine on embeddings
feature scalingunscaled: the feature with the biggest units decidesstandardised or min-max scaled: features contribute comparablyalways scale, inside a Pipeline
algorithmbrute: exact, simple, GPU-friendlykd_tree / ball_tree: fast in low d; ANN libraries for huge nauto lets scikit-learn choose
Hyperparameters and their effect.

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.011/d0.01^{1/d}: 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

python
1import numpy as np
2
3def 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() + 1
6 D = (np.abs(Q[:, None, :] - X_train[None, :, :]) ** p).sum(-1) ** (1 / p) # (m, n) Minkowski
7 idx = np.argsort(D, axis=1, kind="stable")[:, :k] # k nearest, ties by index
8 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 dominates
11 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, d
17
18def loo_accuracy(X, y, k, **kw):
19 hits = 0
20 for i in range(len(X)):
21 keep = np.arange(len(X)) != i
22 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)
25
26names = ["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 = vegetable
31tomato = np.array([[6, 4]])
32
33for 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}")
41
42# 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.400
46# LOO k= 1: uniform 0.786 ... k= 5: uniform 0.929 ... k=11: uniform 0.500 distance 0.929
From scratch in NumPy: Minkowski distance, uniform or 1/d weights, probabilities, and leave-one-out. Runs as-is.
python
1import numpy as np
2from sklearn.neighbors import KNeighborsClassifier
3from sklearn.model_selection import GridSearchCV, LeaveOneOut
4
5X = 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]]
9
10for 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])
14
15search = 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))
19
20# 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.929
scikit-learn on the same data, with k and the weighting chosen by leave-one-out grid search.

Use 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 kk nearest points; the vote shares kc/kk_c/k are Bayes-rule posteriors from a local density estimate.
  • ✓kk is the bias–variance dial: k=1k=1 gives Voronoi islands and 100% training accuracy; large kk 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.
← back to ML Algorithms roadmap