Trees, Random Forests, and Boosting
A decision tree predicts by asking one yes-or-no question at a time, and the unit grows one by hand: the first split of a regression tree for the fuel economy of 32 cars and the Gini index before and after one split of the Palmer penguins. One tree is easy to read and unstable, so the unit averages hundreds of them on bootstrap samples, derives how far the correlation between trees limits the gain, and shows how the random forest lowers that limit and how the out-of-bag error comes free. Boosting then fits small trees one after another to the residuals, two rounds by hand on five cars and a derivation of why the residuals are the right target. A ten-fold cross-validation on the Cleveland heart disease data compares a tree, a forest, and a boosted model, and the closing section says what none of them can do.
Every model of Units 8 to 14 was a formula with coefficients, and a reader who knew the formula could write down the prediction for any new case. This unit builds predictors of a different kind. A decision tree asks one yes-or-no question about the data at a time, as a doctor does, and ends in a prediction that is the average or the majority of the training cases that answered the same way. One tree is easy to read and easy to break. Hundreds of trees, grown on bootstrap samples (Unit 13) and averaged, or grown one after another, each fitted to what the previous ones left unexplained, are hard to read and hard to beat, and for a decade they have won most prediction competitions on tabular data, that is, on data that fit in a table with one row per case. The unit grows a tree by hand, shows why averaging helps and how far, and ends with what such a model cannot tell us.
1 Decision trees
1.1 Splitting a regression problem
Unit 8 predicted a quantitative response \(y\) from a predictor \(x\) with a straight line. A regression tree predicts it with a staircase instead. The range of \(x\) is cut at a point \(t\) into two regions, \(x \le t\) and \(x > t\), and the prediction in each region is the mean of the training responses that fall into it. Then each region is cut again, and so on, until a stopping rule halts the process. The resulting rule is drawn as a tree that stands on its head: the first question at the top, called the root, two branches below it, further questions at the internal nodes, and the final regions at the bottom, called the leaves or terminal nodes, each with its prediction. Because every question has two answers, the procedure is called recursive binary splitting. With several predictors a question may concern any of them, so that the regions become rectangles in two dimensions and boxes in more.
Which cut point is best? The tree uses the criterion of Unit 8, the residual sum of squares, applied to the two regions. Among all predictors and all cut points, the split chosen is the one whose two means fit the data best.
The natural candidate cut points are the midpoints between neighbouring observed values, so with \(n\) distinct values there are \(n - 1\) to try for each predictor. To illustrate this, the first split for a familiar dataset follows.