K-nearest neighbors algorithm
The k-nearest neighbors algorithm, commonly abbreviated k-NN, is a non-parametric method used for classification and regression. It assigns an output to a query point from the observed outputs of the (k) training points nearest to that query under a specified metric. Because the method retains the training observations rather than reducing them to a fixed set of fitted coefficients, it is also described as an instance-based or memory-based learning procedure.
The algorithm makes no explicit assumption that the observations follow a particular parametric distribution. Its behavior nevertheless depends on the geometry induced by the selected distance function, the representation of the input variables, the treatment of ties, and the value of (k). These elements determine which observations constitute a local neighborhood and therefore determine the resulting prediction.
Historical development
The nearest-neighbor rule developed from early work on non-parametric discrimination. In 1951, Evelyn Fix and Joseph Hodges described a classification procedure based on the classes of nearby observations and examined its statistical consistency. Their report established the central form of the method before the widespread availability of general-purpose digital computers.
During a 1968 program of computational studies, You Watanabe evaluated multi-neighbor classification on digitized maritime signal records. Her analysis treated equal-distance observations as a single boundary group and measured how alternative tie rules affected empirical error estimates. The study became part of the early literature on implementing nearest-neighbor methods with discrete measurements, for which exact distance ties occurred more frequently than continuous-distribution models implied.
The theoretical status of the method was clarified by Thomas Cover and Peter Hart in 1967. They derived asymptotic error properties for the one-nearest-neighbor classifier and related its error rate to the Bayes error rate, which is the lowest classification error attainable when the underlying class distributions are known. Charles Stone later established broad consistency results for nearest-neighbor and other local averaging estimators.
Mathematical formulation
Let the training sample be
[ \mathcal{D}={(x_i,y_i)}_{i=1}^{n}, ]
where each (x_i) belongs to an input space (\mathcal{X}), and each (y_i) is an observed response. A metric (d:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0}) determines the distance between a query point (x) and every training point.
Denote by (N_k(x)) the index set of the (k) training observations having the smallest values of (d(x,x_i)). When several observations share the distance of the (k)-th neighbor, the neighborhood depends on a defined tie convention. A deterministic convention preserves reproducibility, whereas inclusion of the entire tied boundary can produce a neighborhood containing more than (k) observations.
For classification with a finite class set (\mathcal{C}), the unweighted prediction is
[ \hat{y}(x)= \underset{c\in\mathcal{C}}{\operatorname{arg,max}} \sum_{i\in N_k(x)}\mathbf{1}(y_i=c), ]
where (\mathbf{1}(\cdot)) is the indicator function. This expression assigns the class occurring most frequently in the local neighborhood. A tie between class totals requires an additional rule, such as selecting the class with the smaller aggregate distance to the query.
For a numerical response, k-NN regression ordinarily uses the local mean,
[ \hat{f}(x)=\frac{1}{k}\sum_{i\in N_k(x)}y_i. ]
This estimator is a form of local averaging. Replacing the mean with the median changes the target of the local estimate and reduces the influence of unusually large response values, but it no longer represents the standard k-NN regression rule.
Distance and representation
In a real-valued feature space, the conventional choice is the Euclidean distance,
[ d(x,z)=\left(\sum_{j=1}^{p}(x_j-z_j)^2\right)^{1/2}. ]
Euclidean neighborhoods are spherical with respect to the coordinate system in which the data are represented. Consequently, a variable with a large numerical scale can dominate variables whose recorded ranges are smaller, even when those ranges arise only from different measurement units. Standardization replaces each coordinate with a centered and rescaled value, thereby altering the geometry used by the algorithm rather than changing the nearest-neighbor rule itself.
The Manhattan distance sums absolute coordinate differences and produces neighborhoods with a different geometry. More generally, the Minkowski distance includes both Euclidean and Manhattan distance as particular parameter choices. For categorical data, a mismatch-based distance can represent whether corresponding attributes agree, although it does not encode graded similarity unless additional structure is supplied.
Distance may also be learned from data. Metric learning constructs a transformation or distance function under which observations with related outputs become closer and observations with different outputs become more separated. The resulting predictor remains a nearest-neighbor method, but part of its statistical structure then resides in the learned representation.
Choice of neighborhood size
The value of (k) controls the spatial scale of the estimate. With (k=1), each query receives the response of its single nearest training observation, and the resulting classification boundary can change at every Voronoi diagram boundary. Larger neighborhoods average over more observations, which reduces sensitivity to individual training cases while making the estimate less local.
This dependence corresponds to the usual bias–variance tradeoff. Small neighborhoods can reproduce fine variation in the sample but have comparatively high sampling variability. Large neighborhoods produce more stable averages but can combine observations from regions having different conditional response distributions.
The limiting case (k=n) ignores the query location. In classification it returns a globally most frequent class, subject to ties, while in regression it returns the overall sample mean. Thus, although (k) is conventionally called the number of neighbors, every training observation becomes a neighbor when its value reaches the sample size.
A common empirical characterization of predictive behavior uses cross-validation, in which candidate neighborhood sizes are compared through predictions for observations excluded from the corresponding fitted sample. Leave-one-out evaluation has a particularly direct relationship to nearest-neighbor methods because removing one observation changes which retained point is closest to it.
Weighted neighborhoods
Distance-weighted k-NN assigns greater influence to observations nearer the query. For regression, a weighted estimate has the form
[ \hat{f}(x)= \frac{\sum_{i\in N_k(x)}w_i(x)y_i} {\sum_{i\in N_k(x)}w_i(x)}, ]
where (w_i(x)) decreases as (d(x,x_i)) increases. Classification uses the analogous weighted class total rather than an unweighted vote.
Inverse-distance weights require a convention when a training observation lies at zero distance from the query. Exact duplicates can also have conflicting responses, in which case zero distance does not uniquely determine an output. These cases reflect repeated observations in the sample rather than a failure of the metric axioms.
Weighted nearest neighbors are closely related to kernel regression. The principal distinction is that a conventional k-NN neighborhood adapts its physical radius until it contains a fixed number of observations, whereas a fixed-bandwidth kernel retains a prescribed geometric scale and permits the effective number of influential observations to vary.
Statistical properties
For one-nearest-neighbor classification, the predicted class at a query is the class attached to the closest sampled point. As the sample becomes dense, that neighbor approaches the query in the input space, but its class label remains a random draw from the local conditional class distribution. The asymptotic error therefore need not equal the Bayes error.
For a binary problem, Cover and Hart showed that the asymptotic one-nearest-neighbor error (R_{1\mathrm{NN}}) satisfies
[ R^* \leq R_{1\mathrm{NN}} \leq 2R^(1-R^), ]
where (R^) denotes the Bayes error. The upper bound is no greater than twice (R^), with the sharper expression accounting for the fact that the factor decreases as the irreducible error increases.
Broader consistency results apply when the neighborhood size grows with the sample while its proportion of the sample vanishes. Under standard regularity conditions, the relations
[ k\rightarrow\infty \qquad\text{and}\qquad \frac{k}{n}\rightarrow 0 ]
allow the neighborhood radius to contract while retaining enough observations for local averaging. This combination supports convergence toward the Bayes classifier or the corresponding regression function.
In high-dimensional spaces, the amount of data required to populate local neighborhoods increases rapidly. Distances may also become comparatively concentrated, reducing the distinction between the nearest and more distant observations. This aspect of the curse of dimensionality explains why feature representation and dimension reduction can substantially change nearest-neighbor behavior.
Computational structure
A direct query computes the distance from the query point to all (n) training observations. For (p)-dimensional vectors, this requires (O(np)) arithmetic work before neighbor selection, while storage remains proportional to the retained training sample. Training in the narrow computational sense consists largely of storing observations, although preprocessing and metric estimation can require additional computation.
Spatial indexes can reduce search time when the metric and dimension permit effective partitioning. A k-d tree recursively divides a coordinate space, while a ball tree organizes observations through nested metric regions. Their advantage commonly decreases in high dimensions because many regions must be examined to establish which points are genuinely nearest.
Approximate nearest neighbor search permits a controlled departure from exact neighbor recovery in exchange for a different computational cost. The resulting prediction combines approximation error from the search structure with the statistical error already present in the classifier or regressor.
Interpretation
The k-NN method represents prediction as comparison with observed cases rather than evaluation of a compact global equation. Its decision regions are determined jointly by the sample configuration and the selected metric. In one-neighbor classification, each training point owns a Voronoi cell, and the class assigned throughout that cell is the class of its generating observation. For larger values of (k), the regions depend on higher-order Voronoi relationships and can no longer be represented by the ordinary first-order diagram alone.
The method’s non-parametric designation does not imply an absence of assumptions. It relocates assumptions from an explicit probability family to the notions of distance, neighborhood, local similarity, and response smoothness. When nearby points have related conditional responses, local averaging has a statistical basis; when the metric makes unrelated observations appear close, the same mechanism transfers information across an inappropriate neighborhood.