k-Nearest Neighbors › Summary

k-Nearest Neighbors is a non-parametric, instance-based method where predictions are computed only at query time. The model retains the training examples and prediction configuration. Our brute-force implementation computes distances to all training points, selects the $k$ nearest, and produces a prediction by majority vote (classification) or local average (regression); an exact search index can retrieve the same neighbors with less distance work. This local prediction rule explains both its flexibility, as it can trace arbitrarily curved decision boundaries, and its brittle dependence on feature scaling, distance choice, and neighborhood size.

We built the mechanism from first principles. Here are the central quantities again, with their symbols defined. The Euclidean distance between a query and a training point is the square root of the sum of squared feature differences; it is the same quantity as the norm of the difference vector, and it can be computed efficiently for all training points at once. Once we have the distances, the k-nearest set is defined by sorting and taking the first $k$; the prediction is a reduction over that neighborhood. The neighborhood size $k$ acts as a bias-variance dial, and kernel weighting lets closer neighbors count more heavily without changing the underlying rule. Feature scales determine the relative contribution of each coordinate to distance. Transform them when their raw units would otherwise impose unintended weights.

We also examined distance concentration under the stated independent Gaussian feature model: as the number of noise features grows in that experiment, nearest and farthest distances become closer in relative terms. This is a reason to examine feature relevance and local support, rather than a claim that every high-dimensional dataset lacks useful neighbors. The worked example showed every step, from distances and sorting through ties, majority vote, weighted vote, and the regression average, in a hand-computable case. Our NumPy implementation, verified against scikit-learn to floating-point precision, demonstrated that the algorithm is nothing more than distance and reduction once written out. With kNN in hand, we turn next to Naive Bayes, which models class-conditional feature distributions and combines them with Bayes’ theorem under a conditional independence assumption.