Earlier notes treated classification as choosing a rule that maps a feature vector to a label, and distances as a way to measure how far apart two observations are. The -nearest-neighbor (kNN) classifier connects these ideas directly. To label a new point, it finds the training observations closest to it and lets them vote.
The idea is simple, and that is why the details deserve care. A kNN rule depends on the training sample, the distance, the value of , the order in which tied distances are resolved, the way tied votes are resolved, and every preprocessing step applied to the features. If any of these is left unspecified, "the kNN prediction" may not be a single well-defined label. This note fixes all of these choices before any prediction is made. It then examines what the classifier does and does not guarantee.
Motivation
Suppose the label of an observation tends to resemble the labels of observations with similar features. Then a reasonable guess for a new point is the label most common among nearby training points. kNN makes no parametric assumption about the shape of the decision boundary. The boundary is whatever the local votes produce.
This flexibility has a cost. The rule is only as meaningful as the notion of "nearby," and "nearby" is decided by the distance and the feature scales, not by the labels. Also, a vote among a handful of neighbors is a noisy summary. It is not automatically a probability.
The rule, stated precisely
Fix a finite training sample with and . The index is the observation's original position in the sample. Fix an integer with and a distance on . Unless stated otherwise, is the Euclidean distance .
Definition 5.5.1
(kNN classifier with fixed tie rules)
For a query point :
- Compute for .
- Sort the indices lexicographically by the pair . Smaller distance comes first. Among equal distances, the smaller original index comes first. Call the sorted order .
- The neighbor set is .
- The neighbor score is
- The prediction is if , and if .
Step 5 breaks an equal vote in favor of class . An equal vote can only happen when is even. Other conventions are legitimate, such as favoring class , or falling back to the nearest neighbors. What matters is that the convention is chosen before any test label is examined and is applied the same way everywhere.
Two kinds of tie must be kept apart.
- A vote tie means . Choosing odd rules this out.
- A distance tie means several training points share the same distance from . If such a group straddles position , the neighbor set depends on how the tie is ordered. An odd does nothing to prevent this.
Theorem 5.5.2
(Determinism and the two extreme values of )
Fix the training sample, the distance, , and the tie rules above.
(a) For each query , the prediction is a single, uniquely determined label.
(b) If , then is the global majority label for every , with class chosen when exactly half of the labels are .
(c) Let and let be a training point. Suppose every training point located exactly at has label . Then . Without this condition the conclusion can fail.
Proof
(Why each part holds)
(a) The pairs are all distinct, because their second coordinates are distinct. Lexicographic order on distinct pairs is a strict total order, so is unique. Therefore , , and the thresholded label are unique.
(b) When , the neighbor set is every index, whatever is. So equals the overall fraction of labels. The threshold rule then gives the stated majority, including the tie to .
(c) Query at . Every training point at location has distance , and every other point has positive distance. So is the smallest index among the points located at . By hypothesis that point has label . If two points share a location but carry different labels, the lowest-index training point among all points at that location supplies the prediction for both. At least one of the two conflicting labels is then misclassified, as the last exercise shows.
Part (a) is a statement about determinism only. For a fixed sample and a fixed query, the output is fixed. Nothing about the score is calibrated just because the rule is well defined.
A worked example in one dimension
Worked example 5.5.3
(Five training points on the line)
The training sample, listed by index, is
| index | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
Query . The distances are . Sorting by gives the order . With the neighbor set is , and all three labels are . So and .
Query . The distances are . Indices and are tied at distance . With , the index rule puts index first, so . If the tie had been broken toward the larger index, the prediction would have been . The data and the distance alone do not determine a unique 1NN decision at . The tie rule is part of the classifier.
Same query, . The full sorted order is , because indices and are tied at distance . The third slot falls inside that tie. The index rule selects index , giving labels , so and the prediction is . A larger-index rule would select index , giving labels and prediction . Here is odd, so no vote tie is possible, yet the prediction still depends on how the distance tie is broken.
. Three of the five labels are , so every query, including , is labeled . The local information that points near have label has been discarded.
Distances, scales, and features
Monotone transformations. Replacing by , where is strictly increasing, preserves every comparison and every equality . So the sorted order and all predictions are unchanged. This is why squared Euclidean distance can be used in place of Euclidean distance. Similarly, a strictly increasing transformation of the score preserves the ranking of queries by score. A decision threshold, however, must be transformed along with the score.
Feature rescaling is different. Multiplying one coordinate by a constant changes the geometry itself, and it can reorder neighbors.
Counterexample mode
Rescaling one feature flips the nearest neighbor
Take the query , a class- training point , and a class- training point . The squared distances from the query are and , so 1NN predicts class .
Now multiply the first coordinate by . The class- point becomes , and the query is unchanged. The squared distances become and , so 1NN predicts class .
Quick check
(In the rescaling counterexample, does multiplying **both** coordinates by change the 1NN prediction?)
Compare how the two distances change.
Solution · Answer
No. Uniform scaling by multiplies every distance by , which is a strictly increasing transformation of , so the order is preserved: the squared distances become and , and 1NN still predicts class . Only rescaling one coordinate relative to the others changes the geometry.
Measuring a feature in different units, or standardizing it, is therefore a modeling decision. Standardization is not neutral bookkeeping.
Irrelevant features. A coordinate unrelated to the label still contributes to every distance. If its spread is comparable to or larger than that of the informative coordinates, it can reorder neighbors essentially at random. In that case predictions move toward a vote among arbitrary training points.
Other metrics. The Manhattan distance or a weighted Euclidean distance encode different judgments about which differences matter. No metric is correct independently of the problem. Comparing metrics is a choice to be made by validation.
Worked example 5.5.4
(Euclidean and Manhattan distance disagree)
Take the query , a class- point and a class- point . In Euclidean distance, , so 1NN predicts class . In Manhattan distance, is at and at , so 1NN predicts class . Euclidean distance favors a point whose difference is spread over two coordinates; Manhattan distance charges each coordinate in full. Neither answer is wrong; they are different classifiers.
High dimension. For example, if all coordinates across the query and a fixed finite number of training points are mutually independent standard Gaussian variables, their distances become relatively concentrated as grows: the ratio of farthest to nearest approaches in probability. In that regime the relative distance contrast shrinks. This is a property of particular distributions, not a theorem about all high-dimensional data. Data concentrated near a low-dimensional structure can behave much better.
Computation
Exact brute-force kNN for a single query proceeds as follows:
- Computing all distances costs .
- Fully sorting the records costs . A selection algorithm can find the first records in expected time, provided it respects the same lexicographic order.
- Tallying the votes costs .
- The algorithm stores the training data, which takes memory, plus distance–index records in this full-sort implementation.
Tree-based or hashing indices can reduce query time. Their gains depend on the dimension and on how the data are spread, and they can degrade toward brute-force cost. Approximate search trades exactness for speed. Its output may differ from the exact rule defined above, so it is a different classifier.
Weighted kNN replaces equal votes with weights such as . This weight is undefined when , so a convention must be stated. One such convention: if any neighbor has distance , only the zero-distance neighbors vote, with equal weight.
Worked example 5.5.5
(Weighting can flip the vote, and needs a zero-distance rule)
Take training points with labels and . At the query the distances are . The unweighted score is , so the prediction is . With weights , the weighted share of class is , so the prediction is .
At the query the first weight would be . Under the convention above only index votes, and the prediction is . Without a stated convention the weighted rule is undefined exactly at training points, the boundary case where a prediction is most likely to be checked.
A finite-sample noise counterexample
It is tempting to argue as follows: 1NN fits every training point, so it must perform well. The next result shows this inference is invalid, even in the simplest possible setting.
Theorem 5.5.6
(1NN error under pure label noise)
Let almost surely, and let with . Let the training pairs , with , be iid copies of . Let the query be an independent copy. Then 1NN with the index tie rule has test error
whereas the Bayes error, attained by the better constant classifier, is .
Proof
(Computing both errors)
Every feature value equals , so all distances are . The index rule therefore selects index regardless of the data, and the prediction is .
The query label is independent of , and both are Bernoulli. Hence
Because carries no information, the best classifier is a constant. Predicting errs with probability , and predicting errs with probability . So the Bayes error is .
Write and . Then , since . Equality holds only at .
Proof X-ray
Where the independence enters
The degenerate feature does one job: it makes every distance , so the index rule picks index whatever the labels are. The prediction is then a fixed function of the training data, chosen before any label is seen.
The independence of the query from the training sample does the rest. It turns into a product computation. If the query were instead one of the training points, say itself, the same rule would have error ; this is exactly the gap between fitting the training set and predicting a new case.
The hypothesis is what makes the comparison informative: both errors are positive, and the inequality is strict unless . At or both errors are .
At , 1NN errs with probability , while the Bayes error is .
Quick check
(With almost surely and , compute the 1NN risk and the Bayes risk.)
Use the theorem with .
Solution · Answer
The 1NN risk is . The best constant predicts and errs with probability , so 1NN is worse by .
Two lessons follow. First, a prediction at a training point is not a prediction at an independent query. In this example every training prediction equals , so the classifier fits the training set exactly when all training labels agree; it need not fit when . Second, small does not imply small test error. This result says nothing for or against the asymptotic behavior of kNN under other assumptions. It is a single, exact, finite-sample case.
How affects the fit. Larger averages over more labels. This reduces sensitivity to individual noisy labels but blurs the boundary. No deterministic finite-sample guarantee says that accuracy improves, or worsens, monotonically in . The extreme ignores the features entirely, as the worked example showed.
Misconception repair: the score is not a proven probability
Common mistake
(Reading four of five neighbors as probability 0.8)
"If 4 of my 5 neighbors are class 1, then ." This conclusion does not follow. The score takes values only in . It depends on the tie rules and the scaling, and it is computed from a finite sample.
In the noise example with , every score is or , while the true conditional probability is everywhere. A score can be useful for ranking. Before reading it as a probability, assess calibration on held-out data, for example by grouping held-out cases by score and comparing each group's average score with its observed frequency of label . Such an assessment is evidence about calibration, not a proof of it.
Validation without leakage
Choosing , the metric, or the features is model selection, and it must follow the same discipline as any other model selection:
- Learn every data-dependent preprocessing step on the training folds only. This includes scaling means and standard deviations, imputation values, and feature selection. Then apply the learned transformation to the held-out rows.
- Keep a final test set untouched until all choices are fixed.
- Random iid splitting assumes the rows are exchangeable. Clustered data, such as repeated records from the same individual, require group-aware splits. Time-ordered data require splits that respect time. Under distribution shift, validation performance may not transfer to the deployment population.
Common mistake
(Standardizing once before leave-one-out)
Fitting the scaler or imputer on all rows and then running leave-one-out lets each held-out row influence its own preprocessing. Remove the held-out observation before fitting any preprocessing, and refit the scaler and the imputer on the remaining rows for each held-out case.
Exercises
Exercise 5.5.7
(For the worked dataset, find the 2NN prediction at the query , and discuss alternative vote-tie policies.)
Foundation
Solution(3)
- 1
Apply the stated rule
The sorted order begins , both at distance . The labels are and , so , which maps to class .
- 2
Compare other vote-tie policies
A rule favoring class would predict . A rule falling back to neighbor would use index and predict . A rule expanding to neighbors meets the distance tie between indices and from the worked example, so it also depends on the distance tie rule.
- 3
Conclude
Each policy is defensible, and different policies can yield different classifiers. The choice must be fixed in advance.
Exercise 5.5.8
(The training data are and , with and the index tie rule. Find the training predictions and the leave-one-out predictions, and discuss leakage.)
Core
Solution(4)
- 1
Compute the training predictions
At , indices and are both at distance , and index comes first, so both duplicate rows are predicted and row is misfit. No 1NN rule can fit two rows that share a location but have different labels. At the prediction is . The training error is .
- 2
Compute the leave-one-out predictions
Key step
Holding out row , index is at distance and predicts ; the truth is . Holding out row , index predicts ; the truth is . Holding out row , indices and tie at distance , index wins and predicts ; the truth is . The leave-one-out error is .
- 3
Check the preprocessing
Each leave-one-out step must refit any standardizer or imputer without the held-out row. With one feature, a positive rescaling does not change neighbor order. When row is held out, however, the remaining values have standard deviation , so the standardizer needs an explicitly stated rule for that case.
- 4
Discuss duplicates
If rows and are two records of the same patient, a random split can place one record in training and the other in the held-out set. The evaluation then measures recall of that patient, not generalization to new patients. Grouping all records of a patient into the same fold prevents this particular overlap.
Related notes
- Classification rules and misclassification risk
- Distances and feature standardization
- Cross-validation and held-out testing
- Calibration of classification scores