k-Nearest Neighbors

Basic k-Nearest Neighbors fits no parametric decision function. It stores the labeled points, and when a query arrives it measures the distance to every one of them, sorts the list nearest-first, and lets the k nearest vote — majority wins. That is the entire algorithm: no weights, no fitting, no model object beyond the data itself.

The other classifiers in this collection do their fitting before the query shows up and then only evaluate a fixed formula on it; kNN does all of its work after.

What makes that worth a lesson is the dial. k appears in exactly one line — the slice dists[:k] in knn_predict — so for the same query, changing it recomputes nothing rank built: same distances, same sorted order, a different cut through the same list. And yet that cut decides everything. In the default run the very same untouched query flips its class between k = 1 and k = 3, the k = 1 decision map grows an island around a single mislabeled point, and k = 9 erases the island while swallowing a real two-point outpost. One end of the dial memorizes everything, the other end forgets everything, and both ends are wrong.

The Model Is the Data

A linear classifier compresses its training set into a handful of numbers and throws the points away. kNN is the opposite extreme: it keeps every point and compresses nothing. There is no training loss, no gradient, nothing to converge — the brute-force model's setup stores the data; preprocessing or building a neighbor index can add work.

The bill arrives at query time instead. One prediction touches all N stored points: N distance computations, then a sort. On this lesson's 14 points that is nothing; on a million points it is the whole cost of the method, which is why some production systems put an index in front of the loop. An exact one — a KD-tree, a ball tree — returns exact neighbors and can avoid a full scan on favorable data, though worst-case and high-dimensional queries may still approach a full scan. An approximate one (HNSW, IVF) is faster still and gives up that guarantee: it usually finds the same neighbors, occasionally misses one, and on a billion vectors that trade can make large-scale retrieval practical. The brute-force loop on this page is the definition all of them accelerate.

The distance itself is plain Euclidean, d = √((p₁−q₁)² + (p₂−q₂)²). That formula silently assumes the axes are comparable — measure one feature in meters and another in millimeters and the millimeter axis can dominate the distances. Rescaling features is preprocessing, not part of the algorithm, but raw kNN without it can be quietly broken.

Which tells you where kNN belongs: a modest number of stored points, features you have standardized, and few enough dimensions that "near" still means something. Under those conditions it is the strongest baseline you can build in an afternoon, because it fits any decision shape the data happens to have. Outside them it degrades quietly rather than loudly — the queries just get slower and the neighbors get less meaningful.

What k Actually Changes

Since k only moves the cut, you can read its whole effect off one sorted list. At k = 1 the committee is a single point: whatever is closest — a fair neighbor or a labeling mistake — speaks for the neighborhood alone. At k = N the committee is everyone: the vote is the dataset's global majority regardless of where the query sits, and the "nearest" in k-Nearest Neighbors has stopped meaning anything. On noisy data like this lesson's, the useful k lives between those failure modes, trading noise-resistance against resolution: a bigger committee can outvote isolated mislabeled points, and by the same construction it can outvote true structure that loses its local majority among the k nearest.

The lesson's default dataset carries both failure directions at once. One B-labeled point sits deep in A territory — a labeling mistake — and two honestly-labeled A points form a small outpost beside B's mass. k = 1 believes the mistake; k = 9 erases the outpost. Nothing distinguishes "noise to smooth away" from "small structure to keep" except whether it holds a local majority of the k nearest votes, and k sets that bar. Choosing it well is a validation problem — measure accuracy on held-out data across k and pick the winner — which is a later lesson's subject.

The Decision Boundary kNN Never Draws

A linear classifier stores its boundary as numbers. kNN has no boundary anywhere in it — only a procedure. But you can make the boundary visible by brute force: ask the same distance-sort-slice-vote question at every location on the plane and tint each answer. The animation samples a 55 × 55 grid (a display resolution, not a property of the algorithm — the true boundary is where the vote changes, and the cells only approximate where that is).

