k-NN makes a prediction from the k training points closest to the query: a majority vote for classification, an average for regression. There is no training step — the model is the data.

Store
Keep the (scaled) training data.
Measure
Compute the distance from the query to every training point.
Select
Take the k nearest.
Predict
Majority class (optionally distance-weighted) or mean target.

Distance	Formula	Notes
Euclidean (L2)	`√Σ(aᵢ − bᵢ)²`	Default (Minkowski with p = 2)
Manhattan (L1)	`Σ\|aᵢ − bᵢ\|`	Less dominated by one large difference
Minkowski	`(Σ\|aᵢ − bᵢ\|ᵖ)^(1/p)`	p = 1 Manhattan, p = 2 Euclidean
Cosine distance	`1 − a·b / (‖a‖‖b‖)`	Direction only — text and embeddings

Python

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

X = np.array([[1, 1], [2, 1], [1, 2], [6, 5], [7, 7], [6, 6]])
y = np.array(["red", "red", "red", "blue", "blue", "blue"])
query = np.array([3, 3])

d = np.sqrt(((X - query) ** 2).sum(axis=1))
nearest = np.argsort(d)[:3]
print(d.round(2))                  # [2.83 2.24 2.24 3.61 5.66 4.24]
print(nearest, y[nearest])         # [1 2 0] ['red' 'red' 'red'] ← vote: red wins
print(KNeighborsClassifier(n_neighbors=3).fit(X, y).predict([query]))   # ['red']

Choosing k

Small k → jagged boundary that follows noise (low bias, high variance); large k → over-smoothed (high bias). k = 1 always scores 100% on its own training data. Pick k by cross-validation, with the features scaled:

Python

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_breast_cancer(return_X_y=True)
scores = {k: cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k)), X, y, cv=5).mean()
          for k in (1, 3, 7, 15, 51, 151)}
print({k: round(float(s), 3) for k, s in scores.items()})   # {1: 0.954, 3: 0.96, 7: 0.97, 15: 0.961, 51: 0.951, 151: 0.912}

The curse of dimensionality

As the number of features grows, space becomes vast and empty. Distances between random points concentrate: the nearest and the farthest neighbour end up almost equally far away, so “nearest” stops meaning “similar”.

Python

import numpy as np

rng = np.random.default_rng(0)
def contrast(d, n=500):
    X = rng.uniform(size=(n, d))
    dist = np.linalg.norm(X - rng.uniform(size=d), axis=1)
    return round(float((dist.max() - dist.min()) / dist.min()), 2)     # relative gap farthest vs nearest

print([contrast(d) for d in (2, 10, 100, 1000)])   # [40.73, 4.65, 0.36, 0.11] ← shrinks toward 0 as dimensions grow

Another view: to capture a fraction r of uniformly spread data with a small cube around a point, the cube's side must be r^(1/d). For 1% of the data that is 0.01 of the range in 1-D, 0.63 in 10-D and 0.95 in 100-D — the “neighbourhood” spans almost the whole range of every feature.

Python

print([round(0.01 ** (1 / d), 2) for d in (1, 10, 100)])   # [0.01, 0.63, 0.95]

Distance-based methods (k-NN, k-means, RBF kernels) suffer most.
The data needed to cover the space grows exponentially with the dimension; models overfit more easily.
Fixes: feature selection, dimensionality reduction (PCA), more data, models that don't rely on raw distances (trees, linear models).
Real data usually lies near a lower-dimensional structure, which is why k-NN still works on, e.g., 64-pixel digits.

How does k affect the bias–variance trade-off in k-NN?

What is the curse of dimensionality?