Decision Trees and Ensemble Learning

Introduction

Decision trees and ensemble methods are among the most widely used predictive-analytics techniques in business. They can model classification and regression problems, capture nonlinear relationships, handle interactions between variables, and produce useful explanations for managerial decision-making. A single tree is easy to understand but can be unstable and prone to overfitting. Ensemble learning addresses these weaknesses by combining many models.

This chapter examines how trees are constructed and how four important ensemble strategies—bagging, random forests, gradient boosting, and stacking—work. The methods are compared in terms of predictive accuracy, interpretability, computational requirements, and business suitability.

Learning Objectives

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

1. Explain the structure and operation of classification and regression trees.
2. Select and interpret splitting criteria.
3. Control tree complexity and diagnose overfitting.
4. Explain bagging, random forests, gradient boosting, and stacking.
5. Compare ensemble methods using suitable evaluation measures.
6. Construct a practical predictive-analytics workflow for a business problem.
7. Assess interpretability, computational demands, governance, and ethical risks.

1. Decision Trees as Predictive Models

A decision tree represents a sequence of decisions. Internal nodes contain tests on predictor variables, branches represent test outcomes, and terminal nodes, or leaves, contain predictions. For example, a bank may predict loan default using income, debt ratio, credit history, and employment status.

A tree partitions the predictor space into relatively homogeneous regions. In a classification tree, the prediction is usually the most common class in a leaf. In a regression tree, it is usually the mean target value of observations in that leaf.

A generic tree prediction can be written as:

Here, x is a vector of predictor values, Rᵣ is region or leaf r, cᵣ is the prediction assigned to that region, and I(·) is an indicator equal to 1 when the condition is true and 0 otherwise. The regions are mutually exclusive and collectively cover the relevant predictor space.

Trees are attractive because they:

• require little data transformation;
• can model nonlinear effects and variable interactions;
• can use numerical and categorical predictors;
• provide rule-like explanations; and
• are useful for both classification and regression.

Their disadvantages include instability, high variance, poor extrapolation in regression, and a tendency to overfit when allowed to grow without restriction.

1.1 Recursive Partitioning

Tree construction begins with all training observations in a root node. The algorithm searches possible variables and thresholds, divides the data into child nodes, and selects a split that improves node purity. The process continues recursively until a stopping rule is reached.

For a classification node containing class proportions p₁, p₂, …, p_K, two common impurity measures are the Gini impurity and entropy.

Here, t denotes a node, pₖ is the proportion of observations belonging to class k, and K is the number of classes. The convention 0 log₂ 0 = 0 is used. Both measures equal zero when a node contains only one class and are larger when classes are mixed.

For a proposed split producing child nodes L and R, weighted impurity is:

where n_L and n_R are child-node sizes, n_t is the parent-node size, and I is Gini impurity or entropy. The selected split minimizes weighted impurity, equivalently maximizing impurity reduction:

These criteria apply to classification. They are not interchangeable with regression criteria without modification.

For regression, a common objective is the residual sum of squares within leaves:

where yᵢ is the observed response and cᵣ is commonly the mean response in region Rᵣ. The mean minimizes squared error within a leaf.

1.2 Worked Example: Choosing a Classification Split

Suppose a node contains 10 customers: 6 renew a subscription and 4 do not. Its Gini impurity is:

Gini = 1 − (0.6² + 0.4²) = 0.48

A proposed split produces a left node of 5 customers, all of whom renew, and a right node of 5 customers, containing 1 renewal and 4 non-renewals. The left impurity is 0. The right impurity is:

1 − (0.2² + 0.8²) = 0.32

Weighted impurity is:

(5/10)(0) + (5/10)(0.32) = 0.16

Therefore, impurity reduction is 0.48 − 0.16 = 0.32. A candidate split with a larger reduction would be preferred, provided that it satisfies minimum-node and other constraints.

1.3 Stopping, Pruning, and Complexity

If a tree continues splitting until every leaf is pure, it may memorize the training data. Common controls include:

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

A tree can also be grown large and then pruned. Cost-complexity pruning minimizes an objective of the form:

Here, T is the tree, R(T) is its training loss, |L(T)| is the number of leaves, and α ≥ 0 controls the penalty for complexity. A larger α favors smaller trees. The parameter should be selected using validation or cross-validation rather than test-set performance.

A practical workflow is to fit candidate trees using the training data, tune complexity using cross-validation, and evaluate the final selected model once on an untouched test set.

2. Bagging: Reducing Variance Through Resampling

Bagging, or bootstrap aggregating, fits many models to bootstrap samples of the training data and combines their predictions. A bootstrap sample of size n is formed by sampling n observations with replacement from a dataset of size n. Some observations appear multiple times and others are omitted.

For regression, bagging averages predictions:

