K-nearest neighbors algorithm

The K-nearest neighbors algorithm (k-NN) is a supervised learning method used in machine learning for classification and regression. It predicts an unknown outcome by finding the $k$ most similar examples in training data and combining their outcomes. Classification typically uses a vote, while regression uses an average. The method is nonparametric: it does not impose a fixed functional form on the relationship between inputs and outputs. (scikit-learn.org)

Prediction rule

Suppose the training set contains $n$ pairs $(x_i,y_i)$ , where $x_i$ is a feature vector and $y_i$ is a class label or numerical target. For a query $x$ , a distance function identifies a neighborhood $N_k(x)$ containing the indices of its $k$ closest training examples. The positive integer $k$ , usually no greater than $n$ , is a hyperparameter. (arxiv.org)

For classification, the predicted class is

\hat y(x)=\arg\max_c\sum_{i\in N_k(x)}\mathbf 1(y_i=c),

where the indicator equals one when example $i$ belongs to class $c$ . Thus, the class receiving the most votes wins; it need not receive an absolute majority. For regression,

\hat y(x)=\frac{1}{k}\sum_{i\in N_k(x)}y_i.

Weighted variants replace equal contributions with weights, commonly giving closer examples greater influence through inverse-distance weighting. (scikit-learn.org)

With $k=1$ , the prediction copies the nearest example’s outcome. Equal class votes and equal distances at the neighborhood boundary require tie-handling conventions; some implementations can produce different results when tied training examples are reordered. (scikit-learn.org)

Distance and feature representation

“Nearest” depends on how observations are represented and compared. For numerical vectors, Euclidean distance is a common choice:

d(x,z)=\sqrt{\sum_{j=1}^{p}(x_j-z_j)^2}.

Alternatives include Manhattan distance, Minkowski distances, and task-specific dissimilarities. Different measures can select different neighbors from the same dataset, so the distance function is part of the predictive specification rather than merely an implementation detail. (arxiv.org)

Feature scaling strongly affects distance-based predictions. A variable measured over a large numerical range can dominate another measured over a small range, regardless of predictive relevance. Standardization rescales features to zero mean and unit standard deviation; it can substantially change both the neighbor structure and classification boundary. It does not establish that every feature is equally informative. (scikit-learn.org)

Categorical variables require suitable representations or comparison rules. One-hot encoding represents unordered categories without assigning them artificial numerical ranks, although it increases the number of coordinates. These choices belong to feature engineering and determine which similarities the algorithm can recognize. (sklearn.org)

Choosing k and evaluating performance

The neighborhood size controls a form of smoothing. Small neighborhoods respond closely to individual observations and noise, increasing susceptibility to overfitting. Larger neighborhoods usually produce smoother predictions but can obscure local distinctions and cause underfitting. This illustrates the bias–variance tradeoff: increasing $k$ generally reduces variability while increasing approximation bias. No single value is optimal for every dataset. (arxiv.org)

The choice of $k$ , distance measure, and weighting rule can be evaluated through cross-validation or a separate validation set. A held-out test set provides a final assessment of generalization after model selection. The evaluation criterion depends on the task: classification and regression require different measures, with mean squared error being one common regression criterion. (scikit-learn.org)

Preprocessing must also respect evaluation boundaries. Scaling, learned transformations, and feature selection are fitted on the training portion of each split, then applied unchanged to the held-out portion. Fitting these operations on the entire dataset can introduce data leakage and optimistic performance estimates. Pipelines provide a mechanism for keeping preprocessing inside each cross-validation split. (scikit-learn.org)

Computation and dimensionality

K-NN is often described as lazy or instance-based learning because much of its work occurs at prediction time rather than during fitting. Stored examples remain central to the predictor, although fitting may construct a search index. A direct search computes distances to all $n$ examples; for $p$ -dimensional dense vectors, this requires approximately $O(np)$ distance-computation work per query. (arxiv.org)

KD-trees and ball trees can accelerate exact neighbor searches for suitable data. Their efficiency depends on dimensionality and data structure; tree-based methods may lose their advantage in high-dimensional spaces. This is one computational manifestation of the curse of dimensionality, which also makes local neighborhoods harder to populate densely. (scikit-learn.org)

Dimensionality reduction can reduce search costs and alter neighborhood quality. For example, principal component analysis projects observations into fewer coordinates, but retained variation need not coincide with information relevant to prediction. Scaling can affect this projection as well as the subsequent neighbor search. (scikit-learn.org)

Statistical foundations

Thomas Cover and Peter Hart’s 1967 paper, Nearest Neighbor Pattern Classification, established a foundational large-sample result. Under the paper’s distributional conditions, the limiting error of the one-nearest-neighbor classifier is no greater than twice the Bayes error—the minimum achievable classification error given the underlying probability distribution. This is an asymptotic bound, not a guarantee for every finite dataset, and it does not imply that fixed $k=1$ achieves the Bayes error. The analysis also explains why using more neighbors must be balanced against keeping the neighborhood local relative to sample size. (isl.stanford.edu)