4.5.5 K-Nearest Neighbors

What K-NN does

K-nearest neighbors is fundamentally a different kind of model than the usual models we have studied yet. K-nearest neighbors, usually shortened to K-NN, predicts a new sample by looking at the training samples most similar to it.

new sample
→ find the closest training examples
→ look at their answers
→ make a prediction

For example, to identify a new flower, K-NN finds known flowers with similar measurements and predicts the species that appears most often among them.

K-NN does almost no learning when fit is called. It mainly stores the training examples. Most of the work happens later, when predict calculates distances and searches for neighbors. This makes K-NN simple to start with, but it also means prediction can become slow when the stored dataset is large.

One prediction by hand

Suppose four labelled points are stored:

We want to classify the new point $x=(2.5,1.5)$. Its distances from the stored points are:

If $k=3$, the three nearest labels are red, red and blue. Red has the majority, so K-NN predicts red.

That is the complete basic idea: calculate distances, take the nearest $k$, and combine their answers.

Classification and regression

The neighbor search is identical for classification and regression. Only the final step changes.

K-NN classification

For classification, the neighbors vote and the most common label wins:

$$\hat{y}=\text{most common label among the }k\text{ neighbors}.$$

This is what happened in the red-and-blue example above.

K-NN regression

For regression, the targets are numbers, so the model averages them:

$$\hat{y}=\frac{1}{k}\sum_{i\in N_k(x)}y_i.$$

For example, to estimate the price of a new house, K-NN can find the $k$ most similar houses and average their prices. Scikit-learn provides KNeighborsClassifier for voting and KNeighborsRegressor for averaging.

What does "nearest" mean?

K-NN needs a way to measure how different two samples are. For ordinary numeric features, the usual choice is Euclidean distance:

$$d(x,z)=\sqrt{\sum_{j=1}^{D}(x_j-z_j)^2}.$$

This is the straight-line distance between two points. Similar feature values produce a small distance; very different values produce a large one.

K-NN therefore depends on two closely connected choices:

features → decide what information describes a sample
distance → decides what “similar” means in that feature space

Why feature scaling matters so much

Imagine a dataset with these two features:

• age ranges from 10 to 80;
• income ranges from 20,000 to 2,000,000.

A difference of 10 years is numerically tiny beside a difference of 100,000 in income. If raw values are placed in the distance formula, income almost completely decides which samples are nearest, even if age is equally important to the task.

Standardisation puts each feature on a comparable scale:

$$x'=\frac{x-\text{mean}(x)}{\text{standard deviation}(x)}.$$

Fit the scaler only on the training data, then reuse it for validation and test data. A scikit-learn pipeline handles this safely. Scikit-learn's preprocessing guide describes other scaling methods.

Choosing k

The number of neighbors controls how local the decision is.

Small k

A small $k$ follows individual training points closely. This creates a flexible, detailed decision boundary, but it is sensitive to noise and can overfit.

At the extreme, $k=1$ gives every training point its own label because the point is its own nearest neighbor. Training accuracy is therefore usually 100%, even when predictions on new data are poor.

Large k

A large $k$ looks at a wider region. Its predictions are smoother and less sensitive to one noisy sample, but useful local patterns can be washed away, causing underfitting.

At the other extreme, if $k$ equals the number of training samples, every query sees the whole dataset. Classification then predicts the overall majority class almost everywhere.

In bias–variance language, small $k$ has lower bias and higher variance; large $k$ has higher bias and lower variance. The important practical lesson is simpler: do not choose $k$ from training accuracy.

How to choose k

Try several values on validation data or with cross-validation, then keep the value that performs best. On a small dataset, trying $k=1,3,5,\ldots,29$ is inexpensive. With two classes, an odd $k$ also reduces the chance of a tied vote.

Do not use the test set to choose $k$. The test set should be used only after the model choices have been made.

The Cross-Validation module will show how to automate the comparison of several values of $k$ and different voting styles.

Letting closer neighbors count more

Ordinary K-NN gives every neighbor one equal vote. Distance-weighted K-NN gives closer neighbors more influence, using a weight roughly like

$$\text{weight}=\frac{1}{\text{distance}}.$$

A very close example can then matter more than one near the edge of the neighborhood. In scikit-learn, use weights="distance"; the default weights="uniform" gives equal votes.

