K-nearest neighbours (KNN)
"To guess for someone new, look at the K most similar people you already know and go with the majority." That's the whole model.
Question type: classification here. The same idea does regression in week 2 (KNN regression) and comes back as a classifier in week 3.
Weeks: 1, 2 and 3.
Book: ISLP 2.2.3 (second half, “K-Nearest Neighbors”). Also 4.7 lab mentions it.
Techniques on this page: distance, neighbourhood vote, choosing \(K\), normalising features.
The problem it solves
The Bayes classifier is perfect, but it needs the true chance of each category, which we never know. KNN is the simplest possible way to estimate those chances from data: the chance of “default” for this person is roughly the fraction of similar people who defaulted.
It assumes no shape for the rule (it’s non-parametric), so it can follow any pattern, however curvy. That flexibility is also its weakness: it needs a lot of data, and you have to choose how many neighbours to listen to.
The idea in everyday words
You move to a new street and want to guess whether your neighbours recycle. You look at the 5 nearest houses: 4 have recycling bins out. Your guess: probably yes, with a “chance” of 4/5.
Words you’ll hear
| Word | Plain meaning |
|---|---|
| \(K\) | how many neighbours you look at. You choose it. |
| neighbours, \(\mathcal{N}_{x_0}\) | the \(K\) training points closest to the new point \(x_0\). The curly N is just a name for that group. |
| Euclidean distance | ordinary straight-line distance, like with a ruler |
| non-parametric | doesn’t assume any shape for the rule; just uses the data directly |
| flexible | able to bend to follow the data closely |
| overfitting | bending so much it follows the luck, not the pattern |
Technique 1: measuring distance
Problem it solves: “closest” needs a definition when there are several inputs.
For two points, square the difference in each input, add them up, and take the square root (Pythagoras):
\[\text{distance}(x, x_0) = \sqrt{(x_1 - x_{01})^2 + (x_2 - x_{02})^2 + \dots + (x_p - x_{0p})^2}\]
With one input it’s just \(|x - x_0|\) (the gap, ignoring sign). The week 3 lab skips the square root because it doesn’t change which points are closest.
From \((1, 1)\) to \((0, 0)\): \(\sqrt{1^2 + 1^2} = \sqrt2 \approx 1.41\). From \((1,1)\) to \((3, 0)\): \(\sqrt{2^2 + 1^2} = \sqrt5 \approx 2.24\).
Technique 2: the neighbourhood vote
Problem it solves: turning the neighbours into a chance for each category, and then a decision.
- Find the \(K\) training points closest to the new point \(x_0\).
- The estimated chance of category \(k\) is the fraction of those neighbours in category \(k\): \[\tilde P(Y = k \mid X = x_0) = \frac{1}{K}\sum_{\text{neighbours}} \mathbb{1}(y = k)\] The sum with the indicator \(\mathbb 1\) just counts neighbours in category \(k\). Dividing by \(K\) turns the count into a fraction.
- Pick the category with the biggest fraction (the Bayes classifier rule, using these estimates).
Slide typo: slide equation (33) leaves out the \(\frac1K\). Without it you get a count, not a chance. The book (eq. 2.12) and the slide’s own worked example (\(\tfrac13\), \(\tfrac23\)) include it.
Worked example (one input).
| \(x\) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(y\) | A | A | B | B | B | A |
New point \(x_0 = 3.4\). Gaps: \(x{=}3\): 0.4, \(x{=}4\): 0.6, \(x{=}2\): 1.4, \(x{=}5\): 1.6, \(x{=}1\): 2.4, \(x{=}6\): 2.6.
- \(K = 1\): nearest is \(x = 3\) (B). Predict B.
- \(K = 3\): B, B, A. Chance of B is \(2/3\). Predict B.
- \(K = 5\): B, B, A, B, A. Chance of B is \(3/5\). Predict B.
- \(K = 6\): everyone, 3 A and 3 B: a tie. That’s why odd \(K\) is preferred with two categories.
Technique 3: choosing \(K\) (the bendiness dial)
Problem it solves: KNN has no numbers to fit, but it has one setting, \(K\), and it decides everything.
- Small \(K\) (like 1): very bendy. The boundary between categories is jagged and chases individual points. Training error is zero for \(K = 1\) (each training point’s nearest neighbour is itself), but that’s memorising, not learning. Low bias, high variance.
- Large \(K\) (like 100): very smooth, nearly a straight boundary. It ignores real local patterns. High bias, low variance.
- In between (the slides show \(K = 10\)): can get very close to the Bayes classifier.
If you plot error against \(1/K\) (so more bendy is to the right), training error keeps falling, but test error falls and then rises again: the U shape from the big picture. The best \(K\) is at the bottom of the U. You choose it with a validation set (week 2), never with training error.
Technique 4: normalising features (put inputs on the same scale)
Problem it solves: distance adds up raw differences, so an input measured in big units drowns out the others.
House age ranges 0 to 100 years; number of rooms ranges 3 to 9. Without fixing this, “nearest” is almost entirely about age. The fix is to rescale each input to have average 0 and spread 1 (subtract the column’s mean, divide by its standard deviation). The week 2 lab’s normalize() does exactly this.
Strengths and weaknesses
| Good at | Bad at |
|---|---|
| any shape of boundary, however curvy | needs lots of data |
| no assumptions | slow to predict (measures distance to every training point) |
| very easy to explain | many inputs make “nearby” meaningless (the curse of dimensionality) |
| tells you nothing about why (no coefficients to read) |
What to read in the book
| Section | Read? | Why |
|---|---|---|
| ISLP 2.2.3, “K-Nearest Neighbors” part, Figures 2.14 to 2.17 | Read | Exactly the slides: the \(K = 3\) picture, \(K = 10\) vs Bayes, \(K = 1\) vs \(K = 100\), the U-curve |
| 2.4 Exercise 7 | Do | KNN by hand, a perfect exam-style practice |
| 3.5 Comparison of linear regression with KNN | Week 2 | See KNN regression |
Practice prompt
I'm studying CS5100 Data Analysis (textbook ISLP, section 2.2.3). I want practice questions on K-NEAREST NEIGHBOURS (KNN) for classification:
- computing Euclidean distances by hand in 1D and 2D
- finding the K nearest neighbours of a test point from a small table
- estimating class probabilities as the fraction of neighbours in each class (with the 1/K)
- predicting the class for different K (1, 3, 5...), including ties
- how K controls flexibility: small K vs large K, bias vs variance, training error vs test error, the U-shaped test error curve
- why features should be normalised before KNN, with a numeric example
- when KNN is a good or bad choice
Please:
1. Use plain, everyday language and explain any technical term in one short sentence.
2. Give me ONE question at a time, easy first, then harder. Use small tables of 5-8 training points with friendly numbers.
3. Wait for my answer, then mark it and show the full working step by step.
4. If I get it wrong, explain what went wrong and give me a similar question.
5. Mix calculations with a few "explain why" questions.
6. Every 5 questions, summarise my strengths and what to practise.