Skip to content

Chapter 6: Decision Trees

Unit 3 predicted a number. The model was a surface passing through the data. Here the answer is a category instead, so the model is a fence. It cuts the feature space into regions and labels each one. That fence has a name — the decision boundary — and every algorithm in this unit is one way of drawing it.

Read the unit as a chain of complaints and answers. A decision tree cuts the space into boxes. You can read its rules aloud, and it overfits badly. Naïve Bayes just counts and multiplies. It is almost free to train, and it rests on an assumption that is plainly false. Logistic regression draws one straight boundary and hands you a probability you can trust. k-NN builds no model at all; it looks at the neighbours. The perceptron is the simplest thing that learns a boundary, and it cannot do XOR. The multilayer perceptron can, but you can no longer see how. And the SVM asks a sharper question: which straight boundary? The one with the widest empty corridor around it.

Then come the last two lectures, and they matter more than any single algorithm: how to tell whether a classifier is any good. Take a dataset where 99 cases in 100 are negative. There, accuracy is worse than useless. Knowing why is what separates somebody who can run scikit-learn from somebody who can be trusted with a model.

Learning outcomes of Unit 4

  • Compute entropy, Gini and information gain, choose a split the way ID3 does, and explain why a deep tree overfits and how pruning stops it.
  • Apply naïve Bayes to a table, explain what the independence assumption buys and costs, and repair the zero-frequency problem with Laplace smoothing.
  • Derive logistic regression from linear regression, explain why squared error is replaced by log-loss, and locate its decision boundary.
  • Classify with k-NN by hand and describe how \(k\) moves the model along the bias–variance axis.
  • Run the perceptron update rule, state its convergence theorem, and say precisely what it cannot do.
  • Carry out a forward pass and one step of back-propagation through a small network, and explain the vanishing-gradient problem from the shape of \(\sigma '\).
  • State the SVM objective, compute a margin, identify support vectors, and explain the roles of \(C\) and the kernel trick.
  • Handle more than two classes: one-vs-rest, one-vs-one and softmax with cross-entropy, and the difference between macro, micro and weighted averaging.
  • Build a confusion matrix and compute every metric from it; read a ROC curve; and choose a metric from the cost of each kind of mistake.

6.1 The classification problem

Definition: Classification and the decision boundary

Given examples (x, y) with \(y\) drawn from a finite set of classes, learn a map from feature vectors to classes. The decision boundary is the surface in feature space where the predicted class changes. Binary classification has two classes; multi-class has more; multi-label allows several at once.

Most algorithms produce a score rather than a class — a probability, a distance from a boundary, a vote count — and a threshold turns the score into a decision. Keeping that distinction in mind explains most of the evaluation section at the end: the model and the threshold are separate choices, and they can be changed separately.

Boundary shape What it gives you
Decision tree — axis-parallel steps; a staircase Rules a human can read out loud
Naïve Bayes — quadratic in general, linear for shared variances A probability, badly calibrated but well ranked
Logistic regression — one straight line (hyperplane) A genuinely calibrated probability
k-NN — arbitrarily wiggly, decided by the points themselves No model at all; the data is the model
Perceptron — one straight line, and nothing else A boundary, with no probability
MLP — as curved as the hidden layer allows High accuracy, low interpretability
SVM — straight, or curved via a kernel The widest possible margin, and sparsity

6.2 Decision trees

A decision tree is the game of twenty questions. Ask the question that tells you the most, split the examples on the answer, and repeat on each part until the group in front of you is all one class. The result is a set of if–then rules you can read aloud to somebody who has never heard of machine learning — which is why trees survive in credit scoring and medicine long after more accurate models exist.

The only technical question is what “tells you the most” means, and information theory answers it.

Definition: Entropy

For a set \(S\) with class proportions \(p_{1}\ldots p_{c}\),

\(H(S) = - \sum p_{i} \log_{2} p_{i}\)

measured in bits: the average number of yes/no questions needed to name the class of a randomly drawn member. \(H = 0\) for a pure set; \(H = 1\) bit for a 50/50 binary split; \(H = \log_{2}c\) for \(c\) equally likely classes.

Entropy, Gini index and misclassification error of a two-class node. All are zero for a pure node and largest at p = 1/2. Entropy peaks at 1 bit and Gini at 0.5. They almost always rank splits the same way; Gini is cheaper because it has no logarithm.
Figure 6.1. Entropy, Gini index and misclassification error of a two-class node. All are zero for a pure node and largest at p = 1/2. Entropy peaks at 1 bit and Gini at 0.5. They almost always rank splits the same way; Gini is cheaper because it has no logarithm.
\[ \text{Gain}(S, A) = H(S) - \sum _{v} (|S_{v}| / |S|) \cdot H(S_{v}) \]

information gain: the impurity before the split, minus the weighted average impurity after it

The weights are what stop the tree from loving useless splits. A split that peels off one lonely example gives a perfectly pure child — but that child carries a weight of 1/m, so almost nothing is gained. ID3 computes the gain for every attribute, takes the largest, and recurses on each branch, stopping when a node is pure, when attributes run out, or when a depth limit is hit.

Information gain of every candidate threshold on one feature (dots are the examples, coloured by class). Gain is near zero at the extremes, where the cut separates nothing, and peaks where the cut best divides the colours; the tree chooses that peak.
Figure 6.2. Information gain of every candidate threshold on one feature (dots are the examples, coloured by class). Gain is near zero at the extremes, where the cut separates nothing, and peaks where the cut best divides the colours; the tree chooses that peak.

Gain has a bias, and C4.5 fixes it

Plain information gain prefers attributes with many values. An ID column splits every example into its own pure branch, so its gain is maximal and its usefulness is nil. C4.5 divides the gain by the entropy of the split itself — the gain ratio — which penalises attributes that fragment the data. CART sidesteps the issue by making only binary splits.

Why trees overfit, and what to do

Left alone, a tree grows until every leaf is pure, which for noisy data means one leaf per noisy point. Training accuracy reaches 100% and test accuracy falls. The tree has a very large hypothesis space and no built-in preference for simplicity, so it needs one imposed from outside.

  • Pre-pruning (early stopping): a maximum depth, a minimum number of samples to split, a minimum gain. Cheap, and it can stop just before a split that would have been valuable.
  • Post-pruning: grow the full tree, then remove subtrees whose removal does not hurt validation accuracy — reduced-error pruning. More expensive and usually better, since it judges a subtree by what it contributed rather than by a guess made before growing it.
# a decision tree, and the rules it learned — read them out loud
from sklearn.tree import DecisionTreeClassifier, export_text

tree = DecisionTreeClassifier(criterion="entropy", max_depth=3,
                              random_state=42).fit(X_tr, y_tr)

print(export_text(tree, feature_names=list(feature_names)))
print(dict(zip(feature_names, tree.feature_importances_.round(3))))
print("train", tree.score(X_tr, y_tr), "test", tree.score(X_te, y_te))

# training and test accuracy as the tree is allowed to grow deeper
for d in range(1, 12):
    t = DecisionTreeClassifier(max_depth=d, random_state=42).fit(X_tr, y_tr)
    print(d, round(t.score(X_tr, y_tr), 3), round(t.score(X_te, y_te), 3))

No scaler anywhere, deliberately — a tree does not need one. Note random_state: ties between equally good splits are broken at random, so without it the tree changes between runs.

The staircase of rectangles a decision tree carves out of the feature plane. A tree can only cut parallel to the axes, and that is its inductive bias; allowed to grow deep it also draws small boxes around individual noisy points.
Figure 6.3. The staircase of rectangles a decision tree carves out of the feature plane. A tree can only cut parallel to the axes, and that is its inductive bias; allowed to grow deep it also draws small boxes around individual noisy points.

A tree for a boolean function

Any boolean function can be written as a decision tree, and drawing one is a common exam question. Write the truth table, choose the variable that makes the largest branch pure, and the tree usually falls out in two or three tests.

Example 6.1: \(A \lor (B \land\) C)

Problem. Draw a decision tree representing \(A \lor (B \land\) C), and justify the choice of root by information gain.

Step 1 — the truth table

A B \(C\) Output
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Five true, three false, so \(H(S) = -(5/8)\log_{2}(5/8) - (3/8)\log_{2}(3/8) = 0.9544\) bits.

Step 2 — which variable to test first

A: the \(A = 1\) branch holds 4 rows, all true — entropy 0. The \(A = 0\) branch holds 4 rows, 1 true and 3 false — entropy 0.8113. Remainder \(=\) ½(0) + ½(0.8113) \(= 0.4056\), so Gain(A) \(= 0.5488\) bits.

B (and by symmetry \(C\)): each branch holds 4 rows, one with 3 true and 1 false and the other with 2 true and 2 false. Remainder \(=\) ½(0.8113) + ½(1.0000) \(= 0.9056\), so Gain(B) \(=\) Gain(C) \(= 0.0488\) bits.

A wins by more than a factor of ten, because it is the only variable that produces a pure branch.

Step 3 — the tree

                 [A]
              0 /   \ 1
               /     \
             [B]     TRUE
          0 /   \ 1
           /     \
      FALSE     [C]
                0 /  \ 1
                 /    \
             FALSE  TRUE

When \(A = 1\) the disjunction is already satisfied, so nothing else need be tested. When \(A = 0\) the function reduces to \(B \land\) C, which needs both.

The same method on the other two you may be asked

\(A \land (B \lor\) C): test A; \(A = 0 \to\) FALSE; \(A = 1 \to\) test B, and if \(B = 0\) test \(C\). Gain(A) is again 0.5488 bits, for the mirror-image reason.

\(A \oplus\) B (XOR): no single variable has any gain at all — each branch is 2 true and 2 false, so the remainder equals \(H(S)\) and the gain is exactly 0. The tree still exists (test A, then B on both branches), but a greedy criterion cannot see which variable to pick, so it takes an arbitrary one. This is the standard example of why pre-pruning on a minimum-gain threshold is dangerous: the useful split lies one level below a useless one.

Answer. Test A first — Gain(A) \(= 0.5488\) bits against 0.0488 for B or \(C\)

6.3 Further topics

Gain ratio and split information

Information gain can only go up as an attribute splits the data into more and smaller groups, which is why it favours many-valued attributes. C4.5 corrects this by dividing the gain by the split information, the entropy of the branch sizes alone:

\[ \text{SplitInfo}(S, A) = -\sum_{v} \frac{|S_{v}|}{|S|} \log_{2} \frac{|S_{v}|}{|S|}, \qquad \text{GainRatio}(S, A) = \frac{\text{Gain}(S, A)}{\text{SplitInfo}(S, A)} \]

The denominator takes simple values that are worth remembering. A two-way split into equal halves has SplitInfo \(= 1\), so the ratio equals the gain. A split into \(n\) equal groups has SplitInfo \(= \log_{2} n\), so an identifier column that puts every one of \(m\) examples into its own branch pays a penalty of \(\log_{2} m\) however perfect its purity. A very lopsided split has a small SplitInfo, which can make the ratio large for a split that is nearly useless, so C4.5 only ranks by gain ratio the attributes whose gain is at least the average of the candidates.

Numeric attributes and binary tests

A numeric attribute is turned into a yes/no question \(x \le t\). The values present in the node are sorted, and the candidate thresholds are the midpoints between neighbours whose class labels differ; a cut inside a run of one class never improves purity. Each candidate is scored with the same gain (or Gini reduction) as an ordinary split, and the best one stands for the attribute. Because the question is binary, the same numeric attribute may be tested again further down with a different threshold, which is how a tree approximates a smooth, increasing relationship by a staircase.

CART takes this idea further and makes every test binary. A categorical attribute with \(v\) values is divided into two groups of values, and there are \(2^{v-1} - 1\) ways to do it: 3 for three values, 15 for five, 31 for six. CART scores each with the Gini index. It can also grow a regression tree, in which a leaf predicts the mean target value of its examples and the impurity of a node is the variance of its targets.

ID3, C4.5 and CART side by side

ID3 C4.5 CART
Split criterion information gain gain ratio Gini index (or variance for regression)
Branching one branch per value one branch per value, or a threshold always two branches
Numeric attributes not handled thresholds \(x \le t\) thresholds \(x \le t\)
Missing values not handled handled surrogate splits
Task classification classification classification and regression
Controls overfitting by stopping rules post-pruning cost-complexity pruning

Cost-complexity pruning

Reduced-error pruning needs a validation set to judge each subtree. Cost-complexity (weakest-link) pruning, used by CART, instead scores a tree \(T\) with a single number that charges for its size:

\[ \text{Cost}_{\alpha}(T) = \text{Error}(T) + \alpha \cdot |\text{leaves}(T)| \]

With \(\alpha = 0\) the full tree wins, because it has the smallest training error. As \(\alpha\) grows, a subtree that buys little accuracy for its leaves becomes too expensive and is collapsed into a single leaf; for large \(\alpha\) only the root survives. Cutting a subtree \(t\) is worthwhile once \(\alpha\) exceeds

\[ g(t) = \frac{\text{Error}(\text{leaf at } t) - \text{Error}(T_{t})}{|\text{leaves}(T_{t})| - 1}, \]

the extra error per leaf saved. The subtree with the smallest \(g\) is the weakest link and goes first; \(\alpha\) itself is then chosen by cross-validation.

A small check on the ten students of the worked examples shows the mechanism. Grow a tree that tests Attendance and then splits the Medium group (R03 with 3.5 hours, R05 with 4.5 and R07 with 6.0) at 5.25 hours. It has 4 leaves and makes no training error. Collapsing the Medium subtree to the leaf Fail makes one error in ten, so \(g = (0.1 - 0)/(2 - 1) = 0.1\). Collapsing the root of the full tree instead would leave the majority error of \(0.5\), so \(g = (0.5 - 0)/(4 - 1) = 0.167\), which is larger, so the Medium subtree is the weakest link. Once it has gone, the three-leaf tree costs \(0.1 + 3\alpha\) and the one-leaf tree \(0.5 + \alpha\), which are equal at \(\alpha = 0.2\). So the full tree is best for \(\alpha < 0.1\), the three-leaf tree for \(0.1 < \alpha < 0.2\), and the single leaf beyond that.

6.4 Worked examples

The examples below work through the calculations of this chapter in full. Try each one on paper before reading the steps.

Example 6.2: Information gain, from counts to a decision

Problem. A node has 9 positive and 5 negative examples. Attribute Wind splits it into Weak (6+, 2−) and Strong (3+, 3−). Compute the information gain, and compare it with an attribute that splits into (9+, 0−) and (0+, 5−).

Step 1 — the parent

\(p_{+} = 9/14 = 0.643, p_{-} = 5/14 = 0.357\)

\(H = -0.643 \log_{2}0.643 - 0.357 \log_{2}0.357 =\) −0.643(−0.637) \(- 0.357(-1.485)\)

\(= 0.410 + 0.530 = 0.940\) bits

Step 2 — the children

Weak: \(6+ 2-, p = 0.75\). \(H = -0.75 \log_{2}0.75 - 0.25 \log_{2}0.25 = 0.311 + 0.5 = 0.811\)

Strong: \(3+ 3-, p = 0.5\). \(H = 1.000\) — a perfectly mixed node, the worst possible.

Step 3 — weighted average, then subtract

Weights: \(8/14 = 0.571\) and \(6/14 = 0.429\)

\(H(\text{after}) = 0.571(0.811) + 0.429(1.000) = 0.463 + 0.429 = 0.892\)

Gain \(= 0.940 - 0.892 = 0.048\) bits

Step 4 — the perfect split, for contrast

Both children are pure, so both entropies are 0 and \(H(\text{after}) = 0\).

Gain \(= 0.940 - 0 = 0.940\) bits — the entire entropy of the parent, which is the maximum any split can achieve.

Answer. Wind gains 0.048 bits; the perfect split gains 0.940. ID3 chooses the latter.

Comment. 0.048 bits is a poor split, and the reason is visible in the children: Wind \(=\) Strong is 3+ 3−, which is exactly as uninformative as knowing nothing. A split is only worth having if at least one branch is purer than what you started with.

The first example grows a complete tree, which the chapter has so far only started. The three that follow use other data sets to bring in the remaining ideas: the Gini index with binary splits, a numeric attribute that needs a threshold, and the gain ratio that stops an identifier column from winning.

Example 6.3: Growing the whole ID3 tree on the PlayTennis data

Problem. Fourteen days are recorded with the weather and whether tennis was played. Use ID3 with information gain to build the complete tree, and write down the rules it encodes.

Day Outlook Temperature Humidity Wind Play
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No

Step 1 — entropy of the whole set

Nine Yes and five No, so \(p_{+} = 9/14 = 0.6429\) and \(p_{-} = 5/14 = 0.3571\).

\(H(S) = -(0.6429)(-0.6374) - (0.3571)(-1.4854) = 0.4098 + 0.5305 = 0.9403\) bits

Step 2 — the gain of every attribute at the root

Outlook splits the days into Sunny (2+, 3−), Overcast (4+, 0−) and Rain (3+, 2−). The Sunny and Rain nodes both have entropy \(-(2/5)\log_{2}(2/5) - (3/5)\log_{2}(3/5) = 0.9710\), and Overcast is pure.

\(H(\text{after}) = (5/14)(0.9710) + (4/14)(0) + (5/14)(0.9710) = 0.3468 + 0 + 0.3468 = 0.6935\)

\(\text{Gain}(\text{Outlook}) = 0.9403 - 0.6935 = 0.2467\)

The other three attributes are worked in the same three lines:

Attribute Branches (Yes, No) Child entropies Weighted entropy Gain
Outlook Sunny (2, 3), Overcast (4, 0), Rain (3, 2) 0.9710, 0, 0.9710 0.6935 0.2467
Humidity High (3, 4), Normal (6, 1) 0.9852, 0.5917 0.7885 0.1518
Wind Weak (6, 2), Strong (3, 3) 0.8113, 1.0000 0.8922 0.0481
Temperature Hot (2, 2), Mild (4, 2), Cool (3, 1) 1.0000, 0.9183, 0.8113 0.9111 0.0292

Outlook has the largest gain, so it is the root.

Step 3 — the Overcast branch

D3, D7, D12 and D13 are all Yes. The node is pure, so it becomes a leaf labelled Yes.

Step 4 — the Sunny branch

The node holds D1, D2, D8, D9 and D11: two Yes and three No, entropy 0.9710. Outlook is used up on this path, so only the other three attributes compete.

  • Humidity: High \(= \{\)D1, D2, D8\(\}\) is (0+, 3−) and Normal \(= \{\)D9, D11\(\}\) is (2+, 0−). Both are pure, so the weighted entropy is 0 and the gain is \(0.9710 - 0 = 0.9710\), the most any split of this node could achieve.
  • Temperature: Hot (0, 2) and Cool (1, 0) are pure, Mild \(= \{\)D8, D11\(\}\) is (1, 1) with entropy 1. Weighted \(= (2/5)(1) = 0.4000\), gain \(= 0.5710\).
  • Wind: Weak (1, 2) has entropy 0.9183 and Strong (1, 1) has 1. Weighted \(= (3/5)(0.9183) + (2/5)(1) = 0.9510\), gain \(= 0.0200\).

Humidity wins and both of its branches are pure leaves: High gives No and Normal gives Yes.

Step 5 — the Rain branch

The node holds D4, D5, D6, D10 and D14: three Yes and two No, entropy 0.9710.

  • Wind: Weak \(= \{\)D4, D5, D10\(\}\) is (3, 0) and Strong \(= \{\)D6, D14\(\}\) is (0, 2). Both are pure, so the gain is 0.9710.
  • Temperature and Humidity each leave a weighted entropy of 0.9510, so each has a gain of only 0.0200.

Wind wins: Weak gives Yes and Strong gives No.

Step 6 — the finished tree and its rules

The complete ID3 tree for the PlayTennis data. Every leaf is pure, with the number of training days in each leaf shown beneath it. Temperature is never tested.

R1: IF Outlook = Overcast                     THEN Play = Yes
R2: IF Outlook = Sunny AND Humidity = High    THEN Play = No
R3: IF Outlook = Sunny AND Humidity = Normal  THEN Play = Yes
R4: IF Outlook = Rain  AND Wind = Weak        THEN Play = Yes
R5: IF Outlook = Rain  AND Wind = Strong      THEN Play = No

Answer. Root Outlook (gain 0.2467); Sunny splits on Humidity, Rain splits on Wind, Overcast is a leaf. The tree has depth 2, three internal nodes and five leaves, and classifies all 14 training days correctly.

Comment. Temperature is never used: once Outlook is known it adds nothing. At the Rain node, Temperature and Humidity tie at 0.0200; a tie means that neither attribute is informative there, and ID3 breaks it arbitrarily. The 100% training accuracy is no evidence that the tree will do well on new days, which is the point of the pruning discussion above.

Example 6.4: The Gini index and CART's binary splits

Problem. For the buys_computer data below, compute the Gini index of the whole set, evaluate every binary split of every attribute, and decide which split CART puts at the root.

RID Age Income Student Credit rating Buys computer
1 youth high no fair no
2 youth high no excellent no
3 middle-aged high no fair yes
4 senior medium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7 middle-aged low yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 senior medium yes fair yes
11 youth medium yes excellent yes
12 middle-aged medium no excellent yes
13 middle-aged high yes fair yes
14 senior medium no excellent no

Step 1 — Gini index of the whole set

Nine yes and five no:

\(\text{Gini}(D) = 1 - (9/14)^{2} - (5/14)^{2} = 1 - 0.4133 - 0.1276 = 0.4592\)

Step 2 — list the candidate splits

CART tests only two-way splits. An attribute with \(v\) values can be divided into two groups in \(2^{v-1} - 1\) ways, so Age and Income (three values each) give 3 splits apiece, and Student and Credit rating (two values) give 1 apiece: eight candidates in all.

Step 3 — one split in full: Age, {middle-aged} against {youth, senior}

Left (RID 3, 7, 12, 13): 4 yes, 0 no, so \(\text{Gini} = 1 - 1 - 0 = 0\).

Right (the other 10 rows): 5 yes, 5 no, so \(\text{Gini} = 1 - 0.5^{2} - 0.5^{2} = 0.5000\).

\(\text{Gini}_{\text{split}} = (4/14)(0) + (10/14)(0.5000) = 0.3571\)

Reduction \(= 0.4592 - 0.3571 = 0.1020\)

Step 4 — all eight splits

Split (left group against the rest) Left (yes, no) Right (yes, no) Gini of left, right Weighted Gini Reduction
Age in (4, 0) (5, 5) 0.0000, 0.5000 0.3571 0.1020
Student = no (3, 4) (6, 1) 0.4898, 0.2449 0.3673 0.0918
Age in (2, 3) (7, 2) 0.4800, 0.3457 0.3937 0.0655
Credit = excellent (3, 3) (6, 2) 0.5000, 0.3750 0.4286 0.0306
Income in (2, 2) (7, 3) 0.5000, 0.4200 0.4429 0.0163
Income in (3, 1) (6, 4) 0.3750, 0.4800 0.4500 0.0092
Age in (3, 2) (6, 3) 0.4800, 0.4444 0.4571 0.0020
Income in (4, 2) (5, 3) 0.4444, 0.4688 0.4583 0.0009

Step 5 — the second level

The {middle-aged} branch is a pure leaf (buys \(=\) yes). The other branch holds 10 rows, 5 yes and 5 no, with Gini 0.5000. Repeating the search on those rows, Student = no gives left (1, 4) and right (4, 1), each with Gini \(1 - 0.8^{2} - 0.2^{2} = 0.32\), so the weighted Gini is 0.3200. The next best candidates, Income in {high} (0.3750) and Credit = excellent (0.4167), are clearly worse, so Student is the second test.

Answer. The root split is Age \(\in \{\text{middle-aged}\}\) (weighted Gini 0.3571, reduction 0.1020), followed on the remaining rows by Student.

Comment. The runner-up, Student, is close (0.3673 against 0.3571). ID3 on the same table, with a three-way split on every attribute, gives information gains of 0.2467 for Age, 0.1518 for Student, 0.0481 for Credit rating and 0.0292 for Income, so it also puts Age at the root. The two criteria usually agree. Never compare a Gini value with an entropy value: for two classes Gini cannot exceed 0.5, whereas entropy reaches 1.

Example 6.5: A numeric attribute and its best threshold

Problem. Ten students are described by the hours they studied and by the result. Find the best binary test of the form \(\text{Hours} \le t\) on the information-gain criterion.

Student R01 R02 R03 R04 R05 R06 R07 R08 R09 R10
Hours studied 1.0 2.0 3.5 4.0 4.5 5.5 6.0 7.0 8.0 9.5
Result Fail Fail Fail Pass Fail Pass Pass Fail Pass Pass

Step 1 — entropy of the whole set

Five Pass and five Fail, so \(H(S) = 0.5 + 0.5 = 1.0000\) bit.

Step 2 — which thresholds are worth trying

The values are already sorted. A threshold is placed midway between two neighbouring values, and a cut inside a run of identical labels can never be the best one, so only the places where the label changes are tested:

Hours:   1.0  2.0  3.5 | 4.0 | 4.5  5.5  6.0 | 7.0 | 8.0  9.5
Result:   F    F    F  |  P  |  F    P    P  |  F  |  P    P

The label changes between 3.5 and 4.0, 4.0 and 4.5, 4.5 and 5.5, 6.0 and 7.0, and 7.0 and 8.0, giving the candidate thresholds \(t = 3.75, 4.25, 5.00, 6.50\) and \(7.50\). (Four of the nine midpoints are skipped.)

Step 3 — one threshold in full: \(t = 3.75\)

Left (\(\text{Hours} \le 3.75\)): 1.0, 2.0, 3.5, which is (0 Pass, 3 Fail), so \(H = 0\).

Right: seven students, (5 Pass, 2 Fail):

\(H = -(5/7)\log_{2}(5/7) - (2/7)\log_{2}(2/7) = 0.3467 + 0.5164 = 0.8631\)

\(H(\text{after}) = (3/10)(0) + (7/10)(0.8631) = 0.6042\)

\(\text{Gain} = 1.0000 - 0.6042 = 0.3958\)

Step 4 — the other four thresholds

\(t\) Left (Pass, Fail) Right (Pass, Fail) Left \(H\) Right \(H\) Weighted \(H\) Gain
3.75 (0, 3) (5, 2) 0.0000 0.8631 0.6042 0.3958
4.25 (1, 3) (4, 2) 0.8113 0.9183 0.8755 0.1245
5.00 (1, 4) (4, 1) 0.7219 0.7219 0.7219 0.2781
6.50 (3, 4) (2, 1) 0.9852 0.9183 0.9651 0.0349
7.50 (3, 5) (2, 0) 0.9544 0.0000 0.7635 0.2365

Answer. The best test is \(\text{Hours} \le 3.75\), with a gain of 0.3958 bits.

Comment. The skipped midpoints cannot beat it: those at 1.5, 2.75, 5.75 and 8.75 give gains of 0.1080, 0.2365, 0.1245 and 0.1080. The Gini index agrees about the winner, since the weighted Gini of the 3.75 cut is \((7/10)(0.4082) = 0.2857\), against 0.3200 for the next best, 5.00. Once the best cut is found, the whole numeric attribute is represented by that one yes/no question when it competes with the categorical attributes, and, unlike a categorical attribute, it may be tested again lower in the tree with a different threshold.

Example 6.6: The gain ratio and the identifier column

Problem. The ten students of the last example also have a roll number and an attendance level (Low, Medium or High). The attendance and result columns are:

Student R01 R02 R03 R04 R05 R06 R07 R08 R09 R10
Attendance Low Low Medium High Medium High Medium Low High High
Result Fail Fail Fail Pass Fail Pass Pass Fail Pass Pass

Compute the information gain and the gain ratio of RollNo, Attendance and the threshold test \(\text{Hours} \le 3.75\) from the last example. Which attribute does plain information gain choose, and which does C4.5?

Step 1 — the formulas

\[\text{SplitInfo}(S, A) = -\sum_{v} \frac{|S_{v}|}{|S|} \log_{2} \frac{|S_{v}|}{|S|}, \qquad \text{GainRatio}(S, A) = \frac{\text{Gain}(S, A)}{\text{SplitInfo}(S, A)}\]

SplitInfo is the entropy of the sizes of the branches, ignoring the classes. The more branches, the larger it is.

Step 2 — Attendance

Low \(= \{\)R01, R02, R08\(\}\) is (0 Pass, 3 Fail), so \(H = 0\). High \(= \{\)R04, R06, R09, R10\(\}\) is (4, 0), so \(H = 0\). Medium \(= \{\)R03, R05, R07\(\}\) is (1, 2), so \(H = 0.9183\).

\(H(\text{after}) = (3/10)(0) + (3/10)(0.9183) + (4/10)(0) = 0.2755\)

\(\text{Gain} = 1.0000 - 0.2755 = 0.7245\)

\(\text{SplitInfo} = -(0.3)\log_{2}0.3 - (0.3)\log_{2}0.3 - (0.4)\log_{2}0.4 = 0.5211 + 0.5211 + 0.5288 = 1.5710\)

\(\text{GainRatio} = 0.7245 / 1.5710 = 0.4612\)

Step 3 — RollNo, ten branches of one student each

Every branch is pure, so \(H(\text{after}) = 0\) and \(\text{Gain} = 1.0000\), the largest value possible.

\(\text{SplitInfo} = -10 \times (1/10)\log_{2}(1/10) = \log_{2}10 = 3.3219\)

\(\text{GainRatio} = 1.0000 / 3.3219 = 0.3010\)

Step 4 — the threshold test

From the last example, Gain \(= 0.3958\). The two branches hold 3 and 7 students:

\(\text{SplitInfo} = -(0.3)\log_{2}0.3 - (0.7)\log_{2}0.7 = 0.5211 + 0.3602 = 0.8813\)

\(\text{GainRatio} = 0.3958 / 0.8813 = 0.4491\)

Step 5 — compare

Attribute Branches Gain SplitInfo Gain ratio
RollNo 10 1.0000 3.3219 0.3010
Attendance 3 0.7245 1.5710 0.4612
\(\text{Hours} \le 3.75\) 2 0.3958 0.8813 0.4491

Answer. Information gain would choose RollNo, giving a ten-leaf tree that is perfect on the training set and useless on a new student. C4.5 chooses Attendance (gain ratio 0.4612).

Comment. Gain ratio has a weakness of its own: when SplitInfo is tiny, the ratio becomes huge for a nearly useless split. C4.5 therefore considers only attributes whose gain is at least the average over the candidates (here \((1.0000 + 0.7245 + 0.3958)/3 = 0.7068\)) and ranks those by gain ratio. That rule removes the threshold test, leaving RollNo and Attendance, and Attendance wins on ratio. In a real project the simplest remedy is to delete identifier columns before training.

6.5 Common mistakes to avoid

Each of the following is a mistake that costs marks in an examination or accuracy in practice.

  • Do not use ln when the question says entropy in bits. Divide by ln 2, or use \(\log_{2}\) directly. A two-class entropy above 1 is always this error.
  • Do not forget the weights in information gain. The child entropies are averaged in proportion to how many examples went each way.

6.6 Summary

After working through this chapter you should be able to do the following.

  • Compute entropy, Gini and information gain from counts, and choose a split the way ID3 does. You can explain why gain is biased towards many-valued attributes, and what the gain ratio does about it. You can describe both kinds of pruning, and the overfitting they exist to stop.

6.7 Exercises

  1. A node has 12 positive and 4 negative examples. Compute its entropy and Gini index.

    Answer

    With \(p_{+} = 0.75\) and \(p_{-} = 0.25\):

    \(H = -0.75\log_{2}0.75 - 0.25\log_{2}0.25 = 0.3113 + 0.5000 = 0.8113\) bits

    \(\text{Gini} = 1 - 0.75^{2} - 0.25^{2} = 1 - 0.5625 - 0.0625 = 0.375\)

  2. A split gives (8+, 0−) and (4+, 4−) from that node. Compute the information gain.

    Answer

    The first child is pure, \(H = 0\). The second is an even mix, \(H = 1\). The weights are \(8/16\) each, so

    \(H(\text{after}) = 0.5(0) + 0.5(1) = 0.5\)

    \(\text{Gain} = 0.8113 - 0.5 = 0.3113\) bits

  3. Why does plain information gain prefer an attribute with 50 distinct values, and what does C4.5 do about it?

    Answer

    Splitting on many values produces many small groups, and small groups are pure by chance. If the attribute is an identifier (50 values for 50 examples) every branch holds a single example, every child has entropy 0, the remainder is 0 and the gain equals the whole entropy of the node, the largest value any attribute can reach. The tree would have 50 leaves, fit the training set perfectly and generalise to nothing.

    C4.5 divides the gain by the split information, the entropy of the branch sizes. For 50 equal singleton branches this is \(\log_{2}50 = 5.64\) bits, so the gain ratio is only \(H(S)/5.64\), while an honest two-way split has a split information of at most 1 and loses nothing. C4.5 also ranks by gain ratio only the attributes whose gain is at least average, because the ratio can be inflated when the split information is very small. CART avoids the problem differently, by allowing only binary splits.

  4. A node has 10 examples, 6 positive and 4 negative. The attribute Wind splits it into Weak (4+, 1−) and Strong (2+, 3−). Compute the parent entropy, the information gain, and then the same split's gain under the Gini index.

    Answer

    Entropy: \(H(\text{parent}) = 0.9710\), \(H(\text{Weak}) = 0.7219\), \(H(\text{Strong}) = 0.9710\). The weights are \(5/10\) each, so \(H(\text{after}) = 0.5(0.7219) + 0.5(0.9710) = 0.8464\) and the gain is \(0.9710 - 0.8464 \approx 0.1245\) bits (0.1245 from unrounded values).

    Gini: parent \(1 - 0.6^{2} - 0.4^{2} = 0.48\); Weak \(1 - 0.8^{2} - 0.2^{2} = 0.32\); Strong \(1 - 0.4^{2} - 0.6^{2} = 0.48\). Weighted \(= 0.5(0.32) + 0.5(0.48) = 0.40\), so the Gini reduction is \(0.48 - 0.40 = 0.08\).

    Both criteria call the split worthwhile but modest. The two numbers (0.1245 and 0.08) are on different scales and must not be compared with each other.

  5. Five people are recorded with their age group, whether they are students and whether they bought the product.

    Person Age Student Buys
    1 Young No No
    2 Young Yes Yes
    3 Old Yes Yes
    4 Old No No
    5 Middle Yes Yes

    Compute the information gain of splitting on Age and on Student. Which does ID3 choose for the root?

    Answer

    Three Yes and two No: \(H(S) = 0.9710\).

    Age: Young is (1+, 1−) with \(H = 1\); Old is (1+, 1−) with \(H = 1\); Middle is (1+, 0−) with \(H = 0\). \(H(\text{after}) = (2/5)(1) + (2/5)(1) + (1/5)(0) = 0.8\), so \(\text{Gain}(\text{Age}) = 0.9710 - 0.8 = 0.1710\).

    Student: Yes holds persons 2, 3, 5, all of whom buy, and No holds persons 1 and 4, neither of whom buys. Both children are pure, so \(H(\text{after}) = 0\) and \(\text{Gain}(\text{Student}) = 0.9710\).

    ID3 chooses Student, which classifies all five people correctly with one test.

  6. A data set has 10 positive and 6 negative examples. (a) Compute its entropy. (b) Node X holds 12 Yes and 0 No; node Y holds 6 Yes and 6 No. Compute their entropies and say which is pure and which is maximally impure.

    Answer

    (a) \(p_{+} = 0.625\), \(p_{-} = 0.375\): \(H = 0.625(0.6781) + 0.375(1.4150) = 0.4238 + 0.5306 = 0.9544\) bits.

    (b) \(H(X) = 0\), since one class has probability 1 and \(0 \log_{2} 0\) is taken as 0; node X is pure. \(H(Y) = 1\) bit, the maximum for two classes; node Y is maximally impure.

  7. Attribute X splits a set into three pure subsets. Attribute Y splits the same set into three impure subsets. Without computing anything, say which attribute ID3 selects, and why.

    Answer

    X. The weighted average of the child entropies is zero for X, since every child is pure, so its gain equals the entropy of the parent, the largest gain any split can have. For Y every child has positive entropy, so the weighted average is positive and the gain is strictly smaller. (Unless X is something like an identifier with a branch for every example, in which case gain ratio, not gain, is the fairer judge.)

  8. At the Rain node of the PlayTennis tree the five days are as below.

    Day Temperature Humidity Wind Play
    D4 Mild High Weak Yes
    D5 Cool Normal Weak Yes
    D6 Cool Normal Strong No
    D10 Mild Normal Weak Yes
    D14 Mild High Strong No

    Compute the gain of each of the three attributes. Two of them tie; what is the tie telling you?

    Answer

    The node has 3 Yes and 2 No, \(H = 0.9710\).

    Wind: Weak \(= \{\)D4, D5, D10\(\}\) is all Yes and Strong \(= \{\)D6, D14\(\}\) is all No. The weighted entropy is 0 and the gain is 0.9710.

    Temperature: Mild (D4, D10, D14) is (2+, 1−) with \(H = 0.9183\), and Cool (D5, D6) is (1+, 1−) with \(H = 1\). Weighted \(= (3/5)(0.9183) + (2/5)(1) = 0.9510\), gain \(0.0200\).

    Humidity: High (D4, D14) is (1+, 1−) and Normal (D5, D6, D10) is (2+, 1−), the same two entropies in the same proportions, so the weighted entropy is again 0.9510 and the gain 0.0200.

    Temperature and Humidity tie at 0.0200, a gain so small that neither says anything about the outcome at this node; the tie is broken arbitrarily (by column order, say), and the choice does not matter because the winner, Wind, is far better.

  9. Ten students studied for the hours shown and either passed or failed.

    Hours 1.0 2.0 3.5 4.0 4.5 5.5 6.0 7.0 8.0 9.5
    Result F F F P F P P F P P

    Compute the Gini index of the whole set and the Gini reduction for the tests \(\text{Hours} \le 3.75\) and \(\text{Hours} \le 5.00\). Which test does CART prefer?

    Answer

    The root has 5 P and 5 F: \(\text{Gini} = 1 - 0.25 - 0.25 = 0.5000\).

    \(\text{Hours} \le 3.75\): left is (0 P, 3 F), \(\text{Gini} = 0\); right is (5 P, 2 F), \(\text{Gini} = 1 - (5/7)^{2} - (2/7)^{2} = 0.4082\). Weighted \(= 0.7(0.4082) = 0.2857\), so the reduction is \(0.2143\).

    \(\text{Hours} \le 5.00\): left is (1 P, 4 F), \(\text{Gini} = 1 - 0.04 - 0.64 = 0.32\); right is (4 P, 1 F), also 0.32. Weighted \(= 0.32\), so the reduction is \(0.18\).

    CART prefers \(\text{Hours} \le 3.75\), the larger reduction, which is also the threshold that maximises information gain on these data.

  10. How many different two-way splits of the values can CART consider for a categorical attribute with 3 values? With 5 values? Why can the number of tests for a numeric attribute never exceed the number of distinct values minus one?

    Answer

    The number is \(2^{v-1} - 1\): for \(v = 3\) it is \(2^{2} - 1 = 3\), and for \(v = 5\) it is \(2^{4} - 1 = 15\). (There are \(2^{v}\) ways to assign each value to the left or the right group, half of them mirror images, and the case with an empty group is excluded.)

    For a numeric attribute a test \(x \le t\) only changes which examples go left when \(t\) passes one of the observed values, so the distinct partitions correspond to the gaps between consecutive sorted values. With \(n\) distinct values there are \(n - 1\) gaps, and C4.5 and CART need examine only those where the class label changes.

  11. Explain why a tree grown until every leaf is pure usually does badly on new data, name one pre-pruning and one post-pruning remedy, and say how tree depth relates to bias and variance.

    Answer

    A tree grown to purity carves a small region around every training point, noisy ones included, so it fits the training set perfectly (training accuracy 100% unless two identical examples carry different labels) but has memorised noise. A new example near a noisy point is then misclassified, and test accuracy falls.

    Pre-pruning stops growth early: a maximum depth, a minimum number of examples needed to split a node, or a minimum gain. Post-pruning grows the full tree and then removes subtrees, for example reduced-error pruning (remove a subtree if validation accuracy does not fall) or cost-complexity pruning (minimise error plus \(\alpha\) times the number of leaves).

    Depth is the tree's bias-variance dial. A shallow tree has high bias and low variance; a deep tree has low bias and high variance. Pruning moves the tree back towards the middle, giving up a little training accuracy for a lot of generalisation.

  12. True or false, with a reason: "A decision tree grown until every leaf is pure always generalises well to new data."

    Answer

    False. Purity of every leaf is perfection on the training set, which for noisy data means the tree has fitted the noise. It overfits (low bias, high variance), and pruning or a depth limit is needed to make it generalise.

  13. Entropy and the Gini index usually choose the same attribute. Why is it still wrong to compare a Gini reduction of 0.08 with an information gain of 0.1245 bits, and why do many libraries default to Gini?

    Answer

    The two measures live on different scales: for two classes the Gini index is at most 0.5 and entropy at most 1 bit, so a number from one is not comparable with a number from the other; only splits scored by the same measure can be ranked against each other. Gini is cheaper because it needs squares where entropy needs logarithms, and in practice the two usually pick the same split, which is why CART and scikit-learn's default (criterion="gini") use it.