K-nearest neighbors algorithm

The algorithm predicts a query point from the labels of nearby training examples. For classification, it selects the most common class among the k closest observations; for regression, it commonly averages their numeric target values.¹ A distance function, such as Euclidean distance, ranks the examples, and the selected neighborhood supplies the prediction. Unlike a fitted linear model, the method does not ordinarily estimate a fixed set of global coefficients.

It is called lazy or instance-based learning because the training data are retained rather than condensed into a conventional parametric model.² The approach can represent irregular decision boundaries, but predictions may become expensive when the data set is large. The parameter k controls how broadly the method smooths local variation.

Distance choice and feature scaling determine what “nearest” means. Euclidean distance is sensitive to measurement units, so variables measured on different scales are often standardized or otherwise normalized before neighborhood search; categorical variables may require a different similarity measure.²

Small values of k can preserve local structure but are sensitive to noise and produce high-variance predictions, while larger values smooth the estimate and may obscure genuine boundaries. Cross-validation is a common way to choose k, the distance metric, and sometimes distance weights.³ Weighted variants give closer observations greater influence, often using inverse distance, although exact zero-distance cases require special handling.

K-nearest neighbors supports both classification and regression, including multiclass classification and predictions with locally varying relationships. A classification system may return class proportions within the neighborhood as informal confidence information, while a regression system may report the local spread of target values rather than only their mean.

Prediction requires locating neighbors, so brute-force search has cost that grows with the number of stored observations and the feature dimension. Data structures such as k-d trees and ball trees can accelerate some low-dimensional searches, but their advantage weakens in high dimensions.² Approximate nearest-neighbor methods trade exactness for speed. Memory use is also a practical concern because the method retains the reference data at prediction time.

The nearest-neighbor rule has a notable theoretical property: under standard assumptions, its asymptotic error is bounded in relation to the Bayes error, although this result does not guarantee strong performance on a finite data set.¹ This distinction between theoretical consistency and practical accuracy is central to evaluating the method.

High-dimensional data create the curse of dimensionality: distances can become less discriminating as irrelevant or numerous features accumulate, making neighborhoods less local.³ Feature selection, dimensionality reduction, and domain-specific metrics can therefore matter more than fine-tuning k. Ties between classes, missing values, duplicate observations, and severe class imbalance also require explicit policy choices. In some applications, nearest-neighbor search is used not as the final predictor but as a retrieval, anomaly-detection, or data-cleaning component.

k

The number of neighboring training observations used to make a prediction.

Instance-based learning

A learning approach that retains examples and makes predictions by comparing new cases with them.

Distance metric

A rule for quantifying dissimilarity between observations.

Curse of dimensionality

The degradation of distance-based methods as the number of features increases.

Bayes error

The irreducible classification error associated with uncertainty in the underlying data-generating process.