Concept30 minBefore this:Vectors, Dot Products & Cosine Similarity Missing Values & Feature Scaling

k-Nearest Neighbours

No training at all: how can copying your neighbours work, and when does it fail?

The situation

You want to automate an inspector who judges a new part by recalling similar ones. Your first version, with k = 1, scores 100% on training data. The interviewer asks:

How does k-NN make a prediction, and what does k control?

Running example: the same factory as the SVM lesson: two sensor readings per part, pass or fail, with a curved boundary between the classes (simulated "two moons", 120 training parts, 30% noise). Test accuracy uses 1,000 fresh parts. Every k-NN on this page runs live in your browser by brute-force search.

"This part looks like those parts"

An experienced inspector doesn't fit equations. They look at a new part and recall similar ones they've seen: "readings like these usually failed". k-NN is that habit written as an algorithm. It needs no training, makes no assumption about the shape of the boundary, and can follow a curved boundary that a linear model can't. The price is paid at prediction time, and in the choice of what "similar" means.

The idea

Think of judging a new part by polling the most similar parts you've seen. Ask just one, and an odd neighbour can mislead you. Ask too many, and you're polling parts that aren't similar at all.

Illustrative. The answer can change with k, so you pick k by validation.

Play

Try to break it. Start at k = 1, move to about 15, then push k as high as it goes. Watch the shading and the test accuracy.

Choosing k

k is a bias–variance dial

training accuracy

–

test accuracy (1,000 new)

–

best k on test

–

Shade = share of the k neighbours voting pass. k = 1: islands around noisy parts. k ≈ 15: follows the moons. k = 119 (all but one training part): the vote loses all local shape and test accuracy falls to 67%.

Small k: low bias, high variance (the boundary jumps with each noisy point). Large k: high bias (the vote reaches into the other moon). Test accuracy on this data peaks at k = 13–15 (89.9% and 89.7%) and drops to 79.1% at k = 61. Pick k by cross-validation; for two classes, use odd k to avoid tied votes (with k = 4, 71 of the 1,000 test parts got an exact 2–2 tie).

Now say why: why does accuracy on new parts rise and then fall, when training accuracy starts at 100%?

Maths

In one breath

k-NN doesn't learn a model at all. It stores the training set, and to classify a new point it finds the k closest stored points and takes a vote (or an average, for regression). Small k memorises noise; large k blurs the boundary; you pick k by cross-validation. Because everything is a distance, feature scaling is not optional, and in high dimensions all distances start to look alike, so "nearest" stops meaning much. Prediction is the expensive part (search the whole set), which is why KD-trees, ball trees and, at scale, approximate nearest-neighbour indexes (the engines behind vector search and RAG) exist.What you'll be able to do after this: explain the bias–variance effect of k, show why scaling matters with numbers, state the Cover–Hart bound, explain distance concentration, and connect k-NN to vector databases.

class +1 (pass)class −1 (fail)the query / its neighbourhoodnumberstest accuracy / winfailure

A distance, a neighbourhood, a vote

Then the prediction is a vote among the k nearest stored points. Read as a probability, it's simply a share:

scikit-learn: neighbours classification "is computed from a simple majority vote of the nearest neighbors of each point" neighbors guide. For regression, average the neighbours' targets instead.

Swipe sideways to see the whole diagram.

A new part arrives (the diamond). We have its two sensor readings and thirteen stored parts with known labels.
k = 1: the single closest part failed, so predict fail.
k = 3: the circle grows to the three closest. Two passed, one failed: predict pass.
k = 5: two more neighbours, both failed. Now it's 3 fail vs 2 pass: predict fail.
Same data, same query, three answers. k is the one knob that matters most, and the sections below show how to set it.

One principle

Similar inputs have similar labels, locally

k-NN assumes only one thing: the label changes smoothly enough that nearby points usually share it. Everything else follows from making "nearby" meaningful: how many neighbours (k), how much each counts (weights), what distance (and on what feature scale), and how many dimensions the distance lives in. The sections below take those one at a time.

A guarantee for the simplest version

Cover & Hart (1967): with infinitely many training points, the 1-NN error R is at most twice the best possible (Bayes) error R*. For two classes, R* ≤ R ≤ 2R*(1 − R*). "In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor" IEEE Trans. Inf. Theory 13. It's an asymptotic result: with finite data, and especially in high dimensions, it says nothing about how close you are.

Distance weighting

Let closer neighbours count more

scikit-learn's weights="distance" "assigns weights proportional to the inverse of the distance from the query point" neighbors guide. Switch it on in the Play lab, in the Intuition tab. Two effects to notice:

It makes large k forgiving. At k = 61, test accuracy rises from 79.1% (uniform) to 86.2% (weighted): far neighbours from the other moon count for little.
Training accuracy becomes 100% at every k. Each training point is at distance 0 from itself, with infinite weight. So with weighted votes, training accuracy tells you nothing; only validation does.

At small k, weighting changed little here (k = 5: 89.3% uniform vs 87.6% weighted). It's not a free win; treat it as a hyperparameter.

Scaling

