𝗗𝗲𝗺𝘆𝘀𝘁𝗶𝗳𝘆𝗶𝗻𝗴 𝗚𝗶𝗻𝗶 𝗜𝗺𝗽𝘂𝗿𝗶𝘁𝘆: 𝗛𝗼𝘄 𝗗𝗲𝗰𝗶𝘀𝗶𝗼𝗻 𝗧𝗿𝗲𝗲𝘀 𝗖𝗵𝗼𝗼𝘀𝗲 𝘁𝗵𝗲 𝗢𝗽𝘁𝗶𝗺𝗮𝗹 𝗦𝗽𝗹𝗶𝘁

Vinaitheerthan Renganathan

4 min read

·

3 days ago

--

Listen

Share

A 𝘮𝘢𝘵𝘩𝘦𝘮𝘢𝘵𝘪𝘤𝘢𝘭 𝘢𝘯𝘥 𝘱𝘳𝘢𝘤𝘵𝘪𝘤𝘢𝘭 𝘥𝘦𝘦𝘱 𝘥𝘪𝘷𝘦 𝘪𝘯𝘵𝘰 𝘊𝘈𝘙𝘛 𝘥𝘦𝘤𝘪𝘴𝘪𝘰𝘯 𝘵𝘳𝘦𝘦𝘴, 𝘎𝘪𝘯𝘪 𝘪𝘮𝘱𝘶𝘳𝘪𝘵𝘺 𝘥𝘦𝘳𝘪𝘷𝘢𝘵𝘪𝘰𝘯𝘴, 𝘴𝘱𝘭𝘪𝘵 𝘦𝘷𝘢𝘭𝘶𝘢𝘵𝘪𝘰𝘯, 𝘢𝘯𝘥 𝘗𝘺𝘵𝘩𝘰𝘯 𝘪𝘮𝘱𝘭𝘦𝘮𝘦𝘯𝘵𝘢𝘵𝘪𝘰𝘯. ━━━━━━━━━━━━━━━━━━━━

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 driven 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.

━━━━━━━━━━━━━━━━━━━━

𝟭. 𝗪𝗵𝗮𝘁 𝗜𝘀 𝗚𝗶𝗻𝗶 𝗜𝗺𝗽𝘂𝗿𝗶𝘁𝘆?

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 𝑚 containing samples across 𝐾 distinct classes, let 𝑝_𝑘 denote the proportion of training instances belonging to class 𝑘:

𝑝_𝑘 = (1 / 𝑁_𝑚) ∑_{𝑖 ∈ 𝑅_𝑚} 𝕀(𝑦ᵢ = 𝑘)

The Gini Impurity 𝐼_𝐺(𝑚) is defined as:

𝐼_𝐺(𝑚) = ∑{𝑘=1..𝐾} 𝑝_𝑘(1 − 𝑝_𝑘) = 1 − ∑{𝑘=1..𝐾} 𝑝_𝑘²

𝗕𝗼𝘂𝗻𝗱𝗮𝗿𝘆 𝗖𝗼𝗻𝗱𝗶𝘁𝗶𝗼𝗻𝘀: • 𝗠𝗮𝘅𝗶𝗺𝘂𝗺 𝗣𝘂𝗿𝗶𝘁𝘆 (𝐼_𝐺 = 0): Every sample in node 𝑚 belongs to a single class (𝑝_𝑗 = 1, and 𝑝_𝑘 = 0 for all 𝑘 ≠ 𝑗). The node is pure and requires no further splitting. • 𝗠𝗮𝘅𝗶𝗺𝘂𝗺 𝗜𝗺𝗽𝘂𝗿𝗶𝘁𝘆: Samples are equally distributed among all 𝐾 classes (𝑝_𝑘 = 1 / 𝐾 for all 𝑘): 𝐼_{𝐺, max} = 1 − ∑ (1 / 𝐾)² = 1 − 1 / 𝐾 For binary classification (𝐾 = 2), maximum impurity is 0.5. For 𝐾 = 3, it is 0.667.

━━━━━━━━━━━━━━━━━━━━

𝟮. 𝗘𝘃𝗮𝗹𝘂𝗮𝘁𝗶𝗻𝗴 𝗦𝗽𝗹𝗶𝘁𝘀: 𝗪𝗲𝗶𝗴𝗵𝘁𝗲𝗱 𝗚𝗶𝗻𝗶 𝗜𝗺𝗽𝘂𝗿𝗶𝘁𝘆 𝗥𝗲𝗱𝘂𝗰𝘁𝗶𝗼𝗻

A decision tree evaluates every candidate feature 𝑗 and threshold 𝑡, splitting node 𝑚 into left (𝑚_𝐿) and right (𝑚_𝑅) subsets: • 𝑚_𝐿(𝑗, 𝑡) = { (𝐱, 𝑦) ∈ 𝑚 ∣ 𝑥_𝑗 ≤ 𝑡 } • 𝑚_𝑅(𝑗, 𝑡) = { (𝐱, 𝑦) ∈ 𝑚 ∣ 𝑥_𝑗 > 𝑡 }

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

