Decision Trees: Entropy and Gini Impurity

You're a loan officer at a bank. Every day, applications cross your desk — income statements, employment records, credit histories. You've developed a mental checklist: check if they're employed first, then look at their income. You can approve or deny most applications in under a minute.

But there are 500 applications waiting. You can't do them all. You need a system that asks the same questions you do, in the same order, and reaches the same decisions.

That system is called a decision tree. The hard part isn't the tree itself — it's figuring out which question to ask first. A tree needs a measure of how "mixed up" the labels are at any point, so it can choose the question that untangles them the most. That measure is either entropy or Gini impurity.

What It Is

A decision tree partitions training samples into progressively purer groups. At each internal node, it tests one feature and routes samples left or right based on the outcome. At each leaf, it predicts the majority class. The construction is top-down and greedy: at each node, pick the single best split — the one that makes child nodes the purest — and recurse. No backtracking.

This is not like linear regression, which draws a single line through the data. A decision tree doesn't assume a relationship exists between the features and the target. It doesn't store training examples like k-nearest neighbors either. It simply asks yes/no questions until it reaches a decision.

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

The Plan — Four Phases to Finding the Best Split

We'll walk through the tree's core decision process in four phases. First we measure the impurity at the root using entropy and Gini. Then we evaluate two candidate splits — first on Income, then on Employed. Finally, we compare and pick the one that reduces impurity the most.

Phase 1: Measure Impurity at the Root

Before any split, our root has 10 samples: 7 approved, 3 not. The class distribution is $P(\text{Yes})=0.7$, $P(\text{No})=0.3$. We need a number that captures how mixed this is.

Entropy — the information-theoretic measure

Entropy comes from information theory, but you don't need to know that to use it. What it measures, in plain terms, is how surprised you'd be if you randomly drew a sample and guessed its label. A pure node (all one class) has zero entropy — no surprise. A 50/50 node has maximum entropy — complete surprise.

We can write this more formally as:

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

The ${\log }_2$ gives us an answer in bits. $H=0$ means pure. For binary classification, $H=1$ means perfectly mixed. Let's compute it for our root:

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

Our root has 0.882 bits of uncertainty — closer to maximum (1.0) than to pure (0.0), because 70/30 is still fairly mixed.

The entropy curve is symmetric — pure at both ends (all Yes or all No), maximum at 50/50. Our root, at the orange dot, sits at $(0.7,0.882)$.

✓ Phase 1 complete. Root entropy computed: $H=0.882$ bits.

Gini Impurity — the simpler alternative

Here's the same idea, but as a probability instead of an information measure. Gini impurity answers: if you pick two random samples from this node, what's the chance they have different labels?

In symbols:

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

A pure node has $\text{Gini}=0$ (both samples always the same class). The maximum for binary classification is $0.5$ (50/50 split). Let's compute it for the root:

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

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

Phase 2: Split on Income

Now let's evaluate our first candidate split. Here's the goal: test whether splitting by income level produces children that are purer than the root.

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

What's the entropy of each child? Same formula, fresh numbers:

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$

To compare the split against the root, we need a single number. The weighted average gives us that — it blends the children's impurities, weighted by how many samples each child holds:

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

The root had $H=0.882$ bits. After the Income split, the weighted entropy is $0.847$ bits — a small reduction. Let's see if we can do better with the other feature.

Phase 3: Split on Employed

Our second candidate: split by employment status. Same goal — see if this produces purer children than the root.

• 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 by sample counts:

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

That's $0.714$ bits — down from the root's $0.882$. A bigger drop than Income's $0.847$.

Phase 4: Compare and Choose the Best Split

Here's the goal: decide which feature makes the best root split. We rank each feature by how much it reduces impurity — that reduction is called Information Gain (for entropy) or Gini Gain (for Gini impurity).

Both measures agree: Employed is the better split. Its Information Gain (0.168) is nearly 5× larger than Income's (0.035). Employed resolves far more of the label uncertainty.

✓ Phase 4 complete. Best split selected: Employed, with IG = 0.168 bits.

Trace Table: Complete Walkthrough

sklearn Confirmation

Let's verify with sklearn. We'll set random_state=42 to make the results reproducible — sklearn's tree algorithm is deterministic given a seed. We limit depth to max_depth=3 because our dataset has only 10 samples and 2 features; depth 3 is enough to capture the full tree without overfitting. We train two separate trees — one with each criterion — to compare how the importance changes.

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

Feature importances (Entropy): [0.17 0.83]  # [income, employed]
Feature importances (Gini):    [0.04 0.96]

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.

Related Concepts

Entropy borrows from information theory — the same formula measures the average bits needed to encode a message from a source with those probabilities. In machine learning, decision trees are the foundation of the most powerful models in production: Random Forest and Gradient Boosting both use decision trees as base learners (covered in the ensemble section). Understanding entropy and Gini impurity — and why they measure node purity — is prerequisite to understanding what gets minimized at each boosting round.

Honest Limitations

Here's something I've learned from spending too many hours tweaking between entropy and Gini, expecting it to make a difference: it almost never does. I once ran a grid search over both criteria on a dataset with 200 features, and the best model used the default Gini — same tree, same accuracy, 2× faster. The real leverage isn't in switching criteria; it's in pruning parameters like max_depth and min_samples_leaf, or switching to an ensemble method.

I've also been burned by feature_importances_ — it's biased toward features with many unique values. A feature with 100 unique values gets more split opportunities than a binary feature, even if the binary feature is more truly predictive. I now use permutation importance (sklearn.inspection.permutation_importance) for any feature importance analysis I actually rely on.

And here's a trap I fell into early on: a decision tree with no constraints will always achieve 100% training accuracy by creating one leaf per unique sample. That number looks great on your console and tells you exactly nothing. Always evaluate on held-out data — I've been humbled by a 100% train / 65% test gap more than once.

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?