k-Nearest Neighbors

To label something new, look at what's closest and copy the majority.

No training. The training set is the model.

The whole idea

Keep every training point. Don't fit anything.
To classify a query: find the k closest points, take a vote.
The only knob is k — small k follows every wiggle, large k smooths.
Proven in 1967 (Cover & Hart): 1-NN error is at most twice the best possible.

The data

150 Iris flowers, three species, two features: petal length and petal width.

Setosa sits alone. Versicolor and virginica overlap in a fuzzy seam.

The whole model

Distance from the query to every point:

d(q, x_i) = \sqrt{\sum_{j=1}^{D} (q_j - x_{ij})^2}

Vote among the k nearest:

\hat{y}(q) = \arg\max_{c} \sum_{i \,\in\, N_k(q)} \mathbb{1}\!\left[\, y_i = c \,\right]

No parameters fit from data. You pick k; everything else is a sort and a count.

Watch it vote

For each test flower: circle the 5 nearest, draw the votes, color by the winner, red-ring it if wrong.

Unanimous in the setosa and virginica clouds. Split 4–1 and 3–2 in the seam — that's where the three mistakes are, and they're the data being ambiguous, not the model being wrong.

k changes the shape, not just the score

Accuracy is flat on Iris — the classes are too clean for k to matter much.

But the decision surface goes from jagged (k = 1) to smooth (k = 15). On noisier data, that shape is the difference between memorizing and generalizing.

Scratch vs. library

KNeighborsClassifier(n_neighbors=5) is the same algorithm. Both score 0.9333 and agree on all 45 test flowers.

The library's edge isn't accuracy — it's the KD-tree that finds neighbors without scanning every point.

Takeaways

Great baseline: zero training, any-shaped boundary, tells you if local structure exists.
Slow at predict time — every query scans the whole training set.
Dies in high dimensions: the curse of dimensionality makes "nearest" meaningless.
Standardize your features first, or the distance is a lie. (That's the next stretch of the course.)