Tree-Based Methods

Introduction: Tree-Based Methods 🌳

This chapter introduces tree-based methods for regression and classification. These methods involve segmenting the predictor space into simpler, more manageable regions. Think of it like creating a flowchart to make decisions!

Core Concepts: Data Mining

Let’s start with the foundational concepts. First up: Data Mining.

Data mining is the process of discovering patterns, anomalies, and insights from large datasets. It utilizes a multidisciplinary approach, blending techniques from:

• Statistics: For analyzing data and drawing inferences.
• Machine Learning: For building predictive models.
• Database Management: For efficiently storing and retrieving large datasets.

It’s like being a detective 🕵️‍♀️, sifting through raw data to find valuable knowledge and clues. The goal is to extract useful information, not just any information.

Core Concepts: Machine Learning

Next, we have Machine Learning.

Machine learning is a subfield of artificial intelligence (AI). It focuses on creating algorithms that allow computers to learn from data without being explicitly programmed. This means we don’t give the computer a set of rules; instead, we give it data and it figures out the rules itself!

Key aspects:

• Learning from Data: The core principle. The algorithm improves its performance as it is exposed to more data.
• Building Models: These models are mathematical representations of the patterns in the data. They can be used to make predictions or decisions about new, unseen data.
• No Explicit Programming: The algorithm learns the patterns and relationships within the data without being explicitly told what those patterns are.

Core Concepts: Statistical Learning

Finally, let’s define Statistical Learning.

Statistical learning refers to a set of tools for modeling and understanding complex datasets. It’s a relatively new field within statistics that intersects with advances in computer science, particularly machine learning. It emphasizes both building predictive models and gaining insights into the underlying data-generating process.

Key aspects:

• Modeling and Understanding: Focuses on both building accurate models and gaining insights into the relationships between variables.
• Conceptual and Practical: Provides both theoretical understanding of the methods and practical tools for applying them.
• Interdisciplinary: Combines statistical theory and computational techniques from computer science.

Relationships of Concepts

The following diagram illustrates how these concepts relate to one another:

graph LR
    A[Data Mining] --> C(Common Ground)
    B[Machine Learning] --> C
    D[Statistical Learning] --> C
    C --> E[Insights & Predictions]

Decision Trees: The Basics 🌲

Decision trees are a fundamental tree-based method. They work by dividing the predictor space (the space of all possible input values) using a series of splitting rules. These rules are organized in a hierarchical tree structure, making them easy to visualize and understand. They recursively partition the data based on the values of the predictor variables.

Key Features:

• Simple Interpretation: Easy to understand and explain, even to non-experts. The decision-making process is transparent.
• Non-linear Relationships: Can capture complex, non-linear patterns in the data. This is a major advantage over linear models, which assume a straight-line relationship.
• Regression & Classification: Can be used for both predicting continuous values (regression) and categories (classification).

Regression Trees: A Simple Example

Let’s illustrate with a regression tree example. We’ll use the Hitters dataset (commonly used in statistical learning examples) to predict a baseball player’s salary. This dataset contains information about Major League Baseball players.

• Predictors: These are the input variables we’ll use to make predictions.
  • Years: Number of years the player has played in the major leagues.
  • Hits: Number of hits the player made in the previous year.
• Response: This is the variable we want to predict.
  • Log Salary: We use the logarithm of salary to make the distribution more bell-shaped (normal), which often improves model performance. This transformation helps to stabilize the variance and make the data more suitable for modeling.

Regression Tree for Hitters Data

This image shows a regression tree built from the Hitters data:

Regression tree for Hitters data

Interpreting the Regression Tree: Top Split

Let’s break down how to interpret this tree. The most important split is at the very top:

Regression tree for Hitters data

• Top Split: Years < 4.5
  • This tells us that the number of years a player has been in the major leagues is the single most important factor in determining their salary (or rather, the log of their salary). Less experience generally means a lower salary. This variable explains the most variance in the response variable.

Interpreting the Regression Tree: Internal Nodes & Branches

Regression tree for Hitters data

