Decision Trees and Ensemble Learning

Introduction

Decision trees are among the most interpretable supervised-learning methods for structured business data. A tree predicts an outcome by recursively partitioning observations according to feature values. Ensemble methods extend this idea by combining many trees or other models to improve predictive accuracy, stability, or robustness. The principal methods considered in this chapter are bagging, random forests, boosting, gradient boosting, and stacking.

These methods are especially valuable in business analytics because business data commonly contain nonlinear relationships, interactions, mixed measurement scales, missing values, categorical variables, and operational thresholds. For example, customer churn may increase sharply after a service-delay threshold, credit risk may depend on an interaction between income and utilization, and demand may vary differently across regions and seasons. Trees can represent such patterns without requiring a predetermined functional form.

Their flexibility, however, creates risks. Deep trees can overfit, feature importance can be misleading, probability estimates may be poorly calibrated, and highly accurate ensembles can be difficult to explain. Sound application therefore requires both statistical evaluation and managerial judgment.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain how classification and regression trees partition feature space.
2. Calculate and interpret entropy, Gini impurity, variance reduction, and information gain.
3. Distinguish pre-pruning from post-pruning and explain their effects on generalization.
4. Compare bagging, random forests, boosting, gradient boosting, and stacking.
5. Explain why ensemble diversity affects predictive performance.
6. Design an evaluation and governance process for tree-based business models.
7. Assess the strengths and limitations of tree methods in structured business data.

1. The Logic of a Decision Tree

A decision tree consists of a root node, internal decision nodes, branches, and terminal or leaf nodes. At each internal node, the algorithm selects a split such as:

• customer tenure ≤ 12 months;
• annual income > $60,000;
• channel = mobile;
• inventory level ≤ 150 units.

The observations satisfying the condition move down one branch and the remaining observations move down another. A classification leaf predicts a class, usually the majority class or an estimated class probability. A regression leaf predicts a numerical value, commonly the mean response of observations in that leaf.

Let the training data be [[M:D = {(x_i, y_i)}_{i=1}^n]], where [[M:x_i]] is the feature vector for observation i and [[M:y_i]] is its response. A tree divides the predictor space into disjoint regions [[M:R_1, R_2, ..., R_J]]. Its prediction is piecewise constant:

Here, [[M:1(x ∈ R_j)]] equals 1 when x is in region [[M:R_j]] and 0 otherwise; [[M:c_j]] is the prediction assigned to region j; and J is the number of terminal regions. This representation explains why trees capture nonlinearities and interactions naturally, but also why predictions can change abruptly near a split.

Classification Trees

For a classification problem with K classes, let [[M:p_{jk}]] be the proportion of observations in leaf j belonging to class k. The most common class prediction is:

The estimated probability of class k for a new observation assigned to leaf j is often [[M:p_{jk}]]. These probabilities are empirical proportions and may be unreliable when a leaf is small.

Two widely used impurity measures are Gini impurity and entropy.

Here, t denotes a node and [[M:p_{tk}]] is the class-k proportion at that node. Terms with [[M:p_{tk}=0]] contribute zero to entropy by continuity. Both measures are zero when a node is pure. For binary classification, Gini impurity is greatest at a 50:50 class mix; entropy behaves similarly. Entropy is measured in bits when the logarithm is base 2, whereas Gini impurity is dimensionless.

Suppose a parent node t is divided into child nodes L and R. If [[M:N_t]], [[M:N_L]], and [[M:N_R]] are their observation counts, the weighted post-split impurity is:

The impurity reduction is:

A greedy tree algorithm evaluates candidate splits and chooses the split with the largest reduction, subject to constraints such as minimum leaf size or maximum depth. The split-selection criterion is local: the best immediate split is not always part of the globally best tree.

Regression Trees

For regression, a leaf commonly predicts the mean response:

where [[M:N_j]] is the number of observations in region j. The within-leaf sum of squared errors is:

