Demystifying Gini Impurity: How Decision Trees Choose the Optimal Split

A mathematical and practical deep dive into CART decision trees, Gini impurity derivations, split evaluation, and Python implementation from scratch and scikit-learn.

---

At the heart of every decision tree classifier lies a fundamental question: Which feature and threshold will split the data into the cleanest, most distinct subsets?

In algorithms like CART (Classification and Regression Trees), this decision is powered by a metric known as Gini Impurity. While modern ensemble methods like Random Forests and Gradient Boosted Trees obscure the math behind abstractions, understanding how Gini Impurity drives node splits is essential for diagnosing tree behavior, controlling overfitting, and interpreting classification boundaries.

---

1. What Is Gini Impurity?

Gini Impurity measures the likelihood that a randomly chosen element from a dataset would be incorrectly labeled if it were randomly labeled according to the class distribution in the subset.

For a node m containing samples across K distinct classes, let p_k denote the proportion of training instances belonging to class k:

p_k = (1 / N_m) ∑_{i ∈ Rm} 핀(y_i = k)

The Gini Impurity I_G(m) is defined as:

I_G(m) = ∑_k=1^K p_k(1 − p_k) = 1 − ∑_k=1^K p_k²

Boundary Conditions

• Maximum Purity (I_G = 0): Every sample in node m belongs to a single class (p_j = 1, and p_k = 0 for all k ≠ j). The node is pure and requires no further splitting.
• Maximum Impurity: Samples are equally distributed among all K classes (p_k = 1 / K for all k):

  I_{G, max} = 1 − ∑_k=1^K (1 / K)² = 1 − K(1 / K²) = 1 − 1 / K

  For binary classification (K = 2), maximum impurity is 0.5. For K = 3, it is 0.667.

---

2. Evaluating Splits: Weighted Gini Impurity Reduction

A decision tree considers every candidate feature j and candidate threshold t, splitting node m into a left child m_L and right child m_R:

• m_L(j, t) = { (x, y) ∈ m ∣ x_j ≤ t }
• m_R(j, t) = { (x, y) ∈ m ∣ x_j > t }

The quality of the split is evaluated using the Weighted Gini Impurity:

G_split(j, t) = (N_L / N_m) I_G(m_L) + (N_R / N_m) I_G(m_R)

Equivalently, the algorithm maximizes the Gini Gain (ΔI_G):

ΔI_G(j, t) = I_G(m) − G_split(j, t)

The optimal split (j^*, t^*) satisfies:

(j^*, t^*) = arg min_{j, t} G_split(j, t)

---

3. Step-by-Step Numerical Example

Suppose a parent node contains 10 samples: 6 Class A and 4 Class B.

Step 1: Calculate Parent Gini Impurity

p_A = 6 / 10 = 0.6,   p_B = 4 / 10 = 0.4

I_G(Parent) = 1 − (0.6² + 0.4²) = 1 − (0.36 + 0.16) = 0.48

Step 2: Candidate Split 1 divides the data into:

• Left Node (4 samples): 4 Class A, 0 Class B → I_G(Left) = 1 − (1.0² + 0.0²) = 0.0
• Right Node (6 samples): 2 Class A, 4 Class B → I_G(Right) = 1 − ((2/6)² + (4/6)²) = 1 − (0.111 + 0.444) = 0.444

G_split = (4 / 10)(0.0) + (6 / 10)(0.444) = 0 + 0.266 = 0.266

ΔI_G = 0.48 − 0.266 = 0.214

Step 3: Candidate Split 2 divides the data into:

• Left Node (5 samples): 3 Class A, 2 Class B → I_G(Left) = 1 − (0.6² + 0.4²) = 0.48
• Right Node (5 samples): 3 Class A, 2 Class B → I_G(Right) = 1 − (0.6² + 0.4²) = 0.48

G_split = (5 / 10)(0.48) + (5 / 10)(0.48) = 0.48

ΔI_G = 0.48 − 0.48 = 0.000

The tree selects Split 1 because it achieves a substantially lower weighted Gini Impurity (0.266 vs. 0.480).

---

4. Gini Impurity vs. Information Gain (Entropy)

Criterion	Mathematical Formula	Computational Cost	Sensitivity & Splitting Behavior
Gini Impurity	1 − ∑ pk2	Lower: Requires basic squaring and addition; highly vectorized.	Favors isolating the largest class into its own pure partition quickly.
Entropy (Shannon)	−∑ pk log2(pk)	Higher: Involves logarithmic operations for every evaluated split.	Penalizes mixed distributions slightly more aggressively, often leading to more balanced branch sizes.

In practice, Gini Impurity and Entropy yield identical split decisions roughly 97% to 99% of the time. Gini is generally preferred as the default due to its runtime efficiency.

---

5. Python Implementation: Verifying Scikit-Learn Splitting

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

# 1. Generate toy dataset matching the manual calculation
# Features: Single numeric attribute X
X = np.array([[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]])
# Target: 6 instances of class 0, 4 instances of class 1
y = np.array([0, 0, 0, 0, 1, 1, 0, 0, 1, 1])

# 2. Fit CART decision tree constrained to a single decision stump
clf = DecisionTreeClassifier(criterion="gini", max_depth=1, random_state=42)
clf.fit(X, y)

# 3. Output tree split criteria
tree_rules = export_text(clf, feature_names=["Feature_X"])
print(tree_rules)

# 4. Programmatic verification of parent Gini impurity
def calculate_gini(labels):
    _, counts = np.unique(labels, return_counts=True)
    probs = counts / len(labels)
    return 1.0 - np.sum(probs ** 2)

print(f"Parent Gini Impurity: {calculate_gini(y):.4f}")

---

6. Summary of Practical Rules for Practitioners

1. Early Stopping (Pre-pruning): Without constraints (such as min_samples_leaf or max_depth), a tree splits nodes until Gini = 0 everywhere, resulting in extreme overfitting.
2. Categorical Cardinality: High-cardinality features can unfairly dominate Gini reduction because they offer an exponential number of split subsets ($2^{k-1} - 1$). Group or frequency-encode these prior to training.
3. Ensembles: In Random Forests and Extra Trees, feature subspacing mitigates the greedy nature of individual Gini splits, turning weak individual trees into a robust ensemble.