K-Nearest Neighbors

K-nearest neighbors (k-NN) predicts a new point's label by finding the $k$ most similar points already in the training data and having them vote. It doesn't fit a formula, doesn't estimate coefficients, and doesn't build a tree — at prediction time, it just measures distance to every stored training point and looks at whichever $k$ are closest. It is the closest thing machine learning has to "ask your neighbors."

The analogy: asking the houses on your street

If you wanted to guess a house's value and had no formula, a reasonable approach is asking the few most similar nearby houses — same size, same street, same age — what they're worth, and averaging their answers. You wouldn't ask a house across town in a different neighborhood; you'd trust the answer of the houses most like the one you're valuing. k-NN formalizes exactly that instinct: find the $k$ most similar examples, and let them answer for you.

Worked example: classifying a new point with k=3

Suppose training data has 6 points, each labeled A or B, plotted by two features (call them $x_1, x_2$):

Point	$x_1$	$x_2$	Label
P1	1	1	A
P2	2	1	A
P3	1	2	A
P4	5	5	B
P5	6	5	B
P6	5	6	B

A new point arrives at $(2, 2)$. Compute Euclidean distance to each:

$$d(P1) = \sqrt{1^2+1^2}=1.41,\ d(P2)=\sqrt{0^2+1^2}=1.00,\ d(P3)=\sqrt{1^2+0^2}=1.00$$ $$d(P4)=\sqrt{3^2+3^2}=4.24,\ d(P5)=\sqrt{4^2+3^2}=5.00,\ d(P6)=\sqrt{3^2+4^2}=5.00$$

With $k=3$, the three nearest are P2, P3 (tied at 1.00) and P1 (1.41) — all labeled A. The vote is unanimous, so the new point is classified A. Note that nothing was "trained" here; the entire computation happened at prediction time, scanning every stored point.

Try shrinking the neighborhood size in the explorer above until the boundary starts hugging individual training points tightly — that jagged, point-chasing boundary is what a small $k$ produces in k-NN, while a larger $k$ smooths the boundary by averaging over more neighbors, exactly like broadening the vote from 1 to 3 to 10 points in the worked example.

What this means in practice

A small $k$ (like $k=1$) produces a highly flexible, jagged boundary that can memorize noise in the training data; a large $k$ smooths predictions by averaging over more neighbors but can blur real, sharp distinctions between classes if $k$ gets too large relative to the data. Because every prediction requires scanning the training set for nearest neighbors, k-NN is also expensive at prediction time on large datasets, which is why it tends to be used on small-to-moderate datasets or paired with an indexing structure that speeds up the neighbor search.