A candidate split is evaluated by the total child SSE. The preferred split minimizes:

Equivalently, it maximizes the reduction in squared error relative to the parent node. This criterion assumes squared-error loss is appropriate and gives greater influence to large residuals. For skewed outcomes or asymmetric business costs, alternative losses, such as absolute error or quantile loss, may be more suitable.

Worked Example: A Classification Split

Consider a churn node containing 10 customers: six churn and four non-churn. Its Gini impurity is:

[[M:Gini(parent) = 1 − (0.6² + 0.4²) = 0.48]]

Suppose a proposed split produces a left child with four customers, all of whom churn, and a right child with six customers, two of whom churn and four of whom do not. The left-child impurity is 0. The right-child impurity is:

[[M:Gini(right) = 1 − ((2/6)² + (4/6)²) = 0.4444]]

The weighted post-split impurity is:

[[M:I_split = (4/10)(0) + (6/10)(0.4444) = 0.2667]]

Therefore, the reduction is approximately:

[[M:∆I = 0.48 − 0.2667 = 0.2133]]

The split substantially improves class separation. This calculation does not establish that the split will generalize; its value must be assessed using validation data.

2. Tree Growth, Overfitting, and Pruning

An unrestricted tree can continue splitting until leaves contain very few observations. Such a tree may fit noise, unusual cases, or accidental correlations in the training sample. Training error usually decreases as a tree becomes more complex, but validation error often follows a U-shaped pattern: it initially decreases, reaches a minimum, and then increases.

Pre-Pruning

Pre-pruning stops growth before the tree becomes excessively complex. Common controls include:

• maximum depth;
• minimum observations required to split a node;
• minimum observations in a leaf;
• minimum impurity decrease;
• maximum number of leaves.

Pre-pruning is computationally efficient but can stop too early. A locally weak split may enable strong later splits, so early stopping can overlook useful structure.

Post-Pruning

Post-pruning first grows a relatively large tree and then removes branches that do not justify their complexity. Cost-complexity pruning uses an objective such as:

Here, [[M:T]] is a tree, [[M:R(T)]] is its empirical prediction loss, [[M:|T|]] is the number of terminal leaves, and [[M:α ≥ 0]] is a complexity parameter. Larger α imposes a greater penalty on tree size. The value of α should be selected using validation or cross-validation, not by optimizing training loss alone.

Pruning improves interpretability and can reduce variance. It does not guarantee superior performance for every dataset, particularly when a later ensemble will average many deliberately complex trees.

3. Bagging and Random Forests

Bagging

Bagging, or bootstrap aggregating, reduces variance by fitting models to multiple bootstrap samples and averaging their predictions. A bootstrap sample of size n is formed by sampling n observations with replacement from the original training set. Approximately 63.2% of distinct observations appear in a bootstrap sample on average; the remaining observations are called out-of-bag observations for that model.

For regression, a bagged prediction is the average:

For classification, the ensemble may use majority voting or average class probabilities. Here, B is the number of fitted base trees. Averaging is most effective when individual models are reasonably accurate and their errors are not perfectly correlated.

Random Forests

A random forest combines bootstrap sampling with random feature selection. At each split, the algorithm considers only a randomly selected subset of predictors rather than all available predictors. This decorrelates trees, which is important because averaging highly correlated trees provides limited variance reduction.

A useful approximation for the variance of an average of B exchangeable predictors is:

Here, [[M:σ²]] is the variance of an individual tree and [[M:ρ]] is the pairwise correlation between tree predictions. As B increases, the second term approaches zero, but the first term remains. Thus, reducing correlation ρ can be more valuable than simply increasing the number of trees.

Random forests generally require little feature scaling, represent nonlinear relationships well, and provide internal out-of-bag error estimates. Their limitations include reduced interpretability, memory and computational demands, and possible bias in impurity-based feature importance toward variables with many possible split points or categories.

Out-of-Bag Evaluation

