11.1.1 How to Build a Tree

As we have seen in the penguins example, a regression tree predicts a response \(Y\) based on \(n\) predictors by finding a number of regions \(R_i \subset \mathbb{R}^n\) with constants \(c_i\), \(i = 1, \ldots, M\), such that the predicted response \(\hat{Y}\) is given by \[\begin{align*} \hat{Y} = f(X_1, \ldots, X_n) = \sum_{i = 1}^{M}c_i \1\{ (X_1, \ldots, X_n) \in R_i \}, \end{align*}\] where \(M\) describes the number of regions that were found by a tree-building algorithm.

In order to build a tree the first step is to split the data that is being fitted into two. This way we go from a tree that only contains a single node, namely its root, to a tree that has one split, i.e. the tree has a one root and two terminal nodes. Once we are able to do that we can iteratively split the terminal nodes further.

If you have trouble imagining this, you may also think of the spanned space of all predictors instead. Actually, this first splitting step is akin to splitting the space that is spanned by all predictors, say \(\tilde{R}_0\), into two regions \(\tilde{R}_1\) and \(\tilde{R}_2\). Then, one may take one of those two new regions, say \(\tilde{R}_1\) and split that into two again, say \(\tilde{R}_3\) and \(\tilde{R}_4\) and so on. This whole procedure can then be done until a region contains only a minimal amount of observations, say 5, which is when the splitting stops. The final regions \(R_1, \ldots, R_M\) are then given by the partition of the \(\tilde{R}_0\) that is present once the splitting procedure stops.

Of course, this begs the question of how an algorithm determines how to split the regions. As we have seen in the previous examples, for a decision tree the splitting rule is somewhat simple: A region \(R\) is split into two parts \(R_1\) and \(R_2\) based on a single predictor denoted by, say, \(X_j\) and a splitting point \(s\) via \[\begin{align*} R_1(j, s) = \{ X \vert X_j \leq s \} \quad \text{ and } \quad R_2(j, s) = \{ X \vert X_j > s \}. \end{align*}\] Here, we have assumed that \(X_j\) is a numerical predictor. For categorical predictors the splitting rule is done similarly though requires some additional considerations beforehand⁸¹.

Now, to determine what splitting variable \(X_j\) and splitting point \(s\) to use, we need to consider that each new region \(R_1(j, s)\) and \(R_2(j, s)\) is also assigned a constant \(c_1\) and \(c_2\) that is later used for prediction if a region is not split further. Thus, an algorithm may be implemented that chooses \(j, s, c_1\) and \(c_2\) in such a way that the regression error will be minimal if the tree is not split any further.

In order to implement this we need to determine some measure \(Q_R(R, c)\), which is sometimes referred to as node impurity measure, that gives us feedback on the regression error given a region \(R\) and associated constant \(c\). An obvious choice would be to use the sum of squared residuals (SSR), i.e. \[\begin{align*} Q_R(R, c) = \sum_{x_i \in R} (y_i - c)^2. \end{align*}\] Obviously, given a region \(R\) the SSR is minimal if \(c\) is the average of response variables \(y_i\) in \(R\). Therefore, we can consider one less variable to optimize by simply considering only \[\begin{align*} Q_R(R) = \sum_{x_i \in R} (y_i - \hat{c}(R))^2 \end{align*}\] as measure of our regression error where \(\hat{c}(R)\) denotes the average of the response variable in the region \(R\).

Consequently, using this measure \(Q\), we can determine the splitting variable \(X_j\) and splitting point \(s\) by simply scanning through all possibilities in order to solve the minimization problem \[\begin{align*} \min_{j, s} \Big( Q_R\big(R_1(j, s)\big) + Q_R\big(R_2(j, s)\big) \Big). \end{align*}\]

Again, this splitting and optimization procedure is repeated until another splitting becomes unfeasible because the new regions would contain less observations than some minimal amount we need specify. In essence, this is what the min_n argument in rand_forest() is controlling and because different values for min_n may yield different trees, we may try to optimize this argument via tuning.

Further, let us talk about how to adjust this tree building procedure for classification purposes. Notice that the only instance where our procedure relied on the fact that our response observations \(y_i\) were numerical is when evaluating the regression error via the node impurity measure.

Previously, the numerical nature of \(y_i\) allowed us to use the sum of squared residuals node impurity measure \(Q_R\). However, this is clearly not an appropriate choice when the responses \(y_i\) are categorical. Therefore, we will need to use a more appropriate measure for categorical responses.

One such measure is given by the Gini impurity measure \[\begin{align*} Q_R(R) = \sum_{k=1}^{K} \hat{p}(R, k)(1 - \hat{p}(R, k)), \end{align*}\] where \(K\) is the number of levels of the response variable \(Y\) and \(\hat{p}(R, k)\) describes the proportion of class \(k\) observations in region \(R\). Here, it might be confusing to not see a sort of comparison between predicted and observed class similar to our previous impurity measure.

This is why it helps to consider the following scenario. Imagine that given a region \(R\) we would classify any observation in \(R\) randomly according to the distribution of classes in \(R\), i.e. any observation in R is classified as being of class \(k\) with probability \(\hat{p}(R, k)\). Then, via a simple argument using the law of total probability we can compute the probability of \(A\) which describes the event that “a randomly chosen observation from \(R\) is classified incorrectly”. Letting \(B\) denote the class of the randomly chosen observation, \(\mathbb{P}(A)\) is given by \[\begin{align*} \mathbb{P}(A) = \sum_{k = 1}^{K} \mathbb{P}(A \vert B = k) \mathbb{P}(B = k) = \sum_{k=1}^{K} \hat{p}(R, k)(1 - \hat{p}(R, k)), \end{align*}\] which is exactly the Gini impurity measure.

