Tree-Based Methods

8 Tree-Based Methods

This chapter focuses on tree-based methods for regression and classification, which stratify or segment the predictor space into simpler regions for predictive modeling.

8.1 The Basics of Decision Trees

Decision trees can be utilized in both regression and classification contexts. The following sections detail their structure, processes, and example applications.

8.1.1 Regression Trees

• Definition: A regression tree predicts continuous outcomes by segmenting the predictor space and assigning mean values to segmented inputs.

• Example: The Hitters dataset is used to predict baseball player salaries based on their years in the major leagues and previous year hits.

  • Data Preparation:

  • Remove entries with missing salary data.

  • Log-transform salaries to approximate normal distribution (e.g., log salary measured in thousands).

• Tree Structure:

  • Internal nodes represent splits based on predictors (e.g., Years < 4.5).

  • Terminal nodes (leaves) contain predicted values (mean responses).

• Regions Defined:

  • R1 = {X | Years < 4.5}

  • R2 = {X | Years ≥ 4.5, Hits < 117.5}

  • R3 = {X | Years ≥ 4.5, Hits ≥ 117.5}

• Predicted salaries for defined regions:

  • R1: $165,174

  • R2: $402,834

  • R3: $845,346

• Interpretation: Experience (Years) is shown as the key determinant of salary, with previous hits being more crucial among experienced players.

• Regression Tree Building Process:

  1. Divide Predictor Space: Segment into J distinct, non-overlapping regions.

  2. Mean Response Prediction: For observations in region Rj, predict the mean of training observations.

  • Shape of Regions: Typically high-dimensional rectangles for ease of use and interpretation.

  • RSS Optimization: Minimize Residual Sum of Squares (RSS) given by:
    $ext{RSS} = ext{ }<br>\bigg( J \bigg) \bigg( \bigg(i ext{, }Rj \bigg)(y<em>i - \bar{y}</em>{Rj})^2 \bigg)$

  • R1(j, s) and R2(j, s) defined as:
    ext{R1(j, s)} = igg t {X|Xj < s} ext{ and } ext{R2(j, s)} = igg t {X|Xj > s}

  • Recursive Binary Splitting: A greedy top-down approach to grow trees, requiring thorough computation of splits.

  • Stopping Criterion: May cease growth when nodes contain fewer than a set number of observations.

8.1.2 Tree Pruning

• Tree complexity can lead to overfitting; therefore, pruning is necessary to simplify and enhance instructive interpretations.

• Two main strategies involve:

  • Early stopping based on a RSS threshold.

  • Growing a full tree and then pruning to a subtree that minimizes cross-validation test error.

• Cost Complexity Pruning:

  • An approach that creates a sequence of trees indexed by a tuning parameter $ext{λ}$ to balance model fit and complexity of the subtree:
    $ext{Minimize} \bigg( ext{RSS} + λ|T| \bigg)$

  • where |T| is the count of terminal nodes, ensuring that as λ increases, the tree shrinks in size as complexity rises.

• Algorithm for Building Regression Trees:

  1. Grow a large tree with recursive binary splitting until splits have too few observations.

  2. Use cost complexity pruning to obtain varying subtrees based on λ.

  3. Use K-fold cross-validation for λ selection to minimize prediction error.

  4. Return the optimum subtree corresponding to chosen λ.

8.1.3 Classification Trees

• Classification Tree Definition: Similar in structure to regression trees, yet predict categorical outcomes.

  • The terminal node indicates the most frequent class among training observations.

• Tree Growth: Uses similar methods as regression trees, but splits are based on metrics like classification error rate, Gini index, or entropy instead of RSS.

  • Classification Error Rate:
    $E = 1 - { ext{max }} \bigg(\bar{p}_{mk}\bigg)$

• Gini Index ($G$): A measure of node impurity given by:
  $G = \bigg( ext{K} \bigg) \bar{p}<em>{mk}(1 - \bar{p}</em>{mk})$

• Entropy ($D$): Defined as:
  $D = -\bigg( ext{K} \bigg) \bar{p}<em>{mk} ext{log} \bar{p}</em>{mk}$

• Example Application: Heart dataset for patients presenting with chest pain predicts binary outcome (presence of heart disease).

  • Split qualitative predictors such as Sex or Chest Pain while growing trees (indicator represented in figures).

8.1.4 Trees vs. Linear Models

• Distinct models with differing assumptions:

  • Linear Regression Model: $f(X) = \beta<em>0 + \bigg( ext{P} \bigg)\beta</em>j X_j$

  • Regression Tree Model: $f(X) = \bigg( ext{M} \bigg) c<em>m imes ext{1}(X ext{in } R</em>m)$

• The model selection depends significantly on the relationship between predictors and response:

  • Linear models suffice if relationships are linear.

  • Non-linear relationships indicate decision trees may outperform linear approaches.

8.1.5 Advantages and Disadvantages of Trees

Advantages:

• Easier understanding and explanation compared to linear models.

• Suitable for qualitative predictors without dummy variable creation.

• Visualization of decisions aligns with human reasoning processes.

Disadvantages:

• Tendency for lower predictive accuracy versus models like linear regression.

• Prone to instability with small data changes, highlighting a necessity for ensemble methods to improve predictive performance.

8.2 Bagging, Random Forests, Boosting, and Bayesian Additive Regression Trees

• Ensemble Methods: Combine outputs from multiple weak learners to create a strong model.

  • Weak learners are simple models that provide decent predictions when aggregately combined.

8.2.1 Bagging

• The bootstrap method, leveraged for variance reduction, enhances stability in decision trees which can exhibit high variance.

• Bagging Mechanism:

  • Resampling data to create multiple training datasets.

  • Each tree grows independently, reducing overall prediction error by aggregating predictions from all trees.