Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 218 / 6 / b / Solution

Let $N_k(x)$ index the $k$ closest training covariates to $x$. The K-nearest neighbors algorithm estimatesand predicts one when this average is at least $1/2$.

Small $k$ gives low smoothing bias but high sampling variance and a jagged decision boundary. Larger $k$ averages more labels, reducing variance and producing a smoother boundary, but it mixes increasingly distant covariates and raises bias. The optimal balance depends on sample size, dimension, and smoothness of ${\eta }_1$, and is commonly selected by cross-validation.