Home / MLT / Week 7

Week 7 · k-NN and decision trees

Official syllabus line: Supervised Learning - Classification - K-NN, Decision tree

About 80 minQuiz 2 material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 1 (distance), MLT week 5 (what supervised learning and overfitting are). Logarithms to base 2.

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine a new, strange fruit arrives, and you don't know what it is. You check the three fruits in your basket that look most similar in size and color. If two are mangoes and one is a peach, you might decide your new fruit is a mango. This is exactly how k-Nearest Neighbours works!
Machine learning models help us classify things. One idea, k-Nearest Neighbours, decides by looking at its closest friends and taking a majority vote. Another, Decision Trees, plays a game of 'twenty questions', asking smart questions to sort things into clear groups. Both are powerful tools.
Let's try k-NN. Imagine points on a map. A new point arrives, and we want to classify it. If we look at just one neighbour, its class might be positive. But looking at three neighbours, it's still positive. Yet, with five neighbours, the answer actually changes to negative!
For exams, remember: k-NN needs features scaled, but decision trees don't. A 1-nearest neighbour model usually has zero training error, but it likely overfits, meaning it's memorized the data too much. Pruning helps trees avoid this. Always aim for a balanced model!

The one-minute story

Think of it like this

k-NN: "tell me who your neighbours are". A new fruit arrives and you have no idea what it is. So you look at the 3 fruits in your basket that look most like it (size, colour, weight). Two are mangoes and one is a peach: you call it a mango. No rules were learned in advance; you just remember the examples and look things up when asked.

Decision tree: "twenty questions". To guess an animal, you ask the question that splits the possibilities best ("Does it live in water?"). Then, depending on the answer, you ask the next best question for that group. A decision tree is that game written down as a flowchart, built automatically from data by always choosing the question that makes the groups cleanest.

Two very different ideas, both for classification (and they also do regression), both easy to read, and both at risk of overfitting.

By the end of this week you can:

run k-NN by hand and see how $k$ changes the answer;
explain the curse of dimensionality and the need for feature scaling;
compute entropy, Gini impurity and information gain;
build the first split of a decision tree and explain overfitting and pruning.

Words you need

Classification - predicting a category (a class label).
Nearest neighbour - the training point with the smallest distance to the query.
Lazy learner - a method that does no training; it stores the data and works at prediction time (k-NN).
Entropy $H$ - a measure of how mixed (unpredictable) a group is: 0 for a pure group, largest for an even mix.
Gini impurity - another measure of mixedness.
Information gain - how much a split reduces entropy.
Pruning - cutting a tree back so it does not memorise the training data.

Idea 1: k-nearest neighbours

The idea

k-NN classification. To classify a new point $\mathbf q$ :

Compute the distance from $\mathbf q$ to every training point (usually Euclidean).
Take the $k$ closest.
Predict the majority class among them.

k-NN regression: predict the average of those $k$ targets.

Solved example: 1. k-NN by hand

Question. Training points (class): $A(1,1)+$ , $B(2,2)+$ , $C(3,1)-$ , $D(6,5)-$ , $F(6,6)-$ , $E(7,7)-$ . Classify the query $\mathbf q=(3,3)$ with $k=1,\,3,\,5$ .

Solution. Distances from $(3,3)$ : $B$ : $\sqrt{1+1}=1.41$ ; $C$ : $\sqrt{0+4}=2$ ; $A$ : $\sqrt{4+4}=2.83$ ; $D$ : $\sqrt{9+4}=3.61$ ; $F$ : $\sqrt{9+9}=4.24$ ; $E$ : $5.66$ .

$k=1$ : nearest is $B$ $(+)$ . Predict +.
$k=3$ : $B,C,A=\;+,-,+$ . Majority +.
$k=5$ : $B,C,A,D,F=\;+,-,+,-,-$ . Majority $-$ .

Same data, same query: the answer changes with $k$ . (For $k$ -NN regression with neighbour targets $3,\,5,\,10$ the prediction is their mean, $6$ .)

Choosing $k$ and other facts

