K-Nearest Neighbors

Store every training row and answer each query with a vote among its k closest rows. There is no training step, so the work and the memory bill both land at prediction time.

Gaps of 1.00, 1.41 and 2.83 vote 2 to 1 at k of 3, while all five rows vote 2 to 3 at k of 5 and flip the answer

Why Does This Exist?

A plant keeps 800 pumps with maintenance history. Each row holds vibration, motor speed, oil temperature, and whether that pump needed a bearing that month. A new pump gets measured tomorrow and someone must decide whether to pull it.

Most models fit a shape with parameters: a line, a boundary, a tree. This one refuses. It stores the 800 rows as they are. When the new pump arrives, it finds the stored rows most like it and copies what happened to them.

That is the whole method. Calling it training is generous, since nothing is fitted. The cost did not vanish. It moved to prediction, where every query pays for a fresh search over the full store.

One idea first. Write a pump as a list of numbers and it becomes a point in a space with one axis per measurement. Distance is the ordinary geometric gap between two such points, and the full menu of gap measures lives in distance and similarity metrics.

This page covers the vote itself: how neighbours are found and how k sets the verdict. The smoothing effect of averaging many neighbours is the variance half of the bias-variance tradeoff. The distance-based boundary it draws sits next to support vector machines.

Think of It Like This

The locksmith board of blanks

A locksmith keeps a board of several hundred key blanks, each tagged with the lock it fits. You hand over your key. He takes no measurements and derives no theory of keys. He holds your key against the board, picks the three closest blanks, and reads their tags. His accuracy comes from the board being large and honestly labelled.

Now the board is hung badly. Position across it is length in millimetres, spanning 40. Position down it is tooth depth in tenths of a millimetre, spanning 3. Every key of matching length now looks adjacent no matter how differently it is cut, and he hands over wrong blanks with full confidence. His method did not break. The board lied about what close means.

Each blank is one stored row, holding the key up is the distance computation, the three closest blanks are k of 3, and the hanging of the board is feature scaling. The locksmith never learns a rule, which is exactly why the board geometry decides everything.

Where it stops: the locksmith sees your key and the board at once. The classifier sees only numbers, so two pumps that differ in a way no column records look identical forever.

How It Actually Works

Call the stored rows $x_1$ through $x_n$ , each with a label $y_i$ that is 0 or 1. Call the newcomer $q$ . Pick a distance $d$ , meaning the rule that scores how far apart two rows are. Euclidean distance is the default:

d(a, b) = \sqrt{\sum_j (a_j - b_j)^2}

Rank every stored row by $d(q, x_i)$ , keep the $k$ smallest, and take the majority label. For regression the same neighbours average their targets instead of voting. That is all the fitting there is.

Worked example: five rows, one query

Two features, five stored rows, labels 0 for fine and 1 for service:

A=(1,1), 0 \qquad B=(1,2), 0 \qquad C=(4,4), 1 \qquad D=(5,4), 1 \qquad E=(4,5), 1

The query is $q=(2,2)$ . Euclidean gaps:

\begin{aligned} d(q,B) &= \sqrt{1^2 + 0^2} = 1.00 \\ d(q,A) &= \sqrt{1^2 + 1^2} = \sqrt{2} \approx 1.41 \\ d(q,C) &= \sqrt{2^2 + 2^2} = \sqrt{8} \approx 2.83 \\ d(q,D) &= \sqrt{3^2 + 2^2} = \sqrt{13} \approx 3.61 \\ d(q,E) &= \sqrt{2^2 + 3^2} = \sqrt{13} \approx 3.61 \end{aligned}

Sorted, the gaps run 1.00, 1.41, 2.83, 3.61, 3.61. At $k = 3$ the voters are B, A, C with labels 0, 0, 1, so the vote is 2 to 1 for fine. At $k = 5$ all five vote and the tally is 2 to 3 for service. Same query, same rows, opposite answers. The diagram draws exactly this: one solid ring holding three voters, one dashed ring holding all five.

