Decision Trees: Calculate Information Gain and Prune Weak Branches

Build one classification tree by hand from ten machine rows, audit every candidate threshold, and see why validation can justify removing a perfectly pure training branch.

KnowledgeGate Team

Exam prep & CS education

Updated 15 Nov 20266 min read
Decision Trees: Calculate Information Gain and Prune Weak Branches

A decision tree looks obvious after software draws it, but every branch compares candidate splits. Even a perfectly pure training branch can be the model's weakest part. Ten machines, two features and a binary fault label show both effects: entropy selects Temperature <= 67.5 with information gain 0.6100, while validation later removes a tiny memorised subtree. For a wider map of model families, see Approaches to AI.

1. Decision trees turn labelled rows into questions

A classification tree recursively partitions rows. An internal node asks a feature question, a branch carries an answer, and a leaf predicts a class. Let S be rows at a node and p_c the class c fraction. A useful split makes its children purer than S.

The values are artificial, so they do not model real equipment behaviour or support deployment decisions.

ID

Temperature (degrees C)

Warning

Fault

1

35

No

No

2

40

Yes

No

3

45

No

No

4

50

Yes

Yes

5

55

No

No

6

65

No

No

7

70

Yes

Yes

8

75

No

Yes

9

80

Yes

Yes

10

90

No

Yes

The root has 5 Yes and 5 No. The apparent fault at 50 is the isolated case that tempts excessive growth. Warning is categorical and forms Yes and No groups directly. Temperature is numeric, so thresholds are midpoints between adjacent sorted values. For a wider AI and machine-learning path, browse Skill Development Courses.

2. Calculate root entropy first

Entropy measures class mixture, not accuracy or row count:

H(S) = -sum_c p_c log_2(p_c), with 0 log_2 0 = 0.

A pure binary node has entropy 0; a balanced node has entropy 1 bit. Here, p(Yes)=5/10=0.5 and p(No)=5/10=0.5, so:

H(root) = -0.5 log_2(0.5) - 0.5 log_2(0.5) = 1.0000 bit.

For children S_j, weighted entropy is H_after = sum_j (|S_j|/|S|)H(S_j), and IG = H(parent) - H_after. Weighting matters: one pure row must not count as much as nine mixed rows. Compare every legal candidate and choose the largest positive gain, subject to the stopping rules applied later.

3. Score every split and choose 67.5

For Warning, the Yes child has 3 Fault=Yes, 1 Fault=No and H=0.8113. The No child has 2 Yes, 4 No and H=0.9183.

H_after=(4/10)(0.8113)+(6/10)(0.9183)=0.8755

IG(Warning)=1.0000-0.8755=0.1245

For temperature, sort and test every midpoint:

Threshold

Left Yes/No

Right Yes/No

Information gain

37.5

0/1

5/4

0.1080

42.5

0/2

5/3

0.2365

47.5

0/3

5/2

0.3958

52.5

1/3

4/2

0.1245

60.0

1/4

4/1

0.2781

67.5

1/5

4/0

0.6100

72.5

2/5

3/0

0.3958

77.5

3/5

2/0

0.2365

85.0

4/5

1/0

0.1080

Audit the winner. At Temperature <= 67.5, the left child has 1 Yes, 5 No and H=0.6500; the right has 4 Yes, 0 No and H=0. Thus H_after=(6/10)(0.6500)+(4/10)(0)=0.3900, and IG=1.0000-0.3900=0.6100. Since 0.6100 > 0.1245, temperature wins at this node on this dataset, not universally.

Corrected split audit: temperature IG 0.6100 exceeds warning IG 0.1245 with 4 Yes and 6 No.

4. Grow branches without memorising noise

The Temperature > 67.5 child is pure, with four Yes rows, so it becomes a Yes leaf. The left child has H=0.6500. Splitting it on Warning makes a pure four-row Warning=No child and a two-row Warning=Yes child with 1 Yes, 1 No, entropy 1.

H_after=(4/6)(0)+(2/6)(1)=0.3333