• Internal Nodes: These represent further splits in the predictor space. For example, the node Hits < 117.5 divides players with less than 4.5 years of experience based on their number of hits. Each internal node represents a decision point based on a predictor variable.
• Branches: The lines connecting the nodes. They represent the “yes” or “no” answers to the splitting rule questions. Each branch corresponds to a specific outcome of the splitting rule.

Interpreting the Regression Tree: Terminal Nodes (Leaves)

Regression tree for Hitters data

• Terminal Nodes (Leaves): These are the final boxes at the bottom of the tree. They represent the predicted values – in this case, the mean log(Salary) for players who fall into that specific region of the predictor space. These are the final prediction points of the tree.

• Example: The left branch means If a player played less than 4.5 years, his predicted log salary is 5.11.

Regions of Predictor Space

The decision tree divides the predictor space (the combination of Years and Hits) into rectangular regions. This image shows how the tree’s splits correspond to these regions:

Three-region partition

Regions of Predictor Space: Region Details

Three-region partition

• R1: Players with Years < 4.5. This region corresponds to the leftmost leaf in the tree.
• R2: Players with Years >= 4.5 and Hits < 117.5. This region corresponds to the middle leaf.
• R3: Players with Years >= 4.5 and Hits >= 117.5. This region corresponds to the rightmost leaf.

Constructing the Regions: Minimizing RSS

The key question is: how do we decide where to make the splits and create these regions? The goal is to find the regions that minimize the Residual Sum of Squares (RSS). RSS is a measure of the overall prediction error of the tree.

The RSS formula is:

\[ \text{RSS} = \sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2 \]

Where:

• \(\hat{y}_{R_j}\): The mean response for the training observations within region Rj. This is the predicted value for all observations in region Rj.
• \(y_i\): The actual response value for the ith observation.

Recursive Binary Splitting: Overview

Recursive binary splitting is a clever way to build the tree efficiently. It’s a heuristic algorithm that finds a good solution, though not necessarily the optimal solution. It has these key characteristics:

• Top-Down: We start with all observations in a single region (the entire predictor space) and successively split the predictor space.
• Greedy: At each step, we make the best split at that particular moment. We don’t look ahead to see if a different split might be better later on. This means we choose the split that minimizes the RSS at the current step.
• Binary: Each split divides a region into exactly two sub-regions. This creates a binary tree structure.

Visualizing Recursive Binary Splitting

This figure illustrates the process of recursive binary splitting:

Recursive binary splitting

• Top Left: The first split is made, dividing the space horizontally based on the value of X1.

Visualizing Recursive Binary Splitting

Recursive binary splitting

• Top Middle: The next two splits are made, one in each of the previously created regions.

Visualizing Recursive Binary Splitting

Recursive binary splitting

• Top Right: Shows the final result of recursive binary splitting in two dimensions (like our Hitters example). The lines represent the splits. The predictor space is fully partitioned into rectangles.

Visualizing Recursive Binary Splitting

Recursive binary splitting

• Bottom Left: Shows the corresponding decision tree. Each split in the top right panel corresponds to an internal node in the tree.

Visualizing Recursive Binary Splitting

Recursive binary splitting

• Bottom Right: Presents a perspective plot of the prediction surface. This gives you a 3D view of how the predicted value (e.g., log salary) changes across the predictor space. The predicted value is constant within each rectangle.

Tree Pruning ✂️

The recursive binary splitting process, if allowed to continue unchecked, will often lead to a very large and complex tree. This tree will likely overfit the training data. Overfitting means the tree is too closely tailored to the training data (including noise) and won’t generalize well to new, unseen data. It will have low bias but high variance.

A smaller tree with fewer splits can have:

• Lower Variance: Less sensitive to the specific details of the training data. It will be more stable and generalize better.
• Better Interpretability: Easier to understand and explain. A simpler model is often preferred for its clarity.

Cost Complexity Pruning

• Goal: Find a subtree T (which is a smaller version of the full tree, T0) that minimizes a penalized version of the RSS:

  \[ \sum_{m=1}^{|T|} \sum_{x_i \in R_m} (y_i - \hat{y}_{R_m})^2 + \alpha|T| \]

