Decision Trees & the ID3 Algorithm

Source: Unit 1 §7

A decision tree is a classification algorithm: a graphical representation of all possible solutions to a decision, where every decision is based on a condition and the reasoning is easily explained. That last property is the reason trees survive alongside far more accurate models - you can read the answer's justification straight off the diagram.

Classification itself means dividing a data set into different categories or groups by attaching a label to each instance - an email becomes spam or not-spam, a day becomes play or don't-play.

⚠GotchaThe slide says decision trees are unsupervised. They are not.

The course slide claims decision trees "come under unsupervised learning". That is incorrect - decision trees are a supervised method, because they need labelled training data to compute entropy and information gain at all. Know what the slide says, but know the truth.

A decision tree is just nested conditions. Every internal node asks about one attribute; every leaf is an answer.

How a tree classifies an instance

Decision tree learning is a method for approximating discrete-valued target functions, in which the learned function is represented by a decision tree. (Tom Mitchell)

→StepsClassifying one instance

1. Start at the root node.
2. Test the attribute specified by that node.
3. Move down the branch matching that attribute's value in the instance.
4. Repeat on the sub-tree at the new node, until a leaf is reached. The leaf gives the classification.

The canonical Play Tennis tree. Every root-to-leaf path is one conjunction; the tree as a whole is the disjunction of those paths.

The tree above is exactly this decision function:

f(outlook, humidity, wind) =

1 if (outlook = sunny AND humidity = Normal)

OR (outlook = overcast)

OR (outlook = Rain AND wind = weak)

0 otherwise

◎Exam cueTrees represent disjunctions

Each root-to-leaf path is a conjunction of attribute tests; the tree is the disjunction (OR) of all the paths that reach a positive leaf. Trees express ORs naturally, which is precisely what conjunction-only learners like Find-S cannot do.

When a decision tree is appropriate

≡FactsThe five conditions that suit tree learning

• Instances are attribute-value pairs - e.g. Temperature = Hot.
• The target function has discrete output values - e.g. yes / no.
• Disjunctive descriptions may be required - trees handle ORs naturally.
• The training data may contain errors - trees are robust to noise, both in the class labels and in the attribute values.
• The training data may have missing attribute values - a tree can still be built and used.

ID3, the core idea

ID3 builds the tree top-down and greedily, by repeatedly asking one question: which attribute should be tested at the root of this subtree?

The answer comes from a statistical test measuring how well each attribute alone classifies the examples. The winner becomes the node; the examples are branched on its values and sorted into descendants; and the procedure recurses.

⚠GotchaID3 never backtracks

The search is greedy. Once an attribute is chosen at a level, ID3 never revisits that choice, no matter how bad the subtree below it turns out to be. This is why ID3 can settle on a locally rather than globally optimal tree.

The statistical measure ID3 uses is information gain, which is built on entropy.

Entropy - measuring impurity

Entropy characterises the (im)purity of a collection of examples. For a Boolean classification with $p$ positive and $n$ negative examples:

$$\text{Entropy}(S) = -\frac{p}{p+n}\log_2\frac{p}{p+n} - \frac{n}{p+n}\log_2\frac{n}{p+n}$$

The general form for $c$ classes, with $p_i$ the proportion of class $i$:

$$\text{Entropy}(S) = \sum_i \left(-p_i \log_2 p_i\right)$$

Entropy peaks at 1 bit for a 50/50 split and falls to 0 at either pure extreme. This is why a split that drives branches towards the ends of the curve is a good split.

Case	Entropy
All samples the same class (pure)	0
Classes perfectly balanced (50/50)	1

→StepsWorked entropy: 3 positives, 4 negatives

1. Total is $p + n = 3 + 4 = 7$, so the proportions are $3/7 = 0.4286$ and $4/7 = 0.5714$.
2. Take logs: $\log_2(3/7) = -1.222$ and $\log_2(4/7) = -0.807$.
3. Substitute: $-(0.4286)(-1.222) - (0.5714)(-0.807) = 0.524 + 0.461$.
4. Entropy(S) ≈ 0.98 - nearly maximal, because 3 against 4 is nearly balanced.

Average information of an attribute

When $S$ is split on attribute $A$, the impurity left behind is the weighted average of the entropies of the branches, weighted by branch size:

$$I(A) = \sum_{v \in \text{values}(A)} \frac{p_v + n_v}{p + n} \cdot \text{Entropy}(A = v)$$

where $p_v$ and $n_v$ are the positive and negative counts inside that branch.

Information gain

Information gain is the expected reduction in entropy caused by splitting on attribute $A$:

$$G(S, A) = \text{Entropy}(S) - I(A)$$

The attribute with the highest information gain is chosen for that node.

The ID3 algorithm

→StepsID3, end to end

