Information Gain and Full Tree Construction

You found the best root split in post 01: Employed. But one split doesn't make a tree. The left child (Employed=No, 4 samples) still has a mix of Yes and No. The right child (Employed=Yes, 6 samples) does too. A good tree keeps splitting until the leaves are pure or you run out of features.

This post builds the full tree level by level — computing Information Gain at each node, choosing splits, and seeing how the tree would predict new loan applications.

Same anchor dataset: 10-sample loan approval.

import pandas as pd
import numpy as np

data = pd.DataFrame({
    'income':   ['Low','Low','Low','High','High','High','Low','High','Low','High'],
    'employed': ['No', 'Yes','Yes','No',  'Yes', 'Yes', 'No', 'No',  'Yes','Yes'],
    'approved': ['No', 'No', 'Yes','No',  'Yes', 'Yes', 'No', 'Yes', 'Yes','Yes']
})

What It Is

Information Gain measures how much a feature reduces label uncertainty. If splitting on a feature drops entropy from 0.88 to 0.71, the Information Gain is 0.17 bits. The higher the gain, the better the split. This is not the same as feature importance in linear regression — there, coefficients tell you direction and magnitude. Here, IG tells you only how much a feature helps separate the classes, with no assumption about the relationship being linear.

The Plan — Four Levels to a Complete Tree

We'll build the full decision tree level by level. Level 0 is the root split (Employed). Level 1 splits both children on Income. At the end we have 4 leaf nodes, and we trace predictions for new loan applications.

Level 0: Root Node

Here's where we left off. All 10 samples at the root: $H(\text{root})=0.882$ bits.

Best split: Employed. Creates two children:

Left branch (Employed=No): Rows 0, 3, 6, 7 → Income=[Low,High,Low,High], Approved=[No,No,No,Yes] → Yes=1, No=3

Right branch (Employed=Yes): Rows 1, 2, 4, 5, 8, 9 → Approved=[No,Yes,Yes,Yes,Yes,Yes] → Yes=5, No=1

✓ Level 0 complete. Root split on Employed with IG = 0.168 bits.

Level 1: Left Node (Employed=No, 4 samples)

Goal: decide whether to split this node further, and on which feature.

Samples: Income=[Low,High,Low,High], Approved=[No,No,No,Yes]

$P(\text{Yes})=1/4=0.25$, $H_{\text{left}}=0.811$ bits. Not pure — can we split further?

Only one remaining feature (Income). Let's compute its IG:

• Income=Low (2 samples): [No, No] → Yes=0, No=2. $H=0$ (pure!)
• Income=High (2 samples): [No, Yes] → Yes=1, No=1. $H=1.0$ bits

Weighted $H=(2/4)\times 0+(2/4)\times 1.0=0.5$ bits

$\text{IG}(\text{Income}\mid \text{Employed=No})=0.811-0.5=0.311\text{ bits}$

Split on Income.

• Left-Left (Employed=No, Income=Low): 2 samples, both No → $H=0$. Predict: No ✓
• Left-Right (Employed=No, Income=High): 2 samples [No, Yes] → $H=1.0$. No features remain. Tie (1:1). Predict: No (majority class of the left parent, which is 3/4 No)

✓ Level 1 (left) complete. Split on Income, IG = 0.311 bits. Two leaves created: one pure (No), one tie (No by parent majority).

Level 1: Right Node (Employed=Yes, 6 samples)

Same goal: should we split this node further?

Samples: Income=[Low,High,High,High,Low,High], Approved=[No,Yes,Yes,Yes,Yes,Yes]

$P(\text{Yes})=5/6$, $H_{\text{right}}=0.650$ bits. Still impure.

Test Income — the one remaining feature:

• Income=Low (2 samples, rows 1 and 8): [No, Yes] → Yes=1, No=1. $H=1.0$ bits
• Income=High (4 samples, rows 2, 4, 5, 9): [Yes, Yes, Yes, Yes] → Yes=4, No=0. $H=0$ (pure!)

Weighted $H=(2/6)\times 1.0+(4/6)\times 0=0.333$ bits

$\text{IG}(\text{Income}\mid \text{Employed=Yes})=0.650-0.333=0.317\text{ bits}$

Split on Income.

• Right-Left (Employed=Yes, Income=Low): 2 samples [No, Yes] → $H=1.0$. Tie. Predict: Yes (majority of right parent, which is 5/6 Yes)
• Right-Right (Employed=Yes, Income=High): 4 samples, all Yes → $H=0$. Predict: Yes ✓

✓ Level 1 (right) complete. Split on Income, IG = 0.317 bits. Two leaves: one tie (Yes by parent majority), one pure (Yes).

Final Tree Structure

Employed?
             /           \
           No              Yes
         Income?          Income?
        /       \         /       \
      Low       High   Low       High
    [No,No]  [No,Yes]  [No,Yes]  [Yes,Yes,Yes,Yes]
    →No      →No(tie)  →Yes(tie)  →Yes

Two leaves are pure (green); two are impure ties (red) — resolved by the parent's majority class.

Trace Table: Full Tree Construction

