K-Nearest Neighbors (KNN) Interactive

Place labelled points, move the query star and watch K neighbours vote. Compare distance metrics, vote weights and K with a leave-one-out score.

Switch to 3D

Presets

Playback

Data

Classifier

Tools

Layers

Model check

The science

The algorithm

k-nearest neighbours has no training step: it stores the labelled points. To classify a query x it finds the K stored points with the smallest distance d(x, xi) and lets them vote: ŷ(x) = argmaxc Σi in NK(x) wi · [yi = c]. With uniform weights wi = 1; with inverse-distance weights wi = 1/(di + 0.001). A tie is broken in favour of the tied class that owns the nearest neighbour. The coloured map is this rule evaluated on a grid; its brightness is the vote share of the winning class.

Distances

Minkowski distance of order p: dp(a,b) = (Σj |sj(aj−bj)|p)1/p, where sj is the scale of feature j. p = 1 is Manhattan, p = 2 Euclidean, p → ∞ Chebyshev (largest coordinate difference). The yellow dashed outline is the set of points at exactly the K-th neighbour distance, so it has the shape of the unit ball of the chosen norm: a circle, a diamond or a square. Cosine distance 1 − a·b/(|a||b|) ignores length and compares directions seen from the origin; it is not a true metric (no triangle inequality), and its neighbourhood is a wedge between two rays.

Why K matters: bias and variance

K = 1 follows every point (low bias, high variance): the training accuracy is 100 % but the leave-one-out accuracy drops on noisy data. A large K averages many points (high bias): the boundary smooths out, and for K = N every query receives the majority class. The leave-one-out curve (green) classifies each point using all other points, so it is an honest estimate of generalisation without a separate test set; the purple dot marks the K with the best score. Its estimate is itself noisy on small data sets.

Feature scaling and dimension

Distances treat all features alike, so a feature with a larger numerical range dominates. The “Signal in x only” data set carries the class in feature 1 only; stretching feature 2 makes the useless coordinate dominate the distance and the accuracy collapses towards chance. In high dimensions all points become almost equally far apart (concentration of distances), so k-NN needs many more samples as dimension grows.

What is known theoretically

Cover and Hart (1967): as N → ∞ the error of 1-NN is at most 2 R*(1 − R*) where R* is the Bayes error, and for K → ∞ with K/N → 0 the error approaches R*. For two equal isotropic Gaussians at distance d apart with standard deviation σ, the Bayes accuracy is Φ(d / 2σ), which check 4 uses.

Honest simplifications

The data sets are synthetic and tiny (at most 400 points) and live in a square of side 2; no feature standardisation is applied unless you change the scale slider; the search is brute force, O(N) per query (real systems use k-d trees, ball trees or approximate indexes); the leave-one-out error shows which points the chosen K gets wrong but is not a confidence interval; the 3D page draws a horizontal slice of a 3-feature decision map, not the whole volume.

Checks run in the page

(1) Leave-one-out accuracy computed by the fast top-K insertion code equals a separate full-sort brute-force implementation. (2) With K = N and uniform votes, every query is assigned the majority class. (3) L1, L2, L-infinity and Minkowski distances satisfy the triangle inequality on 6000 random triples. (4) On a fixed two-Gaussian problem the measured accuracy of 25-NN on 3000 fresh points lies within 3 percentage points of the closed-form Bayes accuracy.

Accuracy against K: leave-one-out and training
Weighted votes for the query star
Distance to the 30 nearest points