For classification, it commonly uses majority voting or averages predicted class probabilities. Here, B is the number of fitted base models. Averaging reduces variance when individual models are unstable and their errors are not perfectly correlated.

Approximately 63.2% of the distinct training observations appear in a bootstrap sample on average, because the probability that an observation is omitted approaches e⁻¹ ≈ 0.368. The omitted observations are called out-of-bag observations. They can provide an internal performance estimate, although a separate test set remains valuable for final assessment.

Bagging normally uses the same predictor set for every tree. Consequently, if a few variables dominate the splits, the trees can remain highly correlated. Random forests address this issue.

3. Random Forests

A random forest combines bagging with random feature selection. At each split, a tree considers only a randomly selected subset of predictors. This decorrelates trees, making aggregation more effective.

The main hyperparameters include:

• number of trees;
• number of candidate predictors at each split;
• maximum tree depth;
• minimum leaf size; and
• whether class weights or sampling adjustments are used.

Increasing the number of trees generally stabilizes predictions but increases training and prediction time. After a sufficient number of trees, accuracy often changes little, while memory and latency may continue to increase.

Random forests are strong general-purpose models for tabular data. They handle nonlinearities and interactions with limited preprocessing and are less sensitive than a single tree to small changes in the data. However, they are less transparent than one tree, can be computationally demanding with many trees, and may produce biased class probabilities unless probabilities are calibrated.

Variable Importance and Interpretation

Common importance measures include impurity-based importance and permutation importance. Impurity importance sums the impurity reductions associated with a variable, but it may favor continuous variables or categorical variables with many levels. Permutation importance measures the deterioration in validation performance after randomly permuting one predictor. It is usually more meaningful, but correlated predictors can make individual importance values difficult to interpret.

Partial-dependence and accumulated-local-effect plots can describe average relationships, while local explanation methods can describe an individual prediction. These tools are explanatory aids, not proofs of causality.

4. Gradient Boosting

Boosting builds models sequentially. Each new weak learner focuses on errors made by the existing ensemble. In regression with squared-error loss, this can be understood as fitting the next tree to residuals.

A simplified additive model is:

Here, Fₘ(x) is the ensemble after iteration m, hₘ(x) is the new tree, and η is the learning rate, usually between 0 and 1. A small learning rate generally requires more trees but can improve generalization when the number of trees is tuned appropriately.

For a general differentiable loss function L(y, F(x)), the next learner approximates the negative gradient of the loss with respect to current predictions:

Here, rᵢₘ is the pseudo-residual for observation i at iteration m. The formula applies when the loss is differentiable with respect to the prediction. For squared-error loss, it reduces to the ordinary residual yᵢ − Fₘ₋₁(xᵢ).

Important boosting parameters include learning rate, number of trees, maximum tree depth, subsampling fraction, and regularization. Deep trees capture complex interactions but raise overfitting risk. Early stopping monitors validation performance and stops training when additional trees no longer improve it.

Gradient boosting often achieves excellent accuracy on structured business data, but it requires more careful tuning than a random forest. Training is sequential, so it is less naturally parallelizable. Modern implementations such as gradient-boosted decision-tree libraries improve speed through optimized computation, regularization, histogram-based splitting, and handling of missing values.

5. Stacking

Stacking combines different types of models through a meta-model. For example, a business may combine logistic regression, a random forest, and gradient boosting. The first-level models generate predictions, and a second-level model learns how to combine them.

The central protection against leakage is the use of out-of-fold predictions. If a base model generates predictions for observations it was trained on, those predictions may be unrealistically optimistic. Instead, the training data are divided into folds. Each observation receives a prediction from a model that did not train on that observation. These predictions train the meta-model.

A simple regression stack is:

where ŷⱼ(x) is the prediction of base model j, βⱼ is its meta-model coefficient, and β₀ is an intercept. Classification stacking may use predicted probabilities and a logistic meta-model. The final evaluation must be performed on data excluded from all training and tuning stages.

Stacking is useful when models make complementary errors. It can improve accuracy, but it increases operational complexity, monitoring requirements, and explanation difficulty.

6. Comparing the Methods

Accuracy should not be the only criterion. A lending model may require clear reasons for adverse decisions, while a recommendation system may prioritize ranking quality and latency. A model with slightly lower accuracy may be preferable if it is more explainable, stable, fair, and easier to monitor.

For classification, common measures include accuracy, precision, recall, F1 score, log loss, and area under the ROC curve. Accuracy is:

where TP, TN, FP, and FN denote true positives, true negatives, false positives, and false negatives. Accuracy can be misleading when classes are imbalanced. Precision is TP/(TP+FP), recall is TP/(TP+FN), and the F1 score is the harmonic mean of precision and recall:

For regression, mean absolute error is:

and root mean squared error is:

