1. The idea from first principles
A classifier is a rule that takes a description of an object and returns a label. Some classifiers fit a compact model, such as a line, a tree or a table of probabilities. Basic brute-force nearest-neighbor classification instead retains the labeled examples and defers distance-based prediction until a query arrives. To label a new object, it finds the training objects closest under the chosen distance and lets them vote.
The method rests on a smoothness assumption: objects that are close together in feature space tend to share a label. When that assumption roughly holds for the chosen features, kNN can work well without fitting a fixed-dimensional parametric decision function. When it fails, kNN degrades. Typical causes are irrelevant features, badly scaled features, or too many features. Understanding these failures is a large part of understanding the method.
2. Setting and notation
We have a training set of labeled examples , with numeric features.
- Each is a vector of d numeric features, .
- Each is a class label from a finite set.
- A query is a new feature vector q whose label we want to predict.
- The integer k satisfies and is fixed in advance.
3. Euclidean distance
Similarity is measured by a distance. Throughout these notes we use Euclidean distance:
This is the straight-line length between two points: Pythagoras' theorem extended to d dimensions. Two facts are used repeatedly.
Proposition 3.4.1
(Squared distances give the same neighbor order)
For a fixed query and training points , if and only if . Ranking by squared distance therefore gives exactly the same order, ties included, as ranking by distance.
Proof
(Monotonicity of the square)
Distances are nonnegative and is strictly increasing on , so it preserves both and . Implementations can therefore skip the square root.
Second, each coordinate contributes the square of its difference. A feature with numerically large differences dominates the sum, whether or not it is more informative. This is the root of the scaling issue in the section on feature scaling.
4. The algorithm and its conventions
Definition 3.4.2
(k-nearest-neighbor prediction with tie conventions)
Given q and k:
- Compute for every training example i = 1, ..., n.
- Sort the examples by increasing distance.
- Distance-tie convention: if two examples are at exactly the same distance, the one with the smaller index i comes first.
- This makes the set of k nearest neighbors uniquely defined, even when a tie straddles the k-th position.
- Take the first k examples in this order. Each casts one vote for its own label (unweighted majority).
- Predict the label with the most votes.
- Vote-tie convention: if several labels share the highest vote count, choose the tied label whose closest selected neighbor is nearest to q.
- If that is still tied, choose the label that comes first in a fixed, stated label order (for example alphabetical).
Why odd k? With exactly two classes, an odd k makes a vote tie impossible, because an odd number of votes cannot split evenly. This is why odd values such as 1, 3 and 5 are common in two-class problems. Odd k has two limits:
- It does not remove distance ties, so step 2 still needs a rule.
- With three or more classes it does not remove vote ties either: 5 votes can split 2–2–1.
Counterexample mode
An odd k does not fix the prediction
A tempting claim is that with two classes and odd the prediction is determined by the data and the query alone. Take one feature, query , , and two training examples (R) and (B). Both are at distance 1, so the distances do not decide the single neighbor. The index rule picks example 1 and predicts R; listing the same two examples in the opposite order would predict B. An odd removes vote ties only; a distance tie straddling the -th position still needs the convention in step 2.
The rules above are conventions, not mathematical truths. Any deterministic rule is acceptable as long as it is stated before the computation and applied consistently.
Choosing k. The trade-off runs in both directions.
- Small k follows the training data closely and is sensitive to individual noisy points. With , the prediction copies the label of a single neighbor.
- Large k smooths the decision but can be swamped by the larger class or by distant points. With , every training label votes. If one label has the unique largest overall count, that label always wins; if the top vote counts tie, the stated nearest-neighbor tie rule can make the answer depend on the query.
Choose k using validation data drawn from the training portion, never the final test set.
5. Worked example
Worked example 3.4.3
(Nearest neighbors of a soil sample, and the effect of k)
A greenhouse project labels soil samples as R (needs re-watering) or B (fine). It uses two features that are already measured on comparable scales: = dryness index and = salt index.
| Index | Label | ||
|---|---|---|---|
| 1 | 1 | 2 | R |
| 2 | 2 | 1 | R |
| 3 | 4 | 4 | B |
| 4 | 5 | 3 | B |
| 5 | 3 | 5 | B |
| 6 | 2 | 3 | R |
The query is . We use , Euclidean distance and the conventions of the algorithm section.
Step 1: distances. For each example, subtract the query from the features, square each difference, add the squares, then take the square root.
| Index | Squared distance | Distance | Label | |
|---|---|---|---|---|
| 1 | (−2, −1) | 4 + 1 = 5 | R | |
| 2 | (−1, −2) | 1 + 4 = 5 | R | |
| 3 | (1, 1) | 1 + 1 = 2 | B | |
| 4 | (2, 0) | 4 + 0 = 4 | 2 | B |
| 5 | (0, 2) | 0 + 4 = 4 | 2 | B |
| 6 | (−1, 0) | 1 + 0 = 1 | 1 | R |
Step 2: order. The full ranking is:
6 (1), 3 (1.414), 4 (2), 5 (2), 1 (2.236), 2 (2.236).
There are two distance ties. Examples 4 and 5 are both at distance 2, so the index rule puts 4 before 5. Examples 1 and 2 are both at , so 1 comes before 2.
Step 3: select and vote. The three nearest examples are 6 (R), 3 (B) and 4 (B). The votes are B = 2, R = 1.
Step 4: predict. The prediction is B.
The third position involves a tie: examples 4 and 5 are both at distance 2, and only one of them fits within . Here both are labeled B, so the prediction does not depend on the tie rule. In general it can, which is exactly why the rule must be fixed in advance.
Varying k on the same ordering is instructive:
- : only example 6 is used, so the prediction is R. The single closest sample is a re-watering case.
- : examples 6, 3, 4, 5 and 1 are used (example 1 beats example 2 by index). The votes are B = 3, R = 2, so the prediction is B.
The prediction changes between and . They reflect different amounts of smoothing. Only held-out evidence can suggest which choice works better for this kind of data, and six points are far too few to settle the question.
Quick check
(With the soil data above, take query and . What does the stated rule predict?)
Solution · Answer
The squared distances to examples 1 to 6 are . The votes are R (examples 1, 2, 6) and B , a vote tie. The nearest selected R example is at squared distance 1, nearer than the nearest B example at 8, so the prediction is R.
6. How feature scaling changes distances
Euclidean distance adds squared differences across features as if one unit of every feature were equally important. When features are measured in different units, that is rarely true.
Worked example 3.4.4
(Raw and min–max distances select different neighbors)
Consider a phone-plan dataset with two features:
- = monthly data use in MB; in the training data it ranges from 0 to 1000.
- = number of customer-service calls; in the training data it ranges from 0 to 10.
Use the following complete four-customer training set and one query:
| Point | (MB) | (calls) | Label |
|---|---|---|---|
| P | 180 | 1 | S (stays) |
| Q | 260 | 8 | T (leaves) |
| U | 0 | 0 | S (stays) |
| V | 1000 | 10 | T (leaves) |
| query | 200 | 8 | ? |
Raw distances.
- To P: differences (20, 7), so 400 + 49 = 449 and the distance is .
- To Q: differences (60, 0), so 3600 + 0 = 3600 and the distance is 60.
- To U: squared distance .
- To V: squared distance .
All four training points have been checked; with the prediction is S. Data use decides the outcome here: Q’s 60 MB gap contributes 3,600 to its squared distance, greater than P’s entire squared distance of 449. The contribution depends on the units chosen for the two features.
Min–max scaled distances. Rescale each feature with the training minimum and maximum, using . Here that means becomes and becomes . The scaled points are , and .
- To P: differences (0.02, 0.7), so 0.0004 + 0.49 = 0.4904 and the distance is .
- To Q: differences (0.06, 0), so 0.0036 and the distance is 0.06.
- U and V scale to (0, 0) and (1, 1), respectively; each is at squared distance 0.68 from the query.
Among all four points, the nearest neighbor is Q and the prediction is T. Nothing about the customers changed; only the units in which differences are measured. Scaling is therefore not cosmetic: it is part of the definition of similarity.
Quick check
(In the phone-plan example, find the raw and the min–max scaled predictions for , taking the table order as the index order.)
Solution · Answer
Raw order is P, Q, U, V, so the neighbors P (S), Q (T), U (S) give S. Scaled squared distances are Q , P , and U and V both . The index rule takes U (S), so the vote is S , T and the prediction is S. Choosing V instead would predict T, so the tie rule matters here.
Two common choices are min–max scaling and standardization, . Each makes a modeling assumption. Min–max scaling, for example, gives an equal-sized scaled interval to each nonconstant feature. If a fitting set has zero range or zero standard deviation, the formula would divide by zero: define a policy in advance, such as dropping that feature in that fitting fold, and apply the same fitted policy to its validation data. A dropped feature cannot represent later variation. If domain knowledge says one feature matters more, express that deliberately, for instance with a feature weight, rather than leaving it to accidents of units.
7. Data leakage: fit preprocessing on training data only
Scaling has parameters: minima and maxima, or means and standard deviations. These parameters are learned from data, so they are part of the trained model. The rule is:
- Split the data into an outer training portion and a final test (holdout) portion first.
- For a validation split within the outer training portion, fit the scaler on the fitting subset only, then apply it unchanged to that subset and its validation subset. In cross-validation, repeat this separately for each fold. Every candidate k must be at most the number of examples in the smallest fitting fold, so that it is valid in every fold.
- Choose k using those validation results. Refit the scaler on the complete outer training portion, then apply that fitted scaler unchanged to the final test set and later queries.
Common mistake
(Fitting the scaler on the whole dataset before splitting)
Suppose instead you compute the minimum and maximum on the whole dataset before splitting. Then information about the test points has entered the model, because the test points helped decide how distances are measured. The resulting test accuracy no longer measures performance on genuinely unseen data, since genuinely unseen data could not have influenced the scaler. The effect may be small or large in a given case, but the evaluation is no longer honest.
This has two practical consequences.
- A test value may fall outside the training range, giving a scaled value below 0 or above 1. That is correct behavior; do not refit the scaler to fix it.
- The same rule applies to choosing k. If you try several values of k and keep the one with the best test score, the test set has been used for training. Choose k with a validation split or cross-validation inside the training data, refitting the scaler inside each fold. Then use the test set once, at the end.
Quick check
(A scaler is fitted on a training feature with minimum 10 and maximum 50. Scale a test value 60 and a training value 30. What would refitting with the test value included change?)
Solution · Answer
The scaled values are and . The value 1.25 is legitimate. Refitting with 60 included would change the range to and move the training value to , so test data would alter the geometry of training points.
8. Training and prediction costs
Model of computation. We assume the following:
- Brute-force kNN on a single processor.
- Each arithmetic operation and each comparison counts as one unit.
- n training examples, d features, k neighbors and m queries.
- Neighbors are ranked by squared Euclidean distance, so no square roots are taken.
Training. Plain kNN only stores the data. That needs memory and, beyond copying, essentially no computation. Fitting a min–max scaler adds two costs, so fitting is overall:
- Finding each feature's minimum and maximum takes about 2(n − 1) comparisons per feature.
- Transforming the stored data takes about 2nd operations (one subtraction and one division per value).
Prediction for one query. The cost has three parts.
- Distances. One squared distance needs d subtractions, d multiplications and additions, which is operations. For all training points that is .
- Selection. Finding the k smallest distances takes with a comparison sort, with a bounded heap, or expected time with an appropriate randomized selection algorithm. Compare
(distance, index)pairs when the index tie rule matters. - Voting. Counting the votes takes with constant-time label-indexed counters; tracking the nearest selected example per label also supports the stated vote-tie rule.
Proposition 3.4.5
(Brute-force prediction cost)
In the model above, one query costs operations for the squared distances, for selecting the smallest with a bounded heap, and for voting. The total is per query and for queries.
Proof
(Add the three stages)
The stages run in sequence, so their costs add. Each of the examples needs operations, and since the voting term is absorbed by the others. Queries are independent, so the single-query cost is multiplied by .
Worked example 3.4.6
(Counting distance operations)
With and , one squared distance needs operations, so one query needs distance operations and queries need . In the boundary case , a squared distance is one subtraction and one multiplication, operations, and the count for one query is . The value of does not enter the distance stage.
kNN reverses the usual pattern: training is cheap and prediction is expensive, because every prediction rescans the stored data. Index structures (k-d trees, ball trees) or approximate search can reduce prediction cost in low dimensions. They are not part of the basic method, and their effectiveness can decline as d grows, depending on the data and queries.
9. Variants that need their own rules
The method above uses unweighted majority voting. Two common variations change the rules and must be stated separately.
- Distance-weighted voting. Each neighbor's vote is weighted, often by 1/d. This needs its own convention for a neighbor at distance 0 (division by zero) and its own tie rule for equal weighted totals. Weighted results can differ from the unweighted results above, and the two should not be mixed.
- Unbalanced classes. When one class is much more common, it tends to dominate neighborhoods, so majority voting may rarely predict the minority class. Options include class-specific weights, resampling the training data, or, for a binary classifier, changing a threshold applied to the positive-class vote fraction. Each remedy defines a different classifier and must be specified explicitly.
10. Limitations
- Irrelevant features. Every feature contributes to the distance, so noise features dilute the useful ones.
- High dimensions. For some distributions and distance models, relative distances concentrate as d grows, making the nearest and farthest points less distinguishable. This is not universal: correlations and data geometry matter.
- Numeric features only, as stated. Categorical features need an encoding or a different distance.
- Limited explanation. kNN can show which examples were used, but it gives no compact summary of how features relate to labels.
11. Summary
For a fixed labeled training set and the unweighted voting rule specified above, kNN predicts by finding the k training examples closest to the query and taking a vote. Four further choices must be stated:
- the distance;
- the preprocessing;
- the value of k;
- the tie rules.
Fit any preprocessing on training data only, and choose k without touching the test set. Cheap training is paid for by expensive prediction.