k-nearest neighbors (k-NN) algorithm

The k-nearest neighbors (k-NN) algorithm predicts a label or value for a new data point from the k stored examples closest to it, where k is a number you choose. It’s non-parametric and instance-based, so training only stores the labeled examples and all the work happens at query time.

Given a query point, the algorithm measures distance to every stored example under a chosen metric, usually straight-line Euclidean distance, and keeps the k nearest neighbors. Classification takes a majority vote of their labels, and regression averages their target values. Neighbors can count equally or be weighted by inverse distance, so closer points pull harder.

The value of k trades detail against noise. A small k follows every wrinkle in the data, while a larger k smooths the decision boundary and blurs it. In scikit-learn, KNeighborsClassifier defaults to five neighbors and uniform weights.

The scatter plot below shades the region each class wins at the chosen k, so a single mislabeled example carves out its own island at the smallest k and dissolves into the majority as k grows. Drag the query point or move the slider to watch the vote change.

Scanning every stored example costs linear time per query, so implementations use spatial indexes such as KD-trees and ball trees. Those work well in low dimensions and degrade as dimensionality grows, which is why embedding search over hundreds of dimensions turns to approximate nearest neighbor (ANN) methods instead.

Hierarchical Navigable Small World (HNSW) graphs, introduced in 2016 by Malkov and Yashunin, trade exact answers for logarithmic search time. That approximation is what a vector database commonly runs underneath retrieval-augmented generation, where the k retrieved chunks become prompt context.

The underlying decision rule predates modern machine learning. A 1967 paper by Cover and Hart proved that given unlimited data, the single-neighbor version makes at most twice as many errors as the optimal Bayes classifier.

Related Resources

Tutorial

The k-Nearest Neighbors (kNN) Algorithm in Python

In this tutorial, you'll learn all about the k-Nearest Neighbors (kNN) algorithm in Python, including how to implement kNN from scratch, kNN hyperparameter tuning, and improving kNN performance using bagging.

intermediate algorithms data-science machine-learning

For additional information on related topics, take a look at the following resources:

• Using k-Nearest Neighbors (kNN) in Python (Course)
• Embeddings and Vector Databases With ChromaDB (Tutorial)
• Practical Text Classification With Python and Keras (Tutorial)
• Split Your Dataset With scikit-learn's train_test_split() (Tutorial)
• Learn Text Classification With Python and Keras (Course)
• Splitting Datasets With scikit-learn and train_test_split() (Course)
• Vector Databases and Embeddings With ChromaDB (Course)
• Embeddings and Vector Databases With ChromaDB (Quiz)
• Split Your Dataset With scikit-learn's train_test_split() (Quiz)