An observation can be evaluated using only trees whose bootstrap samples excluded it. The resulting out-of-bag estimate is useful as an internal performance diagnostic. It is not a substitute for a genuinely untouched test set when model selection, repeated experimentation, or high-stakes deployment is involved.

4. Boosting and Gradient Boosting

Bagging fits trees independently and then averages them. Boosting fits trees sequentially, with later trees emphasizing errors made by earlier trees. The sequential dependence often reduces bias, although it can increase sensitivity to noise and tuning choices.

AdaBoost Intuition

In binary classification, AdaBoost assigns greater weight to observations misclassified by the current ensemble. A new weak learner is then fitted to the reweighted data. The learner receives a weight based on its weighted error. In a conventional formulation, if the weighted error is [[M:ε_m]], the learner coefficient is:

This expression applies when [[M:0 < ε_m < 0.5]]. A learner with error below 0.5 receives positive weight; a learner with error near 0.5 contributes little. AdaBoost is conceptually important because it shows how sequential correction can create a strong classifier from weak learners.

Gradient Boosting

Gradient boosting generalizes sequential correction to differentiable loss functions. Let [[M:F_{m−1}(x)]] be the current model and [[M:L(y,F(x))]] the loss. The negative gradient at observation i is:

A new tree is fitted to these pseudo-residuals, and the model is updated:

Here, [[M:h_m(x)]] is the newly fitted tree and [[M:η]] is the learning rate, usually between 0 and 1. Smaller learning rates often require more trees but can improve generalization when paired with suitable regularization.

For squared-error regression, the negative gradient is the ordinary residual [[M:y_i − F_{m−1}(x_i)]]. Thus, ordinary residual fitting is a special case of gradient boosting. For classification, the loss is commonly logistic loss, and the model may represent log-odds rather than direct probabilities.

Important gradient-boosting controls include tree depth, learning rate, number of trees, subsampling fraction, minimum leaf size, and regularization. Early stopping selects the number of trees using validation performance. Modern implementations such as histogram-based gradient boosting and ordered or categorical-aware methods improve speed or handling of categorical variables, but they do not eliminate the need for careful validation and governance.

5. Stacking

Stacking combines heterogeneous base learners through a meta-learner. For example, a business prediction system may combine a regularized linear model, a random forest, and a gradient-boosting model. The meta-learner learns how to weight their predictions.

A central methodological requirement is that meta-model training predictions must be out-of-fold predictions. If the meta-learner receives predictions generated by models trained on the same observations, it can exploit overfitting artifacts and produce optimistic estimates.

A typical procedure is:

1. Divide the training data into folds.
2. For each fold, train each base learner on the other folds and predict the held-out fold.
3. Concatenate these held-out predictions into a new design matrix.
4. Train the meta-learner on that matrix and the observed outcomes.
5. Retrain base learners on all available training data for final prediction.

Stacking can improve performance when base models have complementary error patterns. It adds complexity, however, and may offer little benefit when one strong model already dominates or when the data are too limited for reliable out-of-fold learning.

6. Ensemble Diversity and Model Selection

Ensemble accuracy depends on two properties: individual competence and diversity. Diversity means that models make different errors. A group of weak but identical models does not become strong merely through repetition. In contrast, models trained on different samples, feature subsets, losses, or representations may correct one another.

Sources of diversity include:

• bootstrap samples;
• random feature subsets;
• different tree depths;
• different loss functions;
• different algorithms;
• different time windows or data representations.

The appropriate model is not necessarily the one with the lowest overall error. Business evaluation should also consider:

• class-specific recall and precision;
• expected financial cost of errors;
• probability calibration;
• stability across time and customer segments;
• latency and infrastructure cost;
• interpretability and contestability;
• fairness and regulatory obligations.

For binary classification, precision and recall are:

Here, TP, FP, and FN denote true positives, false positives, and false negatives. Accuracy can be misleading when classes are imbalanced. A model used to identify fraud, for example, should be assessed using costs, ranking quality, recall at an operational threshold, and the investigation capacity of the organization.

