Mastering Decision Tree Splitting: An In-Depth Guide
Decision trees are a fundamental class of models in machine learning, used for both classification and regression tasks. One of the key steps in learning a decision tree is splitting the nodes to progressively partition the feature space into regions corresponding to the target values. The goal is to maximize the "purity" of the resulting subsets with respect to the target.
In this in-depth guide, we‘ll dive into the technical details of decision tree splitting, covering the mathematical formulation, popular impurity measures and splitting criteria, and practical considerations for achieving optimal splits. Whether you‘re a data scientist looking to deepen your understanding or a machine learning engineer seeking to maximize model performance, this guide will equip you with the knowledge and tools you need to master decision tree splitting.
Decision Tree Learning as Optimization
Under the hood, learning a decision tree is a combinatorial optimization problem. Given a dataset {(x^(i), y^(i))}_(i=1)^N, the goal is to find the tree T that minimizes an objective function representing the prediction error:
$$
\min{T} \sum{i=1}^N L(y^{(i)}, T(x^{(i)}))
$$
where L is a loss function penalizing differences between the true target y and the predicted value T(x).
For classification, common choices of L include:
- 0-1 loss: L(y,ŷ) = 1(y ≠ ŷ)
- Hinge loss: L(y,ŷ) = max(0, 1 – yŷ)
For regression, common losses are:
- Squared error: L(y,ŷ) = (y – ŷ)^2
- Absolute error: L(y,ŷ) = |y – ŷ|
However, this global optimization problem is NP-hard in general. Hence, practical decision tree learning algorithms take a greedy, recursive approach, splitting one node at a time to maximize the improvement in some local splitting criterion.
Impurity Measures for Splitting
The key to this greedy splitting strategy is quantifying the "goodness" of a split in terms of the purity of the resulting subsets. The two most common impurity measures are the Gini index and entropy.
Gini Index
For a node t with a distribution p = (p_1, …, p_K) over the K classes, the Gini index is defined as:
$$
G(t) = \sum_{i \neq j} p_i pj = 1 – \sum{i=1}^K p_i^2
$$
Intuitively, the Gini index measures the probability of misclassifying a randomly chosen sample from the node, if it were randomly labeled according to the class distribution. The Gini index is maximal (0.5 for binary classification) when the classes are perfectly balanced, and minimal (0) when the node is pure.
For example, consider a binary classification problem with a node containing 60% Class 0 samples and 40% Class 1 samples. The Gini index of this node is:
$$
G = 1 – (0.6^2 + 0.4^2) = 1 – (0.36 + 0.16) = 0.48
$$
Entropy
Entropy is another popular impurity measure, based on information theory. The entropy of a node t is defined as:
$$
H(t) = -\sum_{i=1}^K p_i \log_2 p_i
$$
Entropy measures the average amount of information needed to encode the class of a randomly drawn sample from the node. Like the Gini index, entropy is maximal when the classes are balanced and minimal (0) for pure nodes. However, entropy tends to penalize impure splits more heavily than Gini.
For the same 60/40 split as before, the entropy is:
$$
H = -(0.6 \log_2 0.6 + 0.4 \log_2 0.4) = 0.971
$$
Comparison of Impurity Measures
So which impurity measure should you use in practice? In most cases, the choice between Gini and entropy doesn‘t have a huge impact on the final tree. Some key differences are:
- Entropy is slightly more computationally expensive to evaluate due to the logarithm.
- Gini tends to isolate the most frequent class in its own branch, while entropy tends to produce more balanced trees.
- Entropy is more sensitive to changes in the class probabilities, which can lead to overfitting.
In practice, Gini is used as the default in many implementations, including scikit-learn and XGBoost, while entropy is the default in libraries like R‘s rpart. It‘s worth trying both and comparing the results on your problem.
Splitting Criteria and Greedy Search
Given an impurity measure I(t), the greedy splitting algorithm evaluates candidate splits based on the weighted reduction in impurity:
$$
\Delta I (s,t) = I(t) – (\frac{N_L}{N} I(t_L) + \frac{N_R}{N} I(t_R))
$$
where s is a candidate split, t_L and t_R are the left and right child nodes resulting from s, and N, N_L, N_R are the number of samples at the parent and child nodes.
At each node, the greedy algorithm evaluates all possible splits on all features, and selects the one maximizing this impurity reduction:
$$
s^* = \arg\max_{s} \Delta I (s,t)
$$
This process repeats recursively until some stopping criterion is met, such as a maximum depth or minimum number of samples per leaf.
Example: Greedy Splitting on Gini Index
Let‘s walk through an example of greedy splitting on the Gini index. Consider the following tiny dataset:
| x_1 | x_2 | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
At the root node, we have 50% Class 0 and 50% Class 1, so the Gini index is:
$$
G = 1 – (0.5^2 + 0.5^2) = 0.5
$$
Now let‘s evaluate the candidate splits:
- Split on x_1 < 0.5:
- Left child: 100% Class 0, G_L = 0
- Right child: 100% Class 1, G_R = 0
- Impurity reduction: 0.5 – (0.5 0 + 0.5 0) = 0.5
- Split on x_2 < 0.5:
- Left child: 50% Class 0, 50% Class 1, G_L = 0.5
- Right child: 50% Class 0, 50% Class 1, G_R = 0.5
- Impurity reduction: 0.5 – (0.5 0.5 + 0.5 0.5) = 0
The split on x_1 achieves the maximum impurity reduction of 0.5, so we choose it at the root. Since the resulting child nodes are both pure leaves, the tree is complete.
Handling Missing Data
One practical consideration when splitting nodes is how to handle missing feature values. There are a few common strategies:
- Discard samples with missing values
- Assign samples with missing values to a default direction (e.g. always go left)
- Assign samples with missing values to the majority direction based on non-missing samples
- Estimate the probability of the missing value based on non-missing samples and send the sample to both directions weighted by this probability
Options 1 and 2 are simplest but can lead to biased trees if the missing values are informative. Option 3 is a good compromise, while Option 4 (known as surrogate splits) is most theoretically sound but computationally expensive.
In scikit-learn, decision trees handle missing values automatically using Option 3 by default. To use surrogate splits instead, you can set splitter=‘best‘ instead of the default splitter=‘random‘.
Over-fitting and Regularization
A key challenge with decision trees is their tendency to over-fit the training data if grown too deeply. A fully grown tree can achieve perfect accuracy on the train set while generalizing poorly to new data.
To combat overfitting, there are various regularization techniques that limit the complexity of the learned tree:
- Set a maximum depth: Stop splitting nodes beyond a fixed depth threshold
- Set a minimum number of samples per leaf: Don‘t split nodes with too few samples
- Set a minimum impurity decrease: Only split nodes if the impurity reduction exceeds a threshold
- Post-prune the full tree: Grow a deep tree, then merge or remove nodes to minimize held-out error
Here‘s an example of the impact of max depth on a real-world classification dataset:
| Max Depth | Train Accuracy | Test Accuracy |
|---|---|---|
| 2 | 0.807 | 0.785 |
| 4 | 0.861 | 0.808 |
| 8 | 0.986 | 0.785 |
| None | 1.000 | 0.762 |
As the max depth increases, train accuracy approaches 100% while test accuracy peaks and then declines, indicating overfitting. Setting a max depth of 4 achieves the best compromise.
Summary and Further Reading
In this guide, we‘ve covered the key concepts behind splitting decision trees, including:
- The mathematical formulation of decision tree learning as an optimization problem
- Popular impurity measures like Gini index and entropy for evaluating candidate splits
- The greedy recursive splitting algorithm used to learn decision trees in practice
- Strategies for handling missing data during splitting
- Regularization techniques to avoid overfitting and improve generalization
Of course, there‘s much more to learn, from variations like oblique trees and soft trees to ensemble methods like random forests and boosted trees. But with a solid grasp of splitting, you‘re well equipped to dive into these more advanced techniques.
I hope this guide has been helpful in deepening your understanding of this fundamental machine learning concept. For further reading, I recommend:
- "An Introduction to Statistical Learning" by James, Witten, Hastie, and Tibshirani, Ch. 8 and Ch. 9
- "The Elements of Statistical Learning" by Hastie, Tibshirani, and Friedman, Ch. 9 and Ch. 10
- "Decision Trees" by Lior Rokach and Oded Maimon
- Scikit-learn documentation: Decision Trees