• |T|: The number of terminal nodes (leaves) in the subtree T. This is a measure of the tree’s complexity.

• α: A tuning parameter that controls the trade-off between the subtree’s complexity (number of leaves) and how well it fits the training data (RSS). A larger α leads to a larger penalty for complexity.

Classification Trees

Classification trees are very similar to regression trees, but they are used to predict a qualitative response (a category or class label) rather than a continuous value.

• Prediction: Instead of predicting the mean response value in a region, we predict the most commonly occurring class in that region. This is the class with the highest proportion of training observations in that region.
• Interpretation: We also consider the class proportions within each region (the percentage of observations belonging to each class). This gives us an idea of how “pure” each region is.

Growing a Classification Tree

• We still use recursive binary splitting, but we cannot use RSS as the splitting criterion because we’re dealing with classes, not numerical values. RSS is suitable for regression, not classification.
• Alternatives to RSS: We need splitting criteria that measure the impurity of a node (how mixed the classes are within the node).
  • Classification error rate
  • Gini index
  • Entropy

Splitting Criteria: Classification Error Rate

The classification error rate is the simplest option:

\[ E = 1 - \max_k (\hat{p}_{mk}) \]

• \(\hat{p}_{mk}\): The proportion of training observations in the mth region that belong to the kth class. This is the fraction of training observations in region m that are from class k.
• Problem: The classification error rate is not sensitive enough for tree growing. It doesn’t always lead to the best splits. It is possible for different splits to result in the same classification error rate, even if one split produces more homogenous regions.

Splitting Criteria: Gini Index

The Gini index is a more sensitive measure of node purity:

\[ G = \sum_{k=1}^{K} \hat{p}_{mk}(1 - \hat{p}_{mk}) \]

• It measures the total variance across all K classes.
• A small Gini index indicates that the node is pure – most of the observations in that node belong to the same class. (If all \(\hat{p}_{mk}\) are close to 0 or 1, the Gini index will be small). A Gini index of 0 indicates perfect purity.

Splitting Criteria: Entropy

Entropy is another measure of node impurity:

\[ D = -\sum_{k=1}^{K} \hat{p}_{mk} \log \hat{p}_{mk} \]

• Entropy will also take on a value near zero if the node is pure (if the \(\hat{p}_{mk}\) values are close to 0 or 1). An entropy of 0 indicates perfect purity. We use the convention that 0 log 0 = 0.
• The Gini index and entropy are numerically very similar. Both are more sensitive to changes in node purity than the classification error rate.

Example: Heart Data

This figure shows an unpruned classification tree built on the Heart dataset:

Heart data unpruned tree

• Goal: Predict whether a patient has heart disease (Yes or No) based on 13 predictors.

Example: Heart Data - Predictors

Heart data unpruned tree

Trees vs. Linear Models

• Linear Regression: Assumes a linear relationship between the predictors and the response: \(f(X) = \beta_0 + \sum_{j=1}^{p} X_j \beta_j\). The model assumes a constant change in the response for a unit change in each predictor.
• Regression Trees: Assume a piecewise constant model: \(f(X) = \sum_{m=1}^{M} c_m \cdot 1(X \in R_m)\). The predicted value is constant within each region.

Trees vs. Linear Models - Visual Comparison

This figure compares decision boundaries of linear models and trees:

Trees vs. Linear Models

• Top Row: The true decision boundary is linear.

Trees vs. Linear Models - Visual Comparison (Linear Boundary)

Trees vs. Linear Models

• Top Left: The linear model (left) fits the data well, as expected. The decision boundary is a straight line.
• Top Right: The decision tree (right) attempts to approximate the linear boundary with a series of rectangular regions, resulting in a less accurate fit.

Trees vs. Linear Models - Visual Comparison (Non-linear Boundary)

Trees vs. Linear Models

• Bottom Row: The true decision boundary is non-linear.

Trees vs. Linear Models - Visual Comparison (Non-linear Boundary)

Trees vs. Linear Models

