A4.3.2 · Machine learning approaches
Classification
By the end you can
Explain how k-nearest neighbours and decision trees predict a category, work through their calculations, and use them for recommendations and diagnosis.
is supervised learning that predicts a category: spam or not spam, which species of flower, whether a patient is ill. This page covers the two methods the course names for it. One finds the most similar examples; the other asks a sequence of questions.
k-nearest neighbours#
The idea behind is that things which are alike tend to belong to the same class. To classify a new point:
- Measure how far it is from every training point, using √((x₂ − x₁)² + (y₂ − y₁)²), with one more squared term for each extra feature.
- Pick the k training points that are closest.
- Let them vote. The new point gets the class that most of them have.
There is no training step. The model is the stored data, so all the work happens at prediction time, and it gets slower as the data set grows.
A worked example#
Six fruits are described by sweetness (x) and crunchiness (y), both out of 10. A new fruit has sweetness 5.5 and crunchiness 4. Is it an apple or a banana? The distances, nearest first:
| Training fruit | Calculation | Distance | Class |
|---|---|---|---|
| (4, 2) | √((5.5 − 4)² + (4 − 2)²) | 2.50 | Banana |
| (3, 3) | √((5.5 − 3)² + (4 − 3)²) | 2.69 | Banana |
| (5, 1) | √((5.5 − 5)² + (4 − 1)²) | 3.04 | Banana |
| (7, 8) | √((5.5 − 7)² + (4 − 8)²) | 4.27 | Apple |
| (9, 7) | √((5.5 − 9)² + (4 − 7)²) | 4.61 | Apple |
| (8, 9) | √((5.5 − 8)² + (4 − 9)²) | 5.59 | Apple |
With k = 3 the nearest three are Banana (2.50), Banana (2.69), Banana (3.04): the vote is Banana 3, so the new fruit is a Banana. With k = 5 the vote is Banana 3, Apple 2 and the answer is still Banana, but it is closer. Using k = 6 would count every training point, so the result would be a tie and tell us nothing: the choice of k matters.
Click the plot to move the new point. Circles are class A, squares are class B. The shading shows what the model would predict at every position.
Votes
A: 2 B: 1
from the 3 nearest
Prediction
Class A
Nearest distance
0.78
farthest voter 1.27
With k = 1 the boundary bends around every odd point, including the two that sit in the wrong territory. With a very large k the vote is dominated by whichever class has more points nearby, and the boundary becomes too crude. Try k = 1, 5 and 27.
k-NN for recommendations#
Streaming services and shops use the same idea to recommend things. In , each person is described by the ratings they have given. To recommend a book to Ana, find the k readers whose ratings are closest to hers, then suggest books they loved that she has not read. (Item-based filtering turns it around: find items that are rated alike and suggest those.) The steps are to collect the ratings, tidy them (A4.2), find the neighbours, and generate the suggestions.
Decision trees#
A is a flowchart learned from data. Each internal node asks a yes/no question about one feature (“Revision hours ≤ 5.5?”), each branch is an answer, and each leaf is a predicted class. To classify a student, start at the top and answer the questions until you reach a leaf.
The training algorithm builds the tree by choosing, at each node, the question that separates the classes best. “Best” is measured by how pure the groups become. is 1 − the sum of the squared class proportions: 0 for a group that is all one class, 0.5 for an even split of two classes. (Some trees use entropy instead; the idea is the same.) The gain from a split is the parent's impurity minus the weighted average impurity of the two groups it creates.
For the sixteen students below, the parent group has a Gini of 0.492. The best first question is Revision hours a week ≤ 5.5? It sends 10 students one way (Gini 0.420) and 6 the other (Gini 0.000), so the gain is 0.230. No other single question removes more impurity.
| 1h 72% Fail | 2h 85% Fail | 2h 68% Fail | 3h 78% Fail | 3h 92% Pass | 4h 70% Fail | 4h 95% Pass | 4h 80% Fail |
| 5h 75% Pass | 5h 62% Fail | 6h 80% Pass | 7h 95% Pass | 7h 70% Pass | 8h 88% Pass | 9h 66% Pass | 10h 96% Pass |
The four best first questions, ranked by Gini gain (how much impurity they remove)
- 1. Revision hours a week ≤ 5.5: gain 0.230 (10 go yes, 6 go no)
- 2. Revision hours a week ≤ 4.5: gain 0.195 (8 go yes, 8 go no)
- 3. Revision hours a week ≤ 6.5: gain 0.174 (11 go yes, 5 go no)
- 4. Attendance (%) ≤ 86.5: gain 0.174 (11 go yes, 5 go no)
Leaves
2
Right on these 16
13 / 16
Training accuracy
81%
Each split asks one yes/no question and sends students down two branches. A split is chosen because it makes the groups purer (lower Gini). A deeper tree fits the training students better, until every leaf is pure; at that point it may have memorised quirks (a student with high attendance and few hours) rather than the pattern.
A tree can keep splitting until every leaf is pure and the training data is classified perfectly, but that is usually a sign of : the later questions are about quirks of these sixteen students, not about students in general. The usual defences are to limit the depth, to demand a minimum number of examples in a leaf, or to prune branches that do not help on unseen data.
Choosing between them#
| k-nearest neighbours | Decision tree | |
|---|---|---|
| Training | None: stores the data | Builds a tree once |
| Prediction speed | Slow for large data (compares with every point) | Fast: follows one path |
| Explainable? | Only by showing similar cases | Yes: the rules can be read |
| Needs scaling? | Yes, distances depend on it | No |
| Typical overfitting cause | k too small | Tree too deep |
| Typical uses | Recommendations, quick baselines | Medical diagnosis, loan decisions, anything that must be explained |
Medical diagnosis suits trees because the output is a path a doctor can inspect: shortness of breath → wheezing → fever → pneumonia is easier to trust than a score from a black box. But the cost of mistakes matters too: for a serious illness, a missed case is worse than a false alarm, so judge the tree on recall as well as accuracy (A4.3.3).
Check yourself
Classification: k-NN and decision trees
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
6 questions · 23 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Calculate the class of the new point (4, 6), using k-nearest neighbours with k = 3.
[4]Training points: P1 (4, 2) Red, P2 (1, 6) Blue, P3 (5, 9) Blue, P4 (9, 6) Red
Calculate: Work out the number, showing the working.
2.A node in a decision tree holds 6 examples labelled “yes” and 2 labelled “no”. Calculate its Gini impurity.
[3]Calculate: Work out the number, showing the working.
3.Explain the effect of choosing a very small k, and a very large k, in k-nearest neighbours.
[3]Explain: Give reasons: say what happens AND why, or how one thing causes another.
4.Compare k-nearest neighbours with a decision tree as methods of classification.
[4]Compare: Similarities and differences, about both things, point by point.
5.Describe how k-nearest neighbours can be used to recommend books to a reader (user-based collaborative filtering).
[3]Describe: A detailed account: say what happens, step by step if it is a process.
6.A hospital wants a system to help sort emergency patients into urgent and not urgent, using age, blood pressure, temperature and symptoms. Evaluate using a decision tree for this task.
[6]Evaluate: Weigh the strengths against the weaknesses (or the benefits against the costs) and reach a judgement that you back up.
In a nutshell
- Classification predicts a category. It is supervised: it learns from labelled examples.
- k-NN: measure the distance (Euclidean) from the new point to every training point, take the k closest, and give the new point their most common class. Small k overfits; large k blurs. Scale the features first.
- A decision tree asks a series of yes/no questions on features. Each split is chosen to make the groups purer (lower Gini impurity, or lower entropy). Leaves hold the predicted class.
- Deep trees can overfit. Limit the depth, or prune. Trees are easy to explain; k-NN has no training but is slow to predict.
- Uses: recommendations (collaborative filtering with k-NN), medical diagnosis and loan decisions (decision trees).