k-Nearest Neighbors

Imagine you move into a new neighborhood and want to guess whether your street is likely to have quiet or lively evenings. You would not rely on a national average; you would ask your neighbors. If most of the five houses on your block are quiet at night, you predict your own evenings will be quiet too. That single act, looking at the people closest to you and letting them vote, illustrates the basic idea of the k-nearest neighbors (kNN) algorithm. No equation is fit, no coefficients are learned, and no parametric shape is imposed on the data. Instead, the training set itself is the model, and predictions are made by inspecting which training points are most similar to the query we care about.

Standard models such as the linear regression and logistic regression chapters we studied previously compress the training data into a small set of parameters. kNN takes the opposite stance. It is a non-parametric, instance-based method. Every prediction is anchored to concrete examples we have already observed. The "learning" phase is essentially storing the data. The real work happens at prediction time when we compute distances. This makes kNN flexible, capable of tracing arbitrarily curved decision boundaries, but also demanding in terms of memory, distance calculations, and, as we will see, the quality of our feature space.

This chapter builds kNN from first principles. We start with a clear definition of a distance and how a local prediction rule turns neighbors into an answer. We then work through classification by majority vote and regression by local averaging, examine how neighborhood size and feature scaling reshape the predictions, and quantify why high-dimensional spaces break the intuition that "nearby" means "similar." Along the way, we implement brute-force kNN in NumPy, compare several values of $k$ on noisy data, and confirm our results against scikit-learn.

A short clarification before we start. Nearest neighbors in this chapter always means supervised prediction, classifying or regressing using labeled training points. This is a very different idea from k-means clustering (a chapter we will encounter in the unsupervised part of the book), which is also "center-based" and uses distances but has no labels to reason about. Keeping the two separate avoids a common confusion.