4.4.3K-Nearest Neighbors

The idea

K-NN has no training step. It stores the training set, and when a new point arrives, it finds the $k$ stored points closest to it and lets them decide.

Because nothing is fitted in advance, K-NN is called a lazy or instance-based method: all of the work happens at prediction time. It is also non-parametric. The model is the training data itself, so with enough data it can follow a decision boundary of any shape.

1. for each training point $x_i$, compute $d(x, x_i)$
2. $N \leftarrow$ indices of the $k$ smallest distances
3. if classifying, return the most common label among $y_i$ for $i \in N$
4. else return the mean $\frac{1}{k} \sum_{i \in N} y_i$

Measuring distance

A K-NN model is only as good as its distance. For vectors $x, z \in \mathbb{R}^D$ the common choices are:

scikit-learn uses Minkowski with $p = 2$ by default. metric="cosine" also works; scikit-learn then searches by brute force.

Scale your features

Data Processing covers other normalization methods.

Choosing k

The value of $k$ trades variance against bias.

• Small $k$ follows individual training points, noisy ones included. The boundary is jagged, and $k = 1$ scores 100% on the training set because every point is its own nearest neighbor.
• Large $k$ averages over a wide region, so the boundary is smooth but can miss real structure. At $k = n$, every query gets the most common class in the whole training set.

In practice:

• With two classes, an odd $k$ avoids tied votes.
• weights="distance" weights each neighbor by $1/d(x, x_i)$, so closer neighbors count for more. The result is usually less sensitive to the exact $k$.
• Choose $k$ with cross-validation, never with the test set. Trying every $k$ from 1 to 30 is cheap on small datasets.

Cost in time and memory

Training only stores the data. Brute-force prediction compares the query with all $n$ training points in $D$ dimensions, which costs $O(nD)$ time per query and $O(nD)$ memory for the stored set. For the 60,000 MNIST training images of 784 pixels, that is about 47 million subtractions for every test image.

Two ways to search faster:

• KD-trees and ball trees split space so that whole regions can be skipped. They are fast for fewer than about 20 dimensions and lose their advantage as $D$ grows. With algorithm="auto", scikit-learn chooses for you.
• Approximate nearest neighbor libraries such as FAISS give up a little accuracy for much faster search. This is how search over millions of embeddings works in practice.

The curse of dimensionality

In high dimensions, distances stop being informative: the nearest and the farthest points from a query end up almost equally far away. The table measures this for 1,000 points drawn uniformly from the unit cube $[0, 1]^D$, averaged over 200 random queries.

As the ratio approaches 1, "nearest" means less and less. Reduce the dimension first with PCA, or run K-NN on learned embeddings, where distance reflects meaning. Real data usually lies near a much lower-dimensional structure than uniform noise, which is part of why K-NN still does reasonably well on 784-pixel digits.

In scikit-learn

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
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())
param_grid = {
    "kneighborsclassifier__n_neighbors": range(1, 31),
    "kneighborsclassifier__weights": ["uniform", "distance"],
}
search = GridSearchCV(model, param_grid, cv=5)
search.fit(X_train, y_train)
print(search.best_params_)
print("test accuracy:", search.score(X_test, y_test))

make_pipeline names each step after its class in lowercase, which is where the kneighborsclassifier__ prefix comes from. Because the scaler is inside the pipeline, every cross-validation fold fits it on that fold's training part only. Hyperparameter Tuning explains grid search in more depth. For regression, use KNeighborsRegressor in the same way.

Parameters

From scratch in NumPy

Writing K-NN yourself takes a few lines and shows exactly what the library computes.

import numpy as np

def knn_predict(X_train, y_train, X_query, k=5):
    # Squared distance from every query to every training point, shape (q, n)
    d2 = ((X_query[:, None, :] - X_train[None, :, :]) ** 2).sum(axis=2)
    # Indices of the k smallest distances in each row, in no particular order
    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, it makes the same predictions as KNeighborsClassifier(algorithm="brute") for all 30 test points. A few details:

• The square root is skipped because it doesn't change which points are closest.
• np.argpartition finds the $k$ smallest values in $O(n)$ per row, faster than a full $O(n \log n)$ sort.
• np.bincount(row).argmax() needs integer labels $0, 1, 2, \dots$ and breaks ties toward the smaller label.
• Broadcasting builds a $(q, n, D)$ array. For large inputs, use $\lVert x - z \rVert^2 = \lVert x \rVert^2 + \lVert z \rVert^2 - 2x^\top z$ with one matrix product, which needs only a $(q, n)$ array.

K-NN in olympiad tasks

K-NN rarely wins a task on raw features, but it is useful in two ways.

As a baseline. It takes a minute to write and has one hyperparameter that really matters. Its validation score tells you how much a heavier model has to beat to be worth the time.

On top of embeddings. A pretrained network maps images, text or audio to vectors where similar inputs lie close together. K-NN on those vectors gives a classifier with no training, and supporting a new class only means adding its examples.

Reach for K-NN when the dataset is small, the features are few or come from a good embedding, and you need a working model quickly. Avoid it on many raw features, or when the training set is too large to scan for every query within the time limit.