Prediction Trace for New Samples

Information Gain Ratio (C4.5 Variant)

Plain Information Gain has a problem we need to fix: it's biased toward features with many distinct values. A feature that assigns each sample to its own unique bucket — like a sample ID — always achieves IG = H(root). That's perfect information, but it just memorizes the data.

The fix is to normalize IG by the entropy of the feature itself. Here's what that looks like in symbols:

$\text{SplitInfo}(A)=-{\sum }_v\frac{|S_v|}{|S|}{\log }_2\frac{|S_v|}{|S|}$

$\text{GainRatio}(A)=\frac{\text{IG}(A)}{\text{SplitInfo}(A)}$

Let's compute it for both features. Income splits evenly (5 Low, 5 High):

$\text{SplitInfo}(\text{Income})=-2\times (0.5\times {\log }_{2}0.5)=1.0\text{ bit}$ $\text{GainRatio}=0.035/1.0=0.035$

Employed splits unevenly (4 No, 6 Yes):

$\text{SplitInfo}(\text{Employed})=-(0.4\times {\log }_{2}0.4+0.6\times {\log }_{2}0.6)=0.529+0.442=0.971$ $\text{GainRatio}=0.168/0.971=0.173$

Both Gain Ratio and plain IG select Employed. The adjustment doesn't change the decision on this dataset — but on datasets with high-cardinality features (zip code, user ID), it prevents the model from trivially splitting on a unique identifier.

Related Concepts

Information Gain extends directly from entropy (post 01) by measuring how much a feature reduces label uncertainty. The same greedy best-first approach — choose the locally optimal split, recurse — underlies ID3 (Quinlan, 1986) and CART (Breiman, 1984). The same idea appears in gradient boosting: each boosting round greedily fits a regression tree on the residuals from the previous model. Understanding tree construction here directly prepares you for why boosted trees work — and why they overfit in the same ways a single deep tree does.

Honest Limitations

Here's something that tripped me up early on: greedy construction never backtracks. If the first split is a bad one, the entire tree below it is locked in — there's no way to go back and pick a different root. I've seen two trees trained on the same data with different random_state seeds produce completely different structures because the IG values at the root were close. The algorithm commits, and downstream nodes pay for that commitment.

I've also learned the hard way that IG favors high-cardinality features even after Gain Ratio correction. A feature like user ID achieves near-perfect IG at every node and will dominate splits unless removed before training. Now, feature cardinality is the first thing I check before fitting a decision tree — it's saved me from silently overfitting more than once.

sklearn Tree Visualization

Let's verify our manual tree with sklearn. We set random_state=42 for reproducibility and max_depth=2 since we know our dataset only needs 2 levels. The export_text function prints a readable text version of the tree structure.

from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.preprocessing import LabelEncoder
import numpy as np

le_inc = LabelEncoder(); le_emp = LabelEncoder(); le_app = LabelEncoder()
X = np.column_stack([le_inc.fit_transform(data['income']),
                     le_emp.fit_transform(data['employed'])])
y = le_app.fit_transform(data['approved'])

dt = DecisionTreeClassifier(criterion='entropy', max_depth=2, random_state=42)
dt.fit(X, y)

print(export_text(dt, feature_names=['income', 'employed']))

|--- employed <= 0.50
|   |--- income <= 0.50
|   |   |--- class: 0
|   |--- income >  0.50
|   |   |--- class: 0
|--- employed >  0.50
|   |--- income <= 0.50
|   |   |--- class: 1
|   |--- income >  0.50
|   |   |--- class: 1

The root split is on employed — matches our manual calculation. Low Income (≤0.5) maps to No (class 0) under both Employed=No branches.

Test Your Understanding

1. At the tie leaf (Employed=No, Income=High): 1 Yes, 1 No. The tree predicts No (following the parent majority). If this leaf received 10 new predictions where 7 were actually Yes, what would be the local accuracy of this leaf? Is this evidence of underfitting or a data limitation?

2. Information Gain at the root was IG(Employed)=0.168. At the right node (Employed=Yes), IG(Income)=0.317 — larger than the root. Does this mean Income is a better feature than Employed overall? Explain why deeper nodes can have higher IG than the root.

3. GainRatio penalizes features with unequal splits. A feature with only 1 sample in one branch and 9 in the other has $\text{SplitInfo}=-(0.1{\log }_{2}0.1+0.9{\log }_{2}0.9)=0.469$ bits — lower than a 50/50 split. If IG = 0.2 bits for this feature, what is its GainRatio? Is this higher or lower than a feature with IG=0.15 and a 50/50 split?

4. The tree has depth 2 with 4 leaves for 10 samples. The unpruned tree (no max_depth) could create up to 10 leaves. Compute the entropy of each possible pure leaf (1 sample each). What would be the training accuracy?

5. export_text encodes "Low" and "High" as 0 and 1 (alphabetical LabelEncoder order). If you forgot to check the encoding and assumed 0=High and 1=Low, your prediction for {income=High, employed=Yes} would be wrong. How would you verify the encoding direction from the sklearn output?