k-Nearest Neighbors

k-nearest neighbours (k-NN) has no training phase: it simply stores the data. To predict for a new point, find the $k$ training points closest to it and take a majority vote of their labels (classification) or the average of their targets (regression).

$k$ controls the bias–variance trade-off. $k=1$ follows every point, giving jagged boundaries and overfitting (zero training error). Large $k$ smooths the boundary and eventually underfits — with $k=n$, it always predicts the majority class. Choose $k$ by cross-validation; odd $k$ avoids ties in binary problems.

Variants weight neighbours by inverse distance, so closer points count more.

Pros: simple, no assumptions about the data's shape, naturally multiclass. Cons: prediction is slow ($O(nd)$ per query without index structures like KD-trees), memory-heavy, and suffers badly in high dimensions.