$k=1$ : the boundary follows every point, zero training error, very jagged: overfits (high variance). Its training "error" is meaningless because each point is its own neighbour.
$k=n$ : always predicts the overall majority class: underfits (high bias).
Pick $k$ by cross-validation. Use an odd $k$ for two classes to avoid ties.
Scale your features. Distance is dominated by features with big numbers (salary in rupees vs age in years). Standardise first.
Curse of dimensionality. In very many dimensions, all points look about equally far away, so "nearest" stops meaning anything and you need exponentially more data.
No training, slow prediction: every query scans the whole data set.
Weighted k-NN gives closer neighbours more say.

Idea 2: Decision trees

A decision tree asks a question about one feature at each node (such as "age $<30$ ?"), sends the example down the matching branch, and ends at a leaf that holds the prediction (the majority class of the training examples that reached it).

How is the question chosen? Greedily: among all possible splits, pick the one that makes the two child groups purest. We need a number for "purity".

Entropy

For a group in which a fraction $p_c$ belongs to class $c$ :

H=-\sum_cp_c\log_2p_c

A pure group ( $p=1$ ): $H=0$ .
Two classes split 50/50: $H=1$ bit, the maximum.
75/25: $H=-0.75\log_20.75-0.25\log_20.25=0.311+0.5=0.811$ .

Gini impurity

G=1-\sum_cp_c^2

Pure: $0$ . 50/50: $0.5$ . 75/25: $1-(0.5625+0.0625)=0.375$ . (A cheaper, very similar measure.)

Information gain

Splitting a group into children, the information gain is the parent's entropy minus the size-weighted average entropy of the children:

IG=H(\text{parent})-\sum_{\text{children }j}\frac{n_j}{n}H(\text{child }j)

Pick the split with the largest information gain.

Solved example: 2. Which split is better?

Question. A node holds 8 examples: 4 positive, 4 negative. Split A gives children $(3+,1-)$ and $(1+,3-)$ . Split B gives $(4+,0-)$ and $(0+,4-)$ . Compute the information gain of each.

Solution. Parent: $H=1$ .

Split A: each child is 75/25, entropy $0.811$ . Weighted average $=\frac48(0.811)+\frac48(0.811)=0.811$ . $IG=1-0.811=\mathbf{0.189}$ .
Split B: both children are pure, entropy 0. $IG=1-0=\mathbf1$ .

Split B is perfect, so choose B. (With Gini: parent $0.5$ ; A: weighted $0.375$ , gain $0.125$ ; B: gain $0.5$ . The same winner.)

Growing and pruning the tree

Repeat the process on each child until a stopping rule applies: the node is pure, or no features are left, or the depth limit or minimum node size is reached.

A tree grown until every leaf is pure gets zero training error but usually overfits: it memorises noise.
Control complexity with a maximum depth, a minimum number of examples per leaf, or pruning (grow big, then cut back branches that do not help on validation data).
Regression trees split to reduce variance (squared error) and predict the leaf's mean.

Pros: easy to read, no feature scaling needed, handles mixed feature types. Cons: unstable (small data changes can change the tree), axis-aligned boundaries only, and overfits when deep. Both problems are repaired by ensembles (week 11).

Your turn

Your turn: 1. Classify with k-NN

Training: $(0,0)-$ , $(1,0)-$ , $(0,1)-$ , $(3,3)+$ , $(4,3)+$ , $(3,4)+$ . Classify the query $(3,2)$ with $k=1,\,3,\,5$ .

Need a hint?

Compute the distance from $(3,2)$ to each point and sort.

Show the full solution

Distances: $(3,3)$ : $1$ ; $(4,3)$ : $1.41$ ; $(3,4)$ : $2$ ; $(1,0)$ : $2.83$ ; $(0,1)$ : $3.16$ ; $(0,0)$ : $3.61$ . Nearest five in order: $+,+,+,-,-$ . So $k=1$ : +; $k=3$ : $+,+,+$ gives +; $k=5$ : three $+$ against two $-$ gives +. (With $k=6$ it would be a 3 to 3 tie, which is why we prefer odd $k$ .)

Your turn: 2. Entropy

A node has 2 positive and 6 negative examples. Compute its entropy and Gini impurity.

Need a hint?

Fractions $0.25$ and $0.75$ .

Show the full solution

$H=0.811$ (computed above). $G=1-(0.0625+0.5625)=\mathbf{0.375}$ .

Your turn: 3. Information gain

