Decision Trees: Splitting Criteria and Pruning

Module: Machine Learning | Difficulty: Advanced

Splitting Criteria

Information Gain (Entropy):

Gini Impurity:

Error Rate:

Complexity Penalty (Minimal Cost-Complexity)

where is number of leaf nodes.

Pruning

1. Grow full tree
2. For each internal node :
3. Prune node with smallest

import numpy as np

def gini_impurity(labels):
    _, counts = np.unique(labels, return_counts=True)
    probs = counts / counts.sum()
    return 1 - np.sum(probs**2)

def entropy(labels):
    _, counts = np.unique(labels, return_counts=True)
    probs = counts / counts.sum()
    return -np.sum(probs * np.log2(probs + 1e-10))

def information_gain(X, y, feature, threshold):
    left_mask = X[:, feature] <= threshold
    right_mask = ~left_mask
    n = len(y)
    return entropy(y) - (left_mask.sum()/n * entropy(y[left_mask]) +
                          right_mask.sum()/n * entropy(y[right_mask]))

| Criterion | Bias | Variance | Speed | |-----------|------|----------|-------| | Entropy | Low | High | Slow | | Gini | Low | Medium | Fast | | Error | High | Low | Very Fast |

Research Insight: Gini and entropy produce nearly identical trees in practice. The difference is that Gini has a larger gradient near p=0.5, making it more sensitive to changes in moderate probabilities.