K-Nearest Neighbors

Classify a point by majority vote of its neighbours and see the decision boundary change with k

Beginner

Dataset:

Neighbours (k)5

Distance

Tap to

Decision regionsTest points

Drag the diamond (the query point). Filled dots are training data; hollow rings are the held-out test set, which never votes.

Vote among the 5 nearest

Blue

Orange

Prediction: Blue

Training points: 126
Test points: 54
Train accuracy: 90%
Test accuracy: 80%

Accuracy vs k (70/30 split)

training accuracytest accuracy

k = 1 scores 100% on the training set (every point is its own nearest neighbour) but not on the test set. Best test accuracy here: k = 6. Tap the chart to set k.

How k-nearest neighbours works

KNN is a supervised classifier built on one idea: points that are close together usually share a label. To classify a new point, measure its distance to every training point, take the k closest, and let them vote. The most common label wins.

Because every location in the plane gets a vote, KNN implicitly draws a decision boundary. The value of k controls how wiggly that boundary is, and the right k is found by checking accuracy on data the model has not seen: the held-out test set.

Lazy learning

There is no training step. The model is the training set itself; all the work happens when you ask for a prediction.

Small k

k = 1 copies the label of the single closest point. Boundaries become jagged islands around every noisy point: overfitting.

Large k

Many voters smooth the boundary. Push k too far and the majority class swallows the minority: underfitting.

Distance metric

Euclidean distance measures a straight line; Manhattan adds up the axis steps. The neighbourhood is a circle or a diamond.

Key formulas

Distance metrics

Euclidean: d(p, q) = √((p₁ − q₁)² + (p₂ − q₂)²) Manhattan: d(p, q) = |p₁ − q₁| + |p₂ − q₂|

Majority vote

ŷ(x) = argmax_c Σ_{i ∈ Nₖ(x)} 𝟙[yᵢ = c]

Nₖ(x): the k training points nearest to x
𝟙[·]: 1 when the condition holds, otherwise 0

Practical tips

Use an odd k for two classes to avoid ties. Scale features first: if one feature is measured in thousands and another in fractions, the large one decides every distance on its own.

The curse of dimensionality

In high dimensions all points end up roughly the same distance apart, so "nearest" stops meaning much. KNN works best with a modest number of meaningful features.

How to use this visualizer

1
Drag the diamond around. The k nearest training points are circled and their votes appear in the tally.
2
Move the k slider. At k = 1 the regions break into islands around single noisy points; larger k smooths them out.
3
Switch between Euclidean and Manhattan and watch the neighbourhood change from a circle to a diamond.
4
Choose "Add blue" (or another class) under "Tap to" and tap the plot to add labelled training points.
5
Read the accuracy chart: training accuracy is highest at k = 1, but test accuracy usually peaks at a moderate k.

KNN in code

Python

import numpy as np
from collections import Counter

def knn_predict(X_train, y_train, x, k=5, metric="euclidean"):
    diff = X_train - x
    if metric == "euclidean":
        d = np.sqrt((diff ** 2).sum(axis=1))
    else:                                   # manhattan
        d = np.abs(diff).sum(axis=1)
    nearest = np.argsort(d)[:k]
    votes = Counter(y_train[nearest])
    return votes.most_common(1)[0][0]

Complexity

Time complexity

O(n · d) per query

Training is free. Each prediction measures the distance to all n training points in d dimensions, plus O(n) to select the k smallest. KD-trees or approximate search speed this up.

Space complexity

O(n · d)

The whole training set has to be stored and kept around for predictions.

Practice problems

Problem 1: Classify by hand

Training points: A(1, 1) red, B(2, 1) red, C(4, 3) blue, D(5, 4) blue, E(3, 3) red. Classify q = (3, 2) with k = 3 using Euclidean distance, then again with Manhattan distance.

Show solution

Euclidean: A √5 ≈ 2.24, B √2 ≈ 1.41, C √2 ≈ 1.41, D √8 ≈ 2.83, E 1

3 nearest: E (red), B (red), C (blue) → 2 red, 1 blue

Manhattan: A 3, B 2, C 2, D 4, E 1

3 nearest: E (red), B (red), C (blue) → 2 red, 1 blue

Both metrics predict red.

Problem 2: Picking k

A KNN model scores: k = 1 → train 100%, test 78%; k = 7 → train 90%, test 88%; k = 51 → train 74%, test 73%. Which k would you pick, and what is happening at each end?

Show solution

k = 1: perfect on training data, much worse on test data → overfitting.

The model memorises noise: every mislabelled point gets its own island.

k = 51: train and test accuracy are both low and close together → underfitting.

The vote is so broad that it ignores local structure.

Pick k = 7: the highest test accuracy, with a small train/test gap.

Discussion

Questions, ideas or a different approach? Join the conversation.