Change the units, change the neighbours

Suppose sensor 1 is logged in centimetres instead of metres: every value ×100. Nothing about the parts changed, but now a 1 cm difference on sensor 1 counts as much as a whole unit on sensor 2. Distance is dominated by sensor 1, and sensor 2 is effectively ignored.

test accuracy, k = 15

–

sensor 1 spread vs sensor 2 spread

–

The plot always shows the original readings; only the distance used inside k-NN changes. In centimetres the boundary turns into vertical stripes: only sensor 1 decides.

Test accuracy at k = 15 falls from 89.7% to 71.3% after the unit change, and standardising (subtract the mean, divide by the standard deviation, fitted on training data) brings it back to 88.3%. Standardisation makes every feature equally important by default, which is a choice too: if you know a feature matters more, weight it on purpose. my take

The curse of dimensionality

In many dimensions, everyone is about equally far

Take 500 random points in a D-dimensional cube and one random query. In 2-D, the farthest point is dozens of times farther than the nearest. In 1,000-D, the farthest is only about 11% farther. When the nearest and the farthest are nearly the same distance away, "nearest" carries little information.

Dimensions D

farthest ÷ nearest (mean of 20 queries)

–

relative contrast (far − near) ÷ near

–

Histogram for one query: each distance divided by that query's nearest distance. As D grows, the whole histogram squeezes against 1.

Beyer, Goldstein, Ramakrishnan & Shaft (1999) proved this: under broad conditions, as dimensionality grows the distance to the nearest neighbour approaches the distance to the farthest one ICDT 1999. It applies to i.i.d. features like these random cubes. Real data usually lives near a much lower-dimensional surface (images, text embeddings), which is why nearest-neighbour search on learned embeddings still works well. The practical moves: reduce dimensions (PCA, embeddings), select features, or use a distance that suits the data (cosine for embeddings). scikit-learn also notes that KD-trees lose their speed advantage as D grows.

In practice

Lazy learning, and how the search is made fast

scikit-learn calls k-NN "a type of instance-based learning or non-generalizing learning: it does not attempt to construct a general internal model, but simply stores instances of the training data" neighbors guide. So "training" is just indexing, and the work moves to query time:

Search method	Cost	When
Brute force	Compare with all N points: O(D·N) per query	Small N, high D, sparse data. scikit-learn's `auto` picks it when D > 15 or k ≥ N/2
KD-tree	About O(D log N) per query for small D	"very fast for low-dimensional (D < 20)" searches; for larger D "the cost increases to nearly O[DN]"
Ball tree	About O(D log N)	Nested hyperspheres; "can out-perform a KD-tree in high dimensions", depending on the data
Approximate NN (HNSW, IVF, product quantisation; FAISS and vector databases)	Sub-linear, trades a little recall for big speed-ups	Millions to billions of embedding vectors: semantic search, recommendations, RAG retrieval

First three rows: scikit-learn's neighbors guide docs. Approximate methods: my take; see the RAG at scale lesson for how retrieval uses them.

k-NN, end to end

Scale features (StandardScaler or a domain weighting), fitted on training data only.
Reduce dimensions if D is large (PCA, or use embeddings from a model).
Choose the metric: Euclidean for scaled numeric features, cosine for embeddings, Hamming/Jaccard for binary sets.
Cross-validate k (odd for binary) and weights (uniform vs distance).
Pick the index: brute force for small N, KD/ball tree for low D, approximate NN (FAISS, HNSW) for millions of vectors.

When to use it

Use k-NN when

A quick, assumption-free baseline on small, low-dimensional data
You have good embeddings: similarity search, "more like this", recommendations
Data changes constantly and retraining is awkward

Reach for something else when

Many raw features or many irrelevant ones: trees or linear models
Strict latency on large N without an ANN index
You need a compact model or feature effects

The answer that sounds right

The trap

"Use k = 1: the closest example is the best evidence"

With k = 1 every training part is its own nearest neighbour, so training accuracy is always 100%. That number is meaningless. On our noisy moons, 1-NN scores 85.8% on new parts, while k = 15 scores 89.7%. The single nearest neighbour is often one of the noisy parts, and 1-NN copies its mistake into a little island of wrong predictions around it. scikit-learn: "a larger k suppresses the effects of noise, but makes the classification boundaries less distinct" neighbors guide.

Caveats

Strengths

No training; add new data instantly
Any boundary shape; naturally multi-class
Easy to explain: "these similar cases"
The same machinery powers retrieval, recommendations and anomaly detection

Weaknesses

Slow, memory-hungry prediction: the model is the dataset
Needs scaling and a sensible metric
Breaks down with many irrelevant or raw high-dimensional features
Imbalanced classes: the majority dominates votes (weight or resample)

Say it

How does k-NN make a prediction, and what does k control?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

k-NN stores the training data and finds a new point's k nearest neighbours.
It takes a majority vote, or the average for regression.
There's no training, and the cost is at prediction time.
k trades variance for bias and is chosen by cross-validation.
It's distance-based, so you must scale features.
In high dimensions, distances concentrate and neighbours mean less.