28  Decision Trees

A decision tree divides the feature space into rectangular regions by a sequence of binary splits on single features, and predicts a constant in each region. Trees are the building block of the ensembles of the next chapters, and are of interest on their own for the readability of small trees. This chapter describes how a tree is grown and pruned, its properties, and two extensions that fit a linear model within the regions of a tree.

28.1 Recursive partitioning

A tree is grown from the top. The root node contains all training cases. For each feature \(x_j\) and each split point \(s\), the cases are divided into the regions \(\{x_j < s\}\) and \(\{x_j \ge s\}\); for a categorical feature, the levels are divided into two sets. The split that most reduces an impurity criterion is chosen, and the procedure is repeated within each of the two child nodes, until a stopping rule is met (Breiman et al. 1984). The prediction for a case is the mean outcome of the training cases in its terminal node, its leaf, for regression, and the class proportions in the leaf for classification.

The impurity criterion for regression is the residual sum of squares around the node means. For classification with class proportions \(\hat p_{k}\) in a node, the common criteria are the Gini index and the entropy (AMDS: Entropy):

\[ \text{Gini} = \sum_{k} \hat p_{k} (1 - \hat p_{k}), \qquad \text{Entropy} = -\sum_{k} \hat p_{k} \log \hat p_{k} . \tag{28.1}\]

Both are zero in a pure node and largest when the classes are equally represented. The search is greedy: each split is the best available given the splits above it, without regard to splits that might follow. Finding the tree that is optimal overall is computationally intractable.

Figure 28.1 shows regression trees of depth 1, 3 and 6 fitted to the simulated data of Figure 24.1. Each tree is a step function with at most \(2^{d}\) steps for depth \(d\).

Figure 28.1: Regression trees of maximum depth 1, 3 and 6 fitted to 100 simulated cases.

28.2 Size and pruning

The size of a tree controls its flexibility. A tree grown until every leaf contains one case reproduces the training data exactly; a tree with one split is a coarse step function. Size can be limited while growing, by a maximum depth, a minimum number of cases in a node for it to be split, or a minimum improvement in impurity for a split to be made. A stopping rule can prevent a useful split that becomes available only after a split with little improvement, so trees are often grown large and then pruned.

Cost-complexity pruning considers the subtrees \(T\) of a large tree, and for each value of a complexity parameter \(\alpha\) selects the subtree that minimizes

\[ R_\alpha(T) = R(T) + \alpha \lvert T \rvert , \tag{28.2}\]

where \(R(T)\) is the training error and \(\lvert T \rvert\) the number of leaves (Breiman et al. 1984). As \(\alpha\) increases, the selected subtrees are nested and smaller; \(\alpha\) is chosen by cross-validation. In the rpart implementation, the complexity parameter cp is \(\alpha\) scaled by the error of the root node.

28.3 Properties

  • Interactions. Each path from the root to a leaf is a conjunction of conditions on several features, so trees represent interactions without their being specified.
  • Invariance. A split depends only on the ordering of a feature’s values, so trees are invariant to strictly monotone transformations of the features, and require no scaling.
  • Mixed and missing data. Trees split numeric and categorical features alike. Missing values can be handled by surrogate splits, alternative splits on other features that best reproduce the primary split.
  • Readability. A small tree is a set of rules that can be read and checked.
  • Instability. A small change in the data can change the first split and therefore every split below it. Trees have high variance.
  • Step functions. A tree approximates a smooth or additive relationship by steps. A linear effect of one feature requires many splits, and is represented poorly with few cases per leaf.
  • Coarse probabilities. The predicted probability in a leaf is a proportion of few cases, and is 0 or 1 in pure leaves.

The ensembles of Chapter 30 and Chapter 32 address the instability and the step-function bias of single trees by combining many of them.

28.4 Trees with linear models in the leaves

Two extensions fit a linear model in each region instead of a constant.

Model-based recursive partitioning fits a parametric model, such as a GLM, to the cases of a node, and tests whether its parameters are stable across the values of each partitioning variable; the node is split on the variable with the most significant instability, and the procedure is repeated in the children (Zeileis et al. 2008). The result is a tree with a separate GLM in each leaf, and with splits selected by significance tests rather than by an impurity criterion.

The linear additive tree (LINAD), implemented in rtemis, fits a linear model at the root, by forward stepwise selection, ridge or elastic net, then splits on the gradient of the loss and fits a linear model to the residual in each child, so that the coefficients along a path from the root to a leaf add up. Each leaf therefore has its own linear model, built as a sequence of adjustments to the models of its ancestors. Shrinkage of each update by a learning rate, and the weighting of cases into both children of a split, as in the additive tree of Luna et al. (2019), reduce the variance of the fit. With constant node models, no weighting and no shrinkage, LINAD reduces to CART; with a single leaf, to a regularized linear model. The number of leaves is selected on held-out data.

28.5 Summary

  • A decision tree partitions the feature space by greedy binary splits that reduce impurity, and predicts a constant in each leaf.
  • Tree size controls flexibility; trees are grown large and pruned by cost-complexity, with the complexity parameter chosen by cross-validation.
  • Trees capture interactions, need no scaling, and handle mixed and missing data, but are unstable and represent smooth effects by steps.
  • Model-based trees and linear additive trees fit linear models within the regions of a tree.

28.6 Further reading