Decision Trees, Ensemble Methods, and Class Imbalance

From CART & Pruning to Random Forests, XGBoost, and SMOTE

In this lecture, we explore non-parametric tree-based algorithms and techniques for imbalanced data sets.

Required Libraries

# Core ecosystem
library(tidyverse)
library(ISLR2)       # data set
library(caret)       # Unified interface for training and evaluation
library(DT)          # fancy tables

# Tree-based model packages
library(rpart)       # Single decision trees
library(rpart.plot)  # Visualizing CART structures
library(randomForest)# Bagging & Random Forests
library(xgboost)     # Gradient boosted decision trees

# Imbalanced data resampling
library(themis)      # Tidymodels / recipe SMOTE methods
library(recipes)     # Preprocessing pipelines

Single Decision Trees (CART) and Pruning

Theoretical Foundation: Recursive Binary Splitting

Decision trees split the predictor space \(R\) into distinct, non-overlapping regions \(R_1, R_2, \dots, R_J\). For classification, we aim to minimize a measure of node impurity:

• Gini Index:

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

• Cross-Entropy:

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

Where \(\hat{p}_{mk}\) represents the proportion of training observations in the \(m\)-th region that belong to class \(k\).

Data Preparation (ISLR2::Default)

We use the Default dataset from ISLR2. The objective is to predict whether a customer will default on their credit card debt based on student, balance, and income.

data("Default", package = "ISLR2")

# Inspect structure and target distribution
str(Default)

'data.frame':   10000 obs. of  4 variables:
 $ default: Factor w/ 2 levels "No","Yes": 1 1 1 1 1 1 1 1 1 1 ...
 $ student: Factor w/ 2 levels "No","Yes": 1 2 1 1 1 2 1 2 1 1 ...
 $ balance: num  730 817 1074 529 786 ...
 $ income : num  44362 12106 31767 35704 38463 ...

table(Default$default)

  No  Yes 
9667  333 

# Train / Test split (80/20) using caret
set.seed(42)
train_idx <- createDataPartition(Default$default, p = 0.8, list = FALSE)
train_df  <- Default[train_idx, ]
test_df   <- Default[-train_idx, ]

Fitting a Full Tree & Cost-Complexity Pruning

A fully grown tree overfits noise. We prune using Cost-Complexity Pruning (indexed by parameter \(\alpha\) or \(cp\) in rpart):

\[C_\alpha(T) = \sum_{m=1}^{|T|} N_m Q_m(T) + \alpha |T|\]

When you run printcp(), R prints a table with columns like CP, nsplit, rel error, xerror, and xstd.

# Fit initial tree with low complexity parameter to allow deep growth
full_tree <- rpart(default ~ ., data = train_df, method = "class", control = rpart.control(cp = 0.001))

# Plot Complexity Parameter (CP) table
printcp(full_tree)

Classification tree:
rpart(formula = default ~ ., data = train_df, method = "class", 
    control = rpart.control(cp = 0.001))

Variables actually used in tree construction:
[1] balance income  student

Root node error: 267/8001 = 0.033371

n= 8001 

         CP nsplit rel error  xerror     xstd
1 0.0973783      0   1.00000 1.00000 0.060169
2 0.0823970      1   0.90262 0.93633 0.058286
3 0.0524345      2   0.82022 0.86517 0.056096
4 0.0112360      3   0.76779 0.80524 0.054174
5 0.0049938      5   0.74532 0.83146 0.055024
6 0.0037453      8   0.73034 0.84270 0.055384
7 0.0018727     10   0.72285 0.85393 0.055741
8 0.0010701     12   0.71910 0.88390 0.056682
9 0.0010000     19   0.71161 0.91011 0.057490

• CP (Complexity Parameter): The penalty applied to the tree’s size. Smaller CP values mean bigger, more complex trees.
• nsplit: The number of splits (branches) in the tree.
• rel error: The classification error on your training set. This will almost always go down as the tree gets bigger.
• xerror (Cross-Validation Error): The error estimated on unseen data (out-of-sample). This is your primary target.
• xstd: The standard deviation/standard error of xerror.

You want to see where xerror stops dropping and starts going back up (a sign of overfitting).

The Goal: Find the row with the lowest xerror. which.min(full_tree$cptable[, "xerror"]) automatically selects the CP from this row to prune the tree.

plotcp(full_tree) gives you a visual plot of the table above:

