Interactive demo · Applied Statistical Learning in R and Python · Chapter 2

The Bayes classifier and K-nearest neighbours

Two hundred training points, 100 blue and 100 orange, come from a known distribution, so the Bayes classifier (assign each point to its most probable class) and its error rate can be computed exactly. K-nearest neighbours does not know the distribution: it estimates Pr(Y = orange | X = x0) by the fraction of orange points among the K training points nearest to x0 (2.12). Click anywhere on the left plot to see the neighbourhood of that point. Small K gives a ragged, overfitted boundary; large K an over-smooth one; the test error (5,000 new points) is smallest in between, close to the Bayes error rate.

Data

Classifier

Number of neighbours K

Bayes decision boundary

Try these

Each class is an equal mixture of ten Gaussian clusters N(mk, 0.2I) with known centres, and the two classes are equally likely, so Pr(orange | x) = forange(x) / (fblue(x) + forange(x)). The Bayes error rate (2.11) is the integral of min(fblue, forange)/2. Distances are Euclidean; ties in distance go to the lower-numbered training point, and a vote of exactly one half goes to the class of the nearest neighbour.

In the lecture notes