Decision Trees: Entropy and Gini Impurity

A decision tree is a classifier that asks a sequence of yes/no questions about input features, following a path from root to leaf, and returns the prediction at the leaf. The interesting part is not the prediction — it's how the tree decides which question to ask first. It needs a measure of how "mixed" a set of labels is. That measure is either entropy or Gini impurity.

Anchor dataset: 10-sample loan approval dataset. Features: income level (Low/High), employed (Yes/No).

import numpy as np
import pandas as pd

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']
})
# Approved: Yes=7, No=3 out of 10

What Is a Decision Tree?

A decision tree partitions training samples into progressively purer groups:

1. At each internal node, test one feature
2. Route samples to the left or right child based on the test outcome
3. At each leaf, predict the majority class among samples that reached it

The construction is top-down and greedy: at each node, choose the single feature split that most reduces impurity in the resulting children — then recurse. There is no backtracking.

To compare splits, we need a measure of how mixed the class labels are at a node. Two standard measures: entropy and Gini impurity.

Root Node Impurity

Before any split: 7 approved (Yes), 3 not approved (No) out of 10 total.

$P(\text{Yes})=7/10=0.7,P(\text{No})=3/10=0.3$

Entropy

$H=-{\sum }_k{p}_k{\log }_2(p_k)$

Range: $[0,{\log }_2(K)]$ for $K$ classes. $H=0$: node is pure (all one class). $H=1$: perfectly mixed for binary classification.

Computing for the root:

$H=-(0.7\times {\log }_{2}0.7)-(0.3\times {\log }_{2}0.3)$

${\log }_2(0.7)=\ln (0.7)/\ln (2)=-0.357/0.693=-0.515$ ${\log }_2(0.3)=\ln (0.3)/\ln (2)=-1.204/0.693=-1.737$

$H=-(0.7\times -0.515)-(0.3\times -1.737)=0.3605+0.5211=0.882\text{ bits}$

0.882 bits of uncertainty: if you randomly guessed the label of a randomly drawn sample, this measures how surprised you'd be. A perfectly mixed 50/50 node has $H=1$ bit — maximum surprise.

Gini Impurity

$\text{Gini}=1-{\sum }_k{p}_k^2$

Range: $[0,1-1/K]$. $\text{Gini}=0$: pure. Interpretation: the probability that two randomly drawn samples from this node have different classes.

Computing for the root:

$\text{Gini}=1-(0.7^2+0.3^2)=1-(0.49+0.09)=1-0.58=0.42$

If you randomly pick two samples from this node, there's a 42% chance they have different labels.

Computing Impurity After a Split on "Income"

Split the 10 samples by income level:

• Left (Low income): 5 samples → approved = [No, No, Yes, No, Yes] → Yes=2, No=3
• Right (High income): 5 samples → approved = [No, Yes, Yes, Yes, Yes] → Yes=4, No=1

Left node: $P(\text{Yes})=2/5=0.4$, $P(\text{No})=3/5=0.6$

$H_{\text{left}}=-(0.4\times {\log }_{2}0.4)-(0.6\times {\log }_{2}0.6)=-(0.4\times -1.322)-(0.6\times -0.737)=0.529+0.442=0.971\text{ bits}$ ${\text{Gini}}_{\text{left}}=1-(0.4^2+0.6^2)=1-0.52=0.48$

Right node: $P(\text{Yes})=4/5=0.8$, $P(\text{No})=1/5=0.2$

$H_{\text{right}}=-(0.8\times -0.322)-(0.2\times -2.322)=0.258+0.464=0.722\text{ bits}$ ${\text{Gini}}_{\text{right}}=1-(0.8^2+0.2^2)=1-0.68=0.32$

Weighted average (5 samples each, total 10):

$H_{\text{Income}}=\frac{5}{10}\times 0.971+\frac{5}{10}\times 0.722=0.847\text{ bits}$ ${\text{Gini}}_{\text{Income}}=0.5\times 0.48+0.5\times 0.32=0.40$

Computing Impurity After a Split on "Employed"

• Left (Employed=No): 4 samples → approved = [No, No, No, Yes] → Yes=1, No=3
• Right (Employed=Yes): 6 samples → approved = [No, Yes, Yes, Yes, Yes, Yes] → Yes=5, No=1

Left: $P(\text{Yes})=0.25$, $P(\text{No})=0.75$ $H_{\text{left}}=-(0.25\times -2)-(0.75\times -0.415)=0.5+0.311=0.811\text{ bits}$

Right: $P(\text{Yes})=5/6$, $P(\text{No})=1/6$ $H_{\text{right}}=-(5/6\times -0.263)-(1/6\times -2.585)=0.219+0.431=0.650\text{ bits}$

Weighted average (4/10 left, 6/10 right):

$H_{\text{Employed}}=\frac{4}{10}\times 0.811+\frac{6}{10}\times 0.650=0.324+0.390=0.714\text{ bits}$

Comparing Both Splits

Decision: split on Employed first. Both entropy (IG=0.168) and Gini (gain=0.06) agree — Employed tells us much more about loan approval than Income does.

sklearn Confirmation

from sklearn.tree import DecisionTreeClassifier
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_entropy = DecisionTreeClassifier(criterion='entropy', max_depth=3, random_state=42)
dt_entropy.fit(X, y)
print("Feature importances (Entropy):", dt_entropy.feature_importances_.round(4))

dt_gini = DecisionTreeClassifier(criterion='gini', max_depth=3, random_state=42)
dt_gini.fit(X, y)
print("Feature importances (Gini):   ", dt_gini.feature_importances_.round(4))

Employed accounts for 83% of importance by entropy, 96% by Gini — matching our manual IG calculation (Employed's IG was 5× larger than Income's).

Entropy vs Gini — When to Use Which

In practice, entropy and Gini produce identical or very similar trees. Gini is sklearn's default because it avoids the logarithm computation. For most datasets, the choice between them doesn't matter.

Test Your Understanding

1. A node has 100 samples: 50 class A, 30 class B, 20 class C. Compute the entropy and Gini impurity. Which is higher in relative terms (what fraction of the maximum possible impurity does each achieve)?

2. The root has $H=0.882$ bits. After splitting on Employed, the weighted $H=0.714$ bits. After splitting on Income, weighted $H=0.847$ bits. A third feature, "credit score" (Low/High), produces weighted $H=0.750$ bits. Rank all three features by Information Gain.

3. At the left node (Employed=No): Yes=1, No=3. Entropy = 0.811 bits. If you added one more sample to this node — either a Yes or a No — which would reduce entropy more, and by how much?

4. Gini impurity is the probability that two randomly drawn samples have different classes. For the root node (Yes=7, No=3): verify the formula numerically. If you draw two samples with replacement, what is $P(\text{both same class})$ and $P(\text{different classes})$?

5. A fully unconstrained decision tree on this 10-sample dataset would create at most how many leaves? Could it achieve training accuracy of 100%? Would entropy at every leaf be exactly 0?