• Bottom Left: The linear model (left) is unable to capture the non-linear relationship, resulting in a poor fit.
• Bottom Right: The decision tree (right) captures the non-linearity much better than the linear model (left) by partitioning the space into appropriate regions.

Advantages of Trees 👍

• Easy to Explain: Decision trees are much simpler to explain than even linear regression. They are intuitive and can be easily understood by non-experts.
• Human Decision-Making: Some people believe that decision trees more closely mirror human decision-making processes. They resemble a series of “if-then” rules.
• Graphical Representation: They can be easily displayed graphically, making them easy to interpret. Visualizations aid in understanding the model’s logic.
• Qualitative Predictors: They can handle qualitative predictors directly, without the need to create dummy variables (one-hot encoding). This simplifies the data preparation process.

Disadvantages of Trees 👎

• Lower Predictive Accuracy: Single decision trees generally don’t have the same level of predictive accuracy as some other machine learning methods, like support vector machines or neural networks.
• Non-Robust: Small changes in the data can cause large changes in the final estimated tree. This means they can be unstable and sensitive to noise in the data.

Ensemble Methods: Combining Multiple Models

An ensemble method combines multiple “weak learner” models (like decision trees) to create a more powerful model. Think of it like “wisdom of the crowds” Crowd wisdom – the combined judgment of a group is often better than the judgment of any individual member.

• Weak Learner: A simple model that makes only mediocre predictions (slightly better than random guessing). A single decision tree is often a weak learner.
• Ensemble: A combination of many weak learners, which together form a strong learner. The ensemble leverages the diversity of the individual models to improve overall performance.

Bagging (Bootstrap Aggregation)

• Goal: Reduce the variance of a statistical learning method. This is especially useful for decision trees, which tend to have high variance (they are sensitive to the specific training data).
• Idea: Take many (hundreds or thousands) of “bootstrapped” samples from the training data, build a separate decision tree on each bootstrapped sample, and then average the predictions of all these trees. This averaging process reduces the variance.

Bagging: Out-of-Bag (OOB) Error

• OOB Observations: For each tree, the observations that were not included in the bootstrapped sample are called the “out-of-bag” (OOB) observations. On average, about one-third of the observations are OOB for each tree.

• OOB Prediction: We can predict the response for each observation using only the trees in which that observation was OOB. This provides a way to estimate the prediction error without using a separate validation set.

• OOB Error: The OOB error is a valid estimate of the test error of the bagged model. It’s a very convenient way to assess performance, as it doesn’t require setting aside a separate validation set.

Bagging: Variable Importance

• Interpretability Loss: Bagging improves prediction accuracy, but it sacrifices some interpretability because we no longer have a single tree to examine. The combined model is more of a “black box.”
• Variable Importance Measures: We can still get an overall summary of the importance of each predictor.
  • Regression: For each predictor, record the total amount that the RSS decreases due to splits on that predictor, averaged over all B trees. A larger average decrease indicates a more important predictor.
  • Classification: For each predictor, record the total amount that the Gini index decreases due to splits on that predictor, averaged over all B trees. A larger average decrease indicates a more important predictor.

Random Forests

• Improvement over Bagging: Random forests provide an improvement over bagged trees by introducing a small “tweak” that decorrelates the trees. This further reduces variance and improves prediction accuracy.
• Random Subset of Predictors: At each split in the tree-growing process, a random sample of m predictors is chosen as split candidates from the full set of p predictors. Typically, \(m \approx \sqrt{p}\). This means that at each split, some predictors aren’t even considered! This introduces further randomness and diversity among the trees.

Random Forests: Rationale

• Strong Predictor Problem: In bagging, if there’s one very strong predictor, most of the trees will use that predictor in the top split. This makes the trees very similar to each other (highly correlated). The predictions from highly correlated trees will be similar, and averaging them won’t reduce the variance as much as averaging predictions from uncorrelated trees.
• Decorrelation: By limiting the predictors considered at each split, random forests give other predictors a chance to be chosen. This leads to less correlated trees, and when we average the predictions of less correlated trees, we get lower variance and better overall performance.

Boosting

