Interactive demo · Statistical Learning: Theory and Methods · Chapter 2

Least squares versus k-nearest neighbours on the mixture data

Two hundred training points, 100 BLUE and 100 ORANGE, simulated from a known model: each class is an equal mixture of ten Gaussian clusters N(mk, I/5). Code the class as Y = 0 or 1, fit either a linear regression or a k-nearest-neighbour average, and classify as ORANGE where the fitted value exceeds 0.5 (rule 2.7). Least squares gives a rigid straight boundary; k-NN gives a boundary that becomes more ragged as k falls, with a training error that reaches 0 at k = 1. Only an independent test set (here 10,000 points from the same model) shows which k predicts well, and how close it gets to the Bayes rule, which knows the 20 cluster centres.

Classifier

Number of neighbours k

Bayes decision boundary

Try these

Training data: the book's simulated mixture (file ESL.mixture.rda from the book's website). Test data: 5,000 points per class simulated from the same model and rounded to 4 decimals. Distances are Euclidean; ties in distance go to the lower-numbered training point, and a vote of exactly 0.5 (even k) is classified BLUE, as in (2.7). The Bayes rate is the integral of min(fBLUE, fORANGE)/2 over the plane.

In the lecture notes