Here the truth is known: X is uniform on the square and the class probabilities pk(x) wind round in a spiral, sharper for larger β. So the Bayes rate E* = E[1 − maxk pk(X)], the asymptotic 1-nearest-neighbour rate E1 = E[∑k pk(1 − pk)] and the Cover–Hart bound E*(2 − K E*/(K − 1)) are computed exactly, and every error shown is the expected test error 1 − ppredicted class(x) averaged over 2,000 test points. Change the training size N and watch the k-NN curve approach its limit.
Ties in the vote (possible with three classes) go to the tied class whose nearest member comes first. The bottom curve uses the same replicates and seeds for N = 25 to 6,400. The asymptotic k-NN curve (black) is drawn for two classes only.
code/ch13_prototypes_nearest_neighbors.py (spiral_probs, spiral_integrals, spiral_knn_errors, fig_13_s3).