For regression, common metrics include mean absolute error and root mean squared error:

MAE is in the same units as the response and treats errors linearly. RMSE is also in response units but penalizes large errors more heavily. Metric selection should reflect the business loss function.

7. Applied Case: Predicting Customer Churn

The following is an illustrative case, not a report of a specific company.

Background and Problem

A subscription service wants to identify customers likely to cancel within the next 60 days. The organization has billing history, tenure, service tickets, usage frequency, contract type, payment method, and recent price changes. The retention team can contact only 8% of customers each month, so the operational objective is to rank customers rather than classify every customer equally.

Analysis

The data scientist first defines the prediction time precisely. Features must be available before the scoring date, and the outcome window must begin after that date. This prevents leakage from cancellation requests or post-cancellation activity. Because customer behavior changes over time, a chronological training-validation-test split is preferable to a purely random split.

A shallow classification tree provides a transparent baseline. It identifies rules such as short tenure combined with declining usage, but its performance is unstable across samples. A random forest improves ranking stability and captures interactions among contract type, service problems, and usage. Gradient boosting produces the strongest validation lift, particularly when regularization and early stopping are used. A stacked model adds little improvement and is rejected because its additional governance burden is not justified.

The evaluation emphasizes recall among the highest-risk 8%, expected retention value, calibration, and performance by customer segment. If a contact costs $4 and a successful intervention yields an expected margin of $80, the organization should not contact every high-score customer automatically. The threshold should incorporate contact capacity, intervention success probability, customer experience, and the cost of unnecessary contact.

Approach and Solution

The final workflow includes:

1. leakage-controlled feature construction;
2. chronological validation;
3. a pruned tree for explanation;
4. a regularized gradient-boosting model for ranking;
5. probability calibration on a validation set;
6. segment-level fairness and stability checks;
7. human review for unusual or high-value accounts;
8. monthly monitoring of drift, lift, calibration, and realized retention value.

Feature importance is communicated using multiple methods. Global permutation importance estimates the performance change after shuffling a feature, while local explanations describe why a particular account received a high score. These explanations are treated as evidence about model behavior, not as proof of causation. For example, service tickets may predict churn because service quality contributes causally, because dissatisfied customers submit more tickets, or because both reflect an unmeasured problem.

Outcome and Learning Points

The model improves the quality of the limited retention queue, but it does not establish that contacting a high-risk customer will prevent churn. A randomized treatment experiment is required to estimate incremental retention caused by the intervention. The case demonstrates three principles: prediction and intervention are different tasks; temporal leakage can invalidate an apparently strong model; and operational usefulness depends on decision economics, not only an abstract accuracy score.

8. Limitations, Ethics, and Governance

Interpretability and Causality

A single shallow tree is easy to inspect, whereas a large ensemble is not. Post hoc explanation tools can support communication but may be approximate, unstable, or misunderstood. Feature importance does not imply that changing the feature will change the outcome. Managers should distinguish predictive association from causal effect.

Fairness and Disparate Impact

Tree ensembles can reproduce historical discrimination through proxies such as geography, language, purchasing patterns, or service access. Removing a protected attribute does not necessarily remove its information from other variables. Fairness assessment should examine relevant group metrics, error rates, calibration, access to beneficial decisions, and the legal context. Trade-offs among fairness criteria may be mathematically unavoidable, so they require explicit policy decisions.

Privacy and Security

Business datasets may contain personal, financial, or sensitive behavioral information. Data minimization, purpose limitation, access control, retention policies, encryption, and audit trails are essential. Models should be tested for membership inference, unauthorized attribute reconstruction, and vulnerability to manipulated inputs where relevant.

Drift and Monitoring

A deployed tree model can degrade when customer behavior, prices, competitors, policies, or data-generation processes change. Monitoring should include input distributions, missingness, prediction distributions, calibration, outcome performance, and subgroup stability. Retraining should be governed by evidence and version-controlled rather than triggered by arbitrary calendar dates alone.