A node has $5+,5-$ . A split creates $(4+,1-)$ and $(1+,4-)$ . Find the information gain. (Use $H(0.8,0.2)=0.722$ .)

Need a hint?

Parent entropy is 1; both children have the same split of 80/20.

Show the full solution

Weighted child entropy $=\frac5{10}(0.722)+\frac5{10}(0.722)=0.722$ . $IG=1-0.722=\mathbf{0.278}$ .

Your turn: 4. True or false

(a) 1-NN has zero training error. (b) $k=n$ gives the majority-class prediction. (c) A deeper tree can only raise training error. (d) Decision trees need feature scaling.

Need a hint?

Think about each extreme.

Show the full solution

(a) True (each point is its own nearest neighbour). (b) True. (c) False: depth lowers training error; it raises the risk of overfitting. (d) False: splits compare one feature to a threshold, scale is irrelevant.

Your turn: 5. Choosing k

With $k$ -NN on a noisy data set you see: $k=1$ : train 0%, validation 22%; $k=5$ : train 9%, validation 12%; $k=25$ : train 20%, validation 21%. Which $k$ do you choose and why?

Need a hint?

Choose by validation error.

Show the full solution

$k=5$ (lowest validation error, 12%). $k=1$ overfits (a big gap between train and validation); $k=25$ underfits (high error on both).

Exam radar

MLT Quiz 2 summaries mention (of the 21 Quiz 2 papers that have a summary) decision trees in 19, information gain in 11, k-NN in 12, impurity measures in 6, entropy in 5 and k-NN regression in 2. End Term counts: decision trees 24, entropy 19, k-NN 11, information gain 12.

Typical: compute entropy or information gain for a small table; "which split would the algorithm choose first?"; "what is the training error of 1-NN?"; "effect of increasing $k$ "; "does the decision tree need scaling?".

Watch out - real exam trap

Information gain uses the weighted average of child entropies (weights are group sizes).
$\log_2$ , not $\ln$ , for entropy in bits (check what the question uses).
1-NN training error is zero; do not interpret that as a good model.
Scale features for k-NN; not for trees.
A fully grown tree is not a good sign: it probably overfits.

Quick quiz

The entropy of a node with 4 positive and 4 negative examples is...

An even split of two classes has the maximum entropy of 1 bit.

For k-NN with k equal to the number of training points, the prediction is...

always the nearest point's class
the overall majority class
random
impossible to compute

Every query uses all points, so the majority class always wins.

Information gain of a split is...

the entropy of the left child
parent entropy minus the weighted average child entropy
the sum of the child entropies
the number of leaves

IG measures the reduction in entropy produced by the split.

Select all TRUE statements. (select all that apply)

k-NN should use scaled features.
A fully grown decision tree often overfits.
A decision tree needs one-hot encoding of every numeric feature.
Pruning makes a tree fit the training data more closely.

Pruning does the opposite: it simplifies the tree to reduce overfitting.

Recap

Remember this

k-NN: majority vote (or mean) of the $k$ nearest points. Small $k$ overfits, large $k$ underfits. Scale features; beware high dimensions.
Entropy $-\sum p\log_2p$ ; Gini $1-\sum p^2$ ; information gain $=H_{\text{parent}}-\sum\frac{n_j}nH_j$ .
Tree: greedily pick the split with the biggest gain; grow, then prune or limit depth to avoid overfitting.

Formulas to keep

Euclidean distance $\|\mathbf x-\mathbf q\|$ ; k-NN regression: mean of $k$ neighbours
Entropy $H=-\sum_cp_c\log_2p_c$ (50/50 gives 1; 75/25 gives 0.811)
Gini $=1-\sum p_c^2$ (50/50 gives 0.5; 75/25 gives 0.375)
$IG=H(\text{parent})-\sum_j\frac{n_j}{n}H(\text{child}_j)$

Connected weeks (learn them together)

MLP week 9 - Decision trees and ensembles: Decision trees: the theory, then the code.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 59 real questions on this week All Quiz 2 papers

Week 7 · k-NN and decision trees

The one-minute story

Words you need

Idea 1: k-nearest neighbours

Choosing kkk and other facts

Idea 2: Decision trees

Entropy

Gini impurity

Information gain

Growing and pruning the tree

Your turn

Exam radar

Quick quiz

Recap

Practise with real exam questions

Choosing $k$ and other facts