Thus, this measure quantifies in a specific region \(R\) how often a randomly chosen element would be labeled incorrectly if it was randomly assigned a class label according to the label distribution within \(R\). Finally, once regions have been determined, all observations in a given region are labeled according to a majority vote, i.e. all observations in \(R\) are labeled as being of class \(k\) that maximizes \(\hat{p}(R, k)\).

11.1.2 How to Choose a Tree

The previous description allowed us to understand how we can sequentially split our space spanned by the predictors into ever smaller regions until the regions would become too small to split further. This gives us a sequence of sets of regions from a space that is not split at all (one region) to a space that is split a lot (many regions). Similarly, this gives us a sequence of corresponding trees.

Once a full-sized tree has been determined from the data set, it becomes time to consider whether we actually want our decision tree to be full-sized. Fundamentally, this comes down to trying to prevent overfitting because a full-sized tree might split the data into way too many regions such that the tree loses its predictive power for unseen data. Therefore, we might want to use one of our intermediate trees in our sequence of trees that we obtained as part of our splitting procedure.

But in order to decide which of those trees we should use we again need some measure that evaluates a tree. Now, this measure should take into account not only our previous impurity measure \(Q_R\) but also the size of the tree / the number of regions. This defines the cost complexity criterion of a tree \(T\) \[\begin{align*} C_{\alpha}(T) = \sum_{i = 1}^{\vert T \vert} Q_R(R_i) + \alpha\vert T\vert, \end{align*}\] where \(R_i\) correspond to the \(i\)-th region of a tree \(T\) with \(\vert T \vert\) terminal nodes and \(\alpha \geq 0\) is a tuning parameter governing the trade-off between size and impurity.

Moreover, depending on \(\alpha\) each tree along our sequence of trees may have a different cost complexity value. Clearly, for \(\alpha = 0\), the tree with the lowest cost complexity value will be the full-sized tree because by construction this tree minimizes the total impurity \(\sum_{i = 1}^{\vert T \vert} Q_R(R_i)\). This is due to the fact that the the splitting procedure minimizes the total impurity, i.e. as the tree becomes larger the total impurity becomes smaller.

However, when \(\alpha > 0\), then large trees are penalized for their size and the cost complexity value of large trees may exceed that of smaller trees even though the total impurity of the former is smaller than that of the latter trees. Thus, to fit an “optimal” tree we need to find a suitable value for \(\alpha\) and then take the tree that minimizes the cost complexity value given that \(\alpha\). To keep things short here, let me simply mention that this optimal value of \(\alpha\) can be found using some form of v-fold cross validation⁸².

11.1.3 How to Build a Random Forest

Once we are able to fit a single tree to one data set, we are also able to fit a lot of trees corresponding to bootstrapped samples of the same underlying data. After that is done and we have fitted, say, 1000 trees we can run a regression/classification based on a set of predictors for each of those 1000 trees. This gives us 1000 estimates that we can combine into a single estimate via averaging (in case of regression) or casting a majority vote (in case of classification).

This kind of ensemble learning, i.e. combining multiple estimates, is known as bagging. Here, bagging refers to specifically the aggregation of bootstrapped estimates but, in general, ensemble learning can use other means of combining multiple estimates. So, in essence, building a random forest is a bagging procedure based on decision trees.

Though, there is one thing that is somewhat special about random forests, namely the tree building procedure is tweaked in order to decorrelate the resulting ensemble of trees. This is motivated by the fact that bagging is mainly a procedure to reduce variance and the fact that the variance of the average of \(N\) identically distributed random variables with pairwise correlation \(\rho \geq 0\) is given by \[\begin{align*} \frac{\sigma^2}{N} + \bigg( 1 - \frac{1}{N} \bigg)\rho \sigma^2. \end{align*}\]

Consequently, only increasing the number of trees \(N\) would mean that the variance reduction is limited by \(\rho\sigma^2\) but if we also manage to decrease the correlation \(\rho\) without compromising the variance \(\sigma^2\) too much, then this will improve our variance reduction even more. Thus, random forests try to decorrelate the trees. This is done by considering not all predictors in each tree splitting step but only a random selection of predictors. Finally, the parameter mtry in rand_forest() determines the number of predictors that are randomly sampled at each splitting step.

11.3.1 Tuning the Amount of Trees

Use mtry = 2 and min_n = 5 to tune the number of trees of our forest, i.e. find the optimal numbers of trees in \(\{1, 2, \ldots, 20, 50, 75, 100, 200, \ldots, 700 \}\) that maximizes the AUC value. Further, generate a plot that plots the AUC against the number of trees.

Important: Save your variable that is produced bytune_grid() into an RDS-file and push it to your branch so that I do not have to refit your model. Your final code should include read_RDS(...) and your code that generated the RDS file should be commented out.

11.3.2 Fitting a Decision Tree

Instead of using parsnip::rand_forest() use parsnip::decision_tree() to fit the same model as in the lecture notes only with a different model specification using a single decision tree instead of a random forest. Tune the parameters tree_depth and min_n and use the default value for cost_complexity. What is the best AUC value your tuning can produce?⁸⁵

Important: Save your variable that is produced bytune_grid() into an RDS-file and push it to your branch so that I do not have to refit your model. Your final code should include read_RDS(...) and your code that generated the RDS file should be commented out.