9. Best-Practice Implementation Sequence

A disciplined project commonly follows this sequence:

1. Define the decision, prediction horizon, unit of analysis, and business loss.
2. Establish a simple baseline, such as a majority classifier or mean predictor.
3. Partition data according to the deployment process, especially when time matters.
4. Preprocess without leakage; fit transformations only on training data.
5. Train an interpretable tree and inspect splits for plausibility.
6. Tune forests and boosting models using nested or carefully separated validation.
7. Compare performance, calibration, stability, cost, and operational feasibility.
8. Examine errors and performance across important segments.
9. Calibrate probabilities when decisions depend on estimated risk.
10. Document data lineage, features, hyperparameters, evaluation results, limitations, and approval responsibilities.
11. Deploy with monitoring, rollback procedures, and periodic review.

Contemporary Developments

Current tree-based practice increasingly emphasizes scalable gradient boosting, native treatment of categorical variables, monotonic constraints, quantile prediction, and explainable model interfaces. Monotonic constraints can encode domain knowledge such as the requirement that default risk should not decrease as debt burden increases, although constraints must be justified and may reduce predictive flexibility. Quantile regression forests and quantile boosting estimate conditional ranges rather than only conditional means, which is useful for inventory, staffing, and financial planning under uncertainty.

Automated machine-learning systems can search tree architectures and hyperparameters efficiently, but automation does not solve target definition, leakage, fairness, causal interpretation, or governance. Human expertise remains necessary to determine whether a high-performing model supports a legitimate and beneficial business decision.

Chapter Summary

Decision trees recursively partition predictor space into regions and assign a prediction to each terminal leaf. Classification trees use class proportions and impurity measures such as Gini impurity or entropy; regression trees commonly minimize within-leaf squared error. Unrestricted growth can overfit, making pre-pruning, post-pruning, validation, and complexity control important.

Bagging reduces variance by averaging trees fitted to bootstrap samples. Random forests add random feature selection to reduce correlation among trees and thereby improve ensemble variance reduction. Boosting fits models sequentially to correct prior errors. AdaBoost reweights difficult observations, while gradient boosting follows the negative gradient of a chosen loss. Stacking combines heterogeneous models using carefully generated out-of-fold predictions.

Ensemble diversity, individual model quality, and the correlation of errors jointly influence performance. Model assessment must reflect business costs, class imbalance, calibration, time dependence, fairness, interpretability, and deployment constraints. In structured business data, tree methods are powerful because they capture nonlinearities, thresholds, and interactions with limited preprocessing, but they require disciplined leakage prevention, monitoring, governance, and a clear distinction between prediction and causation.

Key Terms

Decision tree: A recursive model that partitions observations using decision rules.

Node: A point in a tree containing a subset of observations.

Leaf: A terminal node that produces a prediction.

Classification tree: A tree used to predict a categorical outcome.

Regression tree: A tree used to predict a numerical outcome.

Gini impurity: A measure of class heterogeneity based on the sum of squared class proportions.

Entropy: An information-based measure of class uncertainty.

Information gain: Reduction in impurity produced by a candidate split.

Pruning: Removing or restricting branches to control complexity.

Bagging: Averaging models trained on bootstrap samples.

Bootstrap sample: A sample drawn with replacement from a dataset.

Out-of-bag observation: An observation omitted from a particular bootstrap sample.

Random forest: An ensemble of bootstrap-fitted trees using random feature subsets at splits.

Boosting: Sequentially combining models so later models emphasize earlier errors.

Gradient boosting: Boosting that fits new learners to negative loss gradients.

Learning rate: The shrinkage factor applied to each boosting update.

Stacking: Combining base-model predictions through a meta-learner.

Calibration: Agreement between predicted probabilities and observed frequencies.

Data leakage: Use of information unavailable at prediction time.

