K-Nearest Neighbors (KNN)

K-nearest neighbors (KNN) is a supervised learning algorithm that predicts the label of a new example from the k labeled examples closest to it: a majority vote among those neighbors for classification, or their average for regression. KNN is nonparametric and "lazy": it learns no weights, simply stores the training data, and does all of its work when a prediction is requested. Evelyn Fix and Joseph Hodges introduced the method in 1951, and in 1967 Thomas Cover and Peter Hart proved that, given unlimited data, the single-nearest-neighbor rule has at most twice the error rate of the best possible classifier. The same nearest-neighbor search now runs at scale in vector databases and image retrieval systems that compare embeddings from neural networks.

How KNN Makes a Prediction#

For each query point, KNN runs three steps:

1. Measure distance: It computes the distance from the query to every stored example. Euclidean distance is the default, Manhattan and Minkowski distances are common alternatives, and cosine similarity is standard for embeddings, where a vector's direction carries its meaning.
2. Select neighbors: It keeps the k examples with the smallest distances.
3. Combine their labels: Classification takes the most common class among the neighbors, and regression takes the mean of their values. With distance weighting (weights="distance" in scikit-learn), closer neighbors count more.

Every feature contributes to the distance, so features on large scales dominate: income in dollars would swamp age in years. KNN pipelines therefore standardize features first, or compare embeddings from a feature extraction model, so that each dimension contributes on a comparable scale.

Choosing k#

The value of k sets the balance between overfitting and underfitting. With k = 1, every training point, including noisy and mislabeled ones, claims its own region, and the decision boundary turns jagged. With a very large k, each vote reaches far from the query and blurs real class boundaries. For two classes, an odd k avoids tied votes, and cross-validation is the standard way to pick k. On scikit-learn's noisy two-moons dataset, the trade-off shows in three values:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

With k = 1 the classifier memorizes its training points, scoring 1.00 on them and 0.83 on held-out points. With k = 15 it scores 0.90 and 0.89, the best test result of the three, and k = 300, nearly half of the 700 training points, smooths the boundary until both scores drop, to 0.84 and 0.81.

Speeding Up Neighbor Search#

A brute-force search compares the query with all n stored points in d dimensions, so each prediction costs on the order of n × d operations and memory grows with the dataset. Space-partitioning structures such as k-d trees and ball trees skip most comparisons in low dimensions, and scikit-learn's algorithm="auto" picks among brute force, k-d tree, and ball tree. In high dimensions the curse of dimensionality makes distances between points nearly equal, tree pruning stops paying off, and large systems switch to approximate nearest neighbor (ANN) indexes such as HNSW graphs and inverted-file (IVF) indexes with product quantization, implemented in libraries like FAISS. These indexes return most of the true nearest neighbors while comparing the query with a small fraction of the stored vectors:

KNN vs. Related Methods#

• K-means clustering: An unsupervised algorithm that groups unlabeled points into k clusters around learned centroids. The names share a letter by coincidence: in k-means, k counts clusters.
• Vector search: The retrieval form of the same operation: it returns the stored items nearest to a query embedding, usually through an approximate index, and the application uses those items directly.
• Support vector machines and logistic regression: Parametric models that learn a decision boundary during training, so prediction cost stays constant as the training set grows.

Real-World Applications#

• Recommendation systems: Item-based collaborative filtering recommends products whose rating or purchase vectors lie nearest to items a user already liked.
• Anomaly detection: The distance from a point to its k-th nearest neighbor serves as an anomaly score, so transactions or sensor readings far from every normal example stand out.
• Missing-value imputation: scikit-learn's KNNImputer fills each gap with the mean of that feature across the k most similar rows.
• Image retrieval and re-identification: Systems compare an image's embedding against a gallery to find the same product, face, or person seen by another camera. The Ultralytics similarity search solution embeds a folder of images with OpenAI's CLIP, scores every indexed image against a text query such as "red car" by cosine similarity in an exact brute-force search, and returns the nearest ones, up to 30 by default.