Why Tune K-Nearest Neighbors?
K-nearest neighbors (KNN) predicts an outcome from observations that are close to a new predictor vector. Its two important tuning choices are the neighborhood size \(k\), the number of observations used, and the rule for weighting those observations. A small neighborhood can follow local patterns closely, but its predictions can change substantially when the training sample changes. A large neighborhood tends to smooth local variation, but can blur meaningful differences.
Cross-validation compares these choices using predictions for observations that were left out of the data used to fit each prediction. It helps estimate how well a setting will perform on new observations. It does not make the selected setting certain to be best in every future sample, and it does not replace a final evaluation on a separate test set.
Predictions and Cross-Validation
For regression, let \(N_k(\mathbf{x})\) denote the indices of the \(k\) nearest training observations to predictor vector \(\mathbf{x}\). Uniform KNN predicts their mean response. A common distance-weighting rule assigns weight \(w_j=1/d_j\), where \(d_j>0\) is the distance from \(\mathbf{x}\) to neighbor \(j\). The prediction is the weighted mean. If a neighbor has distance zero, the method needs a defined convention; one standard convention is to use only the exact-match observations and average their responses.
For classification, uniform KNN chooses the class with the largest count among the neighbors. Distance-weighted KNN instead sums the weights for each class and chooses the class with the largest total. If class totals tie, a tie-breaking rule must be specified in advance. The examples below have no tied class totals.
In \(M\)-fold cross-validation, divide the development data into \(M\) folds. For each fold, fit the prediction procedure using the other \(M-1\) folds and predict the held-out fold. Calculate the chosen error measure from these out-of-fold predictions. Average fold errors when folds have equal sizes; otherwise, calculate the overall error from all out-of-fold predictions, or weight fold errors by their sizes. Repeat this calculation for each candidate combination of \(k\) and weighting rule.
Here, \(n\) is the number of development observations, \(w\) identifies the weighting rule, \(m(i)\) is the fold containing observation \(i\), and \(\hat{f}_{-m(i),\,k,\,w}\) is fitted without that fold. For regression, a common loss is squared error, \(L(y,\hat{y})=(y-\hat{y})^2\). For classification, a common loss is zero-one error: zero for a correct class and one for an incorrect class.
Why Cross-Validation Uses Held-Out Predictions
The point of holding out a fold is to mimic prediction on observations that were not used to construct the model. If an observation is both included in the neighbor search and used to score that prediction, its own response can influence its prediction. In particular, a training observation is at distance zero from itself. Scoring that apparent self-match can make a setting look much more accurate than it is on new data.
A short derivation explains the weighted regression formula. For fixed neighbors and nonnegative weights with positive total, choose a constant prediction \(a\) to minimize the weighted squared error. Differentiate the objective with respect to \(a\), set the derivative to zero, and solve:
Thus, the weighted prediction is the local constant that minimizes weighted squared error over those neighbors. This justification is conditional on the selected neighbors and their weights; it does not establish that a particular \(k\) or weighting rule will predict well on new data. Cross-validation supplies evidence for that choice.
Worked Examples: Comparing Classification Settings
Worked Example: Selecting a Classification Neighborhood
A hypothetical risk-screening study records five development observations with a single, already scaled predictor \(x\) and a binary class. Use leave-one-out cross-validation to compare \(k=1\) with uniform KNN, \(k=3\) with uniform KNN, and \(k=3\) with inverse-distance weights \(w=1/d\). Choose the setting with the lowest cross-validation classification error.
| \(x\) | Class |
|---|---|
| 0 | A |
| 1 | A |
| 2.1 | B |
| 4 | B |
| 6 | B |
Method. Leave out each observation in turn, predict its class using only the other four, and count incorrect predictions. There are five held-out predictions, so each error rate is the number of errors divided by five.
For \(k=1\). The nearest-neighbor predictions, in order of held-out \(x=0,1,2.1,4,6\), are A, A, A, B, B. The observation at \(x=2.1\) is the only error: its nearest neighbor is \(x=1\), class A. The error rate is \(1/5=0.2000\).
For uniform \(k=3\). At \(x=0\), the three neighbors have classes A, B, B, so the prediction is B, an error. At \(x=1\), their classes are A, B, B, also an error. At \(x=2.1\), the three classes are A, A, B, so the prediction is A, an error. At \(x=4\) and \(x=6\), the three neighbors have a B majority, so both predictions are correct. The error rate is \(3/5=0.6000\).
For inverse-distance \(k=3\). At \(x=0\), the neighbors are \(x=1\) (A), \(x=2.1\) (B), and \(x=4\) (B). Their class weight totals are \(1\) for A and \(1/2.1+1/4=10/21+1/4=61/84\) for B. Since \(1>61/84\), predict A correctly. At \(x=1\), the neighbors are \(x=0\) (A), \(x=2.1\) (B), and \(x=4\) (B). The totals are \(1\) for A and \(1/1.1+1/3=10/11+1/3=41/33\) for B, so predict B incorrectly. At \(x=2.1\), the two nearest neighbors are both A; the next is \(x=4\), class B. The A total is \(1/1.1+1/2.1=10/11+10/21=320/231\), while the B total is \(1/1.9=10/19\). Since \(320/231>10/19\), predict A incorrectly. At \(x=4\) and \(x=6\), the weight totals favor B, so both predictions are correct. The error rate is \(2/5=0.4000\).
The lowest error rate among these candidates is \(0.2000\), for uniform \(k=1\). The method is leave-one-out cross-validation with zero-one loss. The common mistake this avoids is scoring an observation using a neighborhood that includes that same observation.
Worked Example: Tuning a Regression Neighborhood
Worked Example: Comparing Uniform and Weighted Regression
A hypothetical portfolio study has four development observations with a scaled one-dimensional predictor \(x\) and a numeric outcome \(y\). Use leave-one-out cross-validation to compare \(k=1\) uniform KNN, \(k=3\) uniform KNN, and \(k=3\) inverse-distance KNN. Select the setting with the lowest mean squared error (MSE).
| \(x\) | \(y\) |
|---|---|
| 0 | 0 |
| 1 | 4 |
| 3 | 10 |
| 4 | 10 |
For \(k=1\). Leaving out \(x=0\) predicts 4 from \(x=1\), giving squared error \((0-4)^2=16\). Leaving out \(x=1\) predicts 0 from \(x=0\), giving \((4-0)^2=16\). Leaving out \(x=3\) predicts 10 from \(x=4\), giving zero squared error. Leaving out \(x=4\) predicts 10 from \(x=3\), also giving zero. Thus, \(\mathrm{MSE}=(16+16+0+0)/4=8\).
For uniform \(k=3\). The held-out predictions are \(8\), \(20/3\), \(14/3\), and \(14/3\), respectively. The squared errors are \(64\), \(64/9\), \(256/9\), and \(256/9\). Therefore, \(\mathrm{MSE}=(64+64/9+256/9+256/9)/4=128/4=32\).
For inverse-distance \(k=3\). At \(x=0\), the three neighbors have distances \(1,3,4\) and responses \(4,10,10\). The prediction is \((4+10/3+10/4)/(1+1/3+1/4)=118/19\), so the squared error is \((118/19)^2=13924/361\). At \(x=1\), the distances are \(1,2,3\) and responses \(0,10,10\). The prediction is \((0+10/2+10/3)/(1+1/2+1/3)=50/11\), giving squared error \((50/11-4)^2=36/121\).
At \(x=3\), the distances are \(1,2,3\) and responses \(10,4,0\). The prediction is \((10+4/2+0/3)/(1+1/2+1/3)=72/11\), giving squared error \((72/11-10)^2=1444/121\). At \(x=4\), the distances are \(1,3,4\) and responses \(10,4,0\). The prediction is \((10+4/3+0/4)/(1+1/3+1/4)=136/19\), giving squared error \((136/19-10)^2=2916/361\). The MSE is \((13924/361+36/121+1444/121+2916/361)/4\), approximately \(14.7199\).
The MSEs are 8 for \(k=1\), 32 for uniform \(k=3\), and approximately 14.7199 for inverse-distance \(k=3\). Select \(k=1\) among these candidates. Weighting improves on uniform \(k=3\) here, but does not make it the best candidate. The method avoids the common mistake of assuming that a smoother, larger neighborhood must improve validation error.
Bias, Variance, and the Choice of \(k\)
A small \(k\) uses a narrow local neighborhood. It can respond to fine-scale patterns, which may reduce bias when the true relationship changes rapidly across predictor space. But each prediction depends on relatively few observations, so a small change in the training sample can change the selected neighbors or their responses. This sensitivity is associated with higher variance.
A large \(k\) averages over more observations. That averaging can make predictions less sensitive to individual observations, reducing variance, but it can also smooth over local structure, increasing bias. These are tendencies, not guarantees: the best setting depends on the data, the distance measure, the outcome, and the loss used for validation. Cross-validation compares predictive performance rather than selecting \(k\) from a rule of thumb.
| Choice | Typical effect | Possible consequence |
|---|---|---|
| Small \(k\) | More local, less smoothing | Lower bias but greater sensitivity to the sample |
| Large \(k\) | More averaging and smoothing | Lower variance but possible loss of local structure |
| Distance weighting | Gives nearer neighbors greater influence | Can help when close observations are more informative, but must be validated |
Worked Example: Keeping the Test Set Separate
Worked Example: Selecting a Classifier Before Final Testing
A hypothetical development sample of 80 independent records is evaluated with four equal folds. Three candidate classifiers produce the following numbers of incorrect predictions on each held-out fold. Choose a setting by cross-validation. A separate test set of 20 records is evaluated only after that choice.
| Candidate | Fold 1 errors | Fold 2 errors | Fold 3 errors | Fold 4 errors | Total errors |
|---|---|---|---|---|---|
| \(k=1\), uniform | 4 | 5 | 4 | 5 | 18 |
| \(k=5\), uniform | 3 | 4 | 4 | 3 | 14 |
| \(k=5\), inverse-distance | 2 | 3 | 4 | 3 | 12 |
Each candidate has 80 out-of-fold predictions. The cross-validation error rates are \(18/80=0.2250\), \(14/80=0.1750\), and \(12/80=0.1500\), respectively. Select inverse-distance \(k=5\), which has the smallest development cross-validation error.
After selection, refit that setting using all 80 development records. On the untouched test set, suppose the classifier correctly identifies 7 positive and 10 negative records, and incorrectly labels 2 positives as negative and 1 negative as positive. There are \(7+10=17\) correct classifications among \(7+10+2+1=20\) records, so test accuracy is \(17/20=0.8500\). The test result describes this final evaluation; it was not used to choose \(k\) or the weighting rule.
The method is to select by development cross-validation, refit on development data, and then evaluate once on the test set. The common mistake is to inspect test performance for several settings and choose the one with the best test result. That reuses the test set for tuning, so its reported performance no longer provides an independent final evaluation.
Preprocessing and Validation Design
KNN depends on distances, so the scale of the predictors can affect which observations count as neighbors. The earlier material on scaling addresses that issue. For valid cross-validation, any data-dependent preprocessing must be learned within each training fold and then applied to that fold's held-out observations. For example, if predictor means and standard deviations are estimated from data, estimate them without the held-out fold. Otherwise, information from held-out observations enters the fitting process before their predictions are scored.
The same principle applies when selecting \(k\) and a weighting rule: compare the planned candidate settings using the same folds and the same scoring rule. If observations are dependent over time, randomly assigning individual observations to folds can place future information in a training fold while scoring an earlier observation. In that setting, use a validation design that respects the time order, such as blocked or rolling-origin validation, rather than treating the observations as independent random cases.
Cross-validation error is an estimate of predictive error under the validation design and the data-generating conditions it represents. It may be variable, particularly with small samples, and selecting the lowest of many candidate scores can make that minimum optimistic. A separate test set helps assess the selected procedure after tuning; it should not be repeatedly consulted during selection.
Check Your Understanding
For each problem, distinguish the tuning calculation from any final evaluation.
- A regression study has 60 independent development observations and uses five equal folds. Candidate A has 18 total squared-error units across all 60 held-out predictions; candidate B has 15. What are their mean squared errors, and which has lower cross-validation error? (Answer: Candidate A has MSE \(18/60=0.3000\); candidate B has MSE \(15/60=0.2500\), so select B among these candidates.)
- For a classification prediction, three neighbors have distances 1, 2, and 4. The first and third belong to class R; the second belongs to class S. Under inverse-distance voting, what are the class weight totals and predicted class? (Answer: R has weight \(1+1/4=1.2500\), S has weight \(1/2=0.5000\), so predict R.)
- A regression prediction uses three neighbors with responses 2, 8, and 11 and distances 1, 2, and 4. Calculate the inverse-distance prediction. (Answer: \((2+8/2+11/4)/(1+1/2+1/4)=6.75/1.75=27/7\), approximately \(3.8571\).)
- A candidate has fold error rates 0.10, 0.20, and 0.25 on three equally sized folds. Calculate its mean cross-validation error. If another candidate has mean error 0.20, which has the lower score? (Answer: \((0.10+0.20+0.25)/3=0.1833\), so the first candidate has the lower score.)
- A team tunes \(k\) using cross-validation on its development sample, then tries four settings on the test set and reports the most accurate test result. What is the problem, and what is the correction? (Answer: The test set has been reused for selection, so the reported result is no longer an independent final evaluation. Select using development cross-validation, then evaluate the selected procedure on the test set once.)