• Sequential Tree Growth: Unlike bagging and random forests, where trees are grown independently, boosting grows trees sequentially. Each tree is grown using information from previously grown trees. This allows boosting to focus on observations that were poorly predicted by previous trees.
• Slow Learning: Boosting “learns slowly” by fitting small trees to the residuals (the differences between the observed values and the current prediction). It gradually improves the model by focusing on the errors made by previous trees.
• No Bootstrapping: Boosting doesn’t use bootstrapped samples. Instead, it uses a modified version of the original data at each step.

Boosting: Tuning Parameters

• B (Number of Trees): Boosting can overfit if B is too large (although overfitting tends to occur slowly). Use cross-validation to choose B.
• λ (Shrinkage Parameter): A small positive number (e.g., 0.01 or 0.001) that controls the learning rate of the boosting process. Smaller values of λ typically require larger values of B to achieve good performance. A smaller λ leads to slower, more gradual learning.
• d (Number of Splits): Controls the complexity of each tree. Often d = 1 (decision stumps, trees with just a single split) works well, leading to an additive model. d is also referred as interaction depth.

Bayesian Additive Regression Trees (BART)

BART, similar to other ensemble methods, employs decision trees as its foundational components. However, BART distinguishes itself through several key characteristics:

• Random Tree Structure: Like random forests, BART incorporates randomness into the construction of its trees. The structure of each tree is not predetermined.
• Sequential Updates: Similar to boosting, BART refines its model iteratively. The model is updated in a sequential manner, using information from previous iterations.
• Tree Perturbation: Instead of fitting entirely new trees at each step, BART modifies existing trees from previous iterations. This modification is key to BART’s regularization properties.

BART: Core Idea

• Initialization: All trees begin with a single root node, predicting the mean of the response variable.
• Iteration: For each tree, BART randomly perturbs the tree from the previous iteration. This perturbation involves:
  • Changing the tree structure (adding or pruning branches, changing splitting rules).
  • Changing the predictions in the terminal nodes.
• Output: A collection of prediction models (one for each iteration). The final prediction is typically the average of the predictions from all trees after a “burn-in” period (discarding the initial iterations). This averaging helps to stabilize the predictions.

BART: Key Features

• Guards Against Overfitting: Perturbing trees instead of fitting entirely new ones limits how aggressively the model can fit the training data. This helps to prevent overfitting. The random perturbations act as a form of regularization.
• Small Trees: Individual trees in BART are usually kept small. This further contributes to regularization.
• Bayesian Interpretation: BART can be viewed as a Bayesian approach, where the tree perturbations represent draws from a posterior distribution. This provides a natural way to quantify uncertainty in the predictions (e.g., by constructing credible intervals).

Summary of Tree Ensemble Methods

This table summarizes the key characteristics of the ensemble methods we’ve discussed:

Summary

• Tree-Based Methods: Powerful and versatile tools for both regression and classification.
• Interpretability vs. Accuracy: Single decision trees offer high interpretability but may sacrifice predictive accuracy.
• Ensemble Methods: Enhance performance by combining multiple trees. Bagging, random forests, boosting, and BART represent different strategies for creating ensembles.
• Choosing the Right Method: The best ensemble method depends on the specific dataset and problem. Consider factors like data structure, desired interpretability, and computational resources.

Thoughts and Discussion 🤔

• Interpretability: When might a single decision tree be preferred over an ensemble method, even if the ensemble method has slightly higher accuracy? (Hint: Think about situations where explaining the model to stakeholders is crucial, such as in medical diagnosis or loan applications.)
• Method Selection: How might you choose between bagging, random forests, and boosting for a particular problem? What factors would you consider? (Hint: Think about the size of the dataset, the number of predictors, and the potential for strong predictors to dominate.)
• Real-World Applications: Can you think of real-world scenarios where tree-based methods would be particularly well-suited? (Hint: Consider applications like fraud detection, customer churn prediction, or image classification.)
• Limitations: What are some limitations of tree-based methods, even with ensemble techniques? When might they not be the best choice? (Hint: Think about situations with very high-dimensional data or where the underlying relationship is very smooth and linear.)