plotcp(full_tree)

• X-axis (top/bottom): CP value and size of tree (number of splits).
• Y-axis: Cross-validated error (xerror).
• Dashed Horizontal Line: Represents the “1-SE rule” (1 standard error above the minimum xerror).

What to Look For:

• A U-shaped or elbow curve.
• The lowest point on the line corresponds to the optimal tree size.
• If the curve drops rapidly and then flattens out, the “elbow point” gives you a good balance between model simplicity and accuracy.

rpart.plot(...) prints the visual representation of your pruned decision tree.

# Extract optimal CP corresponding to minimum cross-validated error
opt_cp <- full_tree$cptable[which.min(full_tree$cptable[, "xerror"]), "CP"]

# Prune the tree
pruned_tree <- rpart::prune(full_tree, cp = opt_cp)

# Visualize the pruned tree
rpart.plot(pruned_tree, main = "Pruned Decision Tree (Default Classification)", extra = 104)

1. The Root Node (Top): Shows the overall default rate in your training set and the total percentage of data (100%).
2. Splitting Variables: The primary feature chosen at each node represents the most significant feature for separating defaults from non-defaults.
3. The Terminal Nodes (Leaves at the Bottom):
   • Top Number: Predicted class (e.g., No for No Default, Yes for Default).
   • Percentages:
     • First percentage: Proportion of observations falling into class 0 vs class 1 at that specific leaf.
     • Second percentage: The percentage of your overall data set that landed in that leaf node.

Ensemble Methods — Random Forests

Why Single Trees Fail

Single trees suffer from high variance: small changes in training data yield radically different tree structures.

Bagging to Random Forests

1. Bagging (Bootstrap Aggregating): Fits \(B\) bootstrap samples and averages predictions: \[\hat{f}_{bag}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}^{*b}(x)\]
2. Random Forests: Solves tree correlation in bagging by restricting each split to consider a random sample of \(m \approx \sqrt{p}\) predictors out of \(p\) available features.

Fitting a Random Forest in R (caret)

fit_control <- trainControl(
  method = "cv",
  number = 5,
  classProbs = TRUE,
  summaryFunction = twoClassSummary
)

set.seed(42)
rf_fit <- train(
  default ~ .,
  data = train_df,
  method = "rf",
  metric = "ROC",
  trControl = fit_control,
  tuneGrid = expand.grid(mtry = c(1, 2, 3)),
  ntree = 300
)

print(rf_fit)

Random Forest 

8001 samples
   3 predictor
   2 classes: 'No', 'Yes' 

No pre-processing
Resampling: Cross-Validated (5 fold) 
Summary of sample sizes: 6401, 6400, 6401, 6402, 6400 
Resampling results across tuning parameters:

  mtry  ROC        Sens       Spec     
  1     0.8565031  0.9956039  0.2664570
  2     0.8867287  0.9906902  0.3113906
  3     0.8908265  0.9900437  0.3303284

ROC was used to select the optimal model using the largest value.
The final value used for the model was mtry = 3.

In Random Forest models, mtry is the number of variables (features) randomly sampled as candidates at each split in a tree.

Instead of testing every single feature in the data set to decide how to split a node (which is what a single, standard decision tree does), a Random Forest randomly picks a small subset of features—here, exactly 3—and only evaluates those 3 to find the best split point.

The main reason Random Forests perform so much better than individual decision trees comes down to decorrelating the trees:

1. Prevents Dominant Features: If your data set has one ultra-strong predictor (e.g., Credit Score), a standard tree will always split on it first. Every single tree in an ensemble would end up looking almost identical, giving you a forest full of identical trees.
2. Forces Variety: By forcing the model to pick from only mtry = 3 random features at each split, it occasionally forces a tree to ignore that dominant feature and discover hidden, secondary relationships in other variables.
3. Reduces Variance: Averaging predictions across hundreds of slightly different, uncorrelated trees drastically cuts down on model variance (overfitting) without increasing bias.

Packages like caret or randomForest in R, mtry is typically the main hyperparameter tuned during cross-validation. Default starting values generally follow these standard conventions:

• Classification: \(\sqrt{p}\) (where \(p\) is the total number of predictor variables)
• Regression: \(\frac{p}{3}\)

Variable Importance

While a single decision tree gives you an explicit flowchart to read, a Random Forest combines hundreds of trees, making it a bit of a “black box.”

