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.
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.
code/ch02_statistical_learning.py (bayes_prob, bayes_error, knn_predict, knn_error_curve).