What happens to a k-NN classifier's decision boundary as k grows from 1 toward the training-set size?
answer
- one voter versus every voter
- jagged at the small end
- noise becomes its own island
- at k equal to n the input stops mattering
- training accuracy would always choose one
basics
~20 sThe boundary starts jagged and grows smoother. At k=1 it wraps around individual points, including mislabelled ones; as k rises each prediction averages more neighbours, so the boundary flattens until, at k equal to the training-set size, every query gets the majority class.
solid answer
~50 sk is the smoothing dial. At `k=1` each prediction copies one stored point, so the boundary encloses individual examples and every noisy label carves out its own island — training accuracy looks perfect while test accuracy suffers, because the model has memorised rather than generalised. Raising k makes each prediction a vote over a wider neighbourhood, so single odd points get outvoted and the boundary straightens. Push k far enough and the neighbourhood stops being local: at k equal to the number of training points, the vote returns the overall majority class for every query and the input is ignored entirely. Sweeping k from 1 to 25 on a bearing-vibration wear detector shows exactly this arc — a speckled boundary at 1, a stable one somewhere in the middle, and an over-smoothed one that erases small wear pockets by 25. So low k means high variance and low bias, high k the reverse, and k is chosen on held-out data.
go deeper
Recall the direction and be able to say it without hesitating: small k gives a jagged, noise-sensitive boundary, large k gives a smooth one. Know that k is chosen by you, not learned from the data.
Explain the mechanism, not just the direction: at k=1 each point owns a region, so a mislabelled example becomes its own island; at k equal to the training-set size the vote returns the global majority for every query.
Demonstrate that you retune k when the data changes — a value tuned on a small sample is a different amount of smoothing once the set is ten times denser — and that you never let training accuracy select it.
Frame k as a policy choice about which errors you are willing to buy: smoothing away rare local pockets is often invisible in aggregate accuracy while being exactly the failure that matters to the business owning the rare cases.
## k is the only smoothing control the method has Once the distance function is fixed, `k` is the sole knob that changes how a k-NN classifier behaves. It sets how many stored examples get to speak for each query, and therefore how local the prediction is. ## The k=1 end: maximally local With `k = 1` the prediction is the label of the single closest stored point. Geometrically, the training points partition the input space into cells, each cell containing the region closer to that point than to any other, and the decision boundary is the union of the cell walls between points of different classes. Three consequences: - **Training accuracy is (essentially) perfect.** If you score the model on the training set, each point retrieves *itself* as its nearest neighbour, so it predicts its own label. The only exceptions are identical feature vectors carrying conflicting labels. This perfect score measures nothing about generalisation. - **Every mislabelled point becomes a region.** One vibration reading recorded as "wear" when the bearing was fine creates a small island of "wear" predictions around it. The model cannot tell a real minority pocket from a recording error, because a single point is enough to create either. - **Predictions are unstable.** Refit on a slightly different sample and the boundary moves substantially. That instability under resampling is what "high variance" means here. ## The k=n end: maximally global At the other extreme, if `k` equals the number of training points, every query retrieves the entire training set. The tally is then the same for every query — the global class counts — so the model returns the overall majority class no matter what the input is. There is no boundary left at all; the prediction surface is one flat region. That is the extreme of "high bias": the model has a fixed, simple story it tells regardless of the data in front of it. ## The arc in between Between those extremes each increment of k widens the neighbourhood and lets more points outvote any one of them. Sweeping k from 1 to 25 on a bearing-vibration sensor labelling wear versus no-wear traces the whole arc: - `k = 1`: the wear region is speckled; isolated no-wear readings sit inside it as holes. - `k = 5` to `k = 9`: the speckles are voted away; the boundary follows the real transition zone in vibration amplitude. - `k = 25`: the boundary has straightened past the point of usefulness — a small but genuine wear pocket that only ever contains a handful of readings can no longer win a vote of 25, so it disappears from the predictions entirely. The direction of the trade is worth memorising precisely, because interviewers reverse it to see if you flinch: **small k means the model is sensitive to individual points (high variance, low bias); large k means it is insensitive to local structure (low variance, high bias).** ## How k interacts with the data, not just the model The right k is not a constant you can carry between problems. - **Sample size.** With a few hundred points, `k = 25` is a large fraction of any local region; with a million, it is a tight neighbourhood. What matters is how much of the input space the k nearest points span, not the number itself. - **Noise level.** Noisier labels reward larger k, because voting is exactly the mechanism that averages label noise out. - **Class geometry.** If the useful structure is small clusters, large k destroys it. If classes are broad and well separated, large k costs almost nothing and buys stability. - **Ties.** An even k in a two-class problem admits exact splits; an odd k removes those but does nothing for three-way ties in multi-class problems. ## Choosing it k is a hyperparameter, so it is chosen by measuring performance on data the vote did not see — held-out or cross-validated folds — and never by training accuracy, which always favours `k = 1` and would pick it every time. A practical habit is to sweep an odd-numbered grid over a range wide enough that performance clearly worsens at both ends: if the best value sits at the edge of your grid, the grid was too narrow. And because k counts neighbours, retuning it is mandatory whenever the training set changes size substantially — the same k spans a different amount of space in a set ten times larger.
- Why is training accuracy useless for choosing k?Because k=1 wins it automatically: each training point is its own nearest neighbour, so it predicts its own label and scores near 100%. That score reflects memorisation, not generalisation. k must be selected on data the vote did not see — a held-out split or cross-validated folds — and the value that wins there is usually well above 1.
- Your training set grows tenfold. Should you keep the same k?No — retune it. k counts neighbours, but what matters is how much of the input space those neighbours span. In a set ten times denser, the same k covers a much smaller region, so the model becomes more local and more variance-prone than it was. The previously tuned value is no longer the same amount of smoothing.
- Why do practitioners often prefer an odd k in a two-class problem?An odd number of voters cannot split evenly between two classes, so exact ties are impossible and no tie-breaking rule is exercised. It is a convenience, not a correctness requirement, and it does not generalise: with three or more classes an odd k can still tie, as six neighbours splitting 2/2/2 across three classes shows.
saying these in an interview costs you the question
- Says a larger k always improves the model
- Claims k=1 underfits because it uses too little data
- Picks k by training accuracy
- Thinks k is learned during fitting rather than chosen
- Assumes a k tuned on one dataset transfers to another size