k-Nearest Neighbors (k-NN)

Hook

Every classifier so far — logistic regression, a decision tree, an SVM — short for support vector machine — spends real effort during training, fitting weights or splits before it can predict anything. What's the classifier that skips training entirely and just... looks at what's nearby?

Intuition

k=1 → predicts "A" (votes A:1)

Two clusters, and one deliberately mislabeled-looking point sitting right inside the wrong cluster's territory. Toggle $k$ — with $k=1$ , the query's prediction comes from whichever single point is closest, noisy point included. Raise $k$ , and that one stray point gets outvoted by its genuine neighbors.

Formalize

$k$ -nearest neighbors has no training phase and no parameters to fit — the "model" is just the dataset itself:

\hat{y}(q) = \underset{c}{\arg\max} \left|\{i \in \text{kNN}(q) : y_i = c\}\right|

$\hat{y}(q)$ — the predicted class for the query point $q$ .
$q$ — the query point being classified.
$k$ — how many nearest neighbors get consulted for the vote.
$\text{kNN}(q)$ — the set of the $k$ points closest to $q$ .
$y_i$ — the true label of training point $i$ .
$c$ — one candidate class, ranging over whatever labels appear among the neighbors.

Vote among the k closest points
Find the $k$ closest points to the query $q$ by ordinary distance, then predict whichever class shows up most among them.
Learning happens at prediction time
All the "learning" happens when a query comes in, not during training — the opposite of every other model built so far in this course.

Play

nearest 5: A(0.28), B(0.50), B(0.70), B(1.12), B(1.12)

Drag the query and check the ranked list of nearest neighbors at every position. The prediction is entirely a local vote — it never looks at the shape of either cluster as a whole, only at whichever handful of points happen to be closest to wherever you're asking about.

Worked example

A query point sits at $(4, 4.5)$ , right at the edge of the B cluster — except for one noisy A point planted at $(4.2, 4.3)$ :

k=1: fooled by the noisy point
The single nearest neighbor is the stray A point, at distance $\approx 0.28$ — closer than any real B point. The prediction is A, which is wrong.
k=3: the noisy point gets outvoted
The three nearest are the stray A point plus two genuine B points. That's $2$ votes for B against $1$ for A — the majority correctly overrides the single noisy neighbor.
k=5: even more confident
Extending to the five nearest adds two more B points, for a $4$ -to- $1$ vote. The noisy point never goes away — it just matters less as more real evidence gets counted alongside it.

Checkpoint

Pick a k whose prediction actually disagrees with k=1's.

k=1 → predicts "A" (votes A:1)

Pick a k to try it

Summary

\hat{y}(q) = \underset{c}{\arg\max} \left|\{i \in \text{kNN}(q) : y_i = c\}\right|

$k$ is kNN's one real hyperparameter, and it trades off exactly the way $k$ -means' cluster count or a tree's depth did: too small and a single noisy point can swing the answer; too large and it starts averaging in points from an entirely different neighborhood that shouldn't count at all. This same nearest-neighbor idea has already shown up all over this course — word embeddings, joint embedding spaces, retrieval — but this is the first time it's the entire classifier by itself, with nothing trained on top of it.