Concept drift: Change in the relationship between predictors and outcomes over time.

Review Questions

Short Answer Questions

1. Why can a deep decision tree have low training error but poor validation performance?
2. What is the purpose of Gini impurity in a classification tree?
3. How does random feature selection improve a random forest?
4. Distinguish bagging from boosting.
5. Why must stacking use out-of-fold predictions for training the meta-learner?

Long Answer Questions

1. Explain the construction of classification and regression trees, including their objective functions and prediction rules.
2. Compare pre-pruning and cost-complexity post-pruning, including their advantages and limitations.
3. Explain the bias–variance rationale for bagging and random forests.
4. Describe gradient boosting mathematically and explain the roles of loss function, learning rate, tree complexity, and early stopping.
5. Develop a governance framework for deploying a tree ensemble in a high-stakes business decision.

Analytical / Application Questions

1. A fraud model has high accuracy but misses most fraudulent transactions because fraud is rare. Which metrics and evaluation design would you use, and why?
2. Design a chronological validation strategy for a demand-forecasting random forest or boosting model. Explain how leakage could occur.
3. A churn model ranks customers accurately but produces poorly calibrated probabilities. Explain how this affects intervention decisions and propose a remedy.

Multiple Choice Questions with Answers

Question 1

Which impurity measure is zero when a classification node contains observations from only one class?

A. Gini impurity

B. Mean absolute error

C. Root mean squared error

D. Variance inflation factor

Correct Answer: A. Gini impurity

Question 2

A parent node has impurity 0.48. A proposed split has weighted child impurity 0.2667. What is the impurity reduction?

A. 0.2133

B. 0.7467

C. 0.2667

D. 0.48

Correct Answer: A. 0.2133

Question 3

What is the principal additional source of randomness in a random forest compared with ordinary bagging?

A. Random feature subsets at each split

B. Random response transformations

C. Random target labels

D. Random evaluation metrics

Correct Answer: A. Random feature subsets at each split

Question 4

Why does reducing correlation among trees help an ensemble?

A. It reduces the portion of prediction variance that remains after averaging

B. It guarantees that every tree is unbiased

C. It eliminates the need for validation

D. It makes all trees use the same features

Correct Answer: A. It reduces the portion of prediction variance that remains after averaging

Question 5

In gradient boosting, what does a new tree typically approximate?

A. The negative gradient of the loss with respect to the current predictions

B. The original feature covariance matrix

C. The bootstrap sampling probability

D. The final test-set error

Correct Answer: A. The negative gradient of the loss with respect to the current predictions

Question 6

Which practice is essential when training a stacking meta-learner?

A. Use out-of-fold predictions from the base learners

B. Train the meta-learner on training-set predictions from the same fitted models

C. Exclude all base-learner predictions

D. Use only the test set to fit the meta-learner

Correct Answer: A. Use out-of-fold predictions from the base learners

Question 7

Which metric is defined as TP ÷ (TP + FN)?

A. Recall

B. Precision

C. Specificity

D. Accuracy

Correct Answer: A. Recall

Question 8

Which statement about RMSE is correct?

A. It is in the same units as the response and penalizes large errors more heavily than MAE

B. It is always smaller than MAE

C. It can be calculated only for classification

D. It ignores large residuals

Correct Answer: A. It is in the same units as the response and penalizes large errors more heavily than MAE

Question 9

Why can a chronological split be preferable for a churn model?

A. It better represents deployment in which future outcomes follow past information

B. It guarantees a balanced class distribution

C. It removes the need to define the outcome window

D. It always produces higher accuracy

Correct Answer: A. It better represents deployment in which future outcomes follow past information

Question 10

What does calibration assess in a probabilistic classifier?

A. Whether predicted probabilities correspond to observed event frequencies

B. Whether all features have equal units

C. Whether the tree has exactly the optimal depth

D. Whether the training sample contains no missing values

Correct Answer: A. Whether predicted probabilities correspond to observed event frequencies