MAE is expressed in the target's units and treats errors linearly. RMSE is also in the target's units but penalizes large errors more strongly. Metric selection should reflect business costs.

7. Illustrative Case: Predicting Subscription Churn

Background

A fictional telecommunications company, Northstar Mobile, wants to identify customers likely to cancel within the next 60 days. The data include tenure, monthly charge, contract type, service complaints, payment method, data usage, and customer-service contacts.

Problem

The company has limited retention capacity. Contacting every customer is expensive, but failing to contact a likely churner loses future revenue. The business therefore needs both a probability of churn and a ranked list of customers.

Analysis and Approach

The analytics team defines the target using only information available before the prediction date. It divides data chronologically: earlier months for training, a later period for validation, and the most recent period for testing. This avoids treating future information as if it were available at prediction time.

A pruned decision tree provides an interpretable baseline. A bagged tree model reduces instability. A random forest provides a robust nonlinear benchmark, while gradient boosting is tuned using learning rate, tree count, depth, and early stopping. Logistic regression is also included because its probability estimates and coefficients provide a useful contrast. A stacking model is considered only after the individual models have been validated.

The team evaluates recall among the top 10% of customers contacted, expected retention profit, calibration, and subgroup performance—not merely accuracy. If contacting a customer costs £4 and a successful retention is worth £80 in expected contribution, the decision threshold should reflect these quantities as well as the probability of successful intervention.

Solution and Governance

The selected model is gradient boosting because it provides the highest validated expected profit while maintaining acceptable calibration. However, the company retains the pruned tree as a communication tool for managers and uses permutation importance and local explanations to investigate predictions. Explanations are reviewed to ensure that protected characteristics and inappropriate proxy variables are not driving decisions.

The model is monitored monthly for data drift, calibration, recall, contact conversion, and performance across customer groups. A champion–challenger process compares the deployed model with a simpler alternative. The model is retrained only under documented conditions rather than automatically whenever performance fluctuates.

Learning Points

1. The best algorithm is determined by business loss, not a single technical score.
2. Temporal splitting is important when the prediction task concerns future behavior.
3. Probability calibration matters when scores determine intervention thresholds.
4. A complex model may require a simpler companion model for communication.
5. Fairness, privacy, and monitoring are part of model design, not post-deployment additions.

8. Implementation and Best Practices

A robust implementation should follow these principles:

• Establish a clear prediction date and prevent target leakage.
• Keep training, validation, and test data conceptually separate.
• Use pipelines so preprocessing is learned only from training folds.
• Tune hyperparameters with cross-validation appropriate to the data structure.
• Use stratification for imbalanced classification where appropriate, and time-based validation for temporal problems.
• Compare against a simple baseline.
• Calibrate probabilities when decisions depend on risk estimates.
• Select thresholds using explicit costs and benefits.
• Examine subgroup performance and error patterns.
• Record data versions, features, parameters, and model versions.
• Monitor drift, latency, missingness, calibration, and outcome performance after deployment.

Ethical and Regulatory Considerations

Trees and ensembles can reproduce historical discrimination. A variable that appears neutral may act as a proxy for a protected characteristic. Removing a protected variable does not guarantee fairness. Organisations should assess disparate error rates, legal obligations, explainability requirements, data minimisation, consent, security, and the right to human review where applicable.

Feature importance should not be interpreted as causal influence. For example, a customer-service complaint may predict churn because dissatisfaction causes both the complaint and cancellation, but the model alone does not establish that changing complaint frequency will prevent churn. Business interventions should therefore be tested through appropriate experiments or quasi-experimental designs.

9. Contemporary Developments

Current practice increasingly uses explainable boosting models, monotonic constraints, calibrated prediction systems, automated hyperparameter optimization, and model monitoring platforms. Monotonic constraints can enforce domain knowledge, such as requiring predicted risk not to decrease as debt burden increases, when such a relationship is justified. These constraints improve governance but may reduce flexibility if imposed incorrectly.

Advanced gradient-boosting systems can handle missing values, categorical variables, sparse data, and large datasets efficiently. Nevertheless, sophisticated software does not remove the need for sound target definition, leakage prevention, validation, fairness assessment, and managerial judgment.

Chapter Summary

Decision trees recursively partition data into increasingly homogeneous regions. Classification trees commonly use Gini impurity or entropy, while regression trees commonly minimize squared error within leaves. Unrestricted trees can overfit, so depth, leaf size, pruning, and validation are essential.

Bagging averages or votes across bootstrap-trained models to reduce variance. Random forests additionally randomize the predictors considered at each split, reducing correlation among trees. Gradient boosting builds trees sequentially to correct prior errors and often provides excellent accuracy, but it requires careful tuning and leakage control. Stacking combines diverse models through a meta-model and must use out-of-fold predictions.

