k-Nearest Neighbors

The Whole Idea in One Line

You are the company you keep.

To classify something new, k-Nearest Neighbors just looks at the k closest examples it has already seen and takes a majority vote. That is the entire algorithm.

A new fruit, apple or orange? Find the 3 most similar fruits you know. Two are oranges, one is an apple, so you call it an orange. No cleverness, just a vote of the locals.

There Is No “Training”

Here is the surprising part. kNN does no training at all. It simply memorizes every example. All the work happens later, when a new point arrives: it measures the distance to every stored point, keeps the closest k, and lets them vote.

That makes it a lazy learner: zero effort up front, all the effort at the moment you ask.

Contrast that with everything so far. Linear and logistic regression fit parameters during training and then answer instantly. kNN flips it: nothing to fit, but every prediction re-scans the whole dataset.

Choosing k

The only real choice is k, how many neighbours get a vote. And it changes everything:

• $k = 1$: trust only the single nearest point. Super flexible, but jumpy, one stray outlier next to your new point flips the answer, leaving little islands.
• $k$ too large: you average over so many neighbours that local detail washes out, and everything drifts toward the most common class overall.
• Just right: somewhere in between. Use an odd $k$ for two classes so a vote can’t tie.

Notice what this is. $k$ is a dial on the bias-variance tradeoff. Small $k$ means low bias but high variance (a jagged, twitchy boundary). Large $k$ means high bias but low variance (a smooth, sluggish one). The same tug-of-war from earlier, in a new costume.

Two Things That Matter

Distance. Usually plain straight-line (Euclidean) distance, $\sqrt{\sum_i (a_i - b_i)^2}$. But you must scale your features first. Otherwise a feature measured in the thousands (like salary) drowns out one measured in single digits (like age), purely because its numbers are bigger.

The boundary it draws. Unlike logistic regression’s straight line, kNN can carve any shape at all, blobs, islands, wiggles. It simply hugs whatever the data does, which is exactly why it can nail patterns a straight line never could.

Where It Breaks: the Curse of Dimensionality

kNN leans entirely on “nearest” being meaningful. In high dimensions, that quietly falls apart.

When you have hundreds of features, points spread out so much that everything becomes roughly equidistant from everything else. The “nearest” neighbour is barely closer than the farthest one, so “close” stops meaning anything, and the vote becomes noise.

This is the curse of dimensionality, and it haunts far more than kNN. It’s why raw pixels or raw words must first be compressed into meaningful features before distance-based methods work at all. Hold that thought: it is exactly the problem embeddings will solve when we reach deep learning.

kNN is also slow at prediction, since every guess compares against every stored point.

When to Reach for It

kNN shines on small, low-dimensional data where the boundary is weird and non-linear, and it’s a wonderful baseline: dead simple, no training, surprisingly hard to beat on the right problem. It struggles as the data grows large or the features grow many.

Next we meet the opposite instinct: instead of trusting local neighbours, Support Vector Machines look for the single best dividing line with the widest possible gap.