KNN is probably the dumbest algorithm in machine learning. Other algorithms need training: gradients, iterations, convergence. KNN doesn't. During "training" it does exactly one thing — store the data unchanged. When new data arrives, it computes distances to every stored point, picks the K nearest, and lets them vote. The majority wins.
It's that simple. A 1967 paper proved that this dumb approach has an error rate at most twice the theoretical optimum. And it's still alive and well — every vector database, every RAG retrieval pipeline searching for "the most relevant document chunks," runs on this algorithm at its core. The name changed, the scale grew, but the kernel is the same.
An Algorithm That Doesn't Need Training
What does "no training" mean? Look at the timing. For 5000 points, KNN training takes 41 microseconds — all it does is copy the data. Prediction, though, requires computing distances against all 5000 points per query: 0.43 seconds.
So KNN is a lazy algorithm: zero training cost, full prediction cost. Other models are the reverse — neural nets train for hours but predict in milliseconds. This determines its use cases: frequently changing data (just add a point, no retraining), infrequent queries, and modest data sizes.
It has only one knob: K.
With K=1, every training point is its own nearest neighbor, so training accuracy is necessarily 100%. That's memorization, not learning. Larger K smooths the decision boundary and resists noise, but too large goes to the other extreme — when K equals the sample count, every query's neighbors are everyone, and the answer is always the majority class. Nothing was learned.
A common starting point is K = sqrt(n). The course recommends cross-validation instead: 300 samples, 5 folds, scanning K from 1 to 31, optimal value 7. Note that 7 differs considerably from the heuristic's 17. Heuristics are only starting points — your own data decides.
The Distance Defines the Neighbors
In KNN, "near" is entirely defined by the distance function. Change the metric, and you change who the neighbors are.
Euclidean distance is the default — straight-line, intuitive. Manhattan distance sums absolute differences without squaring, so large gaps aren't amplified and it's more robust to outliers. Text data calls for cosine distance — between two word vectors, length is noise (caused by document length), direction is meaning (the topic).
Minkowski distance unifies these in one formula with a parameter p: p=1 is Manhattan, p=2 is Euclidean, p→∞ becomes "only the dimension with the largest gap matters." Computing on [1,2,3] vs [4,0,6]: p=1 gives 8, p=2 gives 4.69, p=∞ gives 3. The larger p, the more the worst dimension dominates.
One enhancement: distance weighting. By default, each of K neighbors gets one vote — but why should a neighbor at distance 0.1 have the same weight as one at 5.0? Set the weight to 1/distance so closer neighbors speak louder. Add a small constant to avoid division by zero, in case a query point coincides exactly with a training point.
The High-Dimensional Trap: Numbers That Don't Match
KNN's most famous weakness is the curse of dimensionality. The course claims: scatter random points in 100-dimensional space, and the ratio of farthest to nearest distance drops to just 1.01; at 1000 dimensions, 1.001. All points are equally far — "nearest" loses meaning.
The trend is real. Scattering 200 points in 2D, the farthest/nearest ratio is 44; in 10D, 3.0; in 100D, 1.37. The contraction is visible.
But that 1.01 doesn't reproduce. Running the course's own example code, it prints 1.3748. For the ratio to truly approach 1.01 at this convergence rate, you'd need two more orders of magnitude in dimensions. The textbook took the "limit as dimension goes to infinity" and presented it as the "state at 100 dimensions" — right direction, wrong timetable. Incidentally, in the same course's first season on dimensionality reduction, the same table printed 1.02 for 100 dimensions — two tellings of the same phenomenon, two different numbers, neither matching the demo code.
The curse hits KNN in a concrete way: only a few dimensions carry useful information; the rest are pure noise. One experiment: labels determined only by the first two dimensions (positive if their sum exceeds 1), then keep adding pure noise dimensions. Accuracy is 97.5% in 2D, drops to 75% in 50D. No information was lost — but distance got diluted by 48 noise dimensions, and "near" no longer means near in the useful directions.
Hence the course's rule of thumb: KNN works well up to roughly 20–50 features; beyond that, reduce dimensions first, then query.
Without Scaling, Minority Classes Go Blind
Distance sums differences across dimensions, so scale is everything. Differences in age are single digits; differences in salary are tens of thousands. Without preprocessing, distance is almost entirely decided by salary — including age is the same as not including it.
The course's demo: a dataset where positive class requires "age > 45 and salary < 40k." Without scaling, accuracy is 87.5%; with scaling, 95%. Looks fine? One background number goes unprinted: 85% of the samples are negative. A dunce that blindly guesses negative for everything scores 85%. The unscaled KNN beats that dunce by just 2.5 percentage points.
The real damage hides in recall. Without scaling, only 2 of the 6 positive cases among 40 test samples are caught — because neighbor search only looks at salary, and the age condition goes completely blind. With scaling, 4 of 6 are caught. The 7.5-point accuracy gap is the surface symptom; the jump in minority-class recall from 33% to 67% is what scaling actually bought.
Judging by accuracy under class imbalance is an old statistics trap, and this demo happened to walk right into it.
Weighted Voting: Futile for Classification, Lifesaving for Regression
Distance weighting's classification results were awkward: with K = 3, 7, 15, 25, the weighted version versus plain was tied, minus 2.5 points, minus 2.5 points, tied. It never won a single round. The demo code prints the conclusion "weighting makes large K safer," but its own table doesn't support that sentence.
Regression is where weighting shines. Fitting a noisy sine curve: at K=50 unweighted, mean squared error is 0.0733; weighted, 0.0269 — 2.7x better. Half the reason is obvious: K=50 means averaging 50 neighbors of wildly varying distance with equal weight, and far neighbors flatten the curve; weighting silences them, so of those 50 neighbors only the near ones actually work.
One more fact worth remembering: KNN regression can never extrapolate. If all training targets are between 0 and 100, it will never predict 200 — the prediction is a (weighted) average of neighbor targets, and an average can't exceed the values being averaged. That's both honesty and a ceiling.
KD-Trees: Not Scanning Everyone Per Query
Brute-force KNN computes n distances per query — slow once points pile up. A KD-tree partitions space by feature axes: first split at the x-axis median, then the y-axis median, and so on recursively. A query first descends to the leaf containing the query point, then backtracks only through branches that "might hide closer points," skipping the rest.
The gains are real: 2D data, 5 nearest neighbors, 5000 points — brute force 0.62s, KD-tree 0.006s, a 107x speedup. Correctness was cross-checked: 50 random queries compared neighbor-by-neighbor between KD-tree and brute force, zero mismatches.
The cost: it fails in high dimensions. When dimensions are high, it's unclear which branch a query point belongs to, the un-prunable branches multiply, and it degenerates back to brute force. So KD-trees work from 3D up to about 20 dimensions; ball trees stretch to around 50; beyond that, approximate methods rule — HNSW, IVF, the house algorithms of vector databases, covered in season 1, lesson 14.
Both KD-trees and ball trees are exact: what they find is the true nearest neighbor, no exceptions. Approximate methods trade "probably correct" for speed — that's what sustains billion-scale vector search.
Exercise
Take 1000 random points, run at 2, 5, 10, 50, 100, and 500 dimensions, compute the ratio of farthest to nearest pairwise distances, and plot the curve as it contracts with dimension. Note you must use all pairwise distances — the course demo only sampled 500 pairs, and sampled minimum distances will be biased high. How high do you have to go in dimensions before the ratio truly approaches 1.01? Run this, and the curse of dimensionality stops being just words in a textbook.