KNN (K-Nearest Neighbours) in machine learning

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

KNN (K-Nearest Neighbours), in more detail

KNN does no learning at all, in the usual sense.

It just keeps the training data and looks things up later.

To predict, it finds the closest examples and copies their answer.

That makes training instant and prediction slow.

Every prediction has to measure the distance to every stored point.

The value of k controls how smooth the result comes out.

A k of one follows every wrinkle in the data, including the noise.

A large k smooths everything and can wash out real detail.

Distance means nothing unless your features are on the same scale.

Salary in the thousands will drown out age completely if you skip scaling.

It also struggles as the number of columns grows.

With many columns everything ends up roughly the same distance apart.

It has no model to inspect, so it explains nothing by itself.

But it can show you which neighbours it used, which is its own kind of answer.

It is a fair baseline on small, well-scaled data with few columns.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath KNN (K-Nearest Neighbours)

There is no training

k-NN stores the training set and does all of its work at prediction time.

d(\mathbf{x}, \mathbf{x}') = \sqrt{\sum_{i=1}^{d} (x_i - x'_i)^2}

$\mathbf{x}$ : the point being predicted.
$\mathbf{x}'$ : one stored training point.
$d$ : the number of features.

Every stored point is measured against the query, the $k$ smallest distances win, and those $k$ neighbours decide the answer.

The vote, and the average

\hat{y} = \arg\max_{c} \sum_{i \in N_k(\mathbf{x})} \mathbf{1}[y_i = c]

$N_k(\mathbf{x})$ : the indices of the $k$ nearest stored points.
$\mathbf{1}[\cdot]$ : 1 when the condition holds and 0 when it does not.

For classification the most common label among the neighbours wins.

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

For regression it is their mean instead, and the only thing that changed is what you do with the neighbours once you have them.

One prediction, in order

Compute the distance from the query to every stored training point.
Sort those distances and keep the smallest $k$ .
Read the labels of those $k$ points.
Take the majority label, or the mean value.
Discard everything and start again for the next query.

What $k$ actually controls

$k = 1$ draws a boundary that passes between every pair of differently labelled points, so the training error is zero and the variance is enormous.

Raising $k$ averages more neighbours together, which smooths the boundary, lowers the variance and raises the bias.

k \approx \sqrt{n}

The usual starting point is the square root of the training size, taken as an odd number so a two-class vote cannot tie.

The honest answer is cross-validation, because the right $k$ depends on how much the classes overlap and nothing else predicts that.

The three costs nobody mentions first

O(nd)

Each prediction touches all $n$ stored points across all $d$ features, so the model gets slower as the data grows rather than faster.

The whole training set is the model, so memory scales with the data too.

Distance is measured in the units of the features, so an unscaled column measured in thousands drowns out every column measured in fractions.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

Why is KNN slow at prediction time?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →