K-Nearest Neighbors

KNN is a non-parametric algorithm: it stores all training data and classifies new points by majority vote among the $k$ nearest neighbors.

Algorithm:

1. Given query point $\mathbf{x}_q$, compute distance to all training points
2. Select the $k$ closest neighbors
3. Classification: majority vote. Regression: average of neighbors' values

Key properties:

• No training phase — all computation at inference ("lazy learner")
• Decision boundary can be arbitrarily complex
• $k$ controls the Bias-Variance Tradeoff:
  • Small $k$ → complex boundary, low bias, high variance (overfits)
  • Large $k$ → smooth boundary, high bias, low variance (underfits)

Distance metric matters: Euclidean is default but Manhattan, Minkowski, or learned metrics may be better depending on the problem. Features must be scaled (standardized) first.

Curse of dimensionality: in high dimensions, all points become roughly equidistant — KNN degrades. Dimensionality reduction (Principal Component Analysis (PCA)) can help.

Complexity: $O(nd)$ per query ($n$ = dataset size, $d$ = dimensions). KD-trees or ball trees accelerate to $O(d \log n)$ in low dimensions.

See also: Evaluation Metrics, Cross-Validation