Skip to content
learn
  1. Learn
  2. Machine Learning
  3. Classification

Machine Learning ML-04.02

k-Nearest Neighbours

Classify a point by asking its k closest neighbours to vote. Why k controls smoothness, why scaling is essential and why predictions get slow.

Beginner 10 min Last reviewed

The big idea

You move to a new city and want to guess whether a street is quiet or noisy without visiting it. A reasonable approach: ask the five people who live closest to it, and go with the majority. That is k-nearest neighboursA method that predicts a new point's label from the labels of the k training points closest to it, by majority vote for classification or by averaging for regression. (kNN), one of the simplest ideas in machine learning.

kNN has no training phase at all. It memorises the training data and does all its work at prediction time: measure the distance from the new point to every stored point, take the k closest, and let them vote. Because of that it is called a lazy learnerA model that stores the training data and defers computation until a prediction is requested, instead of learning parameters up front.. Its strength is that it makes no assumption about the shape of the boundary. Its weaknesses all come from the word "distance".

How it works

Step 1: Measure distance to every training point

For a new point q, compute its distance to each training point, usually the straight-line Euclidean distanceThe straight-line distance between two points: the square root of the sum of squared differences across features.:

Other choices exist: Manhattan distance (sum of absolute differences) is more robust to one large difference, and cosine distance suits text vectors where direction matters more than length.

Step 2: Take the k closest and vote

Sort by distance, keep the k nearest, and predict the most common class among them. The share of votes doubles as a rough probability: 3 of 5 neighbours voting "red" gives 0.6. For regression, average the neighbours' values instead of voting.

Nearest neighbours vote Twelve training points, five red and seven blue, and a gold new point. Step 1: a dashed circle holds the three nearest points, two red and one blue, joined to the new point by glowing lines, so red wins. Step 2: a larger circle holds seven neighbours, three red and four blue, so blue wins. feature 1feature 2 new point Figure 1. The new point takes the majority label of its k nearest neighbours. Changing k changes who gets a vote, and here it flips the answer from red to blue.
  1. k = 3 The three nearest neighbours are two red and one blue. Red wins 2 to 1.
  2. k = 7 Widen the circle to seven neighbours: three red and four blue. Now blue wins 4 to 3. Same point, same data, different answer.

Step 3: Choose k

k is the one knob, and it controls the classic trade-off between noise and smoothness:

  • k = 1: every training point owns a small territory. Training accuracy is a perfect 100 percent (each point is its own nearest neighbour), but the boundary is jagged and a single mislabelled point carves out an island. This is overfitting.
  • Large k: each prediction averages over a big neighbourhood. The boundary is smooth, but with k close to the dataset size every prediction becomes the majority class. This is underfitting.

Use an odd k for two classes to avoid ties, and pick k by validation accuracy ( Cross-validation ). A common starting point is somewhere between 5 and the square root of the number of training points.

Training and test accuracy as k grows Accuracy of kNN on a noisy two-moons dataset for k equal to 1, 5, 15, 51 and 151. Training accuracy starts at 1.0 for k = 1 and falls steadily to 0.853. Test accuracy starts at 0.840, peaks at 0.860 for k = 15, then falls to 0.827 at k = 151. 0.80.850.90.951k (number of neighbours)accuracy 1 5 15 51 151 training accuracy test accuracy best: k = 15 Figure 2. Numbers from the code below. k = 1 memorises the training set perfectly but generalises worst among small k; very large k blurs the boundary. The best test accuracy sits in between.

Step 4: Scale the features

Distance adds up differences across features, so whichever feature has the biggest numbers dominates. Mix age (20 to 70) with income (20,000 to 200,000) and a difference of 1,000 in income outweighs a 40-year age gap: the model silently ignores age. Standardize every feature first ( Feature engineering ). In the code below, adding a single useless feature measured from 0 to 1000 drops test accuracy from 0.860 to 0.513, a coin flip; standardizing brings it back to 0.853.

Step 5: Pay at prediction time

Training is free, but each prediction compares the query with every stored point. With a million points and 100 features, that is 100 million subtractions per prediction, and the whole dataset must stay in memory. Tree indexes (KD-trees, ball trees) speed this up in low dimensions; for high-dimensional vectors, systems use approximate nearest neighbour search, the same idea that powers vector databases ( Vector databases and ANN indexes ).

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Set k to 1 with shading on. Look for small islands of one colour inside another: each is a single training point with its own territory.
  2. Raise k to 15, then 25. Watch the islands disappear and the boundaries smooth out. Do any small regions of a class vanish completely?
  3. Drag the query point to the border between two classes and step k from 1 to 9. How often does the prediction flip?

Going deeper

Code: k, scaling and a single prediction

knn.pyruns with python3 + numpy + scikit-learn
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline

# Two interleaved half-moons with noise
X, y = make_moons(n_samples=600, noise=0.35, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=0)

print(" k   train acc  test acc")
for k in [1, 5, 15, 51, 151]:
    m = KNeighborsClassifier(n_neighbors=k).fit(Xtr, ytr)
    print(f"{k:>3}   {m.score(Xtr, ytr):.3f}      {m.score(Xte, yte):.3f}")

