Why Choose k with Validation Error?
In k-nearest-neighbor (KNN) learning, the neighborhood size \(k\) determines how many training observations contribute to a prediction. A small \(k\) can respond closely to individual training points; a larger \(k\) averages over a broader neighborhood. The earlier material on bias and variance explains why neither extreme is automatically best. The choice should be guided by performance on observations not used to fit the predictions.
A validation error curve plots a chosen prediction-error measure against candidate values of \(k\). The curve need not decrease or increase steadily: the observed errors depend on the validation data, and changing \(k\) changes which neighbors contribute. The practical task is to select a value using a rule decided in advance, rather than to infer that one \(k\) must be best for every new sample.
For regression, write the observed validation response as \(y_i\) and its prediction at a candidate neighborhood size \(k\) as \(\hat{y}_i(k)\). For binary or multi-class classification, write the observed class as \(c_i\) and the predicted class as \(\hat{c}_i(k)\). The corresponding error measures are:
Here \(\mathbf{1}\{\cdot\}\) equals 1 when the stated condition holds and 0 otherwise. MSE penalizes larger numerical prediction errors more heavily; misclassification rate counts each incorrect class prediction once. Other loss measures can be appropriate, but candidates should be compared using the same measure on the same validation observations.
What Validation Error Estimates
Suppose a training sample has been used to construct a prediction rule \(\hat{f}\), and a separate validation sample consists of \(n_{\mathrm{val}}\) independent observations from the target population. For a loss function \(L\), the average validation loss is an estimate of the expected loss of that fitted rule on a new observation. This is the generalization error conditional on the training sample.
The justification is direct. Conditional on the training data, \(\hat{f}\) is fixed. If each validation observation has the same distribution as a future observation and is independent of the fitted rule, each validation loss has conditional expectation \(R(\hat{f})\). By linearity of expectation, the expectation of their average is also \(R(\hat{f})\). Thus the validation average estimates the target prediction loss; its realized value can still differ because the validation sample is finite.
This argument depends on a representative validation sample and a prediction rule fitted without using its responses. If observations are dependent, or if the validation data come from a different population or time period, the average may not estimate performance in the intended setting. The split or resampling design must reflect how predictions will actually be used.
Training error is different: it is measured on observations used to construct the prediction rule. It can be substantially smaller than error on new observations. In particular, if a training observation is allowed to be its own neighbor, a \(k=1\) training prediction can reproduce its response or class exactly. That result does not establish good performance on new cases. Validation error is the relevant measure for tuning \(k\), provided the validation set has not been used to fit the predictions.
A Practical Selection Procedure
A straightforward procedure is to specify a candidate set of neighborhood sizes, fit or evaluate the KNN rule at each candidate, and compute the same validation loss for each. Select the \(k\) with the smallest observed error if the instruction is to minimize validation error. If a problem provides a tie-breaking rule or a rule for near-ties, apply that rule exactly. Do not substitute a preferred rule after seeing which candidate it favors.
Choose allowable values of \(k\) and the measure to optimize, such as regression MSE or classification misclassification rate.
Use the same validation observations and the same loss definition for every candidate.
Choose the minimum-error candidate, or use the specified tie-breaking or near-tie rule.
Repeatedly choosing among candidates based on the same validation set can adapt the model to noise in that set. A test set reserved until after tuning provides a less selection-affected final assessment.
Worked Examples
Worked Example: Choosing k by Regression MSE
A hypothetical insurer uses KNN regression to predict claim severity, measured in thousands of dollars. Four validation claims have observed severities of 100, 120, 140, and 160. The predictions from three candidate neighborhood sizes are shown below. Select \(k\) by validation MSE.
| Observed severity | Prediction, \(k=1\) | Prediction, \(k=3\) | Prediction, \(k=5\) |
|---|---|---|---|
| 100 | 90 | 105 | 110 |
| 120 | 130 | 115 | 120 |
| 140 | 150 | 145 | 130 |
| 160 | 140 | 155 | 150 |
Method. For each \(k\), subtract the prediction from the observed value, square each residual, add the squares, and divide by four.
For \(k=1\), the residuals are \(100-90=10\), \(120-130=-10\), \(140-150=-10\), and \(160-140=20\). The squared residuals are \(100,100,100,400\), so \[ \operatorname{MSE}_{\mathrm{val}}(1)=\frac{100+100+100+400}{4}=175. \]
For \(k=3\), the residuals are \(-5,5,-5,5\). Each squared residual is 25, giving \[ \operatorname{MSE}_{\mathrm{val}}(3)=\frac{25+25+25+25}{4}=25. \]
For \(k=5\), the residuals are \(-10,0,10,10\). The squared residuals are \(100,0,100,100\), giving \[ \operatorname{MSE}_{\mathrm{val}}(5)=\frac{100+0+100+100}{4}=75. \]
The errors are \(175\), \(25\), and \(75\), in squared thousands of dollars. The smallest is 25, so choose \(k=3\). The check is that the four \(k=3\) predictions are each only 5 thousand dollars from their observed values, consistent with its lower MSE. Common mistake avoided: choosing \(k=1\) because it may fit training observations closely; the selection here is based on validation error, not training error.
Worked Example: Training Error Does Not Decide k
A hypothetical roadside-assistance program classifies service requests as either urgent or routine. There are eight training observations and six separate validation observations. The following table gives the number of incorrect classifications on each set for three candidate values of \(k\). Select \(k\) using validation misclassification rate.
| \(k\) | Training errors out of 8 | Validation errors out of 6 |
|---|---|---|
| 1 | 0 | 3 |
| 3 | 2 | 1 |
| 5 | 3 | 1 |
Method. Divide each validation error count by six. For \(k=1\), the rate is \(3/6=0.5000\). For \(k=3\), it is \(1/6=0.1667\). For \(k=5\), it is also \(1/6=0.1667\). Thus \(k=3\) and \(k=5\) tie for the smallest observed validation error.
The training error rates are \(0/8=0.0000\), \(2/8=0.2500\), and \(3/8=0.3750\), respectively. Those values do not change the validation-based result: \(k=1\) has the lowest training error but the highest validation error. Suppose the stated tie-breaking rule is to choose the smaller \(k\). Then choose \(k=3\). The check is that both tied candidates make exactly one error among the same six validation cases, while \(k=1\) makes three. Common mistake avoided: selecting \(k=1\) from its zero training errors, which describe fit to the training set rather than performance on separate cases.
Worked Example: Applying the One-Standard-Error Rule
A hypothetical benefits administrator compares three KNN classifiers using five validation folds. The table gives the misclassification rate in each fold. Apply this stated rule: find the candidate with the lowest mean fold error, calculate its standard error across folds, and choose the largest candidate \(k\) whose mean error is no more than one such standard error above the minimum mean.
| Fold | Error for \(k=3\) | Error for \(k=5\) | Error for \(k=9\) |
|---|---|---|---|
| 1 | 0.20 | 0.10 | 0.20 |
| 2 | 0.10 | 0.20 | 0.10 |
| 3 | 0.20 | 0.10 | 0.20 |
| 4 | 0.30 | 0.20 | 0.20 |
| 5 | 0.20 | 0.20 | 0.20 |
Step 1: Calculate the fold means. For \(k=3\), the sum is \(0.20+0.10+0.20+0.30+0.20=1.00\), so the mean is \(1.00/5=0.20\). For \(k=5\), the sum is \(0.80\), so the mean is \(0.80/5=0.16\). For \(k=9\), the sum is \(0.90\), so the mean is \(0.90/5=0.18\). The minimum mean is 0.16, achieved by \(k=5\).
Step 2: Calculate the standard error for the minimum-mean candidate. The five errors for \(k=5\) are \(0.10,0.20,0.10,0.20,0.20\), with mean \(0.16\). Their deviations from the mean are \(-0.06,0.04,-0.06,0.04,0.04\). The sum of squared deviations is \[ 0.0036+0.0016+0.0036+0.0016+0.0016=0.012. \] The sample variance is \(0.012/(5-1)=0.003\), the sample standard deviation is \(\sqrt{0.003}=0.05477\), and the standard error is \(0.05477/\sqrt{5}=0.02449\).
Step 3: Apply the threshold. One standard error above the minimum mean is \(0.16+0.02449=0.18449\). The mean for \(k=3\), 0.20, exceeds the threshold. The mean for \(k=9\), 0.18, is within it, as is the minimum-mean candidate \(k=5\). The largest eligible candidate is therefore \(k=9\). The check is \(0.18\le 0.18449\), while \(0.20>0.18449\). Common mistake avoided: choosing the minimum-mean candidate automatically; the stated one-standard-error rule instead chooses the largest \(k\) within the specified threshold. This rule is a selection convention, not proof that the candidates have equal true prediction error.
Interpreting a Validation-Error Curve
The minimum on a validation curve is the best observed candidate under the chosen loss and validation sample. It is not a guarantee that the selected \(k\) has the smallest true generalization error. With few validation observations, a small difference between candidates may reflect sampling variability. If results are close, use the rule specified for the problem. A common convention is the one-standard-error rule illustrated above: it favors a smoother, larger neighborhood among candidates whose estimated errors are sufficiently close. Use that convention only when it is requested or adopted as the analysis rule.
A single validation split can also give a result that depends on which observations happened to be held out. Cross-validation addresses this by evaluating candidates across several folds and summarizing their errors. Fold means make the comparison less dependent on one split, though fold results are not fully independent because training sets overlap. A standard error computed from folds is therefore commonly used as a practical selection summary, not as an exact confidence bound.
Finally, if many choices—including many \(k\) values—are repeatedly compared on one validation set, the selected value can partly reflect random features of that set. Keep a final test set out of this selection process when an unbiased final assessment is needed. After selecting \(k\), a modeling workflow may refit the chosen rule using the available training and validation observations, then evaluate it once on the untouched test set.
Check Your Understanding
For each problem, use the stated loss and selection rule. Answers are given so you can check your calculations.
- A regression model has validation responses \(8,10,12\). For \(k=2\), its predictions are \(7,12,11\); for \(k=4\), they are \(8,11,10\). Calculate each validation MSE and choose the smaller-MSE candidate. (Answer: \(\operatorname{MSE}_{\mathrm{val}}(2)=2\), \(\operatorname{MSE}_{\mathrm{val}}(4)=5/3\approx1.6667\); choose \(k=4\).)
- A classifier makes 5, 3, and 4 errors on the same 12 validation observations for \(k=1,3,7\), respectively. Calculate the three misclassification rates and select the minimum. (Answer: \(0.4167, 0.2500, 0.3333\); choose \(k=3\).)
- A regression analysis reports training MSEs of 0.5, 1.0, and 1.5 and validation MSEs of 4.0, 2.0, and 2.2 for \(k=1,3,5\), respectively. Which value should be selected by minimum validation MSE, and why not select by training MSE? (Answer: Choose \(k=3\), with validation MSE 2.0; \(k=1\)'s lower training MSE does not make it the best validation candidate.)
- The minimum cross-validation mean error is 0.12 with standard error 0.03. Candidate mean errors for \(k=3,5,9\) are 0.14, 0.15, and 0.18. Under the rule “choose the largest \(k\) with mean error no greater than one standard error above the minimum,” which \(k\) is selected? (Answer: The threshold is \(0.12+0.03=0.15\); \(k=3\) and \(k=5\) qualify, so choose \(k=5\).)
- Two candidates have identical validation misclassification counts: \(k=2\) makes 3 errors among 20 observations, and \(k=6\) also makes 3 errors among 20. If the prespecified tie rule is to choose the larger \(k\), report both rates and the selection. (Answer: Both rates are \(3/20=0.1500\); choose \(k=6\).)