# K-nearest neighbors algorithm

The k-nearest neighbors algorithm (k-NN) is a supervised machine learning method that classifies a query point by majority vote among the k labeled training samples closest to it under a chosen distance metric, or predicts a continuous value by averaging the targets of those samples. It stores the training data rather than building an explicit model, which makes it an instance-based, non-generalizing method.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

| Key fact | Detail |
|---|---|
| First formulation | Fix and Hodges, 1951, an unpublished US Air Force report on non-parametric discrimination for populations with unknown distributions<sup>[2](https://www.sciencedirect.com/science/article/abs/pii/S0378112711004014)</sup> |
| Classic analysis | Cover and Hart (1967), *IEEE Transactions on Information Theory* 13(1), pp. 21–27<sup>[3](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)</sup> |
| Error guarantee | For M categories, R* ≤ R ≤ R*(2 − MR*/(M−1)); the nearest-neighbor error is at most twice the Bayes error<sup>[3](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)</sup> |
| Consistency | Stone (1977) showed the k-NN rule is universally Bayes-consistent when k grows slowly with n, for example k ≈ log(n)<sup>[4](https://www.sciencedirect.com/topics/computer-science/nearest-neighbors-classifier)</sup> |
| Search cost | Brute-force search scales as O[D N²] for N samples in D dimensions; tree structures reduce this to O[D N log(N)] or better<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup> |
| Dimension limit | KD trees are efficient for D < 20 but degrade toward brute-force cost as dimension grows, one manifestation of the curse of dimensionality<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup> |
| Preprocessing | Feature scaling is required: unscaled features with large ranges dominate the distance computation<sup>[5](https://scikit-learn.org/stable/auto_examples/preprocessing/plot_scaling_importance.html)</sup> |

## The decision rule

Given a training set of n pairs (xᵢ, θᵢ), where xᵢ is a measurement vector and θᵢ its class label, the rule assigns to a new observation x the class most heavily represented among its k nearest neighbors under a metric d. The distance can be any metric; standard [Euclidean distance](https://www.edgepedia.org/euclidean-distance) is the most common choice.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup> With k = 1 the rule simply copies the label of the single closest training point. With k > 1 the vote smooths out individual mislabeled or noisy samples: a larger k suppresses the effects of noise but makes the classification boundaries less distinct.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

**Weighted voting.** The basic form gives every neighbor an equal vote. A common refinement weights each neighbor proportionally to the inverse of its distance from the query point, so nearer samples contribute more; a user-defined weighting function of the distance can also be supplied.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

**Radius variants.** Instead of a fixed count k, a radius-based rule uses all neighbors within a fixed radius r. This suits data that is not uniformly sampled, because points in sparse neighborhoods then use fewer neighbors; in high-dimensional parameter spaces, however, the radius method becomes less effective due to the curse of dimensionality.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

## Theoretical guarantees

The first formulation of a nearest-neighbor-type rule and the primary early analysis of its properties are due to Evelyn Fix and Joseph L. Hodges, in a 1951 unpublished US Air Force report later republished in 1977 and 1989; they established consistency of the k-NN rule for sequences with k/n → 0.<sup>[2](https://www.sciencedirect.com/science/article/abs/pii/S0378112711004014)</sup><sup> • </sup><sup>[3](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)</sup>

**Cover and Hart's bound.** [Thomas M. Cover](https://www.edgepedia.org/thomas-m-cover), then at Stanford, and Peter E. Hart of the Stanford Research Institute published the classic finite-sample and large-sample analysis in 1967.<sup>[3](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)</sup><sup> • </sup><sup>[6](https://www.centerconsulting.com/ai-library/papers/nearest-neighbor-cover-hart)</sup> Because the rule ignores the underlying joint distribution, its error probability R must be at least the Bayes error R*, the minimum achievable over all decision rules that use that structure. They proved that for M categories and suitably smooth distributions the large-sample error satisfies R* ≤ R ≤ R*(2 − MR*/(M−1)), so for any number of categories the nearest-neighbor error is bounded above by twice the Bayes error. In their words, half the classification information in an infinite sample set is contained in the nearest neighbor.<sup>[3](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)</sup> They also showed the single-neighbor rule is admissible among k-NN rules: against certain distributions no k ≠ 1 rule achieves lower error for every case.<sup>[3](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)</sup>

**Universal consistency.** [Charles J. Stone](https://www.edgepedia.org/charles-j-stone) proved in 1977 that the k-NN classification rule is universally Bayes-consistent: if k grows with the sample size n but slowly enough, for example k ≈ log(n) so that k/n → 0, the rule's error converges to the Bayes error for essentially any underlying distribution.<sup>[4](https://www.sciencedirect.com/topics/computer-science/nearest-neighbors-classifier)</sup><sup> • </sup><sup>[7](https://arxiv.org/abs/2003.00894)</sup> This result places k-NN among methods whose asymptotic behavior requires no distributional assumptions.

## Making the search fast

Classification requires finding the k closest training points, and fast neighbor search is an active research area. The naive approach computes distances between the query and every training sample; for N samples in D dimensions this scales as O[D N²] over all pairs, and brute force becomes infeasible as N grows.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

**KD trees.** The KD tree, a binary tree that recursively partitions the parameter space along data axes, exploits aggregate distance information: if point A is far from B and B is close to C, then A and C are far without computing that distance. Construction needs no D-dimensional distance calculations, and a query needs about O[log(N)] distance computations. This works well for low dimensions, roughly D < 20, but the cost rises toward nearly O[DN] as D grows large, and tree overhead can make queries slower than brute force.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

**Ball trees.** To address KD-tree inefficiency in higher dimensions, the ball tree partitions data into nesting hyperspheres defined by a centroid C and radius r. One distance calculation to a centroid bounds the distance to every point in the node via the triangle inequality. Construction is more costly, but the structure can outperform a KD tree on highly structured data even in very high dimensions, with performance depending strongly on the data's structure.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

**Approximate search.** In high dimensions exact search is affected by the curse of dimensionality at a fundamental level, and theory shows hard limits: polynomial-space indexes for high-dimensional k-NN in Hamming space require Ω(k) block reads per query.<sup>[8](https://www.sciencedirect.com/science/article/pii/S0898122112006426)</sup><sup> • </sup><sup>[9](https://arxiv.org/abs/2002.04870)</sup> Approximate nearest neighbor (ANN) algorithms trade accuracy for speed, returning a point whose distance is at most c times the true minimum. Piotr Indyk of MIT and Tal Wagner gave a (1+ε)-approximate structure using only O(ε⁻² n log(n) log(1/ε)) bits of space for integer-coordinate points, improving the previous bound of O(ε⁻² n log(n)²) obtained via Johnson–Lindenstrauss dimension reduction.<sup>[10](https://proceedings.mlr.press/v75/indyk18a.html)</sup> Practical ANN methods include randomized divide-and-conquer schemes with random rotations and local graph search, which perform extremely well around 20 dimensions and degrade noticeably by about 100 dimensions.<sup>[11](https://pmc.ncbi.nlm.nih.gov/articles/PMC3179075/)</sup>

## Practical use

**Choosing k and weighting.** The optimal k is highly data-dependent. Larger k reduces noise sensitivity at the cost of blurrier class boundaries; a common default in software is k = 5.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup><sup> • </sup><sup>[12](https://itl.nist.gov/div898/software/dataplot/refman1/auxillar/knn_plot.htm)</sup> Distance-weighted voting helps when neighbors vary widely in distance.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup>

**Feature scaling.** Because prediction depends entirely on distances, k-NN requires normalized features. In the Wine dataset example from scikit-learn, the variable proline varies between 0 and 1,000 while hue varies between 1 and 10, so unscaled distances are dominated by proline and hue is effectively ignored; standardizing both features to roughly the range −3 to 3 produces a completely different, better-balanced decision boundary.<sup>[5](https://scikit-learn.org/stable/auto_examples/preprocessing/plot_scaling_importance.html)</sup>

**Distance choice.** A review of distance measures for k-NN notes that the classifier is among the simplest and most common, yet its performance competes with more complex classifiers, and the choice of distance measure materially affects results.<sup>[13](https://pubmed.ncbi.nlm.nih.gov/31411491/)</sup> Alternatives to Euclidean distance include Manhattan, Minkowski, Chebyshev, cosine, Hamming, and Mahalanobis distances, selectable in standard implementations.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup><sup> • </sup><sup>[12](https://itl.nist.gov/div898/software/dataplot/refman1/auxillar/knn_plot.htm)</sup>

**Applications.** k-NN is used widely in medical image analysis, often on features extracted by convolutional neural networks. A hybrid CNN-KNN approach for brain tumor classification in MRIs from the BraTS 2015 and BraTS 2017 datasets reported 96.25% accuracy, and hybrid CNN-KNN pipelines have been applied to lung nodule and COVID-19 CT image classification.<sup>[14](https://link.springer.com/article/10.1007/s10462-024-10814-2)</sup> Nearest-neighbor techniques also entered fields such as forestry for estimating forest attributes from reference plots.<sup>[2](https://www.sciencedirect.com/science/article/abs/pii/S0378112711004014)</sup>

**Limitations.** The method's costs are memory and query time: it stores all training data, and prediction cost grows with the dataset. Its documented weaknesses in high-dimensional data, its dependence on careful preprocessing, and its vulnerability to noise and class imbalance make it a suboptimal choice for some complex classification tasks.<sup>[1](https://scikit-learn.org/stable/modules/neighbors.html)</sup><sup> • </sup><sup>[15](https://www.nature.com/articles/s41598-025-31562-5_reference.pdf)</sup>

## References

1. [1.6. Nearest Neighbors, scikit-learn documentation](https://scikit-learn.org/stable/modules/neighbors.html)
2. [Estimating forest attribute parameters for small areas using nearest neighbors techniques, Forest Ecology and Management](https://www.sciencedirect.com/science/article/abs/pii/S0378112711004014)
3. [T. Cover, P. Hart (1967). Nearest Neighbor Pattern Classification, IEEE Transactions on Information Theory 13(1), 21–27](https://gwern.net/doc/ai/nn/retrieval/1967-cover.pdf)
4. [Nearest Neighbors Classifier, ScienceDirect Topics (Stone 1977 theorem)](https://www.sciencedirect.com/topics/computer-science/nearest-neighbors-classifier)
5. [Importance of Feature Scaling, scikit-learn example](https://scikit-learn.org/stable/auto_examples/preprocessing/plot_scaling_importance.html)
6. [Nearest Neighbor Pattern Classification, CenterConsulting AI library](https://www.centerconsulting.com/ai-library/papers/nearest-neighbor-cover-hart)
7. [Universal consistency of the k-NN rule in metric spaces and Nagata dimension, arXiv](https://arxiv.org/abs/2003.00894)
8. [Is the k-NN classifier in high dimensions affected by the curse of dimensionality?, Applied Mathematics and Computation](https://www.sciencedirect.com/science/article/pii/S0898122112006426)
9. [On the I/O complexity of the k-nearest neighbor problem, arXiv](https://arxiv.org/abs/2002.04870)
10. [P. Indyk, T. Wagner (2018). Approximate Nearest Neighbors in Limited Space, COLT 2018, PMLR 75:2012–2036](https://proceedings.mlr.press/v75/indyk18a.html)
11. [Randomized approximate nearest neighbors algorithm, PMC](https://pmc.ncbi.nlm.nih.gov/articles/PMC3179075/)
12. [K Nearest Neighbors Classification Plot, NIST Dataplot reference manual](https://itl.nist.gov/div898/software/dataplot/refman1/auxillar/knn_plot.htm)
13. [Effects of Distance Measure Choice on K-Nearest Neighbor Classifier Performance: A Review, PubMed](https://pubmed.ncbi.nlm.nih.gov/31411491/)
14. [Efficient artificial intelligence approaches for medical image processing in healthcare, Artificial Intelligence Review](https://link.springer.com/article/10.1007/s10462-024-10814-2)
15. [Scientific Reports reference list citing KNN limitations](https://www.nature.com/articles/s41598-025-31562-5_reference.pdf)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Machine learning methods › Supervised, unsupervised, and semi-supervised learning › Classification algorithms*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license