K-nearest neighbours
KNN labels a new example by taking a vote among the most similar examples it has already seen — no training, no formula, memory and comparison only.
- 7 min read
- 3 reading levels
- Published
Read these first
On this page 5
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
K-nearest neighbours labels a new thing by taking a vote among the most similar things it has already seen.
Think of how you judge an unfamiliar fruit at the market. You pick it up and compare it with fruits you already know — its weight, its skin, its smell. If it matches the apples in your memory more than the oranges, you call it an apple. You never wrote down a rule. You compared.
K-nearest neighbours (KNN) is that habit turned into an algorithm. The K is how many remembered examples get a vote.
Why it exists
Most models study the training data and boil it down into a formula. That works when a clean formula exists.
But some problems resist formulas. What makes two songs feel similar? What makes two handwritten sevens the same digit? Nobody can write that rule down.
KNN skips the formula entirely. It keeps every example in memory. When a new case arrives, it finds the closest matches and lets them vote. People call this lazy learning — no work at training time, all the work at question time.
How it works
new fruit → measure distance to every stored fruit
→ keep the 3 closest: apple, apple, orange
→ vote: 2 apples beat 1 orange
→ answer: "apple"Small K listens to the single closest example, which can be a fluke. Big K listens to a whole crowd, which can drown out local detail. Choosing K is a balance between those two failures.
A real example you have seen
Open any shopping app and scroll below a product. The "similar products" strip is nearest-neighbour search: items closest to this one by price, category and description. Music apps do the same when they queue a song that "sounds like" the last one.
Remember this
- KNN stores examples and compares; it never builds a formula.
- The K closest examples vote on the answer.
- Everything depends on how you measure "close" — that choice is the whole game.
What to learn next
- Distance metrics — the "how close" choice that KNN quietly depends on.
- Train/test split — how to check a K choice honestly.
- Vector databases — industrial-scale nearest-neighbour search behind RAG.
Developer — Code and libraries.
Setup
pip install scikit-learnOutputs verified with scikit-learn 1.7.2 on CPU. Numbers may shift slightly on other versions.
A fruit sorter in 15 lines
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
# weight in grams, skin smoothness from 0 (rough) to 1 (smooth)
# label 1 = apple, label 0 = orange
X = np.array([[140, 0.90], [152, 0.85], [160, 0.80], [147, 0.92],
[115, 0.30], [125, 0.35], [133, 0.25], [120, 0.40]])
y = np.array([1, 1, 1, 1, 0, 0, 0, 0])
mystery = np.array([[138, 0.45]]) # apple-sized, but orange-like skin
for k in (1, 3, 7):
model = KNeighborsClassifier(n_neighbors=k).fit(X, y)
proba = model.predict_proba(mystery)[0]
print(f"k={k}: P(orange)={proba[0]:.2f} P(apple)={proba[1]:.2f}")k=1: P(orange)=0.00 P(apple)=1.00 k=3: P(orange)=0.33 P(apple)=0.67 k=7: P(orange)=0.43 P(apple)=0.57
Every K says apple. Now watch what scaling does to that verdict:
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
scaled = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=3))
scaled.fit(X, y)
p = scaled.predict_proba(mystery)[0]
print(f"scaled, k=3: P(orange)={p[0]:.2f} P(apple)={p[1]:.2f}")scaled, k=3: P(orange)=1.00 P(apple)=0.00
Same data, same K, opposite answer.
The walkthrough
Why the flip? Weight runs from 115 to 160 — differences of tens. Smoothness runs from 0.25 to 0.92 — differences below one. Raw distance is dominated by weight, so the skin barely counts. Our mystery fruit is apple-sized but orange-skinned. Unscaled KNN hears only the size.
StandardScaler rescales each feature to a comparable range, so both clues get a voice. After scaling, the orange-like skin wins the vote. For fruit the truth is debatable. The lesson is not: whichever feature has bigger units silently controls an unscaled KNN.
.fit(X, y) does almost nothing. It stores the data and builds a lookup structure. All real work happens inside predict, which is why KNN gets slow at prediction time, not training time.
predict_proba is the vote count. With k=7, 0.57 means 4 of 7 neighbours said apple. It is a fraction of votes, not a calibrated probability.
Common mistakes
Forgetting to scale. The single most common KNN bug, and it fails silently — you saw the verdict flip above. Put StandardScaler in a pipeline so it is never skipped.
Passing a 1D array at predict time. model.predict(np.array([138, 0.45])) raises:
ValueError: Expected 2D array, got 1D array instead: array=[138. 0.45]. Reshape your data either using array.reshape(-1, 1) if your data has a single feature or array.reshape(1, -1) if it contains a single sample.
scikit-learn always wants a 2D array: rows are samples, columns are features. Wrap the single fruit in double brackets: [[138, 0.45]].
Asking for more neighbours than you have samples. n_neighbors=9 with 8 stored fruits raises ValueError: Expected n_neighbors <= n_samples_fit, but n_neighbors = 9, n_samples_fit = 8, n_samples = 1.
Using an even K for two classes. A 2–2 vote is a tie, and the tie-break is arbitrary. Stick to odd K for binary problems.
Try it yourself
Set n_neighbors=8 so every stored fruit votes. Predict the mystery fruit and explain the probabilities you get before reading them. Then try KNeighborsClassifier(n_neighbors=7, weights="distance") and work out why the answer sharpens.
What to learn next
- Distance metrics — the "how close" choice that KNN quietly depends on.
- Train/test split — how to check a K choice honestly.
- Vector databases — industrial-scale nearest-neighbour search behind RAG.
Researcher — Mathematics and papers.
Formal setup
Given a training set $D = {(x_i, y_i)}_{i=1}^{n}$ with $x_i \in \mathbb{R}^d$ and labels $y_i$, a query point $x$, a distance $\rho$, and $N_k(x)$ — the set of the $k$ training points closest to $x$ under $\rho$ — the classifier is:
$$ \hat{y}(x) = \arg\max_{c} \sum_{x_i \in N_k(x)} \mathbb{1}[y_i = c] $$
Where:
- $n$ — number of stored training points; $d$ — number of features.
- $\rho$ — the distance function, usually Euclidean.
- $\mathbb{1}[\cdot]$ — the indicator function: 1 when true, 0 when false.
- $c$ — a candidate class label.
The distance-weighted variant replaces the indicator with weights $w_i = 1/\rho(x, x_i)$, so nearer neighbours count more.
Theory worth knowing
Cover and Hart (1967), Nearest neighbor pattern classification, proved the founding result: as $n \to \infty$, the 1-NN error rate is at most twice the Bayes error — the best any classifier can achieve. Half of all the information in an infinite sample sits in the single nearest neighbour. The method itself dates to Fix and Hodges (1951), a technical report on nonparametric discrimination.
Consistency requires $k \to \infty$ while $k/n \to 0$ — the vote must grow, but stay local. Stone (1977) gives the general universal consistency result.
Cost and the curse of dimensionality
- Training: $O(1)$ beyond storing the data (plus tree construction if used).
- Brute-force query: $O(nd)$ per prediction.
- KD-trees and ball trees reach roughly $O(d \log n)$ per query in low dimension, but degrade toward brute force as $d$ grows past ~20.
In high dimension, distances concentrate: the gap between the nearest and farthest neighbour shrinks relative to the distances themselves (Beyer et al., 1999, When is "nearest neighbor" meaningful?). Nearest-neighbour methods then need either dimensionality reduction or learned embeddings to stay meaningful.
Current practice
Exact KNN has largely given way to approximate nearest neighbour (ANN) search at scale: HNSW graphs (Malkov and Yashunin, 2018) and product quantisation in FAISS (Johnson et al., 2019) serve billion-point indexes with millisecond queries. Every modern vector database is, at its core, fast approximate KNN over embeddings.
What to learn next
- Distance metrics — the "how close" choice that KNN quietly depends on.
- Train/test split — how to check a K choice honestly.
- Vector databases — industrial-scale nearest-neighbour search behind RAG.