Using K-NN in practice

Here is a complete first model on the Iris dataset:

from sklearn.datasets import load_iris
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 = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=0
)

model = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5),
)
model.fit(X_train, y_train)
predictions = model.predict(X_test)

The calls hide very little:

fit     → scale and store the training examples
predict → scale each query, calculate distances,
          find five neighbors, and take a vote

K-NN is sometimes called lazy learning because most work waits until prediction time.

Evaluating K-NN

As with every classifier, evaluate on examples that were not used to fit or tune the model. Accuracy is the fraction classified correctly:

from sklearn.metrics import accuracy_score

print(round(accuracy_score(y_test, predictions), 3))
# 0.967

Accuracy alone may not be enough when classes are imbalanced or different mistakes have different costs. Model Evaluation Metrics covers confusion matrices, precision, recall and F1.

The training accuracy here is also 0.967, but that does not make training accuracy a safe way to choose $k$. At $k=1$, it would rise to 1.000 automatically.

Useful K-NN settings

Where K-NN can fail

K-NN works only when nearby samples really are similar in a useful way.

Irrelevant features

Suppose only two features matter, but another 50 random features are included. Differences in those random columns still contribute to distance, so genuinely similar samples may stop appearing close. Feature selection or a better representation can help.

High-dimensional spaces

K-NN relies on meaningful local neighborhoods. As the number of dimensions grows, the nearest and farthest samples can become surprisingly similar in distance. This is part of the curse of dimensionality.

Reducing dimension with PCA or using learned embeddings can make distance more useful.

Large datasets

Fitting is cheap, but brute-force prediction compares each query with all $n$ training samples across $D$ features. This costs roughly $O(nD)$ time per query and $O(nD)$ memory for the stored training set.

For 60,000 MNIST training images with 784 pixels each, one query requires about 47 million pixel subtractions. This is the central K-NN tradeoff:

cheap fit → expensive prediction

K-NN and embeddings

Raw features do not always describe useful similarity. Two sentences can have nearly the same meaning while using completely different words. Two images can show the same object while differing in lighting, background and pixel values.

A pretrained model can turn an input into an embedding vector:

input → pretrained model → embedding vector

Good embeddings place semantically similar inputs near one another. K-NN can then work in that space:

embedding → nearest labelled embeddings → predicted class

This applies to text, image and audio embeddings. K-NN becomes much more useful when the feature space has been designed so that distance represents meaningful similarity.

Optional: K-NN from scratch

import numpy as np

def knn_predict(X_train, y_train, X_query, k=5):
    # Squared distance from every query to every training point: (q, n)
    d2 = ((X_query[:, None, :] - X_train[None, :, :]) ** 2).sum(axis=2)
    # Indices of the k smallest distances in each row
    nearest = np.argpartition(d2, kth=k - 1, axis=1)[:, :k]
    votes = y_train[nearest]
    return np.array([np.bincount(row).argmax() for row in votes])

On the Iris split above, this makes the same predictions as KNeighborsClassifier(algorithm="brute") for all 30 test samples.

K-NN in olympiad tasks

K-NN is useful in two main roles.

As a baseline. On a small dataset, scaling the features and fitting K-NN takes little time. Its validation score tells you how much a more complicated model needs to improve.

On top of embeddings. A pretrained model can provide a useful representation, while K-NN supplies the final class without retraining the pretrained model.

When should I try K-NN?

K-NN is a good choice when:

• the dataset is fairly small;
• the features are few, meaningful and can be scaled sensibly;
• strong embeddings are already available; or
• you need a quick baseline.

Be cautious when:

• the training set is enormous;
• there are many noisy raw features;
• distance does not match real similarity; or
• prediction must be extremely fast.

The whole idea in one view

prediction:      new sample → calculate distances → take nearest k
                 → vote or average → prediction

what matters:    features → what information is available
                 scaling → whether features contribute fairly
                 distance → what “similar” means
                 k → how local the prediction is

generalisation:  store training examples → choose k on validation data
                 → evaluate once on unseen test data

limitations:     many dimensions → distance becomes less meaningful
                 much training data → prediction becomes slow
                 poor features → nearest does not mean similar

modern use:      input → pretrained embedding → K-NN