1. Compute the entropy of the whole data set, $\text{Entropy}(S)$.
2. For every attribute:
   • calculate the entropy of each of its values, $\text{Entropy}(A = v)$;
   • take the weighted average information, $I(A)$;
   • calculate the gain, $G(S, A) = \text{Entropy}(S) - I(A)$.
3. Pick the attribute with the highest gain and make it the node.
4. Split on it and repeat on each branch until the tree is complete. A branch stops when its entropy is 0, that is, when it is pure.

Fully worked example: Play Tennis

#	Outlook	Temp	Humidity	Windy	Play
1	Sunny	High	High	Weak	No
2	Sunny	High	High	Strong	No
3	Overcast	High	High	Weak	Yes
4	Rainy	Medium	High	Weak	Yes
5	Rainy	Cool	Normal	Weak	Yes
6	Rainy	Cool	Normal	Strong	No
7	Overcast	Cool	Normal	Strong	Yes
8	Sunny	Medium	High	Weak	No
9	Sunny	Cool	Normal	Weak	Yes
10	Rainy	Medium	Normal	Weak	Yes
11	Sunny	Medium	Normal	Strong	Yes
12	Overcast	Medium	High	Strong	Yes
13	Overcast	High	Normal	Weak	Yes
14	Rainy	Medium	High	Strong	No

Positives (Yes) = 9, negatives (No) = 5, total = 14.

→StepsStep 1 - entropy of the whole set

1. Proportions: $9/14 = 0.643$ and $5/14 = 0.357$.
2. Logs: $\log_2(9/14) = -0.637$ and $\log_2(5/14) = -1.485$.
3. Substitute: $-(0.643)(-0.637) - (0.357)(-1.485) = 0.410 + 0.530$.
4. Entropy(S) = 0.94.

Step 2 - the gain of Outlook

Split Outlook into sunny / overcast / rain:

Outlook	p	n	Entropy
sunny	2	3	−(2/5)log₂(2/5) − (3/5)log₂(3/5) = 0.971
overcast	4	0	0 (pure)
rain	3	2	0.971

→StepsTurning those branch entropies into a gain

1. Weight each branch by its share of the 14 rows: $I(\text{Outlook}) = \tfrac{5}{14}(0.971) + \tfrac{4}{14}(0) + \tfrac{5}{14}(0.971)$.
2. That comes to $I(\text{Outlook}) = 0.693$.
3. Subtract from the parent entropy: $G(S, \text{Outlook}) = 0.94 - 0.693 = \mathbf{0.247}$.

Repeating that for every attribute:

Attribute	Information gain
Outlook	0.247 - highest
Temp	0.029
Humidity	0.152
Windy	0.048

Step 3 - pick the root

Outlook has the highest gain, so it becomes the root. The overcast branch has entropy 0 (all "Yes"), so it is finished as a leaf. Sunny and rainy are still mixed, so both are recursed into.

After the first split the overcast branch is already pure, so it becomes a leaf immediately. Only the two impure branches are recursed into.

Step 4 - recurse on Outlook = Sunny

The sunny subset is rows 1, 2, 8, 9 and 11: $p = 2$, $n = 3$, giving $\text{Entropy}(S_{\text{sunny}}) = -(2/5)\log_2(2/5) - (3/5)\log_2(3/5) = 0.97$.

Now the gain of each remaining attribute is computed within the sunny subset only.

Temperature:

Temp	p	n	Entropy
cool	1	0	0
high	0	2	0
medium	1	1	1

$I(\text{Temp}) = 0.4$, so $G(\text{Temp}) = 0.97 - 0.4 = 0.571$.

Humidity:

Humidity	p	n	Entropy
normal	2	0	0
high	0	3	0

$I(\text{Humidity}) = 0$, so $G(\text{Humidity}) = 0.97 - 0 = 0.971$.

Windy:

Windy	p	n	Entropy
strong	1	1	1
weak	1	2	0.918

$I(\text{Windy}) = 0.951$, so $G(\text{Windy}) = 0.97 - 0.951 = 0.020$.

Attribute (within sunny)	Gain
Humidity	0.971 - winner
Temp	0.571
Windy	0.020

Humidity wins under sunny, and both of its branches are pure - normal gives all Yes, high gives all No - so both become leaves.

The final tree

The completed tree. The rain subtree splits on Wind: weak gives Yes, strong gives No.

→StepsUsing the tree to predict

1. The forecast is sunny, normal humidity, weak wind.
2. Root test Outlook = sunny, so take the sunny branch to Humidity.
3. Humidity is normal, so take that branch.
4. The leaf reads YES - the player will play tennis.

◎Exam cueThe one-line summary of ID3

Highest information gain wins the node; a branch stops when its entropy hits 0. Everything else is bookkeeping.