# Scaling: add a useless feature measured in big units (say, a customer id / 1000)
rng = np.random.default_rng(0)
noise = rng.uniform(0, 1000, size=(len(X), 1))
X2tr, X2te, _, _ = train_test_split(np.hstack([X, noise]), y, test_size=0.5, random_state=0)
raw = KNeighborsClassifier(n_neighbors=15).fit(X2tr, ytr)
print(f"\nwith a 0-1000 noise feature, unscaled: test acc {raw.score(X2te, yte):.3f}")
scaled = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=15)).fit(X2tr, ytr)
print(f"same data, standardized first:      test acc {scaled.score(X2te, yte):.3f}")

# What a prediction looks like: the neighbours and their vote
m = KNeighborsClassifier(n_neighbors=5).fit(Xtr, ytr)
dist, idx = m.kneighbors([[0.5, 0.25]])
print("\nquery (0.5, 0.25): neighbour labels", ytr[idx[0]], "distances", dist[0].round(2))
print("predicted class", m.predict([[0.5, 0.25]])[0], "probabilities", m.predict_proba([[0.5, 0.25]])[0])

Output

 k   train acc  test acc
  1   1.000      0.840
  5   0.920      0.857
 15   0.910      0.860
 51   0.897      0.853
151   0.853      0.827

with a 0-1000 noise feature, unscaled: test acc 0.513
same data, standardized first:      test acc 0.853

query (0.5, 0.25): neighbour labels [1 0 1 0 0] distances [0.03 0.09 0.09 0.11 0.12]
predicted class 0 probabilities [0.6 0.4]

The last lines show one prediction from the inside: of the five neighbours of (0.5, 0.25), two vote 1 and three vote 0, so the prediction is class 0 with "probability" 0.6. Notice the nearest neighbour voted 1 and lost: plain kNN counts every vote equally. Setting weights="distance" in scikit-learn weighs closer neighbours more heavily.

The curse of dimensionality

In high dimensions, distances stop being informative. With hundreds of features, the nearest and farthest training points end up at almost the same distance from any query, so "nearest" means little. Every irrelevant feature adds noise to every distance. kNN works best with a modest number of meaningful, scaled features, or on learned embeddings where distance has been trained to mean similarity. Gaussian mixture models and EM covers reducing dimensions first.

Trade-offs

OptionWins whenLoses when
kNN Small to medium data, irregular boundaries, a quick baseline, or similarity search on good embeddings Large data with tight latency budgets; many irrelevant features
Logistic regression You need fast predictions and readable weights The boundary is strongly curved
Tree ensembles Tabular data with mixed scales; no scaling needed You want predictions explained by similar past examples
Approximate nearest neighbour index Millions of vectors and millisecond lookups You need exact neighbours every time

Common mistakes

  • Forgetting to scale features, so one large-valued feature decides every distance.
  • Choosing k by training accuracy, which always favours k = 1.
  • Fitting the scaler on all the data before splitting, which leaks test statistics into training ( Data leakage ).
  • Using an even k for two classes and getting ties.
  • Throwing hundreds of raw features at kNN and blaming the algorithm when distances become meaningless.

In the wild

Nearest-neighbour search is everywhere, even where kNN classification is not. Recommendation systems find users or items with similar embeddings and suggest what those neighbours liked ( Collaborative filtering and matrix factorization ). Retrieval for language models finds the stored passages closest to a question. Anomaly detection flags points whose nearest neighbours are unusually far away. In each case the same two lessons apply: the quality of the distance decides the quality of the answer, and at scale you need an index rather than a brute-force scan.

Check yourself

  1. What does kNN do during training?

    Show answer

    B. Stores the training data; the work happens at prediction time kNN is a lazy learner. Training is just storing the points (perhaps in an index); each prediction computes distances to them.

  2. With k = 1, training accuracy is 100 percent but test accuracy is the lowest of the small values of k. What is happening?

    Show answer

    B. Overfitting: every training point, including noisy ones, owns its own region Each training point is its own nearest neighbour, so training accuracy is always perfect. Noisy points create islands that mislead nearby test points.

  3. Features are 'age in years' and 'salary in dollars'. What happens without scaling?

    Show answer

    B. Salary dominates the distance, so age is effectively ignored Salary differences are thousands of times larger than age differences, so they decide which points are nearest.

  4. You need predictions in 5 ms over 50 million stored vectors. What is the practical choice?

    Show answer

    B. An approximate nearest neighbour index Brute force compares against all 50 million points per request. An approximate index trades a little exactness for orders of magnitude less work.

Recap

  • kNN predicts by majority vote (or average) of the k training points nearest to the query.
  • Small k gives jagged, noisy boundaries; large k smooths them and eventually underfits. Pick k on validation data.
  • Distances add up feature differences, so always scale features first.
  • Training is free but prediction scans the data; indexes and approximate search make it fast.
  • In high dimensions raw distances lose meaning; use fewer, better features or learned embeddings.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up