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.
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.
- k = 3 The three nearest neighbours are two red and one blue. Red wins 2 to 1.
- 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.
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
Try this:
- 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.
- Raise k to 15, then 25. Watch the islands disappear and the boundaries smooth out. Do any small regions of a class vanish completely?
- 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
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
| Option | Wins when | Loses 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
-
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.
-
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.
-
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.
-
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.
Next up
- From notebook to production learning path