Nearest neighbours

No parameters, only examples

A nearest-neighbour classifier does not fit a line or a tree. It stores the training rows. At prediction time it finds the k closest rows to the query and takes a vote among their labels. Training is almost free. The cost moves to inference, the step that answers a query. There every prediction compares the query with the stored data.

The decision boundary is implied by the points, not written down as an equation. The boundary is the set of points where the prediction changes. With one neighbour, it is the set of places where the closest point changes label. That boundary can be jagged. It can wrap around a single noisy example. The model has no global view, only local evidence.

The method is called lazy because it puts off the work until prediction. That helps when a dataset changes often, since adding a row needs no refit. It hurts when the dataset is large or the latency budget is tight. The method is also a useful baseline. If a nearest-neighbour model with a sensible distance does well, a more complex model has to justify itself.

Distance is a choice

Euclidean distance is the default. It is the square root of the sum of squared coordinate differences. Manhattan distance adds the absolute differences instead. It behaves differently when movement happens along the axes. Cosine distance compares directions. It is common for text vectors, where length often reflects document size rather than meaning.

The units matter more than the formula. A feature measured in thousands dominates one measured between zero and one. The Euclidean distance then measures the large feature alone. Standardising each column to zero mean and unit variance puts them on a similar footing. Fit the scaler on the training data only, for the reason the previous chapter gave.

Cosine distance is not a drop-in replacement for Euclidean distance. It ignores magnitude. That is right when the direction of a vector is the signal, and wrong when the size is. In text, a long document and a short one can point the same way. In sensor data, the magnitude may be the measurement. The metric should follow the meaning of the columns, not the convenience of the library.

The classifier in scikit-learn

from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

model = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5, metric="euclidean"),
)
model.fit(X_train, y_train)
print(model.predict(X_test))

Choosing k

A small k follows the data closely. One neighbour can be swung by a single mislabelled point. The boundary then has high variance, meaning it changes a lot with a new sample. A large k smooths the boundary and lowers that variance. Eventually it starts averaging across regions that are genuinely different. The bias-variance trade is visible right in the choice of k.

For a two-class problem, an odd k avoids a tied vote. There is no universal value. Tune it on validation data, and report the curve rather than a single winning number.

Distance weighting is a middle ground. Instead of giving every neighbour one vote, weight each by the inverse of its distance. A close point then counts more than a far one. That softens the effect of a large k without ignoring local evidence. It also adds a new choice: how to handle an exact match, where the weight would be infinite. The usual answer is a small constant added to the denominator.

When it fails

In high dimensions, distances lose contrast. The nearest and farthest points become almost equally far, so “nearest” stops meaning much. Irrelevant features add noise to every distance. A single uninformative column can drown a useful one. Feature selection is not optional when the row is wide.

The method also stores the training data. That can be a privacy problem and a memory problem. Inference cost grows with the number of stored rows. A missing value has no natural distance unless you define one. These are reasons to try a linear model or a tree first. They are not reasons the method is useless.