predict = vote of the k closest points is a complete learning algorithm. Store the data, choose a ruler, let the neighbourhood decide — and choose k to balance noise against blur.
KNN does no fitting: keep every labelled example, and when a query arrives measure its distance to all of them. That makes it a lazy learner — zero training time, all the work at prediction time — the opposite trade-off from an SVM or a neural network.
fit = store · predict = scan + votek = 1 follows every point, including the noisy ones (high variance, overfit). Very large k ignores local structure and predicts the global majority (high bias, underfit). Odd k avoids ties; a common start is k ≈ √N, tuned by cross-validation.
k↑ = smoother regions, less varianceEuclidean distance measures straight-line closeness; Manhattan sums axis-aligned steps; cosine measures angle and ignores length. Different rulers pick different neighbours — and unlike the others, cosine needs no feature scaling because it divides the lengths away.
L2 · L1 · cosine = three answersK-nearest neighbours is memory as a model: keep every labelled example, measure the query against all of them with a chosen distance, and let the k closest — or, weighted, the closest to closest — vote.
By the end you will be able to run KNN by hand on a small set, read the bias–variance trade-off off the k dial, choose between Euclidean, Manhattan and cosine distance for a dataset, explain why unscaled features break the ruler, and say when exact search needs a KD-tree or an approximate index instead.
Most algorithms compress the training set into parameters. K-nearest neighbours keeps the training set itself and looks things up at prediction time. That single design choice decides everything else.
K-nearest neighbors (KNN) is an instance-based, or lazy, learner. “Training” is one line: store every labelled example. When a new query point arrives, KNN computes its distance to every stored point, sorts the list, keeps the k closest, and lets them vote — the majority label for classification, the average value for regression. There are no weights, no gradients, no epochs.
That sounds almost too simple, but the design carries real consequences. The model can adapt to new data instantly (append a point), it can represent arbitrarily wiggly boundaries, and it never underfits by construction — with k = 1 it reproduces the training set exactly. The price is paid at prediction time, when every query scans the whole dataset.
Before the algorithm can call anything “nearest,” someone has to define near. That definition — the distance function — is not a detail. It is a modelling choice as important as the loss function in a neural network, and the next chapters show it changing predictions on the same data. KNN is the algorithm; the distance is the opinion.
Drag the ringed query point (or click anywhere) and slide k. The rings and connectors show exactly which points get a vote; the table below lists every distance, so the prediction is never a mystery.
With k = 1 the nearest point alone decides; with k = 9 nearly the whole set votes and the answer tends toward the bigger cluster.
| Aspect | Lazy (KNN) | Eager (SVM, neural net) |
|---|---|---|
| Training time | O(1) — just store the data | O(n · epochs) — fit parameters |
| Prediction time | O(n · d) per query — compare to everything | O(d) or O(parameters) — apply the model |
| Memory at prediction | The entire training set | The model parameters only |
| New data arrives | Add the point — no retraining | Retrain the model |
| Decision boundary | Implicit, computed on the fly | Explicit, fixed after training |
The lab’s six-point set, with the query at (2.0, 2.0). Two candidates, one per class:
With k = 1 the prediction is #1 → A. With k = 3 the third neighbour joins: #2, also class A. The vote is 2–1 and the prediction stays A — but with k = 5 the B points outnumber A 3–2 and the prediction flips. Same data, same ruler; only the size of the jury changed.
What must be chosen before KNN can decide which point is 'nearest'?
Given a labelled dataset and a query point, the entire method fits on an index card. The craft lives in the choices around it: the ruler, the k, and what the neighbours vote on.
k.Everything hangs on step 1: “distance” is a choice, and chapter 04 swaps the ruler. Everything else is bookkeeping. Because the scan touches every stored point, a prediction costs O(n · d) time for n examples with d features — cheap to train, expensive to serve.
The regression flavour. Swap the vote for an average and KNN predicts numbers instead of labels: the prediction is the mean target of the k neighbours (chapter 06 weights that average by closeness). Numeric check: neighbours with targets 10, 20 and 40 give (10 + 20 + 40) / 3 = 23.33. The result is piecewise-constant — KNN can only output values that exist in the neighbourhood, so if every training target lies between 0 and 100, it will never predict 200. No extrapolation, ever.
The six-point worked example from this chapter. Move the query, switch the ruler, change k — every rank, vote and prediction is recomputed from the displayed coordinates, and the arithmetic is printed.
| Rank | Point | Class | Δ from query | d² | d | Votes at k = 3 |
|---|---|---|---|---|---|---|
| 1 | #1 (1.2, 2.0) | A | (0.80, 0.00) | 0.64 | 0.800 | ✓ |
| 2 | #4 (2.9, 1.6) | B | (-0.90, 0.40) | 0.97 | 0.985 | ✓ |
| 3 | #2 (2.0, 3.1) | A | (0.00, -1.10) | 1.21 | 1.100 | ✓ |
| 4 | #5 (3.4, 2.6) | B | (-1.40, -0.60) | 2.32 | 1.523 | — |
| 5 | #6 (0.6, 0.8) | B | (1.40, 1.20) | 3.40 | 1.844 | — |
| 6 | #3 (0.4, 3.4) | A | (1.60, -1.40) | 4.52 | 2.126 | — |
Every number in this table comes from the coordinates displayed in the console above. Change the query there and watch the whole trace — distances, ranks, votes — recompute from the same formula.
def _predict_one(self, x):
distances = []
for i in range(len(self.X_train)):
d = self.distance_fn(x, self.X_train[i])
distances.append((d, self.y_train[i]))
distances.sort(key=lambda pair: pair[0])
neighbors = distances[:self.k]
return self._classify(neighbors)
def _classify(self, neighbors):
votes = {}
for _, label in neighbors:
votes[label] = votes.get(label, 0) + 1
return max(votes, key=votes.get)KNN has a single hyperparameter, and it controls the entire bias–variance trade-off. Turning it up smooths the decision boundary; turning it down lets the model chase every point.
k = 1 is the most flexible model possible: each query copies its single nearest neighbour, the decision regions wrap every training point in its own island, and training accuracy is exactly 100%. That perfect training score is the tell — the model has memorized the noise, and on new data it wobbles (high variance).
Large k is the opposite: every vote averages over a big neighbourhood, so regions smooth out and noisy points are out-voted. Push it all the way to k = n and the query no longer matters at all — every prediction is the global majority class (high bias). The useful range is in between: a common starting point is k ≈ √n, refined by cross-validation. For binary classification use an odd k so a vote can never split evenly.
Every pixel is classified by majority vote of its k nearest points. Slide k from 1 to 25 and watch the jagged islands smooth into continents. The inset line is honest leave-one-out accuracy: each point is predicted with itself removed.
The curve is computed from the displayed points only, one fold per point. A U-shape — high error at both ends, a low middle — is the bias–variance trade-off made visible.
| k | Behaviour |
|---|---|
| k = 1 | Boundary follows every point. Zero training error, high variance. Overfits |
| Small k (3–5) | Sensitive to local structure. Can capture complex boundaries |
| Large k | Smoother boundary. More robust to noise. May underfit |
| k = N | Predicts the majority class for every query. Maximum bias |
Seven points on a line — three class A close together, one noisy class B beside them, then three far-away B points. The query is x = 0.45:
The lesson’s decision-region lab draws exactly this trade-off across a two-dimensional dataset: the inset leave-one-out curve is high at both ends and lowest somewhere in the middle. The middle is where the model has enough neighbours to ignore noise but still enough locality to be useful.
You raise k from 1 all the way to the dataset size n. What happens to the decision regions?
Euclidean, Manhattan and cosine distance are three different answers to “how close are these two points?” On the same data, they can pick different neighbours and deliver different predictions.
Euclidean distance (L2) is the straight-line ruler: d = √(Σ(aᵢ − bᵢ)²) — square every feature difference, add them, take the square root. It is the default in most libraries, and it is the one that suffers when features are not scaled.
Manhattan distance (L1) walks city blocks: d = Σ|aᵢ − bᵢ| — add the absolute differences. Because it does not square, a single large difference is not amplified, which makes L1 more robust to outliers than L2.
Cosine distance measures the angle between vectors and ignores their lengths: d = 1 − (a·b)/(‖a‖‖b‖), which runs from 0 (same direction) to 2 (opposite). It is the standard ruler for text and embeddings, where a long document and a short one on the same topic should count as similar. It also needs no feature scaling, because dividing by the two norms already removes the units.
Minkowski distance is the family that contains L1 and L2: d = (Σ|aᵢ − bᵢ|^p)^(1/p) — sum the p-th powers and take the p-th root. p = 1 is Manhattan, p = 2 is Euclidean, and p → ∞ is Chebyshev distance, the largest single feature difference.
Click or drag the query, switch the ruler, and watch both the highlighted neighbours and the background regions change. Same points, same k — only the definition of “near” changed.
Cosine distance never looks at length, so its regions are wedges of direction. Near the origin the direction is ill-defined — a reminder that zero vectors have no angle.
| Data type | Best metric | Why |
|---|---|---|
| Numeric features, similar scale | L2 (Euclidean) | The default: straight-line closeness in space |
| Numeric features with outliers | L1 (Manhattan) | Does not square the differences, so one huge gap cannot dominate |
| Text embeddings | Cosine | Length is noise, direction is meaning |
| High-dimensional and sparse | Cosine or L1 | L2 suffers most from distance concentration |
| Mixed feature types | Custom metric | Sum per-type distances with weights you choose |
Take a = (1, 2, 3) and b = (4, 0, 6). The per-feature differences are 3, 2 and 3:
Cosine distance needs no per-feature p; it compares direction only. Here a·b = 22, ‖a‖ = √14, ‖b‖ = √52, so dcos = 1 − 22 / (√14·√52) = 0.185 — the two vectors point in fairly similar directions even though their straight-line distance is large.
Now the payoff. The six-point set from chapter 02, query (2.0, 2.0), k = 3:
Phase 1, Lesson 14 develops norms and distances properly — including why every p-norm obeys that ordering and when the differences matter. This lesson only needs the three rulers that KNN uses most.
You are comparing TF-IDF vectors of news articles. One article is 10× longer than another but covers the same story. Which metric is designed to call them similar?
A distance is a sum over features, and features carry units. Unless every column is put on a comparable scale first, KNN is not measuring similarity — it is measuring whichever feature happens to be written in the largest units.
A squared Euclidean distance is (Δx₁)² + (Δx₂)² + … — a sum of per-feature contributions. Salary measured in dollars produces differences in the tens of thousands; age measured in years produces differences in the tens. Squared, that is a factor of roughly a million, so the salary column contributes essentially 100% of the distance and age might as well not exist.
The standard fix is standardization: for each feature, subtract its mean and divide by its standard deviation, z = (x − μ) / σ. Plain English: express every value as “how many typical deviations away from average is this?” After that, one year of age and one salary σ are numerically comparable. (Min–max scaling, (x − min)/(max − min), is the other common choice when you need a bounded range; cosine distance needs neither.)
Two disciplines keep this honest. First, fit the scaler on the training set only, then apply the same μ and σ to validation and test data — otherwise information from the test set leaks into training. Second, scaling never changes cosine distance, because dividing every vector by its length removes the units before the angle is measured.
Eight people with an age and a salary (class A / B). Move the query and compare the two panels: raw units on the left, z-scores on the right. Same k, same people — but the neighbours, the vote, and sometimes the prediction change.
A salary difference of 40,000 contributes 1,600,000,000 to a squared distance; an age difference of 30 contributes 900. Until both features are rescaled, the salary column is the only one the ruler can see.
The classic two-feature example. Query: age 30, salary $50,000. Candidate P1: age 31, salary $90,000. Candidate P2: age 60, salary $55,000.
Notice that scaling does not invent information — it changes which information the ruler can hear. Whether P2 should be nearer is a modelling question. But silently letting salary drown out age is a bug, not a model.
Uniform KNN gives every chosen neighbour exactly one vote. Distance weighting turns that vote into a volume knob: the closer the neighbour, the louder it speaks.
Standard KNN treats all k neighbours as equals. But a neighbour at distance 0.5 is far better evidence than one at distance 4.0. Distance-weighted KNN gives neighbour i the weight wᵢ = 1 / (dᵢ + ε), where ε is a tiny constant that keeps the division finite when a training point coincides with the query. For classification, the votes become weighted sums: score(class) = Σ wᵢ over neighbours of that class. For regression, the prediction becomes the weighted average ŷ = Σ wᵢyᵢ / Σ wᵢ.
The practical payoff: weighted KNN is much less sensitive to k, because adding a far-away neighbour contributes very little to either side. That makes larger k safer — the smoothness of a big neighbourhood without letting distant points drown out the local signal.
Five points on a line, two of class A close to the query and three of class B farther away. Slide the query and k: the uniform vote counts bodies, the weighted vote counts 1 / (distance + ε).
Weighting is a volume knob on distance, not a new algorithm: sort, take k, then let each neighbour speak in proportion to how close it stands.
First the smallest possible flip. Three neighbours vote: class A at distance 0.5, class B at 1.0, class B at 2.0.
Now the six-point set from chapter 02. At k = 4 the uniform vote is a perfect 2–2 tie; weighting breaks it. And with the Manhattan ruler at k = 5, weighting flips the majority entirely:
Weighting is not automatically better — it is a different prior. If local labels are noisy but the broader region is reliable, uniform voting over a larger k can beat weighting. The honest way to choose is cross-validation on both variants.
A class-A neighbour sits at distance 0.5 and a class-B neighbour at distance 2.0. In a distance-weighted vote, who has more say?
KNN’s laziness shifts all cost to prediction, and its accuracy falls apart as dimensions grow. Both problems have standard, engine-room answers.
Storing the data is O(1) per example — KNN’s famous zero training time. Predicting is the bill: each query computes n · d per-feature differences for n examples with d features, then sorts n distances. A million 768-dimensional document embeddings means roughly 768 million subtractions and squares per query. Brute force does not scale to that, so production systems swap the scan for an index.
A KD-tree recursively splits the data along one feature axis at a time, at the median of the current region. A query walks down to its leaf, then backtracks, skipping any region whose bounding box is farther than the best neighbour found so far. In low dimensions that prunes almost all of the tree — average O(log n) per query. A ball tree does the same trick with nested hyperspheres instead of axis-aligned boxes, and keeps pruning longer in moderate dimensions (up to roughly 50).
Beyond that, exact search is abandoned for approximate nearest neighbour indexes: HNSW (a navigable similarity graph), IVF (cluster first, scan a few clusters), and product quantization (compress vectors, compare compressed codes). They trade a little recall for orders of magnitude of speed, and they are what vector databases actually run.
One seeded run: 80 uniform random points in the unit cube [0, 1]^d, all 3,160 pairwise Euclidean distances measured. The ratio of the farthest to the nearest says how much the notion of “nearest” still means; the spread column says how tightly the distances bunch around their average:
| Dimensions d | max / min distance | std / mean distance | mean distance |
|---|---|---|---|
| 2 | 86.74 | 0.467 | 0.514 |
| 5 | 23.34 | 0.281 | 0.927 |
| 10 | 5.47 | 0.198 | 1.258 |
| 50 | 1.85 | 0.082 | 2.876 |
| 100 | 1.48 | 0.057 | 4.070 |
At d = 2 the ratio is wide — 87 to 1 — so there are genuinely near and far points. By d = 100 it has collapsed to about 1.5, and the standard deviation of the distances is only 5.7% of their mean: every point is nearly the same distance from the query, and the ranking KNN depends on becomes noise. That is distance concentration, a mathematical fact and not a quirk of the sample. The exact extremes depend on the sample (the source’s 200-point run reports a max/min ratio of about 1.01 at d = 100 — the same phenomenon, measured a slightly different way).
A second view is geometric. Inscribe a sphere in the unit cube: the sphere’s share of the cube’s volume collapses as dimension grows, because the corners of the cube hold almost all of the volume and the sphere touches none of them.
| Dimensions d | sphere volume / cube volume |
|---|---|
| 2 | 0.7854 |
| 4 | 0.3084 |
| 10 | 0.0025 |
| 50 | 1.5e-28 |
| 100 | 1.9e-70 |
Practical consequence: KNN works well up to roughly 20–50 features. Past that, either reduce dimensionality first (PCA, UMAP, t-SNE) and run KNN in the smaller space, or use an index that exploits the data’s intrinsic lower-dimensional structure — or switch to a model class that does not rely on raw distances at all.
import faiss
index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)Answer before you look. The scaling question and the weighted-vote question are the ones that show up in real debugging sessions.
0 / 6 answered · 0 correct
01KNN is called a “lazy learner.” What does that mean?
02Why is feature scaling critical for KNN?
03In 100 dimensions with uniform random points, what happens to the ratio of max distance to min distance?
04Which distance metric is most appropriate for comparing text documents represented as TF-IDF vectors?
05What happens to the KNN decision boundary as K increases from 1 to N (the full dataset size)?
06What does distance-weighted KNN change about the vote?
Click a card to swap the lazy description for what it actually means.
Four short problems with exact numbers. Try first; a worked answer is one click away.
Points: #1 A (1.2, 2.0), #2 A (2.0, 3.1), #3 A (0.4, 3.4), #4 B (2.9, 1.6), #5 B (3.4, 2.6), #6 B (0.6, 0.8). L2: #1 0.800, #4 0.985, #2 1.100, #5 1.523, #6 1.844, #3 2.126 → k = 3 neighbours #1, #4, #2 → A 2, B 1 → predict A. L1: #1 0.800, #2 1.100, #4 1.300, #5 2.000, #6 2.600, #3 3.000 → #1, #2, #4 → A 2, B 1 → predict A. Cosine: #5 0.0088, #6 0.0101, #2 0.0225, #1 0.0299, #4 0.0393, #3 0.2151 → #5, #6, #2 → B 2, A 1 → predict B. Cosine changes the answer because it ignores vector length: #5 (3.4, 2.6) and #6 (0.6, 0.8) point in directions closer to (2, 2) than #1 and #2 do, even though a straight line puts #1 closest. Same data, same k — the definition of “near” decided the label.
Raw: P1 = √((31 − 30)² + (90,000 − 50,000)²) = √(1 + 1,600,000,000) = 40,000.0000125. P2 = √((60 − 30)² + (55,000 − 50,000)²) = √(900 + 25,000,000) = 5,000.09. Raw units say P1 is “nearer.” Range-scaled: P1 = (0.01, 0.40) → √(0.0001 + 0.16) = 0.4001; P2 = (0.30, 0.05) → √(0.09 + 0.0025) = 0.3041. Now P2 is nearer. Salary's share of the squared raw distance: P1 = 1,600,000,000 / 1,600,000,001 = 99.9999999%; P2 = 25,000,000 / 25,000,900 = 99.9964%. Almost all of the ruler was measuring salary, so the “nearest” point had almost nothing to do with age.
Distances from 0.45: 0.4 A 0.05, 0.6 B 0.15, 0.2 A 0.25, 0 A 0.45, 3.0 B 2.55, 3.2 B 2.75, 3.4 B 2.95. k = 1: nearest is the A at 0.4 → A. k = 3: A (0.4), B (0.6), A (0.2) → A 2, B 1 → A. k = 5: adds A (0) and B (3.0) → A 3, B 2 → A. k = 7: every point votes → A 3, B 4 → B. The noisy B at 0.6 lives beside the A cluster, so local votes keep seeing A; only when k grows large enough for the three far-away B points to outvote the local structure does the prediction flip. At k = N the result is independent of the query — it is always the global majority class, which is the underfitting extreme.
Unweighted: (10 + 20 + 40) / 3 = 70 / 3 = 23.333. Weights: 1/1 = 1.000, 1/2 = 0.500, 1/4 = 0.250, total 1.750. Weighted: (10·1 + 20·0.5 + 40·0.25) / 1.750 = (10 + 10 + 10) / 1.750 = 30 / 1.750 = 17.143. Weighting pulled the prediction toward the nearest neighbour (10) instead of letting two distant points dominate. A point at d = 0 would give w = 1/0 = ∞ without ε, making the weighted average undefined (or letting one point take over completely); with ε, its weight is a huge but finite 1/ε, so the prediction copies that neighbour's value, which is exactly what a duplicate of the query should do.
You do not need to master these here. Each one gets a proper treatment in its own lesson; the one-line meaning is enough to keep reading. Orange dotted underlines in the prose point back to this list.
This lesson is a port of an open course. Everything here traces back to it — and the next step is running the code yourself.
Lesson text adapted from AI Engineering from Scratch (Phase 02, Lesson 06) and the Math Foundations Notebook reference build. Interactive figures, the six-point worked example and its exact distance tables, the decision-region and metric labs, the scaling panels, the weighted-vote board, the KD-tree and curse-of-dimensionality figures, worked exercise answers and the numeric checks are original to this page. Every lab runs in your browser.