Running varImp() gives you the transparency back:

• Interpretability: You can easily explain to non-technical stakeholders which features actually drive the predictions.
• Feature Selection: If you have a massive dataset with 50+ variables, you can use this plot to prune out the bottom half that aren’t contributing, simplifying future data collection and speeding up model execution.

plot(varImp(rf_fit), main = "Variable Importance - Random Forest")

In a Random Forest, feature importance measures how much worse the model performs without that feature. It’s generally calculated in one of two ways:

1. Mean Decrease in Accuracy (Permutation Importance):

• The model takes out-of-bag (OOB) data and randomly shuffles (scrambles) the values of a single variable, keeping everything else the same.
• It measures how much the model’s prediction accuracy drops. If accuracy plummets, that variable was doing heavy lifting.

2. Mean Decrease in Gini / Impurity:

• It sums up the total reduction in node impurity (e.g., Gini impurity for classification or MSE for regression) brought about by splits on that specific variable, averaged across all trees in the forest.

Gradient Boosted Decision Trees (XGBoost)

Boosting Mechanics

Unlike Random Forests (independent parallel trees), Boosting builds trees sequentially. Each new tree is fitted to the residual errors of prior trees: \[f_b(x) = f_{b-1}(x) + \lambda \hat{f}^b(x)\] XGBoost (eXtreme Gradient Boosting) optimizes second-order Taylor approximations of the loss function with L1/L2 regularization to prevent overfitting.

Fitting Native XGBoost with xgb.train

(Note: Trained using xgboost directly to interface cleanly with modern C++ ALTREP memory pointers.)

# One-hot encode predictors for XGBoost
X_train <- model.matrix(default ~ . - 1, data = train_df)
y_train <- ifelse(train_df$default == "Yes", 1, 0)

dtrain <- xgb.DMatrix(data = X_train, label = y_train)

# Set hyperparameter configuration
params <- list(
  booster          = "gbtree",
  objective        = "binary:logistic",
  eval_metric      = "auc",
  eta              = 0.1,
  max_depth        = 4,
  gamma            = 0,
  colsample_bytree = 0.8,
  min_child_weight = 1,
  subsample        = 0.8
)

set.seed(42)
xgb_fit <- xgb.train(
  params    = params,
  data      = dtrain,
  nrounds   = 100,
  verbose   = 0
)

print(xgb_fit)

##### xgb.Booster
call:
  xgb.train(params = params, data = dtrain, nrounds = 100, verbose = 0)
# of features: 4 
# of rounds:  100 

Dealing with Imbalanced Datasets

The Imbalance Problem

In the Default dataset, default events account for only ~3.3% of total samples. A naive model predicting No for all instances yields ~96.7% accuracy, rendering standard accuracy uninformative.

Resampling Strategies

• Down-sampling: Randomly drops majority instances.
• Up-sampling: Randomly duplicates minority instances.
• SMOTE (Synthetic Minority Over-sampling Technique): Creates synthetic minority samples along line segments connecting \(k\)-nearest minority neighbors.

Implementing SMOTE & Comparing Resampling in caret

# Recipe pipeline for SMOTE preprocessing
smote_rec <- recipe(default ~ ., data = train_df) %>%
  step_dummy(all_nominal_predictors()) %>%  # Converts 'student' into numeric dummy variables
  step_smote(default, over_ratio = 0.8)     # Now all predictors are double/integer!

# Control structure tuned for Sensitivity/Recall
eval_control <- trainControl(
  method = "cv",
  number = 5,
  classProbs = TRUE,
  summaryFunction = twoClassSummary
)

# 1. Baseline Model (Standard RF)
set.seed(42)
rf_base <- train(default ~ ., data = train_df, method = "rf", metric = "ROC", trControl = eval_control)

note: only 2 unique complexity parameters in default grid. Truncating the grid to 2 .

# 2. Down-Sampled RF
control_down <- eval_control
control_down$sampling <- "down"
set.seed(42)
rf_down <- train(default ~ ., data = train_df, method = "rf", metric = "ROC", trControl = control_down)

note: only 2 unique complexity parameters in default grid. Truncating the grid to 2 .

# 3. SMOTE-Sampled RF via recipes/themis
set.seed(42)
rf_smote <- train(smote_rec, data = train_df, method = "rf", metric = "ROC", trControl = eval_control)

