Information Gain and Full Tree Construction

Post 01 showed that splitting on Employed reduces entropy more than splitting on Income. This post builds the full decision tree level by level — computing Information Gain at each node, choosing splits, and tracing predictions on new samples.

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']
})

Information Gain — Formal Definition

$\text{IG}(S,A)=H(S)-{\sum }_v\frac{|S_v|}{|S|}\times H(S_v)$

Where $S$ is the current node's sample set, $A$ is the feature being tested, and $S_v$ is the subset where feature $A$ equals value $v$. Information Gain measures how much entropy decreases after observing feature $A$.

High IG: the feature resolves most of the uncertainty in the labels. Zero IG: the feature tells us nothing — class distributions in each child are identical to the parent.

Level 0: Root Node

All 10 samples. $H(\text{root})=0.882$ bits (computed in post 01).

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 1: Left Node (Employed=No, 4 samples)

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). Test it:

• 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: Right Node (Employed=Yes, 6 samples)

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:

• 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 ✓

Final Tree Structure

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

Prediction Trace for New Samples

Information Gain Ratio (C4.5 Variant)

Plain Information Gain is biased toward features with many distinct values. A feature that assigns each sample to its own unique bucket always achieves IG = H(root) — perfect information, but it just memorizes the data (like using a unique sample ID).

The fix: normalize IG by the entropy of the feature itself:

$\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)}$

For Income (5 Low, 5 High — equal split):

$\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$

For Employed (4 No, 6 Yes — unequal split):

$\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 as the root split. For this dataset, the adjustment doesn't change the decision — but on datasets with high-cardinality features (zip code, user ID), it prevents the model from trivially splitting on a unique identifier.

sklearn Tree Visualization

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']))

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?