A decision tree predicts an outcome by asking a sequence of simple questions about the predictors — has the player been in the league for at least five years?, is the price above $127? — each answer sending the observation down one branch, until it reaches a leaf that holds the prediction. Trees can be used when the response is numeric (regression trees) and when it is categorical (classification trees), and they are among the few models that can be drawn on a page and read by someone with no statistical training.
A single tree, however, is rarely the most accurate model available. Its predictions change a great deal when the training data change slightly. The second half of the chapter shows how to fix that by combining many trees: bagging and random forests average trees grown on bootstrap samples, and boosting grows trees one after another, each correcting the errors of the previous ones. Two modern implementations of boosting, XGBoost and LightGBM, are today the standard first choice for prediction on tabular data.
Along the way, the chapter introduces the tools used to evaluate any predictive model: training, validation and test sets, cross-validation, and performance metrics for predicted classes, probabilities and numbers.
The chapter follows Chapter 8 of James et al. (2021) and Chapters 9–12 of Boehmke and Greenwell (2019). The algorithm for growing a single tree is CART, introduced by Breiman et al. (1984).
11.1 Anatomy of a Decision Tree
A decision tree is a hierarchy of nodes connected by branches, drawn upside down: the root at the top, the leaves at the bottom.
Structure of a decision tree (source: https://machinelearning-basics.com/cart-algorithm-and-everything-you-need-to-know-about-decision-trees-1-2/)
Root node: the topmost node. It contains the whole training set and asks the first question — the one that best separates the data into groups with different values of the response.
Internal nodes: the decision points below the root. Each asks a question about one predictor, such as \(X_j < s\) for a numeric predictor or \(X_j \in \{\text{Bad}\}\) for a categorical one.
Branches: the two possible answers to the question at a node. Every observation that satisfies the condition goes down one branch, every other observation goes down the other.
Leaves (terminal nodes): the end points of the tree, where no further question is asked. Each leaf holds a prediction: the mean response of the training observations that reached it (regression), or their most common class (classification).
Subtree: any node together with everything below it. A subtree is itself a decision tree.
Depth: the number of questions between the root and a node. A tree of depth \(1\), with a single split and two leaves, is called a stump.
Every path from the root to a leaf is a rule of the form if this and this, then predict that. A tree with \(J\) leaves divides the space of the predictors into \(J\) non-overlapping rectangular boxes \(R_1, \ldots, R_J\), and predicts a constant in each box.
Packages and commands. No code in this section. The chapter uses rpart for single trees (rpart, printcp, plotcp, prune) and rpart.plot to draw them, randomForest and ranger for bagging and random forests, gbm for gradient boosting, xgboost and lightgbm for their two modern implementations, vip for variable-importance plots, ISLR2 for the data and ggplot2 for the remaining figures. All are installed and loaded by the setup chunk at the top of the chapter.
11.2 The Data
We use three data sets from the package ISLR2, the companion package of James et al. (2021). Each one plays a different role in the chapter.
Data set
Rows
Response
Predictors
Used for
Hitters
\(263\)
logSalary: log of a baseball player’s 1987 salary
\(19\)
the first regression tree, splitting by hand, missing values
Boston
\(506\)
medv: median house value of a census tract ($1000s)
\(12\)
regression trees, pruning and every ensemble method
Carseats
\(400\)
High: does a store sell more than \(8\,000\) car seats?
\(10\)
classification trees, pruning and ensembles for classification
Hitters describes \(322\) Major League Baseball players: their 1986 season (AtBat, Hits, HmRun, Runs, RBI, Walks, PutOuts, Assists, Errors), their whole career (Years in the league and the career totals CAtBat, CHits, CHmRun, CRuns, CRBI, CWalks), their League, Division and NewLeague, and their 1987 Salary in thousands of dollars. The salary is missing for \(59\) players, whom we drop, and it is strongly right-skewed, so we model its logarithm.
Boston describes \(506\) census tracts of the Boston area in 1970 (Harrison and Rubinfeld 1978). The response medv is the median value of owner-occupied homes, in thousands of dollars. The predictors include the average number of rooms per dwelling (rm), the percentage of the population of lower socioeconomic status (lstat), the per-capita crime rate (crim), nitric-oxide concentration (nox), distance to employment centres (dis), the pupil–teacher ratio (ptratio) and the property-tax rate (tax). The values of medv were capped at \(50\) when the data were collected; \(16\) tracts sit at that cap.
Carseats is a simulated data set of child car seat sales at \(400\) stores. We turn the numeric Sales (thousands of units) into a binary response High, equal to "Yes" when Sales exceeds \(8\). The predictors are the store’s Price and the competitor’s price at the same location (CompPrice), the local Advertising budget, the Income, Population, Age and Education of the community, the quality of the shelving location (ShelveLoc: Bad, Medium or Good), and whether the store is Urban and in the US.
Note
The original Boston data, as distributed in MASS, contain a variable black, defined as \(1000(B - 0.63)^2\) where \(B\) is the proportion of Black residents. Its parabolic form encodes the original authors’ assumption about how racial self-segregation affects house prices, an assumption they did not test. The version in ISLR2 leaves the variable out, and we use that version (see also the Data Ethics chapter).
Every method is evaluated on data it has not seen. As in the labs of James et al. (2021), each data set is split in half at random, and the same split is used for every model. For Boston, set.seed(1) gives the same split as the corresponding lab, and where we use the same method — a random forest with mtry = 6, for example — the numbers below match theirs. Why the data are split, and how the training half is used to make choices, is the subject of Section 11.5.
The code below creates the three data sets and the six training and test sets. Run it once: every interactive box in this chapter uses the objects it leaves behind.
Warning
XGBoost, LightGBM and ranger do not currently run in the browser version of R used by this book (webR). The examples that use them are computed when the book is built, and their code can be copied into RStudio. Every other example can also be run, and changed, in the interactive boxes.
Packages and commands. The data come from ISLR2 (Hitters, Carseats, Boston). na.omit drops the players without a salary, factor(ifelse(...)) builds the binary response, and set.seed followed by sample(n, n / 2) draws the training rows; negative indexing, data[-idx, ], gives the test rows.
11.3 Regression Trees
11.3.1 A First Example: Baseball Salaries
We start with only two predictors of logSalary: the number of Years a player has spent in the major leagues and the number of Hits in the previous season. The rpart() function of the rpart package grows the tree, and rpart.plot() of the rpart.plot package draws it. For now the argument cp = 0.1 only keeps the tree small; it is explained in Section 11.7.
library(rpart)library(rpart.plot)hit_small <-rpart(logSalary ~ Years + Hits, data = hitters,control =rpart.control(cp =0.1))hit_small
A regression tree for the log salary of baseball players, using two predictors. Each leaf shows the mean log salary of its players and their share of the data.
The printed tree lists one node per line: its number, the split that leads to it, the number of players \(n\), the deviance (for a regression tree, the residual sum of squares of the node) and yval, the mean logSalary of the node. Terminal nodes are marked with a *.
The tree has three leaves. The first question is about experience: players with fewer than \(4.5\) years in the league form a leaf of their own. Among the more experienced players, the number of hits in the previous season makes the difference. On the original scale of the salaries:
players with less than \(4.5\) years in the league: predicted salary \(1000 \times e^{5.107} \approx \$165\,000\);
experienced players with fewer than \(117.5\) hits: \(\$403\,000\);
experienced players with at least \(117.5\) hits: \(\$845\,000\).
This tree is the one in Figure 8.1 of James et al. (2021). It is easy to read: experience is the most important factor; for players with experience, past performance matters; for inexperienced players, in this tree, it does not. The tree is almost certainly an oversimplification of the true relationship, but the trade-off between simplicity and accuracy is exactly what the rest of the chapter is about.
The three leaves are three rectangles in the plane of the two predictors:
The three regions of the tree above. Every player in a region receives the same prediction, the mean log salary of the training players in that region.
11.3.2 Recursive Binary Splitting
How does rpart() find these splits? The goal is to divide the predictor space into \(J\) boxes \(R_1, \ldots, R_J\) that minimise the residual sum of squares\[
\text{RSS} = \sum_{j=1}^{J} \sum_{i \in R_j} \left(y_i - \hat{y}_{R_j}\right)^2 ,
\] where \(\hat{y}_{R_j}\) is the mean response of the training observations in box \(R_j\). Checking every possible partition into boxes is computationally impossible, so CART uses a top-down, greedy approach called recursive binary splitting:
Start with all observations in a single region, the root.
For every predictor \(X_j\) and every cut point \(s\), consider the two half-planes \[
R_1(j, s) = \{X \mid X_j < s\} \qquad \text{and} \qquad R_2(j, s) = \{X \mid X_j \geq s\},
\] and choose the pair \((j, s)\) that minimises \[
\sum_{i:\, x_i \in R_1(j,s)} \left(y_i - \hat{y}_{R_1}\right)^2 + \sum_{i:\, x_i \in R_2(j,s)} \left(y_i - \hat{y}_{R_2}\right)^2 .
\]
Apply step 2 to each of the two new regions separately, then to the regions that result, and so on.
Stop when a stopping rule is met, for example when every region contains fewer than a given number of observations.
The approach is top-down because it starts from the root and works its way down, and greedy because at each step it takes the best split at that step, without looking ahead to splits that might lead to a better tree later. A categorical predictor with \(L\) levels is split by assigning each level to one of the two branches.
Example: five cars, sorted by weight (in thousands of pounds), and their fuel consumption in miles per gallon.
Car
E
D
C
B
A
weight
\(2.2\)
\(2.6\)
\(3.2\)
\(3.6\)
\(4.0\)
mpg
\(22\)
\(20\)
\(15\)
\(12\)
\(10\)
The mean mpg is \(\bar{y} = 15.8\), and the RSS of the root is \[
(22 - 15.8)^2 + (20 - 15.8)^2 + (15 - 15.8)^2 + (12 - 15.8)^2 + (10 - 15.8)^2 = 104.8 .
\] There are four possible cut points, one between each pair of consecutive weights:
Split
Left
Right
RSS left
RSS right
Total RSS
weight \(< 2.4\)
\(22\)
\(20, 15, 12, 10\)
\(0\)
\(56.75\)
\(56.75\)
weight \(< 2.9\)
\(22, 20\)
\(15, 12, 10\)
\(2\)
\(12.67\)
\(14.67\)
weight \(< 3.4\)
\(22, 20, 15\)
\(12, 10\)
\(26\)
\(2\)
\(28\)
weight \(< 3.8\)
\(22, 20, 15, 12\)
\(10\)
\(62.75\)
\(0\)
\(62.75\)
For the best split, weight \(< 2.9\), the left node has mean \(21\) and RSS \((22-21)^2 + (20-21)^2 = 2\), and the right node has mean \(12.33\) and RSS \((15-12.33)^2 + (12-12.33)^2 + (10-12.33)^2 = 12.67\). The split reduces the RSS from \(104.8\) to \(14.67\). A one-split tree in rpart() finds the same cut point:
Dividing an RSS by the number of observations gives the variance of the node, or equivalently the mean squared error (MSE) of predicting every observation by the node mean. Minimising the total RSS of the two children is therefore the same as minimising their weighted average variance, with weights \(n_L/n\) and \(n_R/n\). Both descriptions appear in the literature.
The same search, written as a short function, finds the root split of the baseball tree. For each candidate cut point it computes the total RSS of the two halves; the best cut point is the one with the smallest total.
rss_split <-function(x, y, s) { left <- y[x < s]; right <- y[x >= s]sum((left -mean(left))^2) +sum((right -mean(right))^2)}scan_splits <-function(x, y) { u <-sort(unique(x)) s <- (head(u, -1) +tail(u, -1)) /2# midpoints between observed valuesdata.frame(s = s, rss =sapply(s, function(si) rss_split(x, y, si)))}y <- hitters$logSalaryscan_years <-scan_splits(hitters$Years, y)scan_hits <-scan_splits(hitters$Hits, y)rbind(Years = scan_years[which.min(scan_years$rss), ],Hits = scan_hits[which.min(scan_hits$rss), ],root =c(NA, sum((y -mean(y))^2)))
s rss
Years 4.5 115.0585
Hits 117.5 160.9715
root NA 207.1537
scans <-rbind(cbind(predictor ="Years", scan_years),cbind(predictor ="Hits", scan_hits))ggplot(scans, aes(s, rss)) +geom_line() +geom_hline(yintercept =sum((y -mean(y))^2), linetype ="dashed") +facet_wrap(~ predictor, scales ="free_x") +labs(x ="cut point s", y ="total RSS of the two halves") +theme_minimal()
Total RSS of the two halves for every possible cut point of Years and of Hits. The horizontal line is the RSS of the root. The best split on Years reduces the RSS much more than the best split on Hits.
Splitting at Years < 4.5 brings the RSS from \(207.2\) down to \(115.1\); the best split on Hits only reaches \(161.0\). So the root asks about Years, as in the tree above. The tree then repeats the search inside each half, which is how Hits < 117.5 is found for the experienced players.
Running the same search over the \(16\) numeric predictors shows that the career totals are better predictors still:
The best root split is CAtBat < 1452 — the number of times at bat over a career, which, like Years, measures experience. It is also the root that rpart() chooses with all \(19\) predictors: the three factors League, Division and NewLeague have two levels each, so each allows a single split, and none of them comes close.
11.3.3 Fitting Regression Trees with rpart
The rpart() function fits classification and regression trees with the CART algorithm. Its simplified format is
formula: the response on the left of ~ and the predictors on the right; . means all other columns.
data: the data frame containing the variables.
method: "anova" for a regression tree, "class" for a classification tree (also "poisson" for counts and "exp" for survival data). If omitted, rpart() guesses from the type of the response: a factor gives a classification tree, a number a regression tree.
parms: options of the splitting rule; for classification, parms = list(split = "information") uses the entropy instead of the Gini index.
control: a list built with rpart.control() that controls how far the tree grows.
na.action: the default na.rpart drops observations with a missing response but keeps those with missing predictors, which are handled by surrogate splits (Section 11.8.1).
The main options of rpart.control() are:
Option
Default
Meaning
minsplit
\(20\)
minimum number of observations in a node for a split to be attempted
minbucket
round(minsplit / 3)
minimum number of observations in a leaf
maxdepth
\(30\)
maximum depth of any node, with the root at depth \(0\)
cp
\(0.01\)
complexity parameter: a split must improve the fit by at least this fraction of the root error (Section 11.7)
xval
\(10\)
number of cross-validation folds used to estimate the error of every subtree
maxsurrogate, usesurrogate
\(5\), \(2\)
number of surrogate splits kept, and how they are used for missing values
We now fit a regression tree to the Boston training set, with all predictors and the default options.
bos_tree <-rpart(medv ~ ., data = bos_train)bos_tree
Regression tree for the median house value (medv, in $1000s) of the Boston census tracts, grown on the training set with the default options of rpart.
The tree has seven leaves and uses four of the twelve predictors. The first split is on rm, the average number of rooms: the \(31\) tracts with \(\text{rm} \geq 6.96\) have a mean value of \(\$39\,200\), and are split again at \(7.55\) rooms into tracts worth \(\$33\,400\) and \(\$45\,400\). Among the other \(222\) tracts, the next question is about lstat: where more than \(14.4\%\) of the population is of lower status, values are lower, and lowest of all (\(\$10\,300\)) where the crime rate also exceeds \(11.5\). Where lstat is below \(14.4\%\), the number of rooms appears again.
The rpart object.rpart() returns an object of class "rpart": a list whose components hold everything that is known about the tree. Printing it gives the table above, but the components can also be used directly.
one row per node, in the order of the printed tree: the split variable var ("<leaf>" for a leaf), the number of observations n and their total weight wt, the deviance dev, the prediction yval, the complexity parameter at which the node’s split would be pruned, and the numbers of competing (ncompete) and surrogate (nsurrogate) splits kept. A classification tree adds yval2, with the class counts and proportions of each node
splits
one row per split kept: for each internal node, the split used, the best competing splits on other variables and the surrogate splits
csplit
for splits on a factor, which levels go left and which go right (only present when the tree splits a factor)
where
for each training observation, the row of frame of the leaf it falls into
cptable
the complexity table, with the cross-validated error of every subtree (Section 11.7)
Its row names are the node numbers of the printed tree. The root is node \(1\), and the two children of node \(k\) are nodes \(2k\) and \(2k + 1\): node \(9\) is split into nodes \(18\) and \(19\), and node \(k\) lies at depth \(\lfloor \log_2 k \rfloor\). The deviance of the root, \(19\,447.9\), is its RSS, \(\sum_i (y_i - \bar{y})^2\); the deviance of every other node is the RSS of its tracts around their mean yval.
The vector where gives, for each training tract, the leaf it falls into — as a row number of frame, not as a node number:
head(bos_tree$where) # rows of frame
505 324 167 129 418 471
10 9 13 6 4 7
table(node =rownames(bos_tree$frame)[bos_tree$where]) # tracts in each leaf
node
10 11 18 19 6 7 8
111 24 31 30 16 15 26
# the fitted value of a training tract is the yval of its leafall.equal(unname(predict(bos_tree)), bos_tree$frame$yval[bos_tree$where])
[1] TRUE
The first training tract, number \(505\) of the Boston data, falls in row \(10\) of frame, which is node \(11\). Every tract in a leaf is predicted by the mean of the leaf, so the fitted values of the training tracts are simply frame$yval[where].
The matrix splits records the splits that rpart() considered at each node. Its first ten rows describe the root, for which frame reports \(4\) competing and \(5\) surrogate splits:
The first row is the split that was used: rm at the cut point index\(= 6.96\). The next four are the best splits on four other variables, the competing splits, and the last five are the surrogate splits, used for observations whose value of rm is missing (Section 11.8.1). For the split used and its competitors, count is the number of observations and improve the share of the node’s deviance that the split removes: \((19\,447.9 - 6\,794.3 - 1\,929.0) / 19\,447.9 = 0.551\) for rm, against \(0.471\) for the best split on lstat. For a surrogate, improve holds instead its agreement with the split used, and adj the adjusted agreement. The sign of ncat gives the direction of the split: \(-1\) when the observations below the cut point go to the left child, \(+1\) when those above it do. For a factor, ncat is its number of levels, and the levels sent to each side are stored in csplit.
Finally, rpart.rules() of rpart.plot writes the path from the root to each leaf as a rule, one line per leaf, sorted by prediction:
rpart.rules(bos_tree, digits =3)
medv
10.3 when rm < 6.96 & lstat >= 14.4 & crim >= 11.5
14.4 when rm < 6.96 & lstat >= 14.4 & crim < 11.5 & age >= 94
18.1 when rm < 6.96 & lstat >= 14.4 & crim < 11.5 & age < 94
21.4 when rm < 6.54 & lstat < 14.4
27.7 when rm is 6.54 to 6.96 & lstat < 14.4
33.4 when rm is 6.96 to 7.55
45.4 when rm >= 7.55
Each line reads as an if–then rule: if the average number of rooms is below \(6.96\), more than \(14.4\%\) of the population is of lower status and the crime rate exceeds \(11.5\), then the predicted median value is \(\$10\,300\).
To judge the tree we predict the test set and compare with two benchmarks: a linear regression on the same predictors, and the null model that predicts every tract by the mean of the training set.
The test MSE of the tree is \(35.29\): its predictions are, on a root-mean-square basis, \(\sqrt{35.29} \approx 5.94\) thousand dollars away from the true median values. The tree is far better than the null model, but it is beaten by a plain linear regression (\(27.65\)). We will see that pruning hardly changes this, and that a forest of trees changes it a lot.
The appearance of the tree is controlled by the arguments of rpart.plot(), whose simplified format is
rpart.plot(x, type =2, extra ="auto", digits =2, fallen.leaves =TRUE,box.palette ="auto", roundint =TRUE, tweak =1)
where x is a tree fitted by rpart(), digits the number of significant digits, fallen.leaves = TRUE draws all leaves at the bottom, box.palette colours the nodes by their prediction, roundint = TRUE rounds split points of integer predictors, and tweak enlarges (tweak > 1) or shrinks the text. The arguments type and extra select what is drawn:
type
Labels
0
a split label at each split, node labels at the leaves only
1
as 0, but all nodes are labelled
2
as 1, with the split labels below the node labels (default)
3
separate split labels for the left and right branches
4
as 3, with all nodes labelled
5
the split variable name in the interior nodes
extra
Extra information in each node
"auto"
106 for binary classification, 104 for more classes, 100 for regression
0
none
1
number of observations (per class, for classification)
2
classification rate (correct / total)
4
probability of each class
6
probability of the second class only (useful for a binary response)
8
probability of the predicted class
+ 100
adds the percentage of observations in the node
Packages and commands.rpart’s rpart(formula, data, method = "anova", control = rpart.control()) grows the tree and returns an object of class "rpart"; printing it lists every node with its n, deviance and yval, and fit$frame holds the same table (var == "<leaf>" marks the leaves). fit$where gives the leaf of each training observation, fit$splits the splits used, their competitors and their surrogates, and fit$cptable the complexity table. predict(fit, newdata) predicts new observations and residuals(fit) gives the training residuals. rpart.plot’s rpart.plot(fit, type = , extra = , digits = ) draws the tree, and rpart.rules(fit) writes it as a set of rules. The split search by hand uses only base R (sort, unique, sapply, which.min), and lm gives the linear benchmark. The figures use ggplot2.
11.4 Classification Trees
A classification tree predicts a qualitative response. Each leaf predicts the most common class among the training observations that reach it, and the class proportions in the leaf serve as estimates of the class probabilities. The tree is grown by recursive binary splitting, as before, but the RSS is no longer a sensible measure of how good a split is. It is replaced by a measure of the impurity of a node.
11.4.1 Measures of Node Impurity
Let \(\hat{p}_{mk}\) be the proportion of training observations in node \(m\) that belong to class \(k\), for \(k = 1, \ldots, K\). Three measures of impurity are in common use.
Classification error: the fraction of observations in the node that do not belong to its most common class, \[
E_m = 1 - \max_k \hat{p}_{mk} .
\]
Gini index: \[
G_m = \sum_{k=1}^{K} \hat{p}_{mk}\,(1 - \hat{p}_{mk}) = 1 - \sum_{k=1}^{K} \hat{p}_{mk}^2 .
\] The Gini index is \(0\) when the node is pure (all of its observations belong to one class) and is largest when the classes are equally represented: \(0.5\) for two classes. A node with \(90\%\) of one class and \(10\%\) of another has \(G = 1 - (0.9^2 + 0.1^2) = 0.18\).
Entropy: \[
D_m = - \sum_{k=1}^{K} \hat{p}_{mk} \log_2 \hat{p}_{mk} ,
\] with \(0 \log_2 0 = 0\). The entropy is also \(0\) for a pure node, and reaches \(1\) for two equally represented classes. The reduction of entropy produced by a split is called the information gain.
The impurity of a split is the weighted average of the impurities of its two children, \(\frac{n_L}{n} I_L + \frac{n_R}{n} I_R\), and the best split is the one that reduces impurity the most.
p <-seq(0.001, 0.999, length.out =200)impurity <-data.frame(p =rep(p, 3),value =c(1-pmax(p, 1- p),2* p * (1- p),-(p *log2(p) + (1- p) *log2(1- p)) /2),measure =rep(c("Classification error", "Gini index", "Entropy / 2"), each =length(p)))ggplot(impurity, aes(p, value, colour = measure)) +geom_line(linewidth =1) +labs(x ="proportion of the second class", y ="impurity", colour =NULL) +theme_minimal()
The three impurity measures for a two-class node, as a function of the proportion p of the second class. The entropy is divided by two so that all three curves reach 0.5 at p = 0.5.
The Gini index and the entropy are numerically very similar, and they are both smooth and strictly concave. The classification error has a kink and is linear on each side of it. That is why it is a poor criterion for growing a tree: it is not sensitive enough to changes in the node proportions. Consider a node with \(400\) observations of each of two classes and two candidate splits (Hastie et al. 2009):
split A produces children with \((300, 100)\) and \((100, 300)\) observations;
split B produces children with \((200, 400)\) and \((200, 0)\) observations.
Both splits misclassify \(200\) observations, so the classification error cannot tell them apart (\(0.25\) for both). The Gini index and the entropy prefer split B, which creates a pure node — a node that never needs to be split again. For this reason trees are grown with the Gini index or the entropy. The classification error is the natural measure of the final tree, and it can be used to prune it if accuracy is the goal (James et al. 2021).
rpart() uses the Gini index by default; parms = list(split = "information") selects the entropy.
11.4.2 A First Example: Iris
The iris data set contains four measurements of \(150\) iris flowers of three species, setosa, versicolor and virginica: Sepal.Length, Sepal.Width, Petal.Length and Petal.Width, in centimetres.
The three species of iris (source: https://www.datacamp.com/tutorial/machine-learning-in-r)
iris_tree <-rpart(Species ~ ., data = iris, method ="class")iris_tree
rpart.plot(iris_tree, type =2, extra =104, fallen.leaves =TRUE)
Classification tree for the species of iris flowers. Each node shows the predicted species, the proportion of each species in the node, and the percentage of all flowers in the node.
For a classification tree the printed output gives, for each node, the number of observations, the loss (the number of observations not in the predicted class), the predicted class yval and the class proportions yprob. The tree has three leaves:
if Petal.Length\(< 2.45\), then setosa: the \(50\) flowers in this leaf are all setosa;
if Petal.Length\(\geq 2.45\) and Petal.Width\(< 1.75\), then versicolor: \(91\%\) of the \(54\) flowers in this leaf are versicolor and \(9\%\) virginica;
if Petal.Length\(\geq 2.45\) and Petal.Width\(\geq 1.75\), then virginica: \(98\%\) of the \(46\) flowers are virginica.
The plot rounds the cut points to two digits (\(2.5\) and \(1.8\)). Versicolor and virginica are harder to separate than setosa, and the tree misclassifies \(6\) of the \(150\) flowers, an accuracy of \(96\%\) on the data it was grown on.
Note
Why only two variables appear in the tree? The tree does not try to use every variable; at each node it picks the one that separates the classes best. In the iris data the petal measurements are much more distinctive between species than the sepal measurements, so the algorithm finds that Petal.Length and Petal.Width alone classify almost perfectly. If we removed the petal variables and grew a new tree, the sepal variables would appear instead.
11.4.3 Predicting High Sales: Carseats
We now grow a classification tree for High on the Carseats training set.
car_tree <-rpart(High ~ ., data = car_train, method ="class")car_tree
Classification tree for High sales at the Carseats stores. Each node shows the predicted class, the proportion of stores with High = Yes, and the percentage of stores in the node.
The most important predictor is the price the store charges. The \(27\) stores with a price below $\(91.5\) have high sales in \(85\%\) of cases. Among the others, the price matters relative to the competitor’s: where the competitor charges less than $\(121.5\), only \(11\%\) of stores have high sales. Where the competitor is more expensive, a price below $\(127\) and a shelving location that is not Bad give a high chance of high sales (\(83\%\)). Notice that the split on ShelveLoc sends two of its three levels, Good and Medium, down the same branch.
On the test set:
car_pred <-predict(car_tree, car_test, type ="class")table(predicted = car_pred, actual = car_test$High)
actual
predicted No Yes
No 81 29
Yes 38 52
mean(car_pred == car_test$High)
[1] 0.665
The tree classifies \(81 + 52 = 133\) of the \(200\) test stores correctly, an accuracy of \(66.5\%\). Of the \(81\) stores with high sales it finds \(52\).
With type = "prob", predict() returns the class proportions of the leaf that each store falls into. A tree with six leaves can only produce six different probabilities:
table(round(predict(car_tree, car_test, type ="prob")[, "Yes"], 3))
0.109 0.14 0.25 0.6 0.826 0.852
62 37 11 12 46 32
Growing the same tree with the entropy instead of the Gini index:
car_tree_info <-rpart(High ~ ., data = car_train, method ="class",parms =list(split ="information"))c(leaves =sum(car_tree_info$frame$var =="<leaf>"),accuracy =mean(predict(car_tree_info, car_test, type ="class") == car_test$High))
leaves accuracy
7.000 0.695
The entropy produces a tree with one more leaf and a test accuracy of \(69.5\%\) instead of \(66.5\%\). The difference is six stores out of \(200\), within the noise of a test set this size; in general the two criteria give very similar trees.
Packages and commands.rpart(method = "class") grows a classification tree with the Gini index, or with the entropy when parms = list(split = "information"). predict(fit, newdata, type = "class") returns the predicted classes and type = "prob" the class proportions of the leaves; table cross-tabulates predictions and true classes, and mean(pred == obs) gives the accuracy. rpart.plot(extra = 104) shows all class probabilities, extra = 106 only the probability of the second class. The impurity measures are short base-R functions.
11.5 Training, Validation and Test Sets
A model is built to predict observations it has not seen. Its error on the observations it was fitted to, the training error, is a poor guide to how well it does that: it measures how closely the model has adapted to those particular observations, and a flexible model can adapt very closely. A tree grown until each leaf holds a single observation has a training error of zero, and yet it predicts new observations badly (Section 11.7). What we want to know is the test error: the expected error on new observations from the same population. It can only be estimated with observations that played no part in building the model.
11.5.1 Three Sets for Three Tasks
Besides fitting the model, building a predictive model involves two tasks that need data of their own (Hastie et al. 2009, sec. 7.2):
model selection: comparing candidate models and choosing their tuning parameters — the size of a tree, the number of predictors sampled by a random forest, the learning rate of boosting;
model assessment: estimating the test error of the final model, once it has been chosen.
When data are plentiful, they are split at random into three parts, one for each task. Hastie et al. (2009) suggest \(50\%\), \(25\%\) and \(25\%\) as a typical split.
Set
Used to
Typical share
training
fit every candidate model: find its splits and leaf predictions
\(50\%\)
validation
estimate the error of every candidate, and choose the best one
\(25\%\)
test
estimate the error of the chosen model, once, at the end
\(25\%\)
The test set must be kept apart from the validation set because the validation error of the winning model is itself optimistic. It is the smallest of several noisy estimates, and it is the smallest partly by luck. A test set that has never been used to make a choice gives an honest estimate.
When data are scarce, setting a quarter of them aside for validation is wasteful. The validation set is then replaced by cross-validation inside the training set, described below, and the data are split in two only. That is what this chapter does: each data set is split in half, every choice is made on the training half — by cross-validation, or by the out-of-bag error of Section 11.9.2 — and the test half is used only to compare the final models.
11.5.2 The Validation-Set Approach
To see the three sets at work, we split the Boston training half once more: two thirds of its \(253\) tracts for fitting the candidate models, and the remaining third for validating them. The test half is not touched. The candidates are regression trees that differ in a single tuning parameter, the minimum number \(m\) of tracts in a leaf (the option minbucket of rpart.control()). With \(m = 1\) a leaf can hold a single tract and the tree can follow the training data very closely; with a large \(m\) the tree has only a few large leaves.
set.seed(1)val_idx <-sample(nrow(bos_train), round(nrow(bos_train) /3))bos_fit <- bos_train[-val_idx, ] # 169 tracts to fit the candidate treesbos_val <- bos_train[val_idx, ] # 84 tracts to validate them# a tree whose leaves hold at least m tracts (cp = 0: no other limit on its size)leaf_tree <-function(data, m) {rpart(medv ~ ., data = data, control =rpart.control(cp =0, minbucket = m, xval =0))}m_grid <-c(1, 2, 3, 5, 7, 10, 15, 20, 30, 50)val_curve <-t(sapply(m_grid, function(m) { fit <-leaf_tree(bos_fit, m)c(m = m,leaves =sum(fit$frame$var =="<leaf>"),training =mse(predict(fit), bos_fit$medv),validation =mse(predict(fit, bos_val), bos_val$medv))}))round(val_curve, 2)
Training and validation MSE of regression trees for the Boston data, against the minimum leaf size m (log scale). The trees are fitted to 169 tracts of the training half and validated on the other 84. The dotted line marks the leaf size with the smallest validation error.
From left to right the trees become smaller, from \(110\) leaves with \(m = 1\) to two leaves with \(m = 50\). The training error only increases: the larger the tree, the closer it follows the data it was grown on, down to an MSE of \(0.22\) for \(m = 1\). The validation error is U-shaped. It is high on the left, where large trees fit the noise of the \(169\) tracts (overfitting: low bias, high variance), and high on the right, where trees with two or three leaves miss most of the structure (underfitting: high bias). It is lowest at \(m = 7\), with a tree of \(12\) leaves.
Once \(m\) is chosen, the tree is grown again on the whole training half — more data give a better tree — and the test half is used, once, to estimate its error:
The final tree has \(20\) leaves and a test MSE of \(32.8\). It is more than twice the validation error of \(14.2\). Part of the gap is the optimism of the validation error after a choice has been made; most of it comes from the test half of Boston, which is harder to predict than the training half (Section 11.9.2).
11.5.3 Cross-Validation
The validation-set approach has two drawbacks (James et al. 2021, sec. 5.1). The models are fitted to only part of the training data, so they are worse than the model that will finally be used, and the validation error tends to overestimate its test error. And the estimate depends on which observations happen to fall in the validation set: with \(84\) tracts, a few hard tracts more or less change it noticeably.
\(K\)-fold cross-validation uses every observation for both purposes. The training set is divided at random into \(K\) groups, or folds, of about equal size. Each fold in turn serves as the validation set for a model fitted to the other \(K - 1\) folds, giving \(K\) estimates \(\text{MSE}_1, \ldots, \text{MSE}_K\), and the cross-validation estimate is their average, \[
\text{CV}_{(K)} = \frac{1}{K} \sum_{k=1}^{K} \text{MSE}_k .
\] Every observation is used for validation exactly once and for fitting \(K - 1\) times. With \(K = n\), each fold holds a single observation: this is leave-one-out cross-validation (LOOCV). The usual choices, \(K = 5\) or \(K = 10\), are cheaper and have been found to give a good balance between the bias and the variance of the estimate (James et al. 2021, sec. 5.1.4).
cv_mse <-function(data, m, folds) {mean(sapply(unique(folds), function(k) { fit <-leaf_tree(data[folds != k, ], m)mse(predict(fit, data[folds == k, ]), data$medv[folds == k]) }))}set.seed(1)folds <-sample(rep(1:10, length.out =nrow(bos_train))) # a fold number for every tracttable(folds)
The same folds are used for every value of \(m\), so that the comparison between candidates is not blurred by differences between folds. To compare the stability of the two approaches, we repeat each of them ten times, with ten different random validation sets and ten different random assignments of the tracts to folds:
one_run <-function(s) {set.seed(s) vi <-sample(nrow(bos_train), round(nrow(bos_train) /3))set.seed(s) f <-sample(rep(1:10, length.out =nrow(bos_train))) val <-sapply(m_grid, function(m)mse(predict(leaf_tree(bos_train[-vi, ], m), bos_train[vi, ]), bos_train$medv[vi])) cv <-sapply(m_grid, function(m) cv_mse(bos_train, m, f))data.frame(run = s, m =rep(m_grid, 2), mse =c(val, cv),method =rep(c("validation set", "10-fold cross-validation"), each =length(m_grid)))}runs <-do.call(rbind, lapply(1:10, one_run))runs$method <-factor(runs$method, levels =c("validation set", "10-fold cross-validation"))ggplot(runs, aes(m, mse, group = run)) +geom_line(colour ="grey35", alpha =0.7) +facet_wrap(~ method) +scale_x_log10(breaks = m_grid) +labs(x ="minimum leaf size m", y ="estimated MSE") +theme_minimal()
Left: validation MSE for ten random validation sets of 84 tracts. Right: 10-fold cross-validation MSE for ten random assignments of the tracts to folds. Both use the Boston training half; each line is one repetition.
# the leaf size chosen by each repetition (one column per repetition)chosen <-sapply(split(runs, runs$method), function(d)sapply(split(d, d$run), function(r) r$m[which.min(r$mse)]))t(chosen)
The ten validation curves differ in level and in shape, and the leaf size they choose ranges from \(1\) to \(7\). The ten cross-validation curves have the same shape and choose \(m = 3\), \(5\) or \(7\). Averaging them — repeated cross-validation — would give a still more stable estimate.
Cross-validation is used throughout the chapter. rpart() runs a 10-fold cross-validation every time it grows a tree, which Section 11.7 uses to choose the size of the tree; random forests offer a cheaper alternative, the out-of-bag error (Section 11.9.2); and gbm, xgboost and lightgbm have cross-validation functions of their own.
11.5.4 Stratified Splits
A random split can, by chance, give the two halves different distributions of the response. In Carseats, \(41\%\) of the \(400\) stores have high sales; the training half has \(41.5\%\) and the test half \(40.5\%\), which is close. Over many random splits, however, the proportion in the training half varies quite a lot:
# sample half of the rows of each class separatelystratified_half <-function(y) {unlist(lapply(split(seq_along(y), y), function(rows) sample(rows, round(length(rows) /2))))}set.seed(1)strat_idx <-stratified_half(carseats$High)c(train =mean(carseats$High[strat_idx] =="Yes"), test =mean(carseats$High[-strat_idx] =="Yes"))
train test
0.41 0.41
In \(95\%\) of random splits the training half has between \(36.5\%\) and \(45.5\%\) of high-sales stores. A stratified split samples separately within each class, so that both halves have exactly the class proportions of the whole data set. Stratifying matters most when one class is rare — in a data set with \(6\%\) of positive cases, such as the Caravan data of Exercise 6, a random training set may contain very few of them — and for cross-validation folds, which are smaller still. For a numeric response, the same idea is applied to groups defined by its quantiles, for example the quartiles of medv. We keep the simple random splits of the labs of James et al. (2021), so that the numbers can be compared with theirs.
The iris data of the classification section have \(50\) flowers of each species. A stratified split puts \(25\) of each species in each half; we use these halves to evaluate the iris tree in Section 11.6.
Use the test set once. If several models are compared on the test set and the best one is kept, its test error is optimistic for the same reason as a validation error.
Learn everything from the training data. Every step that learns from data is part of the model: imputing missing values, standardising the predictors, selecting predictors, choosing tuning parameters. Each step must use the training set alone, and with cross-validation it must be repeated inside every fold. When information from the test set reaches the model this way, the estimate is optimistic; this is called data leakage.
Respect the structure of the data. A random split assumes that the observations are independent. With data ordered in time, the model should be fitted to the past and tested on the future. With several rows per unit — the same patient on several visits, the same store in several weeks — all the rows of a unit go to the same side of the split. The rows of our three data sets are distinct players, census tracts and stores.
Mind the size of the test set. A larger training set gives a better model, a larger test set a more precise estimate of its error. With a few hundred observations, test errors are noisy; Section 11.6 shows how to attach a standard error to them.
Packages and commands. All in base R and rpart. sample(n, size) draws the rows of a random split, and sample(rep(1:K, length.out = n)) assigns every row to one of \(K\) folds; split(seq_along(y), y) groups the rows by class for a stratified split. rpart.control(cp = 0, minbucket = m, xval = 0) grows a tree limited only by its leaf size, without the internal cross-validation; sapply evaluates every candidate, and which.min picks the best one. The packages rsample (initial_split(data, prop, strata = ), vfold_cv()), used by Boehmke and Greenwell (2019), and caret (createDataPartition(), createFolds()) provide the same splits ready-made.
11.6 Performance and Prediction Metrics
So far a classification tree has been judged by its accuracy and a regression tree by its test MSE. A single number hides a great deal: which kinds of error the model makes, how confident it is when it is wrong, how large its typical error is. This section collects the main measures of performance — for predicted classes, for predicted probabilities and for predicted numbers. They are computed on the test set or, when they are used to choose a model, by cross-validation on the training set. The measure used to choose a model should be the one used to assess it, and both should reflect what an error costs in the application.
11.6.1 The Confusion Matrix
For a binary response, one class is called positive — usually the event of interest, here High = "Yes" — and the other negative. Every prediction then has one of four outcomes:
actual positive
actual negative
predicted positive
true positive (TP)
false positive (FP)
predicted negative
false negative (FN)
true negative (TN)
The table of the four counts is the confusion matrix, and most measures of performance are ratios of its cells:
The false positive rate is \(1 - \text{specificity}\). Cohen’s kappa(Cohen 1960) compares the accuracy with the accuracy \(p_e\) that would be expected by chance given the row and column totals of the matrix, \(\kappa = (\text{accuracy} - p_e) / (1 - p_e)\): it is \(0\) for agreement no better than chance and \(1\) for perfect agreement.
The function below computes all of them, and we apply it to the predictions of the Carseats tree of the classification section:
Of the \(81\) test stores with high sales, the tree finds \(52\): a sensitivity of \(64.2\%\). Of the \(119\) other stores it recognises \(81\): a specificity of \(68.1\%\). When it predicts high sales it is right in \(52\) of \(90\) cases, a precision of \(57.8\%\). Its accuracy of \(66.5\%\) should be compared with the no-information rate, the accuracy of predicting the majority class for every store: “No” is right for \(119\) of the \(200\) test stores, \(59.5\%\). The kappa of \(0.32\) says the same thing in another way — the tree is about a third of the way from chance to perfect agreement.
Which measure matters most depends on the cost of each kind of error. If a prediction of high sales means sending extra stock to a store, a false positive wastes stock and a false negative loses sales; a screening test for a disease must above all have a high sensitivity. When one class is rare, the accuracy is particularly misleading. With \(6\%\) of positive cases, as in the Caravan data of Exercise 6, a “model” that predicts “No” for everybody is \(94\%\) accurate and has a sensitivity of \(0\).
The precision of a test estimate. The test accuracy is a proportion of \(n\) test observations, with standard error \(\sqrt{\text{accuracy}\,(1 - \text{accuracy}) / n}\):
The standard error is \(3.3\) percentage points, so an approximate \(95\%\) confidence interval for the accuracy of the tree runs from about \(60\%\) to \(73\%\). Differences of a few stores between two trees — such as the six stores, three percentage points, between the Gini and the entropy trees of the classification section — are well within this margin. The standard error of a test MSE is computed in the same way, as the standard deviation of the squared errors divided by \(\sqrt{n}\); Section 11.11.6 uses it to compare the final models.
More than two classes. With \(K\) classes the confusion matrix is \(K \times K\). Sensitivity and precision are computed for each class against all the others together, and can be averaged over the classes (macro-averaging). We grow the iris tree on the stratified training half of Section 11.5 and evaluate it on the other half:
iris_half_tree <-rpart(Species ~ ., data = iris_train, method ="class")iris_half_tree
Grown on \(75\) flowers, the tree splits twice on Petal.Length, where the tree grown on all \(150\) flowers used Petal.Width for its second split. It classifies \(70\) of the \(75\) test flowers correctly (\(93.3\%\), against \(96\%\) on the data the full tree was grown on). All the errors are between versicolor and virginica: four versicolor flowers are classified as virginica, so the sensitivity for versicolor is \(84\%\) and the precision for virginica \(85.7\%\).
11.6.2 Thresholds, ROC Curves and AUC
A classification tree predicts the class with the larger probability, which for two classes means using a threshold of \(0.5\). Other thresholds give other classifiers: lowering it predicts “Yes” more often, which raises the sensitivity and lowers the specificity. The receiver operating characteristic (ROC) curve shows this trade-off for every possible threshold, by plotting the sensitivity against the false positive rate. The area under the curve (AUC) summarises it in one number: \(0.5\) for a classifier that guesses at random, \(1\) for one that separates the classes perfectly. The AUC is also the probability that a randomly chosen positive observation receives a higher predicted probability than a randomly chosen negative one, with ties counting one half (Fawcett 2006).
We compare the tree with a logistic regression on the same predictors (Classification chapter). Both functions below are written directly from these definitions:
car_prob <-predict(car_tree, car_test, type ="prob")[, "Yes"]car_logit <-glm(High ~ ., data = car_train, family = binomial)logit_prob <-predict(car_logit, car_test, type ="response")# false positive rate and sensitivity when "Yes" is predicted for prob >= thresholdroc_points <-function(prob, obs, positive ="Yes") { thresholds <-c(Inf, sort(unique(prob), decreasing =TRUE))data.frame(threshold = thresholds,fpr =sapply(thresholds, function(t) mean(prob[obs != positive] >= t)),sensitivity =sapply(thresholds, function(t) mean(prob[obs == positive] >= t)))}# probability that a random positive gets a higher score than a random negativeauc <-function(prob, obs, positive ="Yes") { r <-rank(prob) # tied scores share their average rank n1 <-sum(obs == positive) n0 <-sum(obs != positive) (sum(r[obs == positive]) - n1 * (n1 +1) /2) / (n1 * n0)}round(roc_points(car_prob, car_test$High), 3)
ROC curves of the Carseats classification tree and of a logistic regression, on the test set. Each point on the tree’s curve is one of its possible thresholds; the dashed diagonal is a classifier that guesses at random.
The tree has only six different probabilities, one per leaf, so it has only seven possible classifiers, from “No” for every store to “Yes” for every store; its ROC curve joins them by straight lines. The usual threshold of \(0.5\) gives the point with a false positive rate of \(31.9\%\) and a sensitivity of \(64.2\%\). A threshold of \(0.14\) would find \(75\%\) of the high-sales stores, at the price of predicting high sales for \(65\%\) of the others. The logistic regression is better at every threshold: its AUC is \(0.96\), against \(0.66\) for the tree.
11.6.3 Probabilities: Brier Score, Log-Loss and Calibration
When the predicted probabilities themselves are used — to rank stores, or to compute expected sales — they should be assessed as probabilities. With \(y_i = 1\) for a positive and \(0\) for a negative observation, the two standard measures are the Brier score(Brier 1950) and the log-loss, \[
\text{Brier} = \frac{1}{n} \sum_{i=1}^{n} (\hat{p}_i - y_i)^2 ,
\qquad
\text{log-loss} = -\frac{1}{n} \sum_{i=1}^{n} \left[ y_i \log \hat{p}_i + (1 - y_i) \log (1 - \hat{p}_i) \right] .
\] Both are \(0\) for perfect, fully confident predictions. The log-loss is the Bernoulli deviance that logistic regression and boosting for classification minimise (Section 11.10), divided by \(n\). It punishes confident mistakes severely, and is infinite if an event happens to which the model gave probability \(0\) — a real risk for a tree, whose pure leaves predict exactly \(0\) or \(1\). As a benchmark we use the null model, which gives every store the proportion of high-sales stores in the training set, \(41.5\%\):
The tree’s probabilities are worse than those of the null model, by both measures (\(0.248\) against \(0.241\), and \(0.725\) against \(0.675\)), even though its classes beat the no-information rate. The reason is calibration. A model is well calibrated when, among the observations to which it gives a probability \(p\), a share of about \(p\) are positive. For a tree the check takes one line per leaf:
leaf_prob <-factor(round(car_prob, 3)) # one level per leafdata.frame(predicted =as.numeric(levels(leaf_prob)),observed =round(as.vector(tapply(y01, leaf_prob, mean)), 3),test_stores =as.vector(table(leaf_prob)))
The leaves that promise \(83\%\) and \(85\%\) of high-sales stores deliver \(59\%\) and \(69\%\), and the leaf that promises \(11\%\) delivers \(32\%\). The leaf proportions are too extreme because they are computed from the same stores that were used to choose the splits, and every split was chosen precisely because it made its two children look as pure as possible; leaves with \(10\) or \(12\) training stores make this worse. Averaging the probabilities of many trees, as bagging and random forests do, gives far better calibrated probabilities. For a model with many different probabilities, the predictions are grouped into bins (deciles, for example), and the observed share of positives is plotted against the mean predicted probability of each bin: a calibration plot.
11.6.4 Prediction Metrics for a Numeric Response
For a numeric response, the measures are built from the test residuals \(e_i = y_i - \hat{y}_i\): \[
\text{MSE} = \frac{1}{n} \sum_{i=1}^{n} e_i^2 , \qquad
\text{RMSE} = \sqrt{\text{MSE}} , \qquad
\text{MAE} = \frac{1}{n} \sum_{i=1}^{n} |e_i| , \qquad
\text{bias} = \frac{1}{n} \sum_{i=1}^{n} e_i , \qquad
R^2_{\text{test}} = 1 - \frac{\text{MSE}}{\text{MSE}_{\text{null}}} .
\]
The MSE is the criterion that a regression tree minimises when it chooses its splits. Because it squares the errors, a few large errors can dominate it.
The RMSE ranks models as the MSE does, but is expressed in the units of the response.
The mean absolute error (MAE) is the average size of an error, also in the units of the response; large errors count in proportion to their size, not to its square. The median absolute error is the size of a typical error, and ignores the largest ones altogether.
The bias is positive when the model predicts too low on average.
\(R^2_{\text{test}}\) is the share of the test MSE of the null model, \(\text{MSE}_{\text{null}}\), that the model removes; the null model predicts every observation by the mean of the training set. Unlike the \(R^2\) of a fitted linear model, it can be negative: a model can predict new data worse than the mean does.
MSE RMSE MAE median_AE bias R2
tree 35.29 5.94 3.69 2.37 0.68 0.62
linear 27.65 5.26 3.68 2.91 0.26 0.70
null 93.08 9.65 6.91 5.09 1.49 0.00
The three measures of the size of the errors tell different stories. By MSE, the linear regression is clearly better than the tree (\(27.65\) against \(35.29\)). By MAE the two are tied (\(3.68\) against \(3.69\), that is, about \(\$3\,700\)). By the median absolute error the tree is better (\(2.37\) against \(2.91\)). The tree predicts the typical tract at least as well as the linear regression, but it makes a few very large errors, and the MSE squares them. Both models remove about two thirds of the error of the null model, and all three have a positive bias: the test tracts are on average worth \(\$1\,490\) more than the training tracts.
Observed against predicted median value for the 253 Boston test tracts. The tree can only predict seven different values, one per leaf. The dashed line marks perfect predictions.
The largest errors of both models are tracts whose value is capped at \(50\): the three largest errors of the tree, and four of the five largest of the linear regression. The tree predicts \(\$21\,400\) for each of those three tracts.
The scale of the response. For Hitters the response is the logarithm of the salary. A residual \(e_i\) on the log scale means that the predicted salary is off by a factor \(\exp(e_i)\), so the metrics on the log scale measure relative errors. The predictions can also be transformed back to dollars, and the metrics computed there:
hit_tree <-rpart(logSalary ~ ., data = hit_train)hit_lm <-lm(logSalary ~ ., data = hit_train)hit_mean <-mean(hit_train$logSalary)hit_pred <-list(tree =predict(hit_tree, hit_test), linear =predict(hit_lm, hit_test), null = hit_mean)# on the log scaleround(t(sapply(hit_pred, reg_metrics, obs = hit_test$logSalary, train_mean = hit_mean)), 3)
MSE RMSE MAE median_AE bias R2
tree 0.274 0.524 0.404 0.347 -0.006 0.656
linear 0.530 0.728 0.586 0.503 -0.226 0.334
null 0.797 0.893 0.765 0.687 -0.006 0.000
# in dollarssalary <-1000*exp(hit_test$logSalary)round(t(sapply(hit_pred, function(p) { e <- salary -1000*exp(p)c(RMSE =sqrt(mean(e^2)), MAE =mean(abs(e)), median_pct_error =100*median(abs(e) / salary))})))
RMSE MAE median_pct_error
tree 338689 215690 35
linear 1002053 420523 48
null 501406 342340 54
On the log scale the tree removes \(66\%\) of the error of the null model and the linear regression only \(33\%\). The tree’s MAE of \(0.40\) means that a typical prediction is off by a factor of about \(\exp(0.40) \approx 1.5\), and in dollars its median error is \(35\%\) of the salary. In dollars, the linear regression is worse than the null model by both RMSE and MAE: a few of its predictions are much too high on the log scale, and the exponential turns them into enormous errors in dollars. A metric should be computed on the scale on which the predictions will be used.
Packages and commands. The measures are short base-R functions: table(predicted = , actual = ) builds the confusion matrix, diag, rowSums and colSums give the per-class counts, rank computes the AUC, and tapply the observed share of positives in each leaf. predict(fit, type = "prob") (rpart) and predict(fit, type = "response") (glm) return probabilities. Ready-made versions are in yardstick (conf_mat(), sens(), spec(), precision(), f_meas(), roc_curve(), roc_auc(), mn_log_loss(), rmse(), mae(), rsq()), pROC (roc(), auc(), ci.auc()) and caret (confusionMatrix()).
11.7 Pruning and Complexity Reduction
11.7.1 Why a Large Tree Overfits
Recursive binary splitting can continue until every leaf contains a single observation, or only observations with the same response. Such a tree fits the training data perfectly and generalises badly: it has low bias but very high variance. To see this, we grow the Boston tree as far as it will go, with cp = 0 (no minimum improvement), minsplit = 2 and minbucket = 1:
The tree has \(243\) leaves for \(253\) training tracts, and a training MSE of exactly \(0\). Its test MSE, \(43.8\), is worse than that of the seven-leaf tree of the previous section (\(35.3\)). A smaller tree, with fewer splits, has lower variance and is easier to interpret, at the cost of a little bias. There are two ways to obtain one: stop the growth early, or grow a large tree and then prune it back.
11.7.2 Early Stopping
Early stopping, or pre-pruning, stops splitting a node when a rule is met. The rpart.control() options of the previous section are rules of this kind: minsplit (do not split a node with fewer observations), minbucket (do not create a leaf with fewer observations) and maxdepth (do not grow below a given depth). A fourth natural rule is to split only if the split reduces the RSS, or the impurity, by more than some threshold.
Early stopping is fast but short-sighted. A split that looks worthless may be followed by a very good one. The classic example is an exclusive or (XOR): two predictors \(x_1\) and \(x_2\) uniform on \([-1, 1]\), and a class that is \(A\) when exactly one of them is positive.
set.seed(1)n <-400x1 <-runif(n, -1, 1)x2 <-runif(n, -1, 1)cls <-ifelse((x1 >0) != (x2 >0), "A", "B")flip <-runif(n) <0.1# label noise: each label flipped with probability 0.1cls[flip] <-ifelse(cls[flip] =="A", "B", "A")xor_data <-data.frame(x1, x2, class =factor(cls))stump <-rpart(class ~ x1 + x2, data = xor_data, method ="class",control =rpart.control(maxdepth =1, cp =0))deep <-rpart(class ~ x1 + x2, data = xor_data, method ="class")c(root_error =1-max(table(xor_data$class)) / n,stump_error =mean(predict(stump, type ="class") != xor_data$class),tree_error =mean(predict(deep, type ="class") != xor_data$class))
No single split helps much. Predicting the majority class at the root misclassifies \(48\%\) of the observations, and the best stump still misclassifies \(45\%\), because each half of the square contains both classes in roughly equal numbers. Yet a tree of depth two, splitting at \(x_1 = 0\) and then at \(x_2 = 0\), would misclassify only the \(12\%\) of observations whose labels were flipped. A rule such as “split only if the error falls by at least five percentage points” would stop at the root and never find this tree. The default rpart() tree finds the pattern anyway (training error \(12\%\)), because its cp rule is applied to whole subtrees, as described below.
11.7.3 Cost-Complexity Pruning
The better strategy is to grow a very large tree \(T_0\) and then prune it back to a subtree. We cannot estimate the test error of every possible subtree, but cost-complexity pruning (also called weakest-link pruning) considers only a sequence of them, indexed by a tuning parameter \(\alpha \geq 0\). For each \(\alpha\) there is a subtree \(T \subset T_0\) that minimises \[
\sum_{m=1}^{|T|} \sum_{i:\, x_i \in R_m} \left(y_i - \hat{y}_{R_m}\right)^2 + \alpha\,|T| ,
\] where \(|T|\) is the number of leaves of \(T\) and \(R_m\) the region of the \(m\)-th leaf. The parameter \(\alpha\) is the price of one extra leaf. When \(\alpha = 0\) the minimiser is \(T_0\) itself; as \(\alpha\) increases, branches are pruned off one at a time, always the branch that buys the smallest decrease in RSS per leaf removed (the weakest link). The subtrees form a nested sequence, from \(T_0\) down to the root alone, and the whole sequence can be computed quickly. For a classification tree the RSS is replaced by the misclassification count, or by an impurity measure.
Grow a large tree \(T_0\) on the training data, stopping only when each leaf has fewer than some minimum number of observations.
Compute the sequence of best subtrees as a function of \(\alpha\).
Choose \(\alpha\) by \(K\)-fold cross-validation: for each fold \(k\), repeat steps 1 and 2 on all but the \(k\)-th fold, and evaluate the error of each subtree on the \(k\)-th fold. Average over the folds, and pick the \(\alpha\) with the smallest average error.
Return the subtree of step 2 that corresponds to the chosen \(\alpha\).
rpart expresses \(\alpha\) relative to the error of the root, which makes it unit-free: \[
\texttt{cp} = \frac{\alpha}{\text{RSS of the root}} .
\] A split is worth keeping if it reduces the error by at least cp times the error of the root. The default cp = 0.01 therefore asks every split to improve the \(R^2\) by at least one percentage point. While it grows the tree, rpart() already discards any subtree that does not meet this standard, which is why it found the XOR pattern above: the first split is kept because the subtree below it is worth much more than cp per split.
Every rpart() call also performs step 3: with xval = 10 (the default) it runs a 10-fold cross-validation of the whole sequence, and stores the result in the cp table.
11.7.4 Pruning the Boston Tree
printcp() prints the cp table. For the large Boston tree it has \(183\) rows; the first ten are:
CP: the smallest value of cp for which the tree in this row is the best subtree (it stays the best up to the CP of the row above); prune() with this value returns that tree;
nsplit: the number of splits, one less than the number of leaves;
rel error: the training error of that tree relative to the root, \(\text{RSS}(T) / \text{RSS}(\text{root})\), which always decreases;
xerror: the cross-validated error, also relative to the root;
xstd: the standard error of xerror across the folds.
plotcp() plots xerror against cp, with the size of the tree on the top axis and a horizontal line one standard error above the minimum:
plotcp(bos_big, upper ="size")
Cross-validated relative error of the subtrees of the large Boston tree. The dashed line is one standard error above the minimum.
Two rules are common for choosing the tree. The first takes the cp with the smallest xerror. The second, the one-standard-error rule(Breiman et al. 1984), takes the smallest tree whose xerror is within one standard error of that minimum, on the grounds that the cross-validation estimates are themselves uncertain and a simpler tree is preferable when the data cannot tell the two apart.
Here both rules choose the same row: \(5\) splits, that is \(6\) leaves, with cp\(= 0.0151\). The function prune() cuts the large tree back at this value:
bos_pruned <-prune(bos_big, cp = cp_tab[i_1se, "CP"])rpart.plot(bos_pruned, type =2, digits =3)
The Boston tree pruned by cross-validation: 6 leaves, out of the 243 of the unpruned tree.
Pruning reduces the tree from \(243\) leaves to \(6\) and the test MSE from \(43.8\) to \(35.2\). The pruned tree is the default tree of the previous section without its split on age — the default cp = 0.01 is itself a (cruder) choice of the pruning parameter.
The next figure tracks the three errors along the whole sequence of subtrees. The training error falls steadily to \(0\). The cross-validation and test errors both reach their minimum at \(6\) leaves, and are higher for every larger tree.
Training, cross-validation and test MSE of the subtrees of the large Boston tree, against the number of leaves (log scale). The dotted line marks the tree chosen by cross-validation.
The cross-validation error is computed from the training half only, and is lower than the test error throughout: the test half of Boston is harder to predict than the training half, a point we return to in Section 11.9.2. What matters for pruning is that both curves agree on where the minimum lies.
11.7.5 Pruning the Carseats Tree
The same steps apply to a classification tree, with the misclassification rate in place of the RSS:
The Root node error is the misclassification rate of predicting “No” for every store, \(83/200 = 0.415\), and rel error and xerror are relative to it. The full tree has \(39\) leaves and classifies every training store correctly. The smallest xerror is reached with \(6\) splits; the one-standard-error rule selects \(4\) splits.
Pruning takes the tree from \(39\) leaves to \(5\), and the test accuracy from \(67.5\%\) to \(69.5\%\). The difference is four stores out of \(200\) and well within the noise of a test set of this size; the gain is a tree that can be read at a glance. This is also the conclusion of the corresponding lab in James et al. (2021).
Packages and commands.rpart.control(cp = 0, minsplit = 2, minbucket = 1) grows the largest possible tree, and maxdepth, minsplit and minbucket are the early-stopping rules. Every fit stores its cross-validated cp table in fit$cptable (columns CP, nsplit, rel error, xerror, xstd), printed by printcp(fit) and plotted by plotcp(fit, upper = "size"); set.seed makes the folds reproducible. which.min and which implement the minimum and one-standard-error rules, and prune(fit, cp = ) returns the pruned subtree.
they are easy to explain, even more so than linear regression, and a small tree can be read by someone without statistical training;
they arguably mirror human decision-making more closely than other models;
they handle qualitative predictors without creating dummy variables;
they need no scaling or transformation of the predictors: a split depends only on the order of the values, so it is unchanged by a logarithm, and an extreme value of a predictor cannot pull a split towards it;
they capture interactions between predictors automatically, and they handle missing values in the predictors.
This section looks at the last of these advantages and at two diagnostics, variable importance and stability. The last subsection compares trees with linear models.
11.8.1 Missing Values and Surrogate Splits
When a predictor is missing for an observation, a tree cannot ask the question that involves it. CART solves this with surrogate splits. At every node, after choosing the primary split, rpart() looks for splits on other predictors that send the observations to the same side as the primary split as often as possible. An observation with a missing value of the primary variable is sent down the tree by the best surrogate whose variable is not missing; if all of them are missing, it follows the majority of the training observations. The summary() of a tree lists the surrogates. To keep the output short, we grow a stump on the Hitters training set:
hit_tree <-rpart(logSalary ~ ., data = hit_train)summary(rpart(logSalary ~ ., data = hit_train, control =rpart.control(maxdepth =1)))
Call:
rpart(formula = logSalary ~ ., data = hit_train, control = rpart.control(maxdepth = 1))
n= 131
CP nsplit rel error xerror xstd
1 0.5488897 0 1.0000000 1.0118635 0.09239132
2 0.0100000 1 0.4511103 0.5635742 0.08689602
Variable importance
CAtBat CRuns CHits CRBI CWalks Years
19 19 19 16 16 12
Node number 1: 131 observations, complexity param=0.5488897
mean=5.930225, MSE=0.7786933
left son=2 (50 obs) right son=3 (81 obs)
Primary splits:
CRuns < 179.5 to the left, improve=0.5488897, (0 missing)
CAtBat < 1407.5 to the left, improve=0.5488897, (0 missing)
CHits < 331 to the left, improve=0.5454099, (0 missing)
CWalks < 123 to the left, improve=0.5303501, (0 missing)
CRBI < 98 to the left, improve=0.5186866, (0 missing)
Surrogate splits:
CAtBat < 1407.5 to the left, agree=1.000, adj=1.00, (0 split)
CHits < 347.5 to the left, agree=0.992, adj=0.98, (0 split)
CRBI < 134.5 to the left, agree=0.931, adj=0.82, (0 split)
CWalks < 132 to the left, agree=0.931, adj=0.82, (0 split)
Years < 4.5 to the left, agree=0.855, adj=0.62, (0 split)
Node number 2: 50 observations
mean=5.09811, MSE=0.4091354
Node number 3: 81 observations
mean=6.443876, MSE=0.3155612
The root of the tree splits on CRuns < 179.5. For each surrogate, agree is the proportion of players it sends to the same side as the primary split, and adj the improvement over the trivial rule of sending everybody to the larger side. CAtBat < 1407.5 agrees on every one of the \(131\) players, and CHits < 347.5 on all but one: career totals are very highly correlated with each other.
To see the surrogates at work, we predict the test set as if CRuns had not been recorded for any player:
With the surrogates, the test MSE barely moves (\(0.256\) against \(0.274\) with the complete data; only \(7\) of the \(132\) predictions change). With usesurrogate = 0 every player stops at the root, because the root’s question cannot be answered, and receives the mean of the whole training set: the MSE jumps to \(0.797\), the error of the null model.
Surrogates also let rpart()train on incomplete data. If \(10\%\) of the values of every predictor in the training set are deleted at random, only \(18\) of the \(131\) players are left with complete records, so a method that needs complete cases would lose most of the data:
set.seed(1)hit_train_na <- hit_trainfor (v in num_vars) hit_train_na[[v]][runif(nrow(hit_train_na)) <0.1] <-NAc(complete_rows =sum(complete.cases(hit_train_na)),test_mse =mse(predict(rpart(logSalary ~ ., data = hit_train_na), hit_test), hit_test$logSalary))
complete_rows test_mse
18.0000000 0.2609167
The tree grown on the damaged training set has a test MSE of \(0.261\), as good as the one grown on the complete data. The ensemble methods differ in this respect: randomForest does not accept missing values (they must be imputed first, for example with na.roughfix() or rfImpute()), while xgboost and lightgbm learn, at each split, which branch the missing values should follow. Surrogates help only when other predictors carry the same information; when no predictor resembles the primary one, nothing can replace it. See also the Missing Values chapter.
11.8.2 Variable Importance
A tree with a handful of splits shows its important variables directly. For larger trees, rpart computes an importance score for each variable: the sum of the reductions in RSS (or impurity) of all the splits on that variable, plus the reductions of the splits in which the variable is a surrogate, weighted by its adj. The vip package (Greenwell and Boehmke 2020) draws it:
Variable importance of the Hitters tree. CHits and CRBI rank high although they are never used as a primary split, because they are excellent surrogates for CRuns.
The tree splits on CRuns, CAtBat, Walks, HmRun and Division, yet CHits, CRBI and CWalks rank among the most important variables. They are near-copies of CRuns, and the importance score credits them for the splits they could have made. The scores show which variables carry the information, not which ones happen to appear in the drawing.
11.8.3 Instability
The main weakness of a tree is its instability: a small change in the data can produce a very different tree. Errors made near the root propagate to every split below it. At the root of the Carseats tree, summary(car_tree) shows that the best split on Price (improvement \(11.9\)) is only slightly better than the best split on ShelveLoc (\(11.1\)), and a few different stores could reverse the order. To see this, we grow trees on bootstrap samples of the training set — samples of \(200\) stores drawn with replacement from the \(200\) training stores, so that some stores appear several times and others not at all.
boot_tree <-function(seed) {set.seed(seed) rows <-sample(nrow(car_train), replace =TRUE)rpart(High ~ ., data = car_train[rows, ], method ="class")}par(mfrow =c(2, 2))for (b in1:4) {rpart.plot(boot_tree(b), type =2, extra =106, roundint =FALSE,main =paste("Bootstrap sample", b))}
Four classification trees grown on bootstrap samples of the same 200 Carseats stores.
par(mfrow =c(1, 1))# the variable used at the root, over 50 bootstrap samplestable(root =sapply(1:50, function(b) as.character(boot_tree(b)$frame$var[1])))
root
Age CompPrice Price ShelveLoc
2 1 32 15
The four trees, grown on four versions of the same \(200\) stores, start with four different questions: Age\(\geq 51\), Price\(\geq 92\), Price\(\geq 88\) and ShelveLoc. They also differ in size, from six to eight leaves, and in the variables used further down. Over \(50\) bootstrap samples, the root splits on Price\(32\) times, on ShelveLoc\(15\) times, and on Age or CompPrice in the remaining three.
The test predictions vary just as much. We grow \(100\) bootstrap trees and look at the probability each one gives to High = "Yes" for every test store:
set.seed(1)probs <-replicate(100, { rows <-sample(nrow(car_train), replace =TRUE) fit <-rpart(High ~ ., data = car_train[rows, ], method ="class")predict(fit, car_test, type ="prob")[, "Yes"]})dim(probs) # 200 test stores x 100 trees
For a typical store, the probability of high sales varies by \(0.29\) (one standard deviation) from tree to tree. A single bootstrap tree classifies \(69.3\%\) of the test stores correctly on average. If instead we average the \(100\) probabilities and classify with the average, the accuracy rises to \(79\%\). Averaging cancels much of the tree-to-tree variability. This is the idea behind bagging, the subject of the next section.
11.8.4 Trees Versus Linear Models
A linear model assumes \[
f(X) = \beta_0 + \sum_{j=1}^{p} \beta_j X_j ,
\] while a regression tree assumes \[
f(X) = \sum_{m=1}^{|T|} c_m \cdot \mathbb{1}(X \in R_m) ,
\] a constant \(c_m\) in each box. Which one is better depends on the problem. If the relationship between the response and the predictors is close to linear, a linear model will be hard to beat, and a tree can only approximate the straight line by a staircase. If the relationship is highly nonlinear, or driven by interactions, a tree may do better (James et al. 2021).
set.seed(1)lin <-data.frame(x =runif(200, 0, 10))lin$y <-2+0.5* lin$x +rnorm(200, sd =0.5)lin$tree <-predict(rpart(y ~ x, data = lin), lin)ggplot(lin, aes(x, y)) +geom_point(colour ="grey60", size =1) +geom_smooth(method ="lm", formula = y ~ x, se =FALSE, colour ="grey40") +geom_step(aes(y = tree), linewidth =0.9) +theme_minimal()
A tree (black) approximating a linear relationship (simulated data) by a staircase. The grey line is the least-squares fit.
The Carseats data are an example of the first kind: in this simulated data set the sales are close to a linear function of the predictors (a linear regression of Sales on the ten predictors explains \(87\%\) of its variance). A logistic regression for High (Classification chapter) does far better than the tree:
car_logit <-glm(High ~ ., data = car_train, family = binomial)car_logit_pred <-ifelse(predict(car_logit, car_test, type ="response") >0.5, "Yes", "No")c(logistic =mean(car_logit_pred == car_test$High), pruned_tree =accuracy(car_pruned))
logistic pruned_tree
0.885 0.695
The linear regression also beat the tree on Boston (\(27.65\) against \(35.2\)). The ensemble methods of the next two sections close most of these gaps, and on Boston overtake the linear model, by combining many trees.
Packages and commands.summary(fit) lists the primary and surrogate splits of every node, with agree and adj; rpart.control(usesurrogate = 0) switches the surrogates off. fit$variable.importance holds the importance scores, and vip’s vip(fit, num_features = ) plots them. Bootstrap samples are sample(n, replace = TRUE), and replicate repeats the fit; par(mfrow = c(2, 2)) places four rpart.plot drawings on one figure. glm(family = binomial) fits the logistic regression, and ggplot2’s geom_step draws the staircase.
11.9 Bagging and Random Forests
11.9.1 Bagging
The bootstrap experiment of the previous section suggests a remedy for the variance of trees. Given \(n\) independent observations \(Z_1, \ldots, Z_n\), each with variance \(\sigma^2\), their mean \(\bar{Z}\) has variance \(\sigma^2 / n\): averaging reduces variance. Ideally we would fit a tree to each of \(B\) separate training sets and average the predictions. We have only one training set, but we can bootstrap it: draw \(B\) samples of size \(n\) with replacement, grow a tree \(\hat{f}^{*b}\) on the \(b\)-th sample, and average, \[
\hat{f}_{\text{bag}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}^{*b}(x) .
\] This is bagging, short for bootstrap aggregation(Breiman 1996). The trees are grown deep and not pruned: each one has low bias and high variance, and the averaging takes care of the variance. For classification, the trees vote and the forest predicts the majority class, or the class proportions of the votes are used as probabilities.
The number of trees \(B\) is not a critical parameter: a large \(B\) does not lead to overfitting, it only costs time. It needs to be large enough for the error to settle down, usually a few hundred.
11.9.2 Out-of-Bag Error
Bagging comes with a free estimate of its test error. The probability that a given observation is not drawn in a bootstrap sample of size \(n\) is \[
\left(1 - \frac{1}{n}\right)^n \approx e^{-1} \approx 0.368 ,
\] so each tree is grown on about two thirds of the observations, and the remaining third are out-of-bag (OOB) for that tree. Each observation can be predicted by the roughly \(B/3\) trees for which it was out-of-bag; averaging those predictions gives an OOB prediction for every observation, and from them an OOB error. With \(B\) large, the OOB error is essentially the leave-one-out cross-validation error, obtained without fitting any extra model.
11.9.3 Random Forests
When one predictor is much stronger than the others, most bagged trees use it for their first split, and the trees end up looking alike. Their predictions are then correlated, and averaging correlated quantities reduces variance much less: if the \(B\) predictions each have variance \(\sigma^2\) and pairwise correlation \(\rho\), their average has variance \[
\rho\,\sigma^2 + \frac{1 - \rho}{B}\,\sigma^2 ,
\] which never falls below \(\rho\,\sigma^2\), however many trees are added.
Random forests(Breiman 2001) decorrelate the trees with a small change: each time a split is considered, only a random sample of \(m\) of the \(p\) predictors is eligible. A fresh sample is drawn at every split. On average \((p - m)/p\) of the splits cannot use the strongest predictor, which gives the other predictors a chance and makes the trees more different from each other. With \(m = p\) a random forest is bagging. Common defaults are \(m = \lfloor p/3 \rfloor\) for regression and \(m = \lfloor \sqrt{p} \rfloor\) for classification, but \(m\) is a tuning parameter; a small \(m\) helps most when there are many correlated predictors.
11.9.4 Bagging and Random Forests in R
The randomForest package (Liaw and Wiener 2002) implements Breiman’s original algorithm. Its simplified format is
where ntree is the number of trees, mtry the number \(m\) of predictors sampled at each split (by default \(\lfloor p/3 \rfloor\) for regression and \(\lfloor \sqrt{p} \rfloor\) for classification), nodesize the minimum size of a leaf (\(5\) for regression and \(1\) for classification), and importance = TRUE computes permutation importance (see below).
Bagging is the special case mtry\(= p\). Boston has \(p = 12\) predictors:
Call:
randomForest(formula = medv ~ ., data = bos_train, mtry = 12, importance = TRUE)
Type of random forest: regression
Number of trees: 500
No. of variables tried at each split: 12
Mean of squared residuals: 11.40162
% Var explained: 85.17
mse(predict(bag, bos_test), bos_test$medv)
[1] 23.41916
The printed output gives the OOB MSE (Mean of squared residuals) and the share of the variance of medv that it explains. On the test set, the \(500\) bagged trees reach an MSE of \(23.42\), against \(35.2\) for the pruned tree — a reduction of a third.
A random forest only changes mtry. With the default \(\lfloor 12/3 \rfloor = 4\):
set.seed(1)rf <-randomForest(medv ~ ., data = bos_train, importance =TRUE)rf
Call:
randomForest(formula = medv ~ ., data = bos_train, importance = TRUE)
Type of random forest: regression
Number of trees: 500
No. of variables tried at each split: 4
Mean of squared residuals: 10.43128
% Var explained: 86.43
mse(predict(rf, bos_test), bos_test$medv)
[1] 18.99266
The test MSE falls again, to \(18.99\), well below the linear regression (\(27.65\)). (The lab in James et al. (2021) uses mtry = 6 and obtains \(20.07\).)
The OOB errors, \(11.40\) for bagging and \(10.43\) for the forest, are much lower than the test errors. That is mostly the luck of the split rather than a failure of the OOB estimate. The test half contains \(11\) of the \(16\) tracts whose value is capped at \(50\), which are the hardest to predict, and a handful of tracts dominate the test MSE:
Five of the \(253\) test tracts account for \(52\%\) of the test sum of squared errors. With a few hundred observations, any single test set gives a noisy estimate; the comparisons between methods on the same test set remain fair.
The OOB error is recorded after every tree, in rf$mse, so we can see how many trees are needed:
OOB MSE against the number of trees, for bagging (mtry = 12) and the random forest (mtry = 4). Both settle after about 100–200 trees.
The forest starts worse than bagging — a single tree that can only see four predictors at each split is a weak tree — but overtakes it after about \(50\) trees. The effect of mtry, on the OOB and on the test MSE:
mtry_effect <-t(sapply(1:12, function(m) {set.seed(1) fit <-randomForest(medv ~ ., data = bos_train, mtry = m)c(mtry = m, oob_mse =tail(fit$mse, 1), test_mse =mse(predict(fit, bos_test), bos_test$medv))}))round(mtry_effect, 2)
On both measures, every value of mtry from \(3\) to \(11\) does better than bagging (\(m = 12\)), and \(m = 1\) — trees that split on a randomly chosen variable — does worst. The OOB error is lowest at \(m = 5\) and the test error at \(m = 3\): the precise optimum is noisy, the general shape is not.
11.9.5 Interpreting a Forest
A forest of \(500\) trees cannot be drawn, so we need summaries. Two measures of variable importance are standard:
impurity importance: the total decrease in RSS (or Gini index) from the splits on each variable, summed over all trees and averaged;
permutation importance: for each tree, the OOB observations are predicted, then the values of one variable are randomly permuted and the OOB observations predicted again. The increase in error, averaged over all trees, measures how much the forest relies on that variable.
importance() returns both for a randomForest fit with importance = TRUE: %IncMSE is the permutation importance (divided by its standard error) and IncNodePurity the impurity importance.
Permutation importance of the twelve predictors in the Boston random forest.
Both measures rank the number of rooms (rm) and the share of lower-status population (lstat) first and second: far ahead of the rest by impurity, less markedly by permutation, where the crime rate crim is a clear third. The two measures usually agree on the top variables and differ further down. The impurity importance is biased in favour of continuous predictors and categorical predictors with many levels, which offer many more candidate splits (Strobl et al. 2007); the permutation importance does not have this bias and is generally preferred.
Importance says which variables matter, not how. A partial dependence plot(Friedman 2001) shows the average prediction of the model as one variable \(x_s\) varies over a grid, with all other variables kept at their observed values: \[
\bar{f}_s(x_s) = \frac{1}{n} \sum_{i=1}^{n} \hat{f}(x_s, x_{i,-s}) ,
\] where \(x_{i,-s}\) denotes the other predictors of observation \(i\). It takes a few lines to compute:
partial_dependence <-function(model, data, var, n_grid =30) { grid <-seq(min(data[[var]]), max(data[[var]]), length.out = n_grid) pd <-sapply(grid, function(v) { data[[var]] <- v # every tract gets the same value of varmean(predict(model, data)) })data.frame(variable = var, value = grid, prediction = pd)}pd <-rbind(partial_dependence(rf, bos_train, "lstat"),partial_dependence(rf, bos_train, "rm"))ggplot(pd, aes(value, prediction)) +geom_line(linewidth =1) +facet_wrap(~ variable, scales ="free_x") +labs(x =NULL, y ="average predicted medv ($1000s)") +theme_minimal()
Partial dependence of the predicted median value on lstat and on rm, in the Boston random forest.
Neither relationship is linear. The predicted value falls steeply as lstat rises from \(2\%\) to about \(10\%\), from about \(\$30\,000\) to \(\$22\,000\), then more slowly, and it is flat above \(25\%\). It hardly depends on rm below six rooms, rises by about \(\$9\,000\) between \(6.5\) and \(7.2\) rooms, and levels off above \(8\). The steepest parts of the curves lie close to the cut points of the single tree of Section 11.7 (rm at \(6.54\) and \(6.96\), lstat at \(14.4\)); the forest averages many such step functions into smoother curves.
11.9.6 Random Forests for Classification
The same functions work for a classification problem; with a factor response, randomForest() grows classification trees and samples \(\lfloor \sqrt{10} \rfloor = 3\) predictors at each split:
set.seed(1)car_rf <-randomForest(High ~ ., data = car_train)car_rf
Call:
randomForest(formula = High ~ ., data = car_train)
Type of random forest: classification
Number of trees: 500
No. of variables tried at each split: 3
OOB estimate of error rate: 21%
Confusion matrix:
No Yes class.error
No 104 13 0.1111111
Yes 29 54 0.3493976
set.seed(1)car_bag <-randomForest(High ~ ., data = car_train, mtry =10)# predict() breaks tied votes at random, so we predict once and keep the resultcar_rf_pred <-predict(car_rf, car_test)car_bag_pred <-predict(car_bag, car_test)c(bagging =mean(car_bag_pred == car_test$High),random_forest =mean(car_rf_pred == car_test$High))
bagging random_forest
0.820 0.825
The printed output includes the OOB error rate (\(21\%\)) and the OOB confusion matrix, which shows that most errors are stores with high sales classified as “No”. On the test set, bagging classifies \(82\%\) of the stores correctly and the random forest \(82.5\%\), against \(69.5\%\) for the pruned tree. On these data, with only ten predictors, decorrelating the trees does not help; both ensembles still fall short of the logistic regression (\(88.5\%\)).
11.9.7 Tuning a Random Forest with ranger
For tuning, speed matters. The ranger package (Wright and Ziegler 2017) is a fast C++ implementation of random forests, and Boehmke and Greenwell (2019) use it to tune the forest with the OOB error. The hyperparameters, with their recommended starting points, are:
number of trees (num.trees): start with \(10p\) trees, and add more if the error has not settled;
mtry: try about five values between \(2\) and \(p\), centred on the default; ranger’s default is \(\lfloor \sqrt{p} \rfloor\) for regression as well as classification;
node size (min.node.size): the smallest node that may still be split, by default \(5\) for regression, \(1\) for classification and \(10\) for probability forests (see below); larger values give shallower trees and shorter run times, try a few values between \(1\) and \(10\). Unlike nodesize in randomForest, it does not limit the size of the leaves (min.bucket does);
sampling scheme (sample.fraction, replace): bootstrap samples are \(100\%\) of the data drawn with replacement; smaller fractions, with or without replacement, give more diverse trees, try values between \(25\%\) and \(100\%\);
split rule (splitrule): the default variance (regression) or Gini (classification) criterion, or "extratrees" for extremely randomised trees, which pick random cut points and are much faster.
mtry and the number of trees usually matter most. We search a full grid of \(140\) combinations, with \(500\) trees each, and rank them by OOB root mean squared error (RMSE):
The best combination uses mtry = 4, min.node.size = 3, and samples of \(80\%\) of the training set drawn without replacement. Its OOB RMSE (\(3.13\)) is about \(6\%\) lower than that of ranger’s defaults (\(3.34\)), and its test MSE falls from \(18.38\) to \(17.56\). The gain is real but modest — a random forest with its default settings is already a good model, which is one of the reasons for its popularity. Boehmke and Greenwell (2019) reach the same kind of conclusion for the Ames housing data, where small node sizes and samples of less than \(100\%\) drawn without replacement also performed best.
Classification. With a factor response, ranger() grows classification trees, and prediction.error is the OOB misclassification rate. With probability = TRUE it grows a probability forest instead (Malley et al. 2012): each tree predicts the class proportions of the leaf an observation falls into, the forest averages these proportions rather than counting votes, and prediction.error becomes the OOB Brier score of Section 11.6. For the Carseats stores:
The OOB error rate of \(19\%\) is close to the \(21\%\) of randomForest(), and the OOB confusion matrix shows the same pattern: \(26\) of the \(38\) errors are high-sales stores classified as “No”.
To tune the forest, we search the same grid as for Boston, with five values of mtry around the default \(\lfloor \sqrt{10} \rfloor = 3\), and record both OOB measures for each of the \(140\) combinations:
car_grid <-expand.grid(mtry =c(2, 3, 5, 7, 10),min.node.size =c(1, 3, 5, 10),sample.fraction =c(0.5, 0.632, 0.8, 1),replace =c(TRUE, FALSE))car_grid <- car_grid[!(car_grid$sample.fraction ==1&!car_grid$replace), ]car_grid[, c("oob_error", "oob_brier")] <-t(sapply(seq_len(nrow(car_grid)), function(i) {sapply(c(FALSE, TRUE), function(probability) { fit <-ranger(High ~ ., data = car_train, num.trees =500,mtry = car_grid$mtry[i],min.node.size = car_grid$min.node.size[i],sample.fraction = car_grid$sample.fraction[i],replace = car_grid$replace[i],probability = probability, seed =1) fit$prediction.error })}))# number of combinations with each OOB error ratetable(car_grid$oob_error)
On \(200\) stores, the OOB error rate is a poor guide for tuning. It moves in steps of \(0.5\%\), one store, so the \(140\) combinations share only \(12\) different values, and \(8\) of them tie for the lowest, \(19\%\) — which the default forest already reached. The Brier score uses the probabilities themselves, not only the side of \(0.5\) they fall on, and separates the combinations much better. The best one uses mtry = 5, min.node.size = 1, which grows every tree until its leaves are pure, and samples of \(63.2\%\) of the training set drawn without replacement; its OOB Brier score (\(0.151\)) is about \(6\%\) lower than that of the default probability forest (\(0.161\)). All six best combinations use mtry = 5 and samples drawn without replacement. With other seeds the best mtry is \(7\), again with samples of \(50\)–\(63\%\) drawn without replacement: as for Boston, the precise optimum is noisy, the general shape is not.
On the test set, tuning lowers the Brier score from \(0.148\) to \(0.144\) and the log-loss from \(0.467\) to \(0.453\), and raises the accuracy from \(80.5\%\) to \(81.5\%\), but the AUC falls slightly, from \(0.895\) to \(0.882\): on \(200\) test stores, differences of this size are noise. The forest itself matters far more than its tuning. The probabilities of the single Carseats tree had a Brier score of \(0.248\), worse than the null model’s \(0.241\); averaging \(500\) trees brings it down to \(0.144\), as anticipated in Section 11.6. The logistic regression remains well ahead, with a Brier score of \(0.079\) and an AUC of \(0.96\): on data as close to linear as Carseats, no tuning of a forest closes that gap.
Packages and commands.randomForest’s randomForest(formula, data, ntree = , mtry = , importance = TRUE) fits bagging (mtry equal to the number of predictors) and random forests; printing the fit shows the OOB error, fit$mse (regression) and fit$err.rate (classification) hold it after every tree, and plot(fit) draws it. randomForest::importance(fit) returns %IncMSE and IncNodePurity; ranger also has a function called importance(), hence the explicit randomForest::. ranger’s ranger(formula, data, num.trees = , mtry = , min.node.size = , sample.fraction = , replace = , probability = , seed = ) is the fast alternative: fit$prediction.error is the OOB MSE (regression), misclassification rate (classification) or Brier score (probability = TRUE), fit$confusion.matrix the OOB confusion matrix of a classification forest, and predict(fit, newdata)$predictions the predictions — for a probability forest, a matrix with one column per class. expand.grid builds the tuning grid. vip’s vip() plots the importance, and the partial dependence is computed directly with predict and sapply (the pdp package provides a general partial() function).
11.10 Boosting
11.10.1 The Idea: Learning Slowly
Bagging and random forests grow their trees independently, each on its own bootstrap sample, and average them. Boosting grows trees sequentially: each new tree is fitted to the errors left by the trees before it. Instead of fitting the data hard with one large tree, boosting learns slowly, adding many small trees, each of which improves the fit a little where it is still poor. For regression trees the algorithm is (James et al. 2021):
Set \(\hat{f}(x) = 0\) and \(r_i = y_i\) for every observation \(i\) of the training set.
For \(b = 1, 2, \ldots, B\), repeat:
fit a tree \(\hat{f}^b\) with \(d\) splits (\(d + 1\) leaves) to the training data, using the residuals\(r\) as the response;
add a shrunken version of the new tree to the model: \(\hat{f}(x) \leftarrow \hat{f}(x) + \lambda \hat{f}^b(x)\);
update the residuals: \(r_i \leftarrow r_i - \lambda \hat{f}^b(x_i)\).
Output the boosted model \[
\hat{f}(x) = \sum_{b=1}^{B} \lambda \hat{f}^b(x) .
\]
Boosting has three tuning parameters:
the number of trees \(B\): unlike bagging and random forests, boosting can overfit if \(B\) is too large, although slowly; \(B\) is chosen by cross-validation;
the shrinkage \(\lambda\), or learning rate: a small positive number, typically \(0.01\) or \(0.001\); a small \(\lambda\) needs a large \(B\);
the number of splits \(d\) of each tree, which controls the interaction depth: with \(d = 1\) every tree is a stump on a single variable and the boosted model is additive, \(\hat f(x) = \sum_j f_j(x_j)\); a tree with \(d\) splits can involve at most \(d\) variables. Small trees, with \(d\) between \(1\) and \(8\), are typical.
The algorithm is short enough to write directly, with small rpart() trees as the \(\hat{f}^b\):
ggplot(hand, aes(trees, mse, colour = model)) +geom_line() +coord_cartesian(ylim =c(10, 60)) +labs(x ="number of trees", y ="test MSE", colour =NULL) +theme_minimal()
Test MSE of boosting by hand on the Boston data, as trees are added, for stumps (d = 1) and for trees of depth 2 (up to d = 3 splits), with learning rate 0.1.
Because \(\hat{f}\) starts at \(0\), the first trees spend their effort climbing from \(0\) to the average value of medv, and the test MSE starts above \(100\). After \(100\) trees it is down to \(22.2\) for stumps and \(18.2\) for the trees of depth two; after \(1000\) trees it has reached \(18.3\) and \(14.6\), and it is still slowly decreasing. Trees of depth two, which can capture interactions between pairs of predictors, do clearly better than stumps here. Nothing in this loop was tuned, and the test set played no part in fitting it.
11.10.2 Gradient Boosting
Fitting trees to residuals is a special case of a more general idea, gradient boosting(Friedman 2001). Let \(L(y, f(x))\) be a loss function and \(\hat{f}\) the current model. Each new tree is fitted to the pseudo-residuals\[
r_i = - \left. \frac{\partial L(y_i, f)}{\partial f} \right|_{f = \hat{f}(x_i)} ,
\] the direction in which the predictions should move to reduce the loss fastest; the model then takes a small step, of size \(\lambda\), in that direction. Boosting is thus gradient descent, carried out in the space of functions, with trees as the steps.
For squared-error loss, \(L = \frac{1}{2}(y - f)^2\), the pseudo-residual is \(y_i - \hat{f}(x_i)\), the ordinary residual, and we recover the algorithm above.
For a binary response \(y \in \{0, 1\}\), \(f\) is the log-odds, \(p = 1/(1 + e^{-f})\), and the loss is the Bernoulli deviance (or log-loss) \(L = -\left[ y \log p + (1-y) \log(1-p) \right]\). The pseudo-residual is \(y_i - \hat{p}_i\): the difference between the observed class and the predicted probability.
Other losses give boosting for counts (Poisson), for robust regression (absolute or Huber loss), or for quantiles. A precursor for classification, AdaBoost(Freund and Schapire 1997), reweights the misclassified observations at each step instead; it was later shown to fit an additive model of trees, one at a time, with an exponential loss (Friedman et al. 2000).
Friedman (2002) added a random element: each tree is grown on a random subsample of the training set, drawn without replacement. This stochastic gradient boosting reduces variance, guards against overfitting and speeds up the fit; subsamples of \(50\%\) to \(80\%\) are typical (Boehmke and Greenwell 2019).
11.10.3 Boosting with gbm
The gbm package implements stochastic gradient boosting. Its simplified format is
distribution: the loss function — "gaussian" (squared error) for regression, "bernoulli" for a \(0/1\) response, also "poisson", "laplace" (absolute error), "quantile" and others;
n.trees: the number of trees \(B\);
interaction.depth: the number of splits \(d\) of each tree;
shrinkage: the learning rate \(\lambda\);
n.minobsinnode: the minimum number of observations in a leaf;
bag.fraction: the fraction of the training set drawn for each tree (\(0.5\), so gbm boosting is stochastic by default — set the seed);
cv.folds: if larger than \(1\), a cross-validation that gbm.perf() uses to choose the number of trees;
n.cores: the number of processor cores used for the cross-validation. With n.cores = 1 the folds are fitted one after another; we use it throughout, because it is the only setting that works in the browser and it gives the same results on every computer.
Note
Both James et al. (2021) and Boehmke and Greenwell (2019) give \(0.001\) as the default learning rate of gbm(). Current versions of the package use \(0.1\).
We fit \(5000\) trees with \(4\) splits each and a learning rate of \(0.01\), and let 5-fold cross-validation choose how many to keep:
library(gbm)set.seed(1)boost <-gbm(medv ~ ., data = bos_train, distribution ="gaussian",n.trees =5000, interaction.depth =4, shrinkage =0.01,cv.folds =5, n.cores =1)
While it runs, gbm() prints CV: 1, …, CV: 5 as it fits each fold. gbm.perf() then finds the number of trees with the smallest cross-validation error, and plots both errors:
best_trees <-gbm.perf(boost, method ="cv")
Training error (black) and 5-fold cross-validation error (green) of the boosted model against the number of trees. The dashed line marks the minimum of the cross-validation error.
Cross-validation keeps \(2112\) trees, and the boosted model reaches a test MSE of \(17.92\), below the random forest (\(18.99\)). The training error keeps decreasing long after the cross-validation error has stopped improving — the trees added after that point fit noise.
summary() gives the relative influence of each variable, the impurity importance of boosting, scaled to sum to \(100\):
head(summary(boost, n.trees = best_trees), 6)
var rel.inf
rm rm 46.342269
lstat lstat 32.715182
crim crim 5.046451
dis dis 4.182054
nox nox 3.336572
age age 2.666196
The same two variables lead as in the forest, rm (\(47\)) and lstat (\(33\)), followed at a distance by crim, dis and nox.
The learning rate and the number of trees go together. The next figure fits the model with four learning rates and plots the test MSE as trees are added (the test set is used here only to illustrate; in practice the number of trees is chosen by cross-validation, as above):
n_trees <-seq(10, 5000, by =10)shrink <-do.call(rbind, lapply(c(0.001, 0.01, 0.1, 0.5), function(lambda) {set.seed(1) fit <-gbm(medv ~ ., data = bos_train, distribution ="gaussian",n.trees =5000, interaction.depth =4, shrinkage = lambda) pred <-predict(fit, bos_test, n.trees = n_trees) # one column per value of n_treesdata.frame(trees = n_trees, lambda =factor(lambda),mse =colMeans((pred - bos_test$medv)^2))}))ggplot(shrink, aes(trees, mse, colour = lambda)) +geom_line(linewidth =0.8) +coord_cartesian(ylim =c(15, 40)) +labs(x ="number of trees", y ="test MSE", colour ="learning rate") +theme_minimal()
Test MSE of boosting with trees of 4 splits, for four learning rates, against the number of trees.
With \(\lambda = 0.5\) the model reaches its best error within a few hundred trees and then stays at a poor level; with \(\lambda = 0.1\) it is good quickly; \(\lambda = 0.01\) takes about ten times as many trees and ends slightly lower; and with \(\lambda = 0.001\), \(5000\) trees are not enough. Small learning rates generally give better models, at the cost of more trees and more computing time.
11.10.4 Boosting for Classification
With distribution = "bernoulli", gbm() boosts the log-odds of a binary response, which must be coded \(0/1\):
type = "response" returns probabilities rather than log-odds. With \(1312\) trees of \(2\) splits, boosting classifies \(85\%\) of the test stores correctly — better than both bagging and the random forest, and close to the logistic regression (\(88.5\%\)). Trees with few splits build a model that is nearly additive, which suits the nearly linear structure of these data.
Packages and commands. The algorithm by hand uses rpart(control = rpart.control(maxdepth = , cp = 0, xval = 0)) for the small trees. gbm’s gbm(formula, distribution = , data, n.trees = , interaction.depth = , shrinkage = , bag.fraction = , cv.folds = , n.cores = 1) fits the boosted model; gbm.perf(fit, method = "cv") returns (and plots) the number of trees that minimises the cross-validation error, which is stored in fit$cv.error. predict(fit, newdata, n.trees = ) accepts a vector of tree counts and returns one column per count, and type = "response" gives probabilities for "bernoulli". summary(fit, n.trees = ) gives the relative influence of each variable.
11.11 XGBoost and LightGBM
XGBoost(Chen and Guestrin 2016) and LightGBM(Ke et al. 2017) are implementations of gradient boosting designed for speed and for very large data sets. They have become the standard first choice for prediction on tabular data: of the \(29\) winning solutions published on the competition site Kaggle in 2015, \(17\) used XGBoost (Chen and Guestrin 2016). The underlying model is the one of the previous section — a sum of small trees, each fitted to the gradient of a loss — with several additions:
an explicit regularisation of the trees in the objective function;
a second-order (Newton) step, which uses the curvature of the loss as well as its gradient;
histogram-based split finding: each predictor is binned into at most a few hundred values, and only the bin boundaries are tried as cut points;
row and column subsampling, as in stochastic boosting and random forests;
built-in handling of missing values, cross-validation and early stopping, and parallel computation.
11.11.1 XGBoost
XGBoost minimises a regularised objective. With \(K\) trees \(f_1, \ldots, f_K\) and predictions \(\hat{y}_i = \sum_k f_k(x_i)\), \[
\mathcal{L} = \sum_{i=1}^{n} L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k),
\qquad
\Omega(f) = \gamma\, T + \frac{1}{2}\, \lambda \sum_{j=1}^{T} w_j^2 ,
\] where \(T\) is the number of leaves of a tree and \(w_j\) the value it predicts in leaf \(j\) (its weight). The term \(\gamma T\) penalises the number of leaves, like the \(\alpha |T|\) of cost-complexity pruning, and \(\lambda \sum w_j^2\) shrinks the leaf values towards \(0\), like ridge regression.
When the \(t\)-th tree is added, the loss is approximated by a second-order Taylor expansion around the current predictions, with gradients \(g_i = \partial L / \partial \hat{y}_i\) and second derivatives \(h_i = \partial^2 L / \partial \hat{y}_i^2\). For a fixed tree structure, the best weight of leaf \(j\) and the resulting value of the objective are then available in closed form: \[
w_j^* = - \frac{G_j}{H_j + \lambda},
\qquad
\mathcal{L}^* = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma\, T ,
\] where \(G_j\) and \(H_j\) are the sums of \(g_i\) and \(h_i\) over the observations in leaf \(j\). A split of a leaf into a left and a right child is worth making only if its gain\[
\text{Gain} = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma
\] is positive. For squared-error loss, \(g_i = \hat{y}_i - y_i\) and \(h_i = 1\), so \(w_j^*\) is the sum of the residuals in the leaf divided by \(n_j + \lambda\): a mean residual shrunk towards \(0\), and \(H_j\) is simply the number of observations in the leaf.
The main parameters of XGBoost, with their names in R and their defaults:
Parameter
Default
Role
nrounds
—
number of trees \(B\); usually chosen by early stopping
learning_rate (eta)
\(0.3\)
shrinkage \(\lambda\) of boosting (not the \(\lambda\) above)
max_depth
\(6\)
maximum depth of each tree
min_child_weight
\(1\)
minimum \(H_j\) in a leaf; for squared error, the minimum number of observations
min_split_loss (gamma)
\(0\)
\(\gamma\): minimum gain needed to make a split; values of \(1\)–\(20\) often suffice
reg_lambda (lambda)
\(1\)
\(\lambda\): L2 penalty on the leaf weights
reg_alpha (alpha)
\(0\)
L1 penalty on the leaf weights
subsample
\(1\)
fraction of the rows sampled for each tree
colsample_bytree
\(1\)
fraction of the columns sampled for each tree (also colsample_bylevel, colsample_bynode)
objective
—
the loss: "reg:squarederror", "binary:logistic", "multi:softprob", "count:poisson", …
11.11.2 XGBoost in R
Note
Version 3 of the R package xgboost changed its interface: parameters are built with xgb.params() and the data monitored during training are passed as evals (formerly watchlist). Older tutorials, including Boehmke and Greenwell (2019), use the previous interface. The code below uses the current one.
xgb.train() needs a numeric matrix of predictors, wrapped together with the response in an xgb.DMatrix. All Boston predictors are numeric:
We set a learning rate of \(0.05\), trees of depth \(3\), and sample \(80\%\) of the rows and of the columns for each tree. xgb.cv() runs a 5-fold cross-validation with early stopping: it adds trees until the cross-validation error has not improved for \(50\) rounds, and records the best number of rounds.
The cross-validation RMSE is lowest after \(247\) rounds, at \(3.15\). The evaluation log shows the familiar picture: the training error keeps falling, while the cross-validation error levels off.
Training and 5-fold cross-validation RMSE of XGBoost against the number of rounds. The dotted line marks the number of rounds chosen by early stopping.
The final model is fitted on the whole training set with that number of rounds:
The test MSE is \(18.43\), in the same range as the forest and gbm. xgb.importance() reports three measures for each variable: Gain, the share of the total improvement of the objective due to its splits (the impurity importance); Cover, the share of the observations (strictly, of the \(h_i\)) affected by its splits; and Frequency, the share of all splits made on it. By gain, rm and lstat again account for more than \(80\%\) of the total.
Tuning. We search a small grid over the depth of the trees, min_child_weight and subsample, using early stopping in every cross-validation:
The best combination has trees of depth \(4\), at least \(5\) observations per leaf, and aggressive row subsampling: each tree sees only half of the training set. Its cross-validation RMSE is \(2.97\), and its test MSE \(17.14\).
Classification. The predictors must be numeric, so factors are first turned into dummy variables with model.matrix(). The formula High ~ . - 1 (no intercept) creates one column for each level of the first factor (ShelveLoc) and one for the second level of Urban and US. The objective "binary:logistic" boosts the log-odds, and predict() returns probabilities:
Xc_train <-model.matrix(High ~ . -1, data = car_train)Xc_test <-model.matrix(High ~ . -1, data = car_test)colnames(Xc_train)
With \(214\) rounds of depth-two trees, XGBoost classifies \(84.5\%\) of the test stores correctly, about the same as gbm.
Since version 3, the package also has a higher-level function, xgboost(x, y, ...), which accepts a data frame with factor columns — split natively as categories, without dummy variables — and chooses the objective from the type of y: a factor with two levels gives "binary:logistic". Its parameters are ordinary arguments:
type = "class" returns the predicted levels of the factor directly. On these data the native treatment of the three factors gives the same accuracy as the dummy variables. xgb.cv() and xgb.train() remain the functions to use for cross-validation and for full control over the training.
11.11.3 LightGBM
LightGBM uses the same regularised, second-order boosting as XGBoost, but grows its trees differently, adds two sampling and bundling techniques for large data sets, and splits categorical predictors natively (Ke et al. 2017):
Leaf-wise growth. XGBoost, like CART, grows trees level-wise: all the nodes at one depth are split before moving to the next. LightGBM grows leaf-wise (best-first): at each step it splits the one leaf, anywhere in the tree, whose split reduces the loss the most. With the same number of leaves, a leaf-wise tree reaches a lower loss, but it can become deep and lopsided, and overfit small data sets. Its size is therefore controlled by the number of leaves, num_leaves, rather than by the depth, with min_data_in_leaf and, if needed, max_depth as further limits. (XGBoost can also grow leaf-wise, with grow_policy = "lossguide".)
Gradient-based one-side sampling (GOSS). Observations with small gradients are already well fitted. GOSS keeps all observations with large gradients and a random sample of the others, reweighted to keep the gradient sums unbiased. It is switched on with data_sample_strategy = "goss".
Exclusive feature bundling (EFB). In sparse data many predictors are rarely non-zero at the same time — the dummy variables of one factor, for example. EFB, which is on by default, bundles such predictors into a single one, reducing the number of columns to scan.
Native categorical predictors. A factor with many levels can be split directly, by ordering its levels according to their gradient statistics and searching the best cut in that order, as CART does for a binary response — without creating dummy variables.
Parameter
Default
Role
num_leaves
\(31\)
maximum number of leaves per tree: the main control of complexity
learning_rate
\(0.1\)
shrinkage
min_data_in_leaf
\(20\)
minimum number of observations in a leaf
max_depth
\(-1\)
maximum depth (\(-1\): no limit)
feature_fraction
\(1\)
fraction of the columns sampled for each tree
bagging_fraction, bagging_freq
\(1\), \(0\)
fraction of the rows sampled, and how often (every bagging_freq trees; \(0\) means never)
lambda_l1, lambda_l2
\(0\), \(0\)
L1 and L2 penalties on the leaf weights
max_bin
\(255\)
maximum number of bins per predictor
objective
"regression"
the loss: "regression", "binary", "multiclass", "poisson", …
11.11.4 LightGBM in R
The R interface mirrors XGBoost’s: lgb.Dataset() wraps a numeric matrix and the response, lgb.cv() cross-validates with early stopping, and lgb.train() fits the final model. With only \(253\) training tracts, we limit the trees to \(8\) leaves and \(10\) observations per leaf. seed fixes the random row and column sampling, and set.seed() the folds of lgb.cv(), which are drawn in R:
Note that LightGBM reports the l2 loss, which is the MSE, where XGBoost reported the RMSE. Early stopping keeps \(323\) rounds, with a cross-validation MSE of \(10.24\) (an RMSE of \(3.20\), against \(3.15\) for XGBoost). The test MSE is \(18.75\), and the importance by gain is almost the same as XGBoost’s: rm and lstat account for \(81\%\) of the total.
Native categorical predictors. For Carseats, lgb.convert_with_rules() turns each factor into integer codes and returns the coding rules, which are then applied unchanged to the test set. The argument categorical_feature tells LightGBM to split these columns as categories rather than as numbers:
Feature Gain
<char> <num>
1: Price 0.318234199
2: ShelveLoc 0.201095467
3: CompPrice 0.176166238
4: Age 0.110727808
5: Income 0.092175094
6: Advertising 0.071395377
7: Education 0.015925757
8: US 0.008793610
9: Population 0.005486451
With \(144\) rounds of trees with four leaves, splitting ShelveLoc, Urban and US as categories, LightGBM classifies \(84.5\%\) of the test stores correctly — the same as XGBoost. The importance table lists ShelveLoc as a single variable, second only to Price, rather than spread over three dummy columns.
11.11.5 A Tuning Strategy
Boosting has more tuning parameters than a random forest, and they interact. Boehmke and Greenwell (2019) suggest tuning them in stages:
Fix a relatively high learning rate (for example \(0.05\)–\(0.1\)), set a large number of trees, and let early stopping find how many are needed.
Tune the tree-specific parameters — max_depth or num_leaves, and min_child_weight or min_data_in_leaf — at that learning rate.
Explore the stochastic parameters: row subsampling (subsample, bagging_fraction) and column subsampling (colsample_bytree, feature_fraction), typically between \(0.5\) and \(0.8\).
If the cross-validation error is still far above the training error, try the regularisation parameters: gamma, lambda and alpha in XGBoost, lambda_l1, lambda_l2 and min_gain_to_split in LightGBM.
Lower the learning rate (and let early stopping increase the number of trees) to see whether accuracy improves further.
Fit the final model with the chosen settings, and check it with a more thorough cross-validation or on a test set that played no part in the tuning.
Tip
A test set used to make choices is no longer a test set. Above, every choice — the pruning parameter, mtry, the number of trees — was made by cross-validation or the OOB error, on the training half alone, so that the test half could compare the methods fairly at the end.
11.11.6 Comparing the Models
The table collects the test errors of every model fitted to the Boston data in this chapter. The standard error of each test MSE is computed from the \(253\) squared errors.
The models fall into three groups. The single trees are the worst (\(35\)–\(44\)), worse than the linear regression (\(27.6\)). Bagging (\(23.4\)) is a large step forward. The random forests and the boosted models all lie between \(17.1\) and \(19.0\), about a third below the linear regression, and with standard errors of about \(4\) they cannot be ranked on this test set. Since all the models are evaluated on the same \(253\) tracts, a fairer measure is the standard error of the difference between two models’ squared errors. For the random forest against gbm it is about \(2.2\), twice the difference of \(1.1\) between them; the forest’s advantage over the linear regression (\(8.7\)) is four times its standard error. (The untuned boosting by hand of the boosting section reached \(14.6\) — also within the noise.)
Every ensemble improves on the pruned tree by \(12\) to \(16\) percentage points, the boosted models a little more than the forests, and none reaches the logistic regression. As explained in the section on trees and linear models, the Carseats sales are close to linear in the predictors, and on such data a linear method is hard to beat. Boosting with shallow trees comes closest because it builds a nearly additive model.
Packages and commands.xgboost: xgb.DMatrix(X, label = ) wraps a numeric matrix, xgb.params(objective = , learning_rate = , max_depth = , min_child_weight = , subsample = , colsample_bytree = , ...) builds the parameter list, xgb.cv(params, data, nrounds = , nfold = , early_stopping_rounds = ) cross-validates (best number of rounds in $early_stop$best_iteration, errors in $evaluation_log), xgb.train(params, data, nrounds = ) fits, and xgb.importance(model = ) returns Gain, Cover and Frequency. lightgbm: lgb.Dataset(X, label = , categorical_feature = ), lgb.cv() (with $best_iter and $best_score), lgb.train(), lgb.importance(), and lgb.convert_with_rules() to code factors as integers consistently in the training and test sets. Base R’s model.matrix(y ~ . - 1, data) creates the dummy variables that XGBoost needs.
11.12 Summary
A decision tree divides the predictor space into rectangles by recursive binary splitting and predicts a constant in each one: the mean response (regression) or the most common class (classification).
Splits are chosen greedily, to minimise the RSS for regression and the Gini index or entropy for classification; the classification error is too insensitive to grow a tree.
The training error is an optimistic estimate of the test error. Models are fitted on a training set, compared and tuned on a validation set or by cross-validation, and assessed once on a test set that played no part in any choice. \(K\)-fold cross-validation is far more stable than a single validation set; stratified splits keep the class proportions equal.
Accuracy alone hides the kind of errors a classifier makes. The confusion matrix gives sensitivity, specificity and precision; the ROC curve and the AUC cover every threshold; the Brier score and the log-loss assess the probabilities — those of the default Carseats tree were worse than a constant. For a numeric response, MSE, MAE and the median absolute error can rank models differently, and the scale of the response matters.
A fully grown tree overfits. Cost-complexity pruning, with the complexity parameter chosen by cross-validation (cp in rpart, often with the one-standard-error rule), gives a much smaller tree with similar or better test error: from \(243\) to \(6\) leaves on Boston, from \(39\) to \(5\) on Carseats.
Trees are easy to explain, need no scaling, handle categorical predictors and interactions, and deal with missing values through surrogate splits. Their weaknesses are lower accuracy and high variance: a slightly different training set can produce a very different tree.
Bagging averages deep trees grown on bootstrap samples, and random forests decorrelate them further by sampling the predictors eligible at each split. The out-of-bag error estimates the test error without extra fitting. On Boston, a random forest cut the test MSE of the pruned tree nearly in half.
Boosting grows small trees sequentially, each fitted to the (pseudo-)residuals of the current model and added with a small learning rate. Its tuning parameters — number of trees, learning rate, tree size — must be chosen by cross-validation, because, unlike a forest, boosting can overfit.
XGBoost and LightGBM are fast, regularised implementations of gradient boosting with built-in cross-validation, early stopping and handling of missing values; LightGBM grows trees leaf-wise and splits categorical predictors natively.
Importance measures and partial dependence plots make ensembles interpretable. Prefer permutation importance to impurity importance.
No method wins everywhere. On Carseats, whose structure is nearly linear, a logistic regression beat every tree-based model; the ensembles’ advantage is largest when the relationship is nonlinear and involves interactions.
For a two-class node with proportion \(p\) of the second class, write the Gini index, the entropy and the classification error as functions of \(p\), and plot the three curves on one graph.
A node contains \(60\) observations of class \(A\) and \(40\) of class \(B\). Compute its Gini index and entropy.
Two splits of this node are proposed: split 1 gives children \((50, 10)\) and \((10, 30)\); split 2 gives \((60, 20)\) and \((0, 20)\). Compute the weighted Gini index, entropy and classification error of each split. Which split does each criterion prefer?
Check your answers to question 3 with rpart(). Build a data frame of the \(100\) observations with one predictor that takes three values, \(1\) for the \(50 + 10\) observations that both splits send left, \(2\) for the next \(10 + 10\), and \(3\) for the last \(0 + 20\), so that its two possible cut points produce the two splits. Which one does rpart() choose with split = "gini", and with split = "information"?
A regression tree for the Hitters data
Grow a regression tree for logSalary with all predictors on hit_train, and draw it. Which variables are used?
Compute the test MSE on hit_test, and compare it with that of a linear regression on the same predictors.
Grow the largest possible tree (cp = 0, minsplit = 2, minbucket = 1), and prune it with the minimum-xerror rule and with the one-standard-error rule. How many leaves does each pruned tree have, and what are their test MSEs?
Repeat question 3 with five different seeds for the cross-validation. Is the selected tree size stable?
Repeat the whole comparison with five different train/test splits. Which conclusion of question 3 survives?
Orange juice
The data set OJ in ISLR2 records \(1070\) purchases of orange juice, of the brands Citrus Hill (CH) or Minute Maid (MM), with \(17\) characteristics of the customer and the product (James et al. 2021, Exercise 8.9).
Create a training set of \(800\) random purchases and a test set with the rest.
Grow a classification tree for Purchase on the training set. How many leaves does it have, and what is its training error rate?
Draw the tree, and interpret one of its leaves in words.
Predict the test set and produce the confusion matrix. What is the test error rate?
Use printcp() and plotcp() to choose a tree size, and prune the tree. If cross-validation does not lead to a smaller tree, prune to \(5\) leaves.
Compare the training and test error rates of the pruned and unpruned trees.
Random forests for Boston
On bos_train, fit random forests with mtry\(\in \{2, 4, 6, 12\}\) and \(1000\) trees each. Plot, on one graph, the OOB MSE against the number of trees for the four forests (James et al. 2021, Exercise 8.7).
For the same forests, plot the test MSE against the number of trees. (Hint: predict(fit, bos_test, predict.all = TRUE)$individual gives the predictions of every tree; apply(..., 1, cumsum) accumulates them.)
Compare the two graphs. Do they rank the four values of mtry the same way?
Use the partial_dependence() function of this chapter to draw the partial dependence of medv on crim and on dis. Describe the relationships in words.
Boosting the Hitters data
Fit boosted models with gbm() (distribution = "gaussian", \(1000\) trees, interaction.depth = 1) to hit_train, for a range of learning rates \(\lambda\) between \(0.001\) and \(0.5\)(James et al. 2021, Exercise 8.10).
Plot the training MSE and the test MSE against \(\lambda\).
Compare the best test MSE with that of the linear regression and of the pruned tree of Exercise 2.
Which variables are the most important in the boosted model? Compare with the variable importance of the single tree.
Fit a bagged model (randomForest with mtry = 19). How does its test MSE compare?
XGBoost and LightGBM on an imbalanced problem
The data set Caravan in ISLR2 records whether \(5822\) customers of an insurance company bought a caravan insurance policy (Purchase), with \(85\) socio-demographic and product-ownership predictors. Only \(6\%\) of the customers bought one (James et al. 2021, Exercise 8.11). This exercise must be run in RStudio, because xgboost and lightgbm do not run in the browser.
Use the first \(1000\) customers as the training set and the others as the test set.
Fit a boosted model with gbm (\(1000\) trees, learning rate \(0.01\), distribution = "bernoulli"). Which predictors are the most important?
Predict that a customer buys if the estimated probability exceeds \(20\%\). Produce the confusion matrix. What fraction of the customers predicted to buy actually do?
Repeat questions 2 and 3 with XGBoost and with LightGBM, choosing the number of rounds by cross-validation with early stopping. Try the parameter scale_pos_weight (XGBoost) or is_unbalance = TRUE (LightGBM), which give more weight to the rare class.
Compare the three models with a logistic regression.
Breiman, Leo, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. 1984. Classification and Regression Trees. Wadsworth.
Brier, Glenn W. 1950. “Verification of Forecasts Expressed in Terms of Probability.”Monthly Weather Review 78 (1): 1–3.
Chen, Tianqi, and Carlos Guestrin. 2016. “XGBoost: A Scalable Tree Boosting System.”Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 785–94. https://doi.org/10.1145/2939672.2939785.
Cohen, Jacob. 1960. “A Coefficient of Agreement for Nominal Scales.”Educational and Psychological Measurement 20 (1): 37–46.
Freund, Yoav, and Robert E. Schapire. 1997. “A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting.”Journal of Computer and System Sciences 55 (1): 119–39.
Friedman, Jerome H. 2001. “Greedy Function Approximation: A Gradient Boosting Machine.”The Annals of Statistics 29 (5): 1189–232.
Friedman, Jerome H. 2002. “Stochastic Gradient Boosting.”Computational Statistics & Data Analysis 38 (4): 367–78.
Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. 2000. “Additive Logistic Regression: A Statistical View of Boosting.”The Annals of Statistics 28 (2): 337–407.
Greenwell, Brandon M., and Bradley C. Boehmke. 2020. “Variable Importance Plots—an Introduction to the vip Package.”The R Journal 12 (1): 343–66. https://doi.org/10.32614/RJ-2020-013.
Harrison, David, and Daniel L. Rubinfeld. 1978. “Hedonic Housing Prices and the Demand for Clean Air.”Journal of Environmental Economics and Management 5 (1): 81–102.
Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer.
James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2021. An Introduction to Statistical Learning: With Applications in R. 2nd ed. Springer. https://www.statlearning.com.
Ke, Guolin, Qi Meng, Thomas Finley, et al. 2017. “LightGBM: A Highly Efficient Gradient Boosting Decision Tree.”Advances in Neural Information Processing Systems 30: 3146–54.
Liaw, Andy, and Matthew Wiener. 2002. “Classification and Regression by randomForest.”R News 2 (3): 18–22.
Malley, James D., Jochen Kruppa, Abhijit Dasgupta, Karen G. Malley, and Andreas Ziegler. 2012. “Probability Machines: Consistent Probability Estimation Using Nonparametric Learning Machines.”Methods of Information in Medicine 51 (1): 74–81. https://doi.org/10.3414/ME00-01-0052.
Strobl, Carolin, Anne-Laure Boulesteix, Achim Zeileis, and Torsten Hothorn. 2007. “Bias in Random Forest Variable Importance Measures: Illustrations, Sources and a Solution.”BMC Bioinformatics 8: 25. https://doi.org/10.1186/1471-2105-8-25.
Wright, Marvin N., and Andreas Ziegler. 2017. “ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R.”Journal of Statistical Software 77 (1): 1–17. https://doi.org/10.18637/jss.v077.i01.