𝐺_split(𝑗, 𝑡) = (𝑁_𝐿 / 𝑁_𝑚) 𝐼_𝐺(𝑚_𝐿) + (𝑁_𝑅 / 𝑁_𝑚) 𝐼_𝐺(𝑚_𝑅)

Equivalently, the tree maximizes the Gini Gain (Δ𝐼_𝐺):

Δ𝐼_𝐺(𝑗, 𝑡) = 𝐼_𝐺(𝑚) − 𝐺_split(𝑗, 𝑡)

The chosen split satisfies: (𝑗*, 𝑡*) = arg min_{𝑗, 𝑡} 𝐺_split(𝑗, 𝑡)

━━━━━━━━━━━━━━━━━━━━

𝟯. 𝗦𝘁𝗲𝗽-𝗯𝘆-𝗦𝘁𝗲𝗽 𝗡𝘂𝗺𝗲𝗿𝗶𝗰𝗮𝗹 𝗘𝘅𝗮𝗺𝗽𝗹𝗲

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

𝗦𝘁𝗲𝗽 𝟭: Calculate Parent Gini Impurity 𝑝_𝐴 = 6 / 10 = 0.6, 𝑝_𝐵 = 4 / 10 = 0.4 𝐼_𝐺(Parent) = 1 − (0.⁶² + 0.⁴²) = 1 − (0.36 + 0.16) = 0.48

𝗦𝘁𝗲𝗽 𝟮: Candidate Split 1 divides the data into: • Left Node (4 samples): 4 Class A, 0 Class B → 𝐼_𝐺(Left) = 1 − (1.⁰² + 0.⁰²) = 0.0 • Right Node (6 samples): 2 Class A, 4 Class B → 𝐼_𝐺(Right) = 1 − ((2/6)² + (4/6)²) = 1 − 0.555 = 0.444

𝐺_split = (4 / 10)(0.0) + (6 / 10)(0.444) = 0.266 Δ𝐼_𝐺 = 0.48 − 0.266 = 0.214

𝗦𝘁𝗲𝗽 𝟯: Candidate Split 2 divides the data into: • Left Node (5 samples): 3 Class A, 2 Class B → 𝐼_𝐺(Left) = 1 − (0.⁶² + 0.⁴²) = 0.48 • Right Node (5 samples): 3 Class A, 2 Class B → 𝐼_𝐺(Right) = 1 − (0.⁶² + 0.⁴²) = 0.48

𝐺_split = (5 / 10)(0.48) + (5 / 10)(0.48) = 0.48 Δ𝐼_𝐺 = 0.48 − 0.48 = 0.000

The tree selects Split 1 because it yields a significant reduction in impurity (0.266 vs 0.480).

━━━━━━━━━━━━━━━━━━━━

𝟰. 𝗚𝗶𝗻𝗶 𝗜𝗺𝗽𝘂𝗿𝗶𝘁𝘆 𝘃𝘀. 𝗘𝗻𝘁𝗿𝗼𝗽𝘆 (𝗜𝗻𝗳𝗼𝗿𝗺𝗮𝘁𝗶𝗼𝗻 𝗚𝗮𝗶𝗻)

• Gini Impurity (1 − ∑ 𝑝_𝑘²): Computationally faster because it avoids logarithmic operations. It tends to favor isolating the most frequent class quickly. • Entropy (−∑ 𝑝_𝑘 log₂(𝑝_𝑘)): Slower due to log calls. It penalizes mixed distributions somewhat more heavily, often yielding slightly more balanced subtrees.

In practice, both criteria make identical split choices 97–99% of the time, making Gini the preferred default in high-throughput implementations like scikit-learn.

━━━━━━━━━━━━━━━━━━━━

𝟱. 𝗣𝘆𝘁𝗵𝗼𝗻 𝗜𝗺𝗽𝗹𝗲𝗺𝗲𝗻𝘁𝗮𝘁𝗶𝗼𝗻

Python

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

# 1. Define synthetic feature and binary target
X = np.array([[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]])
y = np.array([0, 0, 0, 0, 1, 1, 0, 0, 1, 1])# 2. Fit CART decision tree (single depth stump)
clf = DecisionTreeClassifier(criterion="gini", max_depth=1, random_state=42)
clf.fit(X, y)# 3. Print learned split rule
print(export_text(clf, feature_names=["Feature_X"]))# 4. Verification function
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}")

━━━━━━━━━━━━━━━━━━━━

𝟲. 𝗞𝗲𝘆 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆𝘀 𝗳𝗼𝗿 𝗣𝗿𝗮𝗰𝘁𝗶𝘁𝗶𝗼𝗻𝗲𝗿𝘀

• Pre-pruning is Essential: Without depth limits or leaf constraints, trees partition until every node reaches 𝐺 = 0, capturing dataset noise.
• High-Cardinality Bias: Categorical features with many levels can unfairly minimize Gini impurity through sheer partition variety.
• Foundation of Ensembles: The speed of Gini impurity calculations allows ensembles like Random Forests to evaluate thousands of candidate feature splits across hundreds of trees in seconds.