k-NN Boundaries, Bias–Variance, and the Bayes Floor

Watch the decision boundary go from memorized to over-smoothed, with training error at zero the whole time it is useless.

Ch 5 5.3

Explorer

Supervised Learning

18 mindifficulty 3/5

Controls

Neighboursk1

k = 1 memorizes; large k averages the whole cloud.

Class geometry

Class overlapσ0.900

Sets the irreducible Bayes error.

Training sizen200

Boundary resolution40

Grid points per side used to paint the decision region.

Random seed

Every result on this page is a deterministic function of the seed and the controls.

Decision boundary

Background shading is the k-NN vote; points are the training sample.

class 0class 1

Error against model complexity

Training error at k = 1 is zero and tells you nothing.

training (resubstitution)held-out testBayes error

Test error

16.0%

400 fresh points

Resubstitution error

0.0%

the point is its own neighbour

Leave-one-out error

15.5%

honest use of the training data

Bayes error

9.1%

irreducible at this overlap

Best k on test

error 10.3%

Effective parameters

200

≈ n/k regions of the input space

Zero training error is not skill

At k = 1 every training point is its own nearest neighbour, so resubstitution error is exactly 0 for any data whatsoever — including pure noise. The leave-one-out and test readouts are the ones that carry information.

Predict before you look

A 1-nearest-neighbour classifier is fitted to 200 patients and misclassifies none of them. What does that tell you?

Scenarios

Teacher-ready starting points.

Documentation

What this shows

A two-class problem in the plane with three geometries, a k-NN classifier whose decision regions are painted on a grid, and three error estimates side by side: resubstitution, leave-one-out, and a fresh test set of 400 points. For the Gaussian geometry the Bayes error is computed numerically and drawn as a floor.

Neighbourhood averaging and the error decomposition

k-NN estimates P(Y = 1 | x) by the fraction of ones among the k nearest training points and predicts the majority. Small k gives a flexible, high-variance rule whose boundary follows individual observations; large k averages over a wide neighbourhood, which lowers variance but biases the estimate toward the overall class proportion.

The effective number of parameters is roughly n/k: the classifier partitions the space into about that many locally constant regions. Complexity therefore decreases as k grows, which is why the error curve is read right-to-left compared with a usual complexity axis.

No rule can beat the Bayes classifier, which predicts argmax P(Y = y | x). Its error rate is the integral of the smaller class-conditional density and depends only on the overlap of the classes. Extra data moves an estimator toward that floor; it never lowers it.

Resubstitution error at k = 1 is identically zero because each point retrieves itself, so it cannot discriminate a good rule from a memorizing one. Leave-one-out removes the point before voting and restores a usable estimate.

P̂(Y=1|x) = (1/k) Σ_{i ∈ N_k(x)} yᵢ

effective parameters ≈ n / k

E*_Bayes = ∫ min_y P(Y=y, x) dx

Try this

At k = 1 read resubstitution error and test error together, then explain the gap.
Increase k step by step and find the minimum of the test curve; compare with “Best k on test”.
Switch to XOR and set k = 70. Why does a smoother rule fail badly here?
On the Gaussian setting raise overlap to 2.5 and check that no k beats the Bayes line.
Fix k = 5 and raise n from 40 to 600: the boundary stabilizes but the error stops improving at the floor.

Common misconception

“My classifier got every training case right, so it will do well on new patients.”

A 1-nearest-neighbour rule achieves zero training error on any dataset, including randomly labelled noise, because each training point is its own nearest neighbour. Training error measures memorization capacity, not generalization. Only an estimate that never uses a case in its own prediction — leave-one-out, k-fold, or a held-out test set — measures the quantity you care about, and even that estimate is bounded below by the Bayes error implied by class overlap.

DSPA3 Chapter 5 — Supervised classification