The classifier that trains nothing.
On this page
You move to a new street and want to know which bakery is best. You could build a statistical model of bakeries, or ask your five nearest neighbors and go with the majority. k-NN is the second option: to classify a new point, find the k training points closest to it and take a majority vote. Cover and Hart (1967) showed that, with enough data, the one-nearest-neighbor rule makes at most twice the error of the best possible classifier.
"Training" is just memorizing the dataset: the model is the data, and all the thinking happens at query time. The main setting you choose before predicting, a hyperparameter, is k.
The neighbors are set by the straight-line (Euclidean) distance from the query q to each training point x across every feature (a feature is one measured number that describes a point).
The distance adds raw feature values, so a feature measured in thousands drowns one measured in fractions. Standardizing every feature first fixes that; scikit-learn does it with StandardScaler, and PCA (principal component analysis) needs the same fix.
The k nearest points then form the set Nk(q), and the prediction ŷ is their most common label.
The snippet is the whole algorithm on five stored points: one distance line, then the sort and the vote.
import numpy as np
X_train = np.array([[1.0, 1.2], [0.8, 0.9], [3.1, 3.0], [2.9, 3.3], [1.1, 0.7]])
labels = np.array([0, 0, 1, 1, 0])
q = np.array([1.0, 1.0])
k = 3
dist = np.sqrt(((X_train - q) ** 2).sum(axis=1))
nearest = np.argsort(dist)[:k]
votes = np.bincount(labels[nearest])
y_hat = votes.argmax()
print(y_hat) # 0With two classes an odd k can never tie; with three or more, ties can still happen and need a rule, such as the nearest voter decides.
Figure 2. Blue wins with 5 voters, orange with 15.
One noisy neighbor can swing a small vote, while many voters average the noise out. That is the bias-variance tradeoff: bias is the error from a boundary too smooth to follow the true one (large k), and variance is how much the boundary changes when the noisy points change (small k).
Figure 4. At k = 1 or 3 orange noise points win; from 5 on, blue wins.
The plain vote treats the nearest neighbor and the farthest voter as equals, and it only predicts labels.
Plain k-NN scans every stored point per query. KD-trees and ball trees (nested boxes or balls of points) skip most of that scan, and graph indexes such as HNSW (hierarchical navigable small world graphs, which link each point to a few near points) trade a little accuracy for a lot of speed.
This snippet builds four variants with the same 17 voters, each behind a StandardScaler, and prints each one’s accuracy on held-out test points; the one changed argument is the whole difference.
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier as KNN
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
X, y = make_classification(n_samples=400, n_features=2, n_informative=2, n_redundant=0, random_state=2)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
k = 17
variants = {
"weighted by 1/d": KNN(k, weights="distance"),
"manhattan": KNN(k, metric="manhattan"),
"cosine": KNN(k, metric="cosine"),
"kd-tree search": KNN(k, algorithm="kd_tree"),
}
for name, knn in variants.items():
model = make_pipeline(StandardScaler(), knn).fit(X_train, y_train)
print(name, model.score(X_test, y_test))k-NN regression is KNeighborsRegressor(k), the same call with numbers for labels.
In scikit-learn, k-NN sits after a scaler in one pipeline; fit stores the scaled training points once, and predict or score runs the distance and the vote for every new point.
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
X, y = make_classification(n_samples=400, n_features=2, n_informative=2, n_redundant=0, random_state=2)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5))
model.fit(X_train, y_train)
print(model.score(X_test, y_test)) # accuracy on new pointsStandardScaler, the standardizing card in Section 2, with KNeighborsClassifier.| step | when, on what, and its cost |
|---|---|
fit | Once, storing the training points with no learning. |
predict | Per query, one distance per stored point over every feature, then the vote; time grows with the training set. |
| state | The whole training set. |
| setting | raise it, lower it | default |
|---|---|---|
n_neighbors, k in Nk(q) | Up smooths the boundary; k equal to the number of training points predicts the majority class everywhere. Down makes it jagged; k = 1 copies the nearest point and overfits. | 5 |
weights, the 1/d factor | "distance" lets near voters count more; "uniform" counts each voter once. | "uniform" |
metric, p, the d(x, q) card | Changes what near means. The default Minkowski distance raises each feature gap to the power p; p = 2 is straight-line distance, p = 1 Manhattan. | "minkowski", p=2 |
Defaults from the KNeighborsClassifier docs; the per-query cost, linear in the training set, is from Manning, Raghavan and Schütze (2008). Gotchas are in Section 7.
With no training step, overfitting never shows up in a training curve. It shows up at query time as a jagged boundary: small k wraps noisy points, big k averages them away.
Near means similar only in a few meaningful dimensions. With a thousand raw features everything is far from everything, and the nearest neighbors are barely nearer than the rest, the curse of dimensionality. Cutting the features down to a few directions first, as PCA does, gives the distances their meaning back.
The same nearest-point idea runs without labels in k-means, where each point joins its nearest center. k-NN votes with neighbors. The next classifier, Naive Bayes, votes with word counts and rests on Bayes rule.