Mathematics
The K-Nearest Neighbours Algorithm and Its Bias-Variance Tradeoff
Quick fact
k-NN has no training phase; it memorizes the entire dataset and makes predictions at query time by averaging the labels of its k nearest examples. This makes it a 'lazy' learner, and the choice of k directly controls the bias-variance tradeoff: a single neighbor (k=1) perfectly fits training data but often overfits noise, while a huge k smoothes everything and can underfit.
Why this is interesting
You want to predict an unknown value—like the price of a house. The simplest approach might be to ask your closest neighbors how much they paid. But how many neighbors should you ask? The answer reveals a deep tension in all of machine learning.
Read the full explanation
Understanding The K-Nearest Neighbours Algorithm and Its Bias-Variance Tradeoff
Imagine you're trying to estimate the price of a new house in a neighborhood. You could just look at the one house sold closest to it (k=1), but that might be an outlier. Or you could average the prices of all houses in the city (very large k), but then you'd miss local trends. The k-nearest neighbours algorithm does exactly this: to predict the value of a new point, it finds the k training examples that are 'closest' to it (using a distance metric like Euclidean distance), and then takes the majority vote (for classification) or the average (for regression) of their labels. The key is choosing k. With a small k, the prediction depends on very few, very close points—making it highly sensitive to noise. With a large k, the prediction averages over many points, smoothing out noise but also blurring the local structure. This is the core of the bias-variance tradeoff: small k yields a model with low bias (it can capture any pattern) but high variance (it changes a lot with small changes in the training data). Large k yields a model with higher bias (it imposes smoothness) but lower variance (it's more stable across data samples).
A deeper explanation
The bias-variance tradeoff is a fundamental property of predictive models. The expected prediction error of a model can be decomposed into three parts: irreducible noise, bias², and variance. Bias is the error introduced by approximating a complex real-world problem with a simpler model—here, the smoothness imposed by averaging over k neighbors. Variance is the error introduced by sensitivity to the specific training set; a k=1 model will change its predictions drastically if a single training point moves. As you increase k, the model becomes smoother, increasing bias (the averaged prediction is less flexible) but decreasing variance (it's less sensitive to individual points). The optimal k is where the total expected error is minimized—the sweet spot where the combined bias and variance is lowest. This is often found by cross-validation: try different k values, train on a subset of the data, and evaluate on a hold-out set. k-NN also highlights the curse of dimensionality: as the number of features grows, the notion of 'nearest' becomes less meaningful because in high-dimensional spaces, all points are almost equidistant, making the bias-variance tradeoff even more challenging.