Decision Trees: Gini, Entropy and Pruning

Decision trees are non-parametric supervised learning models that partition feature space into regions, making predictions based on the majority class (classification) or mean value (regression) within each region. Their intuitive, tree-like structure makes them one of the most interpretable models in machine learning.

How Decision Trees Work

A decision tree recursively partitions the input space by selecting feature thresholds that maximize predictive purity. Each internal node represents a feature test, each branch represents the outcome of that test, and each leaf node represents a prediction.

Recursive Partitioning Process:

1. Select the best split — evaluate all features and thresholds
2. Partition the data — split into child nodes
3. Repeat — recursively split child nodes until stopping criteria are met
4. Assign predictions — leaves hold class labels or regression values

Decision Tree Structure

Impurity Measures

The quality of a split is measured by the reduction in impurity it produces. Three primary impurity measures are used in practice.

Gini Impurity

The Gini impurity measures the probability of incorrectly classifying a randomly chosen element if it were labeled according to the class distribution of the dataset.

where is the proportion of class in dataset , and is the number of classes.

Properties:

• Ranges from 0 (pure node) to (maximum impurity)
• For binary classification: maximum Gini = 0.5
• Computationally efficient (no logarithms required)

Entropy

Entropy measures the expected amount of information (surprise) in the class distribution.

Properties:

• Ranges from 0 (pure node) to (maximum impurity)
• For binary classification: maximum Entropy = 1.0
• Rooted in Shannon's information theory

Information Gain

Information Gain quantifies the reduction in entropy (or impurity) achieved by splitting on a feature .

where is the subset of where feature takes value , and is the number of distinct values of .

Gini vs Entropy Comparison

Key Insight: Both measures peak at for binary classification, but Entropy has a sharper peak. In practice, Gini and Entropy produce very similar trees; the difference rarely exceeds 1–2% in accuracy.

Splitting Criteria: Mathematical Framework

For a candidate split on feature with threshold :

Goal: Minimize (or maximize Information Gain)

Gain Ratio (C4.5)

To avoid bias toward multi-valued features, C4.5 uses the Gain Ratio:

where:

For Regression Trees

The splitting criterion minimizes the mean squared error (MSE):

Tree Building Algorithms

ID3 (Iterative Dichotomiser 3)

• Uses Information Gain as splitting criterion
• Handles only categorical features
• No pruning — grows until pure leaves or no more splits
• Prone to overfitting

C4.5 (Successor to ID3)

• Uses Gain Ratio to reduce multi-valued feature bias
• Handles continuous features via thresholding
• Handles missing values through fractional instance weighting
• Includes post-pruning via error-based pruning

CART (Classification and Regression Trees)

• Uses Gini impurity (classification) or MSE (regression)
• Produces binary trees only (2-way splits)
• Supports both classification and regression
• Uses cost-complexity pruning for generalization

Hyperparameters

Pruning Strategies

Pruning removes branches that provide little predictive power, reducing overfitting and improving generalization.

Pre-Pruning (Early Stopping)

Stop growing the tree before it becomes too complex.

• max_depth — limit tree height
• min_samples_split — require minimum samples to split
• min_samples_leaf — require minimum samples in leaves
• min_impurity_decrease — require minimum improvement

Advantage: Computationally efficient — avoids growing unnecessary branches.

Disadvantage: May stop too early (horizon effect) — a seemingly poor split now might lead to a good split later.

Post-Pruning

Grow the full tree first, then remove branches that don't improve generalization.

Reduced Error Pruning

1. Grow tree to maximum depth
2. For each non-leaf node (bottom-up):
   • Evaluate validation accuracy if subtree is replaced by a leaf
   • Prune if accuracy doesn't decrease

Cost-Complexity Pruning (CART)

Minimize the cost-complexity function:

where:

• is the misclassification rate (resubstitution error)
• is the number of leaf nodes
• is the complexity parameter

Optimal is found via cross-validation:

Overfitting vs Proper Fit

Advantages and Disadvantages

Advantages

Disadvantages

Implementation in Python

Complete Pipeline

Regression Trees

Key Takeaways

1. Gini vs Entropy — both produce similar trees; Gini is slightly faster, Entropy tends to produce slightly more balanced trees
2. Pre-pruning is computationally efficient but risks the horizon effect; post-pruning is more robust but requires a validation set
3. Cost-complexity pruning with cross-validation is the standard approach for finding optimal tree size
4. Decision trees are the foundation for ensemble methods (Random Forests, Gradient Boosting) which address individual tree limitations
5. Feature importance from trees is based on impurity decrease and can be biased toward high-cardinality features — consider permutation importance as an alternative

Further Reading

• Breiman, L. et al. (1984). Classification and Regression Trees. Wadsworth.
• Quinlan, J.R. (1986). Induction of Decision Trees. Machine Learning, 1(1), 81–106.
• Quinlan, J.R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
• Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning. Springer. Chapter 9