k-NN skips training. It stores the training data, and when a new point arrives it finds the stored points nearest to it and takes a majority vote of their labels (or, for regression, an average of their values). It assumes only that nearby points tend to share a label. The design questions are which to use, how to measure "nearby", and how to avoid comparing against every stored point for every query.
After this you canInstance-based ("lazy") learning
Last week's models (perceptron, linear regression) learned something: a weight vector that summarizes the training data, after which the data could be thrown away. k-NN is the opposite. Its "model" is the training data itself. Nothing happens at training time; all the work happens when a query arrives. That's why it's called lazy or instance-based learning.
The professor's analogy is image retrieval: to find photos like a query photo, compare it with every photo in the database one by one and return the most similar. There's no model, just comparison. Any data works as long as it's a vector. A 100×100 grayscale image becomes a point in 10,000-dimensional space.
| Linear model (week 3) | k-NN | |
|---|---|---|
| Training | slow: fit the weights | instant: just store the data |
| Prediction | fast: one dot product | slow: compare with every stored point |
| What's kept | a few weights | the entire training set |
| Boundary shape | a straight line / plane | any shape the data suggests |
| Adding new data | retrain | append it; done (slide 28: "incremental") |
k-NN is also called non-parametric: there's no fixed set of parameters to estimate, so its complexity grows with the data. It still makes assumptions, just quieter ones: that the distance you chose reflects similarity, and that the labels change smoothly in space.
The lecture says "if your model is growing with your training data, it's called parametric", and the reverse for non-parametric. The standard definitions are the opposite. A parametric model has a fixed number of parameters no matter how much data you have (linear regression: weights). A non-parametric model grows with the data (k-NN stores all points). k-NN is non-parametric, as the slides correctly say.
The k-NN vote
- Compute the distance from the query to every training point.
- Keep the closest: .
- Predict the most common label among them.
- the set of possible labels
- 1 if , else 0 (Kronecker delta), so the sum counts votes for label
With labels this is just the sign of the sum: . That's the shortcut the professor wrote on slide 9.
Use an odd k for two classes so the vote can't tie. That trick only works for binary problems. The lecture's example (13:23): three classes, k = 5, and the votes split 2–2–1, so two classes tie for the win. Your code has to handle ties explicitly (Section 7). Also, k = 1 has its own name: the nearest-neighbor classifier.
Decision boundaries and Voronoi cells
For 1-NN, every training point "owns" the region of space that is closer to it than to any other point. These regions are Voronoi cells, and together they tile the plane (a Voronoi tessellation). The 1-NN decision boundary is made of the cell edges that separate points of different classes. Each edge lies exactly halfway between the two points it separates.
Unlike last week's linear classifiers, this boundary can take any shape. It bends around the data, which is the source of both k-NN's power and its tendency to overfit.
Choosing k
is a hyperparameter. This is exactly the example the professor used in week 2. It controls how smooth the boundary is:
| Small k (e.g. 1) | Large k | |
|---|---|---|
| Boundary | jagged, follows every point | smooth |
| Sensitivity | one noisy point changes answers | stable |
| Failure mode | overfitting | underfitting: at the extreme () every query gets the majority class. This gets worse with imbalanced data (the lecture's example: 10 positives, 100 negatives) |
How to pick it: the same way as any hyperparameter (week 2). Hold out validation data or cross-validate, try several k, and keep the one with the smallest validation error. For the 47 points above, leave-one-out cross-validation gives:
| k | 1 | 3 | 5 | 7 | 9 | 15 | 25 |
|---|---|---|---|---|---|---|---|
| Error | 0.191 | 0.085 | 0.128 | 0.106 | 0.106 | 0.085 | 0.106 |
k = 1 is clearly worst. Several larger values are close, which is typical, and the curve is noisy with this little data. A rule of thumb from slide 13 is (here ), but the professor says plainly (26:49) that "in practice this rule does not work well. Very often we're using cross-validation." For binary problems he suggests small odd values like 3, 5, 7 or 9.
Distance and feature scaling
"Nearest" depends entirely on how you measure distance. The common choices:
Which metric is best? "We don't know" (lecture, 28:15). The default is Euclidean. If performance matters, treat the metric as another hyperparameter and pick it with cross-validation, just like k.
, . The differences are 3 and 4.
Euclidean . Manhattan (walking city blocks). Chebyshev .
Scale your features
The slides mention this only briefly ("sensitive to extreme differences in a single attribute"), but in practice it's the most important k-NN detail. If one feature is measured in much bigger numbers than another, it takes over the distance.
Query: age 30, income $50,000. Neighbor A: age 31, $58,000. Neighbor B: age 55, $51,000.
Raw: , . So B is "nearest", even though B is 25 years older, because income differences in dollars swamp age differences in years.
Standardized (divide age by 10 years and income by $20,000, roughly each feature's spread): , . Now A is nearest, which matches intuition.
Fix: standardize each feature (subtract its mean, divide by its standard deviation) using the training data's statistics, and apply the same transformation to queries. Géron does this with StandardScaler throughout. Slide 15 also lists Mahalanobis distance, which does this scaling (and accounts for correlated features) using the data's covariance matrix. The professor notes it's mainly used in metric learning, and that for plain k-NN it's risky: if the training data doesn't represent the true distribution well, the estimated covariance is wrong and test performance suffers. Stick with standardized Euclidean by default.
Each digit is a 16×16 grayscale image = 256 features, one per pixel. Using Euclidean distance over raw pixels, 7-NN reaches about 95.2% accuracy, versus 95.8% for an SVM and 97.5% for humans (slide 16). That's remarkably close for a method with no training. (Modern deep networks exceed 99% on this task.)
k-NN regression
For a number instead of a class, replace the vote with an average of the neighbors' values:
Unweighted is the special case (slide 19). Weighting by lets closer neighbors count more. The same trick works for classification: weight each vote.
As the professor stresses (36:06), this is an illustration, not a guarantee: more neighbors or more data do not automatically bring the prediction closer to the truth, especially in high dimensions. Here k = 2 happens to beat k = 3.
Shalev-Shwartz & Ben-David (§19.1) write a weighted average with weights proportional to the distance itself. As printed, that gives farther neighbors more weight, the opposite of the intent. Use weights that decrease with distance, such as .
Ties and missing values
- Tied vote (e.g. 2–2 with k = 4): use odd k for two classes, or break the tie by a coin flip, by the class that's more common overall (the "prior"), or by the single nearest neighbor (fall back to 1-NN).
- Missing feature values: you can't compute a distance with a blank, so fill it in. A reasonable default is that feature's average over the dataset, which changes the distance as little as possible.
"Don't first pick your algorithm and then see your data. Look at your data first, then select the algorithm." If your data has lots of missing values or very high dimension, k-NN may simply be the wrong tool.
Making k-NN fast
Training costs nothing (), but each prediction compares the query against all training points, and each comparison costs for features. Then the smallest distances have to be picked out. The lecture worked this out on the slide (48:10): sorting all distances costs , so a query costs
and since usually (e.g. features vs. for a million points), the distance computation dominates: per query, paid at test time, which is the worst place to pay it. (A full sort isn't actually needed to get the top : a heap gives and quickselect . It doesn't change the conclusion.) The professor adds that in practice the distance matrix is computed in parallel on GPUs, so brute force is often fast enough. Two ways to cut the cost:
- Reduce D: keep fewer features (feature selection, or PCA in week 10).
- Reduce N: only compare against a short list of likely candidates, using one of the data structures below.
k-d trees (low-dimensional numeric data)
Split the data at the median along one coordinate, then split each half along another coordinate, and repeat. To answer a query, walk down the tree to the region containing the query, and check the points there first.
The full algorithm handles this by backtracking. After checking the leaf, it also visits any neighboring region that the current best-distance circle crosses. With backtracking the k-d tree is exact, and it typically takes about per query in low dimensions. If you check only the query's own leaf (the shortcut drawn on slide 24), the search is fast but approximate: it can miss the true nearest neighbor. That's what the slide means by "inexact: may miss neighbors".
Move the query to (6.5, 4). What does leaf-only search return, and what is the true nearest neighbor?
It still lands in the leaf {(7,2), (9,6)}: distances and , so the leaf answer is (7, 2).
But (5, 4) is only away, on the other side of x = 6. Leaf-only search gets it wrong; backtracking finds (5, 4) because the 2.06 circle crosses the x = 6 line.
k-d trees stop helping in high dimensions: with many features, the circle crosses almost every split and you end up checking most of the data anyway. The professor's guide: up to about 6 dimensions. A classic use is robotics, searching over a 6-degree-of-freedom pose (3 position + 3 rotation).
The lecture (49:44) describes k-d trees as always approximate: "the nearest neighbor is only found within the leaves". That's true of the leaf-only shortcut. Shalev-Shwartz & Ben-David (§19.3) and the standard algorithm add backtracking, which makes the search exact. If asked, give both: leaf-only is fast and approximate; with backtracking it's exact.
Inverted lists (sparse, high-dimensional data like text)
For each word, store the list of training documents that contain it, the way a search engine does. For a query, merge the lists for the words it contains. Only those documents can share any feature with it, so only those need a distance computed.
New email: "account review". The list for account is {D6} and the list for review is {D2, D6}, so the only candidates are D2 and D6 out of six emails. D6 ("review your account", ham) shares both words, so it's the nearest neighbor and the email is classified ham.
Slide 23 also mentions fingerprinting (and the textbook locality-sensitive hashing): compress each point to a short code so that similar points get similar codes. It's fast and works for dense data too, but it's approximate.
The curse of dimensionality
k-NN relies on neighbors being close. In many dimensions, nothing is close. Suppose your data fills a unit cube evenly and you want a neighborhood holding just 1% of it. In one dimension that's a sliver of width 0.01. In dimensions the cube you need has edge length :
So in high dimensions, the "nearest" neighbors are nearly as far away as everything else, and their labels say little about the query. Shalev-Shwartz & Ben-David make this precise: the training set size 1-NN needs can grow exponentially with . Irrelevant features make it worse, because each one adds noise to every distance. The practical cure is to reduce dimensionality before running k-NN (week 10).
The professor's caveat (53:32): high dimension alone doesn't doom k-NN. Handwritten digits have hundreds of pixel features, yet k-NN works because the real variation lives on a much smaller set of shapes that the training data covers well. What matters is whether your training data can cover the space you're querying.
The precise result (Cover & Hart 1967; SSBD §19.2): as the training set grows, 1-NN's error approaches at most twice the best achievable (Bayes) error. k-NN with growing slowly with approaches the Bayes error itself. Both are statements about unlimited data; with finite data in high dimensions, the curse above applies.
Cheat sheet
| Classify | majority label of the k nearest; with ±1 labels, |
| Regress | mean of the k nearest values; weighted: , |
| Small k | jagged boundary, overfits; large k: smooth, underfits; → always the majority class |
| Pick k | validation / cross-validation; odd k for 2 classes; rule of thumb |
| Euclidean / Manhattan / Chebyshev | / / |
| Hamming | number of categorical features that differ |
| Scaling | standardize features first, or the biggest-unit feature dominates |
| Cost | train ; predict per query |
| k-d tree | low-d numeric; exact with backtracking, approximate if leaf-only |
| Inverted list | sparse data (text); compare only to items sharing a nonzero feature |
| Curse of dim. | neighborhood edge for fraction ; needs exponentially more data |
| Asymptotics | 1-NN error → at most 2 × Bayes error |
Practice
Q1Why is k-NN called a "lazy" learner?
Q2The 5 nearest neighbors of a query, from closest to farthest, have labels +1, −1, −1, +1, +1. What does 3-NN predict?
Q3A training set has 600 cats and 400 dogs. What does k-NN with k = 1000 predict for every query?
Q4Why can't you choose k by picking the value with the lowest training error?
Q5What is the Manhattan distance between (1, 2) and (4, 6)?
Q6Features are house size (in square feet, ~500–5000) and number of bedrooms (1–6). What goes wrong with Euclidean k-NN on raw values?
Q7Brute-force k-NN with N training points and D features. Cost per prediction?
Q8Which speed-up suits k-NN on email text (thousands of word features, each email using a few dozen)?
Q9Data is spread evenly over the unit square (d = 2). What edge length must a square neighborhood have to contain 1% of the data?
Q10When does a k-d tree search return the exact nearest neighbor?
Problem 1: Training points (label in brackets): A(1,1)[+], B(2,1)[+], C(4,3)[−], D(5,4)[−], E(1,3)[−]. Classify the query (2,2) with 1-NN, 3-NN and 5-NN (Euclidean).
Distances from (2,2): A , B , C , D , E .
Order: B (1.00, +), then A and E tied at 1.41 (+ and −), then C (2.24, −), then D (3.61, −).
1-NN: B → +. 3-NN: B, A, E → 2 plus, 1 minus → +. 5-NN: everyone → 2 plus, 3 minus → −.
The A/E tie at distance 1.41 doesn't matter for k = 3, because both are included.
Problem 2: k-NN regression. Neighbors of a query are at distances 1, 2 and 4, with values 10, 20 and 40. Give the plain 3-NN prediction and the 1/distance-weighted one.
Plain: .
Weighted: weights . .
Weighting pulls the answer toward the closest neighbor's value (10).