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

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.

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.

6. Make splitting and pruning reproducible
At each node:
Count classes and calculate parent impurity.
Enumerate categorical groups and numeric midpoint thresholds.
Calculate row-weighted child impurity and keep the largest gain.
Enforce depth and sample constraints, then recurse.
Compare pruning candidates on validation data from the bottom upward.
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 | 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
Measure parent impurity.
Enumerate legal questions.
Weight each child by row count.
Choose the largest gain.
Stop tiny or unhelpful growth.
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.
Keep learning
B-Trees and B+ Trees: Structure, Splits and Insertion
Trace the same eight keys through an order-4 B-tree and B+ tree. The worked states show exactly when a key moves, when it is copied and how the final trees differ.
Backtracking Technique Interview Questions and Answers: Trace, Prune and Explain
Learn to explain backtracking through exact traces, safe pruning, clean state restoration, N-Queens constraints, complexity derivation and interview follow-ups.
Smart Pointers in C++: unique_ptr, shared_ptr and weak_ptr with Worked Examples
Learn who owns a C++ object, when it is destroyed, and how to choose among unique_ptr, shared_ptr, weak_ptr and a borrowed raw pointer.
SSC JE Cutoff Trends: Compare Branches and Set a Practical Target Score
Clearing the qualifying minimum and reaching the shortlisting cutoff are different goals. Compare SSC JE Paper-I results, then turn a historical reference into a mock target and an error-ledger plan.





