The k-nearest neighbors algorithm (k-NN) is a non-parametric, instance-based learning method used for classification and regression. In both cases, the input consists of the k closest training examples in a feature space. The output depends on whether k-NN is used for classification or regression: in classification, the output is a class membership, determined by a majority vote among the k nearest neighbors; in regression, the output is the average (or weighted average) of the values of the k nearest neighbors. k-NN is a type of lazy learning, where the function is only approximated locally, and all computation is deferred until function evaluation. Because it relies on distance calculations, the algorithm is sensitive to the local structure of the data and the choice of distance metric.
The algorithm was first developed in 1951 by Evelyn Fix and Joseph Hodges at the US Air Force School of Aviation Medicine, originally as a non-parametric classification technique. It was later expanded and formalized by Thomas Cover and Peter Hart in 1967, who established its asymptotic error bounds. Since then, k-NN has become a fundamental tool in Machine learning, pattern recognition, and data mining, often used as a baseline for more complex models.
How It Works
Given a query point, the algorithm computes the distance (typically Euclidean, Manhattan, or Minkowski) to every training example. It then selects the k training examples with the smallest distances. For classification, the predicted label is the one most frequent among these k neighbors. For regression, the predicted value is the mean of the neighbors' target values. The choice of k is critical: a small k (e.g., 1) leads to high variance and sensitivity to noise, while a large k can smooth over local patterns, increasing bias. Common practice is to select k via cross-validation, often using odd values for binary classification to avoid ties.
The algorithm also requires a distance metric. Euclidean distance is standard for continuous features, but for high-dimensional or categorical data, other metrics like Hamming distance or cosine similarity may be used. Feature scaling (e.g., normalization or standardization) is essential because features with larger ranges dominate the distance calculation.
Properties and Variants
k-NN is non-parametric, meaning it makes no strong assumptions about the underlying data distribution. It is also instance-based, storing the entire training set and using it directly at prediction time. This makes training trivial (essentially just storing data) but prediction computationally expensive, with a time complexity of O(nd) per query, where n is the number of training samples and d is the number of features.
Several variants address these limitations. Weighted k-NN assigns higher influence to closer neighbors, often using inverse distance weights. Locally weighted regression fits a linear model within the neighborhood. For large datasets, approximate nearest neighbor search techniques, such as k-d trees, ball trees, or locality-sensitive hashing, reduce the search cost. In high dimensions, the curse of dimensionality degrades performance, as distances become less discriminative; dimensionality reduction or feature selection is often applied.
Applications
The algorithm is widely used in fields such as Computer vision for image classification, Natural language processing for text categorization, and bioinformatics for gene expression analysis. It appears in recommendation systems, where it finds users or items with similar preferences. In finance, it is used for credit scoring and fraud detection. Its simplicity and interpretability make it a common first choice for exploratory analysis and as a benchmark against more complex models like Neural networks.
Strengths and Limitations
k-NN's main strengths are its simplicity, ease of implementation, and effectiveness on small to medium-sized datasets with low to moderate dimensionality. It requires no training phase, making it suitable for incremental learning. However, its limitations include high memory usage (storing all training data), slow prediction time, sensitivity to irrelevant features and noise, and poor performance in high-dimensional spaces. It also assumes that all features are equally important, which is rarely true in practice.
Relation to Other Methods
k-NN is often compared to other non-parametric methods like decision trees and support vector machines. It is a foundational technique in Machine learning and is frequently taught alongside Artificial intelligence curricula. Its principles underpin more advanced methods such as Data Augmentation techniques that generate synthetic neighbors, and it is used in Curriculum Learning as a way to order training examples by difficulty. In modern practice, k-NN is sometimes used as a final layer in deep learning models for metric learning, where learned embeddings are compared using nearest neighbor search.
See Also
References
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.