Why scaling decides the vote

Motor speed spans thousands of rpm while vibration spans single digits of millimetres per second. Raw Euclidean distance then measures speed and ignores vibration, because a 300 rpm gap dwarfs a 7.5 mm/s gap before squaring even starts. The neighbour set is chosen by one column and the rest are decoration.

Standardise every column from training rows only, or map each into a fixed range, and all features arrive comparable. Which transform suits which column is the whole subject of feature scaling. An outlier in one column still drags its neighbours, which is why a Manhattan sum of absolute gaps sometimes replaces the squared version.

Choosing k and paying per query

Small $k$ follows the data closely. At $k = 1$ one mislabelled row owns its own island of wrong answers. Large $k$ smooths toward the majority class everywhere. There is no formula: sweep $k$ on held-out data, keep it odd for two classes so votes cannot tie, and prefer the flat middle of the curve over a sharp single best point.

Every query compares against every stored row, so prediction cost grows linearly with training size and the full set stays in memory. Spatial indexes help in low dimensions and degrade toward brute force in high ones.

The hard ceiling is geometric. With hundreds of features, the nearest and farthest rows sit nearly equidistant and nearest stops carrying information. That is the curse of dimensionality, and the repair is fewer, better columns, for instance through principal component analysis, or a model that ignores weak columns on its own.

Code

The point is the flip: the same five rows vote one way at k of 3 and the other way at k of 5.

1from math import dist2
3train: list[tuple[float, float]] = [(1.0, 1.0), (1.0, 2.0), (4.0, 4.0), (5.0, 4.0), (4.0, 5.0)]4labels: list[int] = [0, 0, 1, 1, 1]5query: tuple[float, float] = (2.0, 2.0)6
7gaps: list[float] = [dist(query, p) for p in train]8order: list[int] = sorted(range(len(train)), key=lambda i: gaps[i])9print([round(gaps[i], 2) for i in order])  # -> [1.0, 1.41, 2.83, 3.61, 3.61]10print(sum(labels[i] for i in order[:3]))  # -> 1, so 2 to 1 for class 011print(sum(labels[i] for i in order[:5]))  # -> 3, so 2 to 3 for class 1

The printout matches the hand computation: gaps 1.00, 1.41, 2.83, 3.61, 3.61, one service vote among the closest three, three among all five. Change the query to (4.5, 4.5) and watch k stop mattering, since all nearby rows agree.

Watch Out For

Scaling after the split instead of inside it

The tempting order is to standardise the full table and then split off validation, because it is one line instead of two. The mean and spread applied to validation rows then include those rows, so held-out information walks into every neighbour decision.

Symptom: a validation score that never reproduces in production, worse on small tables. Fix: compute scaling statistics from training rows only and refit them per fold, since a data leak bites distance models hardest, where scaling is load-bearing rather than cosmetic.

Tuning k when the geometry is the problem

Four hundred sensor channels go in, accuracy sits near chance, and sweeping k from 1 to 50 leaves the curve almost flat. The flatness is the diagnosis: the neighbour set is noise at every k, so averaging more of it changes nothing.

Symptom: accuracy invariant to k across the whole sweep. Fix: cut to channels that separate the classes or reduce dimensions first, then vote. If neither helps, switch model families rather than sweeping further.

The Quick Version

KNN stores every training row and labels a query by majority vote of its k closest rows, with no fitted parameters.
Our five rows sit at gaps 1.00, 1.41, 2.83, 3.61 and 3.61, so k of 3 votes 2 to 1 for fine while k of 5 votes 2 to 3 for service.
The distance function is the model, and one unscaled wide-range column elects every neighbour alone.
Small k copies noise, large k smooths toward the majority, and even k risks ties in two-class votes.
Prediction cost grows linearly with training size per query, and the full store stays in memory.
In high dimensions nearest and farthest converge, so neighbours stop meaning anything until the space shrinks.