The local gain is 0.6500-0.3333=0.3167. Unrestricted growth then splits the two-row node: temperatures 40 -> No and 50 -> Yes are separated at threshold 45, creating two pure one-row leaves with local gain 1.0000. The resulting four-leaf tree classifies all ten training rows correctly.

Gain alone is not a safety check. min_samples_leaf=2 rejects that last split because both children would have one row. max_depth=2 stops before the third level. A minimum-gain rule would not help because the tiny split has high gain. Purity, no legal split and a fixed leaf budget are other valid stopping reasons.

5. Prune the weak subtree with validation rows

Post-pruning replaces a grown subtree with a leaf when held-out performance does not justify its extra leaves.

Row

Temperature (degrees C)

Warning

Fault

A

42

Yes

No

B

52

Yes

No

C

58

No

No

D

62

Yes

No

E

69

No

Yes

F

75

Yes

Yes

Full-tree predictions are No, Yes, No, Yes, Yes, Yes. B and D are wrong, so accuracy is 4/6. Replace the left subtree with its training-majority class, No, from 5 No versus 1 Yes. Predictions become No, No, No, No, Yes, Yes, giving 6/6. Training accuracy falls from 10/10 to 9/10 because row 4 is no longer memorised. This trade does not prove every smaller tree is better.

With R_alpha(T)=training error rate + alpha x number of leaves, full costs 0 + 4alpha and pruned costs 0.1 + 2alpha. They tie at alpha=0.05. At alpha=0.04, full is 0.16 versus pruned 0.18; at alpha=0.08, full is 0.32 versus pruned 0.26. Select with validation or cross-validation because libraries may scale this objective differently.

Decision-tree pruning comparison showing full four-leaf and pruned two-leaf trees with training and validation results.

6. Make splitting and pruning reproducible

At each node:

  1. Count classes and calculate parent impurity.

  2. Enumerate categorical groups and numeric midpoint thresholds.

  3. Calculate row-weighted child impurity and keep the largest gain.

  4. Enforce depth and sample constraints, then recurse.

  5. Compare pruning candidates on validation data from the bottom upward.

  6. Keep the final test set out of split tuning and pruning.

For the pruned boundary, (Temperature=66, Warning=Yes) goes left because 66 <= 67.5 and predicts No. (Temperature=71, Warning=No) goes right and predicts Yes. Exactly 67.5 also goes left under the locked <= rule. Warning no longer affects this pruned tree.

A Python implementation should log each node's class counts, threshold, gain and leaf prediction. Compare them with the hand calculation before trusting its plot. Python Programming is a broader path for readers building the language foundation for such implementations.

7. Split and pruning traps to repair

Wrong move

What goes wrong

Correct move

Average child entropies equally

Tiny children count too much

Weight by child row count

Reuse parent counts in a child

Child impurity is false

Recount each child

Test numeric thresholds unsorted

Legal midpoints are missed

Sort values first

Change < to <= later

Boundary predictions change

Lock one rule

Accept a one-row leaf as safe

Purity can be memorisation

Apply sample constraints

Tune with the final test set

Reported performance is biased

Prune on validation data

Quick checks: root entropy is 1.0000, not 0.5. Threshold 67.5 gives the highest root gain, 0.6100, and its left child has 6 rows, not 5. The pruning comparison uses validation accuracy of 4/6 versus 6/6, not the training score.

Stopping rules block proposed growth; post-pruning removes a branch after evaluating the larger tree. Artificial Neural Networks MCQs offers adjacent learned-model practice, not questions using this toy dataset.

8. Decision trees short version and next step

  1. Measure parent impurity.

  2. Enumerate legal questions.

  3. Weight each child by row count.

  4. Choose the largest gain.

  5. Stop tiny or unhelpful growth.

  6. Prune branches whose validation value does not justify their complexity.

Here, 67.5 wins with gain 0.6100. Pruning trades training accuracy 10/10 -> 9/10 for validation accuracy 4/6 -> 6/6. Now hide the split table, recompute the Warning gain from 3/1 and 2/4, then explain why gain 1.0000 can still be weak: the split has only two rows and fails on held-out behaviour. Artificial Intelligence (AI) is a broader next path into AI and machine-learning study.