The shape of that emergent map is k's signature. At k = 1 it is the Voronoi diagram of the data: every point rules the region nearer to it than to anyone else, mistakes included, and training accuracy is a perfect 100% — each point is its own nearest neighbor. That perfect score is the purest picture of overfitting you will ever see: zero error on the data it memorized, an island of wrong answers around every bad label. As k grows the map smooths, small patches dissolve into their surroundings, and at k = N the entire plane is one color (near N it usually is too, unless the classes are almost evenly split).

The map is also where kNN answers the linear-classifier lesson. That lesson proves no choice of (W, b) can give one class two separated islands — argmax regions are convex, full stop. The islands preset here hands kNN exactly that impossible dataset, and three votes hold both islands without effort: kNN's regions are built from local majorities, not half-planes, so they can be any shape the data takes. Slide k to 13 on the same data and the islands drown in the global majority — the ceiling is not the shape this time, it is the committee size.

k-Nearest Neighbors Step by Step

The default run stores 14 points — 8 labeled A, 6 labeled B. Six A points spread across the upper half of the plane and five B points cluster lower-right; one point at (−1, 3) is labeled B despite being surrounded by A territory (a labeling mistake, drawn like any other B point — nothing marks it), and two honest A points at (0, −3) and (1, −4) form a small outpost beside B's cluster. The query is q = (−1, 2) with k = 3.

Setup (beat 1). The 14 points appear in their class colors, plus q, drawn hollow — it has no class yet. Nothing else exists: no parameters, no arrows, no learned anything. The status panel says what the code's missing training function says: the points are the model.

Measure (beat 2). Fourteen dashed segments fan out from q, one per stored point, and the left-hand list fills with fourteen distances in storage order. The nearest is the mislabeled point at (−1, 3), at d = 1.00; the honest A points at (−2, 3) and (−2, 1) sit at d = 1.41; the far corner of B's cluster is over 7 away. This fan is the cost of one prediction — all of it at query time.

Sort (beat 3). The rows glide into rank order, nearest first. The mislabeled point takes rank 1. Ties sort the way Python sorts (d, y) tuples: by distance, then by label, A before B.

Select and vote (beats 4–5). A heavy cut line lands under row 3: only the rows above it get a say. The committee is B, A, A — the mislabeled point and two honest A neighbors — and a dashed circle appears on the plane through the third-nearest point, the geometric twin of the cut line. The tally fills: A 2 : 1 B.

Verdict (beat 6). q fills with A. Three stored points decided that; no learned score function was evaluated; the distance and vote formulas supplied the decision.

The k = 3 map (beat 7). The whole plane tints with each location's answer: A's territory upper-left, B's lower-right, and the outpost holding its own small A patch inside B's side. The border is wherever the committee changes — nobody drew it.

Re-slice to k = 1 (beats 8–10). The cut line slides to row 1 and the circle shrinks to the nearest point. Every distance on the list is visibly untouched — the code highlight sits on the single line that changed, top = dists[:k] — yet the vote is now B 1 : 0 and q flips to B. The one voter is the mislabeled point. Then the k = 1 map appears: an island of B tint around (−1, 3), deep inside A territory. Every future query inside that island inherits the mistake, while the map scores 100% on the stored points themselves.

Re-slice to k = 9 (beats 11–13). The cut slides down to row 9, the circle inflates, and the vote is A 6 : 3 — the mislabeled point is outnumbered by construction, and q returns to A. But the k = 9 map shows the price: the island is gone and so is the outpost. At (0, −3) the nine nearest are four A's and five B's — the two honest outpost points are outvoted by the surrounding B mass and now sit ringed as errors inside B tint. The mislabeled point is misclassified by this map too — it says A where the label says B — and is deliberately not ringed: the rings count disagreements with honestly-labeled points only, so they measure structure lost rather than noise corrected. Smoothing cannot tell the two apart; the ring rule can only because the dataset's author declared which is which.