Model choice should balance accuracy, calibration, interpretability, computational cost, latency, fairness, governance, and business value. A reliable predictive system includes appropriate data splitting, explicit decision costs, monitoring, documentation, and human oversight.

Key Terms

Decision tree: A hierarchical model that makes predictions through recursive if–then splits.

Root node: The first node containing all training observations.

Internal node: A tree node where a splitting decision is made.

Leaf: A terminal node containing the final prediction.

Gini impurity: A classification impurity measure based on squared class proportions.

Entropy: An impurity measure based on the information content of class proportions.

Impurity reduction: The improvement obtained by replacing a parent node with child nodes.

Pruning: Removing branches to reduce tree complexity and overfitting.

Bagging: Combining models trained on bootstrap samples.

Bootstrap sample: A sample drawn with replacement from the training data.

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

Random forest: An ensemble of bagged trees with random feature selection at splits.

Gradient boosting: Sequentially adding weak learners to reduce a loss function.

Learning rate: The multiplier controlling each boosting learner's contribution.

Early stopping: Ending training when validation performance stops improving.

Stacking: Combining predictions from several base models through a meta-model.

Calibration: Agreement between predicted probabilities and observed frequencies.

Data leakage: Use of information unavailable at prediction time.

Permutation importance: Performance deterioration after randomly permuting a feature.

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

Review Questions

5 Short Answer Questions

1. What is the purpose of a leaf in a decision tree?
2. How does pruning reduce overfitting?
3. What is the main difference between bagging and random forests?
4. Why is learning rate important in gradient boosting?
5. Why are out-of-fold predictions required in stacking?

5 Long Answer Questions

1. Explain how a classification tree selects a split using Gini impurity.
2. Compare a single decision tree, random forest, and gradient-boosting model.
3. Discuss why accuracy may be inappropriate for an imbalanced business problem.
4. Explain how model interpretability affects the selection of an ensemble method.
5. Describe a complete validation and monitoring process for a deployed tree ensemble.

3 Analytical / Application Questions

1. A bank must predict loan default and provide reasons for adverse decisions. Recommend a modelling strategy and justify the trade-off between performance and interpretability.
2. A retailer has a highly imbalanced churn dataset and limited retention resources. Design an evaluation framework that connects model scores to business profit.
3. A stacking model performs well in training but poorly in testing. Diagnose possible causes and propose corrective actions.

Multiple Choice Questions with Answers

Question 1

Which measure is commonly used to evaluate impurity in a classification tree?

A. Gini impurity

B. Mean absolute error only

C. R-squared only

D. Akaike information criterion only

Correct Answer: A. Gini impurity

Question 2

What is the main purpose of pruning a decision tree?

A. To increase the number of leaves

B. To reduce overfitting by controlling complexity

C. To remove the target variable

D. To guarantee perfect test accuracy

Correct Answer: B. To reduce overfitting by controlling complexity

Question 3

What additional source of randomness distinguishes a random forest from ordinary bagging?

A. Random target values

B. Random test-set selection

C. Random subsets of predictors at splits

D. Random evaluation metrics

Correct Answer: C. Random subsets of predictors at splits

Question 4

In gradient boosting, what does a new learner primarily model?

A. The original feature names

B. Errors or negative loss gradients from the current ensemble

C. Only the test observations

D. The number of classes

Correct Answer: B. Errors or negative loss gradients from the current ensemble

Question 5

Why are out-of-fold predictions important in stacking?

A. They prevent base-model training predictions from creating leakage

B. They eliminate the need for a test set

C. They guarantee that all models are linear

D. They increase the number of target variables

Correct Answer: A. They prevent base-model training predictions from creating leakage

Question 6

Which metric is especially sensitive to large regression errors?

A. RMSE

B. Median category

C. Accuracy

D. Precision

Correct Answer: A. RMSE

Question 7

A classifier has TP = 30 and FN = 10. What is its recall?

A. 25%

B. 40%

C. 75%

D. 90%

Correct Answer: C. 75%

Question 8

Which validation approach is most appropriate when predicting future customer behavior from historical monthly data?

A. Randomly mixing all months before splitting

B. Chronological or time-based splitting

C. Using only the test period for training

D. Removing the date information and skipping validation

Correct Answer: B. Chronological or time-based splitting

Question 9

What is a major limitation of impurity-based variable importance?

A. It cannot be calculated for trees

B. It may favor continuous variables or categorical variables with many levels

C. It always proves causality

D. It measures only computational cost

Correct Answer: B. It may favor continuous variables or categorical variables with many levels

Question 10

Which statement best describes stacking?

A. It uses one unpruned tree only

B. It averages bootstrap samples without a meta-model

C. It combines predictions from diverse models using a second-level model

D. It replaces validation with training accuracy

Correct Answer: C. It combines predictions from diverse models using a second-level model