K-nearest neighbors (KNN) is the simplest useful classifier: to label a new point, find the k training points closest to it and take a majority vote (or, for regression, average their targets). There is no training step beyond storing the data, which makes KNN a lazy, instance-based, non-parametric method. Its quality depends almost entirely on two choices — the distance metric and k — and on whether the feature space makes "close" meaningful. The same nearest-neighbor idea, at massive scale, is what vector databases do for semantic search and RAG retrieval.
Part of Classification within Supervised Learning.
Given a query x:
d(x, xi) to every training point (or use an index to find the closest ones quickly).k points with the smallest distances, Nk(x).Nk(x); the class fractions give predict_proba. Regression: predict the mean target.With weights="distance", each neighbor votes with weight 1/d, so closer points count more and ties become rare. KNN is consistent: as n → ∞ with k → ∞ and k/n → 0, its error approaches the Bayes-optimal error. Even 1-NN has an asymptotic error at most twice the Bayes rate (Cover & Hart, 1967). The catch is that "asymptotically" can require enormous amounts of data in high dimensions.
The metric defines what "similar" means:
√Σ(xj − zj)2 — the default (Minkowski with p = 2).Σ|xj − zj| (p = 1) — less dominated by a single large difference.1 − x·z / (‖x‖‖z‖) — for text vectors and embeddings, where direction matters more than length.Because distances sum over features, a feature measured in thousands swamps one measured in fractions. Always scale numeric features (standardize or min-max) before KNN, and think about how categorical features should contribute. In high dimensions, distances also concentrate: the nearest and farthest neighbors end up nearly equidistant, which is the curse of dimensionality. Reduce dimensions first (PCA, feature selection, or a learned embedding) when d is large.
k is the smoothing knob. k = 1 reproduces the training labels exactly and produces a jagged boundary (a Voronoi tessellation) that follows every noisy point. Increasing k averages over a larger neighborhood, lowering variance but blurring real structure; at k = n every query gets the majority class. Choose k by cross-validation; √n is a common starting guess, and odd values avoid ties in binary problems. Distance weighting makes results less sensitive to the exact k.
KNN moves all the cost to prediction time. Brute-force search is O(n · d) per query and the full training set must stay in memory. scikit-learn's algorithm="auto" picks between brute force, a KD-tree and a ball tree; trees prune whole regions and are much faster in low dimensions but lose their advantage as d grows. For millions of high-dimensional vectors (embeddings), use approximate nearest-neighbor libraries — FAISS, hnswlib, ScaNN, or a vector database — which use graph (HNSW) or quantization/inverted-file indexes to answer queries in sub-linear time at a small cost in recall.
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
X, y = load_wine(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)
pipe = Pipeline([("scale", StandardScaler()), ("knn", KNeighborsClassifier())])
grid = GridSearchCV(
pipe,
{
"knn__n_neighbors": list(range(1, 31, 2)),
"knn__weights": ["uniform", "distance"],
"knn__p": [1, 2], # Manhattan vs Euclidean
},
cv=5,
).fit(X_tr, y_tr)
print("best:", grid.best_params_)
print("test accuracy:", round(grid.score(X_te, y_te), 3))
# Same model without scaling, for comparison
raw = KNeighborsClassifier(n_neighbors=grid.best_params_["knn__n_neighbors"]).fit(X_tr, y_tr)
print("unscaled accuracy:", round(raw.score(X_te, y_te), 3))
# Inspect the neighbors behind one prediction
dist, idx = grid.best_estimator_["knn"].kneighbors(
grid.best_estimator_["scale"].transform(X_te[:1]))
print("neighbor labels:", y_tr[idx[0]], "distances:", dist[0].round(2))
On the wine dataset, whose features span very different ranges, the unscaled model is noticeably worse — a quick demonstration of why the scaler belongs inside the pipeline. kneighbors returns the actual supporting examples, which is KNN's built-in explanation.
| Strength | Limitation |
|---|---|
| No training; add new data instantly. | Slow, memory-heavy prediction on large n. |
| Non-parametric: any boundary shape. | Curse of dimensionality; needs a meaningful metric. |
| Naturally multiclass; explanations by example. | Very sensitive to scaling and irrelevant features. |
| Works on embeddings for similarity search. | Imbalanced classes bias the vote toward the majority. |
Use KNN as a quick baseline on small, low-dimensional data, for recommendation and similarity lookups ("items like this one"), for imputation (KNNImputer), and on top of good embeddings where distances are semantically meaningful.
k in binary problems creates ties that are broken by training-set order.The query q = (2, 3) has five labeled training points at Euclidean distances 1.00, 1.41, 2.00, 3.00 and 3.61. With k = 3 and uniform votes, the neighbors are A (red), B (blue) and C (blue), so the prediction is blue with predict_proba of 2/3. With distance weighting (1/d), red scores 1.00 and blue scores 0.71 + 0.50 = 1.21; still blue, but with a smaller margin. With k = 5 and uniform votes, the two far red points D and E join and red wins 3 to 2. Distance weighting at k = 5 gives red 1.00 + 0.33 + 0.28 = 1.61 versus blue 1.21, so red again.
The example is small but the lesson generalizes: predictions near class boundaries depend on k, and the class probabilities from KNN are coarse (multiples of 1/k) and often poorly calibrated. If you need probabilities for thresholding or ranking, use a larger k, distance weighting, or calibrate on a held-out set.
Nearest-neighbor methods rely on "near" meaning something. In high dimensions it often stops doing so. A classic illustration: to capture 10% of uniformly distributed data in a unit hypercube with a smaller cube around the query, the sub-cube's edge must be 0.11/d of the full range. In 2 dimensions that is about 0.32, in 10 dimensions about 0.79. The "local" neighborhood spans most of the range of every feature. Beyer and colleagues showed that, under broad conditions, the ratio between the farthest and nearest distances approaches 1 as dimension grows, so the ranking of neighbors becomes fragile to noise.
KNN still works well on high-dimensional embeddings because those vectors lie near a much lower-dimensional structure learned by the model, and because cosine similarity on them was what the model was trained to make meaningful. On raw, wide tabular data, reduce dimension first (feature selection, PCA) or use a different model.
At scale, exact search is replaced with approximate nearest neighbor (ANN) indexes that trade a small amount of recall for large speedups:
| Index family | Idea | Typical use |
|---|---|---|
| KD-tree / ball tree | Exact space partitioning | Low dimensions (roughly under 20) |
| HNSW graph | Greedy search on a layered proximity graph | High-recall, in-memory embedding search |
| IVF (inverted file) | Cluster vectors; search only the nearest clusters | Large collections, tunable speed vs recall |
| Product quantization | Compress vectors into short codes | Billions of vectors in limited memory |
Libraries such as FAISS, hnswlib and the vector features of databases (see Vector Search) implement these. Always measure recall@k of the ANN index against brute force on a sample, because the index parameters, not the model, can become the accuracy bottleneck.