From a neighborhood to a decision
A density estimator asks how much probability mass lies near a location. A classifier asks a different question: among observations near that location, how often is the label one? A local proportion can estimate a conditional class probability without specifying a finite-dimensional formula for it. This lets the decision boundary bend, but also makes the choice of distance, feature units and neighborhood size consequential.
Definition 25.1.1
(k-nearest-neighbor vote and decision)
Let , , be independent copies of with and . At a fixed query , order the sample by Euclidean distance to , breaking distance ties deterministically by index. For , let be the first indices and define
A vote tie is assigned to class one by convention; other fixed tie conventions are possible.
Here denotes a chosen version of the conditional probability; for the theorem we require that version to be continuous at the particular query. Under equal error costs, a Bayes decision is . With unequal costs the threshold changes: a local probability estimate and a decision rule are separate ingredients.
Worked example 25.1.2
(Three neighbors, then five)
Consider training pairs and query . With ties resolved by sample index, the distances in order are 1, 1, 2, 3, 4, giving labels . With , the estimate is and the equal-cost prediction is one. With , it is , again predicting one. If a false positive costs four times a false negative, the conditional risks of actions one and zero are and ; predict one only when . The same two estimates now give action zero. These fractions are local estimates, not guarantees that the true conditional probabilities equal them.
Why both neighborhood size and radius matter
If stays small, even nearby labels retain sampling noise. If stays large, the neighborhood need not shrink, and labels far from can introduce persistent bias. The following result makes both statements precise at one fixed query; it does not assert uniform convergence or rates.
Theorem 25.1.3
(Pointwise probability and excess-risk consistency)
Assume is continuous at and for every . If integer satisfies and , then in probability. Under zero-one loss, the conditional excess risk at of the random fitted decision also converges to zero in probability.
Proof
(Shrink the radius and average the label noise)
Fix and write . The number of training features in the ball is binomial with mean and variance . Since eventually , Chebyshev's inequality gives . Therefore the distance to the th neighbor converges to zero in probability.
Conditional on all training features, the labels are independent Bernoulli variables with means , almost surely. Put . Conditional variance of the vote is at most , so conditional Chebyshev yields in probability. Continuity at and imply in probability: on the event , every summand differs from by less than any prescribed tolerance for a suitable . Combining the two terms proves the first claim.
For a fixed training sample, the conditional error at of action one is and of action zero is . If the fitted action differs from a Bayes action, and lie on opposite sides of (ties cause no difficulty). Its excess conditional error is at most ; when the actions agree it is zero. The bound proves the second claim. This conditions on a fresh test label whose distribution at is the one defining .
Proof X-ray
Two separate sources of error
The radius argument controls how different nearby conditional means can be from the target. The variance argument controls random label fluctuations around those means. Neither alone is enough: local labels may be noisy, while an accurately averaged distant neighborhood may target the wrong probability.
Counterexample mode
One neighbor does not average away noise
Let every feature equal zero and let the labels be independent Bernoulli. At , the one-neighbor estimate is just the first label under the tie rule. For every , it is either zero or one and differs from by at least . It does not converge in probability to . Its expected classification error on an independent test label is , above the Bayes error .
Worked example 25.1.4
(Perfect training accuracy, zero leave-one-out accuracy)
Take four one-dimensional points with labels . With and the training point included, each point is its own nearest neighbor at distance zero, so training accuracy is . Now leave each point out in turn and classify it from the other three. Point has nearest remaining neighbor with label : wrong. Point has neighbors and at distance one, both labeled : wrong. Point has neighbors and , both labeled : wrong. Point has nearest neighbor with label : wrong. The leave-one-out accuracy is . With the leave-one-out estimates are for the points , giving predictions , and again every point is wrong. This labeling is deliberately anti-smooth, but it shows that training accuracy at carries no information about new cases.
Worked example 25.1.5
(Changing a unit changes the nearest neighbor)
Take two training points with label and with label , and the query . The Euclidean distances are to and to , so the one-neighbor rule predicts . Now measure the second coordinate in units ten times larger: , and the query . The distances become and , so the nearest neighbor is and the prediction is . The data are the same, but the rule has changed, because Euclidean distance depends on the units. Feature scaling is therefore part of the procedure and must be chosen using training data only.
Common mistake
(A good training vote is not a test guarantee)
With , a training observation is normally its own nearest neighbor, so training accuracy can look perfect even when predictions on new cases are poor. Select , feature scaling and any preprocessing using training folds only; assess the complete selection procedure on data held out from those choices.
Common mistake
(Larger k trades variance for bias)
A larger can reduce vote variance but blur a boundary. In high dimension neighborhoods can require much more data to become local, so the theorem is not a finite-sample performance promise.
Practice and solutions
Quick check
(At a query the five ordered labels are . Find the estimates and the equal-cost decisions for .)
Average the first labels.
Solution · Answer
The estimates are , and , so the respective decisions are zero, one and zero. A different can change the decision even for the same ordered data.
Quick check
(Let . Check the theorem's two requirements. What happens if ?)
Compute .
Solution · Answer
The square-root sequence tends to infinity and its ratio to tends to zero. For , the ratio is one; the neighborhood is the entire sample, so the shrinking-neighborhood argument does not apply.
Quick check
(Suppose and the fitted estimate is . Compute the conditional excess zero-one risk and compare it with the proof bound.)
Find the fitted action first.
Solution · Answer
The fitted action is zero and has conditional error ; the Bayes action is one with error . Excess error is , bounded by . This calculation concerns a fresh label at this fixed .