The whole dial (beat 14). The stage clears and four maps of the same fourteen points appear side by side: k = 1, 3, 9, 13. The first is the island; the second holds both the island's correction and the outpost; the third has lost the outpost; the fourth is a single flat color. Thirteen voters out of fourteen means every location on the plane polls almost the entire dataset, so every location gets the same answer — the dataset's majority class, A. The five honestly-labeled B points sit ringed as errors on their own territory. That is where the dial ends: a classifier that has stopped looking at where you asked.

Done (beat 15). The map returns to the configured k = 3, the verdict to A. Store, sort, slice, vote — k is the only dial, 1 memorizes and N forgets, and picking it well needs held-out data.

Time and Space Complexity

One query against N stored points in d dimensions costs O(N·d) to measure the distances and O(N log N) to sort them (a heap of the k best does it in O(N log k); the full sort is shown because the re-slice experiments read the whole list). Space is O(N·d): the model is the dataset. Training does no arithmetic whatsoever — the only setup cost is storing the data, O(N·d) to copy it and O(N·d) to keep it. Exact indexes (KD-trees, ball trees) cut the query cost dramatically on large N and return the identical neighbors, so nothing else on this page changes; approximate ones cut it further and drop that guarantee, so a small fraction of queries get a different neighbor set and, occasionally, a different verdict.

Edge Cases

The query coincides with a stored point. Its distance is 0 and it takes rank 1 — legal, and with k = 1 the answer is simply that point's label, mistakes included. Distance-weighted variants have to special-case d = 0 for exactly this reason.

Tied distances. Two points at the same distance sort by label (Python compares the (d, y) tuples), and equally-distant same-label points keep their storage order. The tie that would actually matter — a tied vote — cannot happen in this lesson: two classes and an odd k make the majority unique, which is why the k slider only offers odd values. With three or more classes, or an even k, most_common(1) silently breaks ties by count order, and a real implementation must decide that rule deliberately.

k = N. The committee is everyone, every query gets the dataset's majority class, and the map is one color. The default run's comparison beat already shows this one step short of the limit — k = 13 of 14 is monochrome — and the majority-only preset runs the whole trace there if you want to watch a single query arrive at it.

A query far outside the data. kNN never refuses to answer: the distances all grow, each outward direction settles on a few frontier points, and whole outer regions inherit one verdict. There is no extrapolation and no "none of the above" — like the linear classifier, kNN has no way to say it has never seen anything like your query.

Too many dimensions. This lesson lives in the plane, where "nearest" is obvious. Add dimensions and distances concentrate: with enough independent features the nearest and the farthest point end up almost equally far away, the ratio between them creeps toward 1, and the sorted list the whole algorithm depends on becomes an ordering of noise. Nothing errors out — the verdicts just stop meaning anything. Reduce the dimension first (PCA, a learned embedding) or use a metric built for the space; do not assume Euclidean distance survives the trip.

Common Mistakes

Expecting a training step. There is nothing to fit. If you are timing kNN, time the queries; "training time" is the time it takes to copy the data.

Believing a new k recomputes anything. k appears only in the slice. The distances and the sort are reused unchanged — that is why the animation's re-slice beats highlight one line of code while every number on the list stays put. If your mental model has the loop re-running, the flip at k = 1 looks like magic; if it has the cut moving, the flip is obvious.

Trusting k = 1 because its training accuracy is perfect. It is perfect here because each point is its own unique zero-distance neighbor; conflicting labels at identical coordinates break that guarantee. The islands on the k = 1 map are what that perfection costs on every query that is not a training point. Judge k on held-out data, never on the points the model stores.

Feeding unscaled features to a Euclidean distance. A feature with a large numeric range can dominate the sum of squares, so the "nearest" neighbors end up nearest mostly along that one axis. Standardize features first; the algorithm will not warn you.

Reading the sampled map's cell edges as the boundary. The 55 × 55 grid is how the animation draws the map, not how kNN computes. The real boundary is wherever the vote changes, between cell centers as much as on them.