note: only 2 unique complexity parameters in default grid. Truncating the grid to 2 .

Comprehensive Model Comparison

We evaluate performance on the held-out test data set using Precision, Recall (Sensitivity), Specificity, and ROC-AUC.

models <- list(
  "Pruned CART"  = pruned_tree,
  "Random Forest"= rf_fit,
  "XGBoost"      = xgb_fit,
  "RF (SMOTE)"   = rf_smote
)

evaluate_model <- function(model, test_data, target_col = "default") {
  
  if (inherits(model, "rpart")) {
    probs <- predict(model, test_data, type = "prob")[, "Yes"]
    preds <- factor(ifelse(probs > 0.5, "Yes", "No"), levels = c("No", "Yes"))
    
  } else if (inherits(model, "xgb.Booster")) {
    # Prepare test matrix matching model.matrix structure
    X_test <- model.matrix(as.formula(paste(target_col, "~ . - 1")), data = test_data)
    dtest  <- xgb.DMatrix(data = X_test)
    
    probs  <- predict(model, dtest)
    preds  <- factor(ifelse(probs > 0.5, "Yes", "No"), levels = c("No", "Yes"))
    
  } else {
    probs <- predict(model, test_data, type = "prob")[, "Yes"]
    preds <- predict(model, test_data)
  }
  
  cm <- confusionMatrix(preds, test_data[[target_col]], positive = "Yes")
  
  c(
    Accuracy    = unname(cm$overall["Accuracy"]),
    Sensitivity = unname(cm$byClass["Sensitivity"]), # Recall
    Specificity = unname(cm$byClass["Specificity"]),
    Precision   = unname(cm$byClass["Pos Pred Value"]),
    F1          = unname(cm$byClass["F1"])
  )
}

results <- sapply(models, evaluate_model, test_data = test_df) %>% t()
datatable(round(results, 4), caption = "Out-of-Sample Performance Comparison on Credit Default Test Set")

When deciding which model to choose for credit default prediction, raw accuracy is misleading. Because default events are relatively rare (~3.3% of the data set), predicting “No” for everyone yields ~96.7% accuracy.

In credit risk modeling, the business cost of a False Negative (approving a loan for a borrower who defaults, leading to charge-offs) is drastically higher than the cost of a False Positive (flagging a borrower who would have paid, resulting in a minor review or slight loss of transaction fee).

Therefore, model selection comes down to your primary risk objective:

RF (SMOTE) for Risk Management

If the primary goal is loss mitigation and catching as many potential defaults as possible, RF (SMOTE) is the clear choice.

• Sensitivity/Recall (0.7727): It identifies 77.3% of all actual defaults on unseen test data, compared to only 37.8%–43.9% for the un-resampled models.
  
• The Trade-Off: Because SMOTE balances the class distribution during training, it trades off Precision (0.2315) and Specificity (0.9141). You will flag more non-defaulting borrowers for secondary review, but you protect the business from massive credit losses.

Bottom Line for Credit Risk: Missing a default costs thousands in principal loss; doing a secondary manual review on a false flag costs a few dollars. RF (SMOTE) aligns best with actual bank economics.

Pruned CART for Balanced Automation:

If the goal is to balance predictive performance with regulatory interpretability and operational simplicity, Pruned CART is the strongest candidate.

• Best Unadjusted Performance: Among the non-SMOTE models, it yields the highest Sensitivity (0.4394), the highest F1 score (0.5179), and competitive Accuracy (0.9730).
• Interpretability & Compliance: Under financial compliance frameworks (e.g., FCRA/ECOA adverse action notices), a single pruned tree (rpart.plot) provides transparent, explicit rules for why a applicant was denied credit. Ensemble black-boxes like standard Random Forest and XGBoost offer virtually no performance gain here to justify losing that interpretability.

Comparison Summary Table

Model	Primary Advantage	Best Use Case
RF (SMOTE)	Maximum Defaulter Detection (75.8% Recall)	High-risk lending / Loss minimization
Pruned CART	Clear decision rules + solid baseline F1	Regulatory compliance / Explainable approval engines
XGBoost / Standard RF	High Precision (~64%), but poor Recall (~38–39%)	Conservative screening where False Positives are heavily penalized

If you are optimizing for financial loss prevention, choose RF (SMOTE). If you are optimizing for transparent automated underwriting, choose Pruned CART.