k-Nearest Neighbors

k-NN (Fix & Hodges, 1951; Cover & Hart, 1967) is the most intuitive classifier in existence: to classify a new point, look at the \(k\) most similar known points and take a vote. No equations to fit, no training loop — the "model" is the training data.

The algorithm

To predict for a query point \(x\):

1. compute the distance from \(x\) to every training point;
2. take the \(k\) closest ones;
3. classification: predict the majority class among them (optionally weighting closer neighbors more); regression: predict their (weighted) average.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

knn = make_pipeline(StandardScaler(),                 # distances need scaling!
                    KNeighborsClassifier(n_neighbors=5))
knn.fit(X_train, y_train)

k-NN is a lazy (instance-based) learner: fit just stores the data. All the work happens at prediction time — the opposite cost profile of most models (slow to predict, instant to "train").

Distance metrics

The notion of "similar" is a modeling choice. For the Minkowski family,

• \(p = 2\): Euclidean — straight-line distance, the default;
• \(p = 1\): Manhattan — sum of coordinate differences; less dominated by one large-difference feature;
• cosine similarity for text/embedding vectors (Text Representation); Hamming for binary vectors.

Choosing k: bias–variance in its purest form

\(k\) is the complexity knob, and it maps perfectly onto the bias–variance trade-off — just inverted (small \(k\) = complex model):

• \(k = 1\): every training point rules its own island — jagged boundary, noise memorized, training error zero, high variance (overfit);
• \(k = 15\): smooth boundary following the true structure — the sweet spot here;
• \(k = 100\) (half the dataset): the vote is swamped by the global majority — high bias (underfit); at \(k = n\) every prediction is the majority class.

Choose \(k\) by cross-validation; odd values avoid ties in binary problems. Typical good values grow roughly like \(\sqrt{n}\), but validate rather than trust rules of thumb.

Play with the vote yourself — drag the query point into the overlap zone and watch small k flip-flop while large k stays stable:

The curse of dimensionality, revisited

k-NN's premise — near means similar — degrades as dimensions grow (Dimensionality Reduction):

• volume grows exponentially: with uniform data, covering 10% of the samples in \(d=100\) dimensions requires a neighborhood spanning ~98% of each axis — "nearest" neighbors are not near;
• pairwise distances concentrate: the ratio between the farthest and nearest neighbor tends to 1, so the vote becomes arbitrary;
• irrelevant features add pure noise to the distance.

Remedies: feature selection, PCA/UMAP before k-NN, or metric learning. Rule of thumb: k-NN shines in low-to-moderate dimensions with plenty of data.

Practical profile

The "find the nearest embeddings" operation is also the heart of modern vector databases powering retrieval-augmented LLM systems (The Frontier) — 1950s ideas serving 2020s systems.

Class materials

Quiz