Decision Trees and Ensemble Learning

Introduction

Decision trees are supervised learning models that represent a prediction as a sequence of feature-based decisions. They are valuable because their logic can often be inspected directly: a record follows a path from the root to a terminal leaf, where a prediction is produced. However, a single tree can be unstable and may overfit training data. Ensemble learning addresses this weakness by combining multiple models. Bagging, random forests, boosting, gradient boosting, and stacking are among the most important ensemble methods used in contemporary machine learning.

This chapter develops the theory and practice of these methods. It explains how trees are constructed, how split quality is measured, why ensembles improve generalisation, how hyperparameters control complexity, and how feature contributions should be interpreted responsibly.

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. Calculate entropy, Gini impurity, information gain, and variance reduction.
3. Construct a small decision tree and interpret its predictions.
4. Distinguish bagging, random forests, boosting, gradient boosting, and stacking.
5. Select hyperparameters that control variance, bias, computation, and overfitting.
6. Evaluate ensemble models using appropriate validation procedures.
7. Interpret feature importance and recognise the limitations of model explanations.
8. Apply tree ensembles in a professionally responsible and reproducible manner.

1. Decision-tree foundations

A decision tree partitions the feature space into regions. At an internal node, the model tests a condition such as x_j < t, where x_j is feature j and t is a threshold. The two resulting subsets are recursively split. A leaf assigns a class, probability, or numerical value.

Important terminology includes:

• Root: the first node, representing the complete training set.
• Internal node: a node containing a splitting rule.
• Branch: an outcome of a splitting rule.
• Leaf or terminal node: a node that produces a prediction.
• Depth: the number of edges from the root to a node.
• Impurity: the degree to which a node contains mixed classes.
• Pruning: reducing tree complexity by removing branches.

For classification, a leaf commonly predicts the majority class. If class k occurs n_k times in a leaf containing n observations, its estimated probability is:

This estimate assumes that the observations reaching the leaf are representative of future observations. For regression, the usual leaf prediction is the mean response:

Here, R is a leaf region, n_R is its number of observations, y_i is an observed response, and ŷ_R is the prediction. Under squared-error loss, the mean is the value that minimises the sum of squared residuals.

Trees can handle numerical and categorical variables, nonlinear relationships, and interactions without requiring feature scaling. Their principal weaknesses are instability, greedy optimisation, and a tendency to create overly specific regions when unrestricted.

2. Choosing a split

A split should produce child nodes that are more homogeneous than the parent. Let a node contain observations with class proportions p₁, p₂, ..., p_K. Two common classification impurity measures are entropy and Gini impurity.

Entropy

Here, S is the node data and K is the number of classes. The convention 0 log₂ 0 = 0 is used. Entropy is zero when all observations belong to one class and is largest when classes are equally represented.

For a proposed split producing child nodes S₁, ..., S_m, the weighted child entropy is:

Information gain is:

The preferred split maximises information gain. Entropy is dimensionless because it is based on a logarithm of probabilities.

Gini impurity

Gini impurity can also be interpreted as the probability of incorrectly labelling an observation if its class is assigned randomly according to the node's class distribution. For two classes, its maximum is 0.5; for K equally likely classes, its maximum is 1 − 1/K. Many implementations use Gini because it is computationally simple and usually produces results similar to entropy.

Worked classification example

Suppose a parent node contains 10 observations: 6 positive and 4 negative. A candidate split produces child A with 4 positive and 1 negative, and child B with 2 positive and 3 negative.

The parent entropy is approximately:

H_parent = −0.6 log₂0.6 − 0.4 log₂0.4 ≈ 0.971

Child A has entropy approximately 0.722, while child B has entropy approximately 0.971. Therefore:

H_split = (5/10)(0.722) + (5/10)(0.971) ≈ 0.847

Thus, information gain is approximately:

IG ≈ 0.971 − 0.847 = 0.124

The calculation compares this value with the gains of other candidate splits. The best split at the node is the one with the greatest gain, not necessarily the one that produces equal-sized children.

Regression splits

For regression, a common objective is to minimise the weighted within-node sum of squared errors:

A split is preferred when it produces a large reduction in error:

The units of SSE are the squared units of the response variable. Some software reports mean squared error instead; the comparison must then use a consistent weighting convention.

3. Tree construction and complexity control

Most practical tree algorithms use greedy recursive partitioning. At each node, the algorithm evaluates candidate features and thresholds, chooses the best available split according to an impurity reduction criterion, and repeats the process until a stopping rule is reached. This procedure does not generally find the globally optimal tree, because exhaustive search over all possible trees is computationally difficult.

Important stopping and regularisation parameters include:

A cost-complexity objective can be written as:

Here, T is a tree, R(T) is its empirical loss, |T| is a measure such as the number of leaves, and α ≥ 0 controls the complexity penalty. The formula is applicable when the loss and complexity term are placed on compatible scales. A larger α favours simpler trees.

Pruning can be pre-pruning, which stops growth early, or post-pruning, which first grows a larger tree and then removes branches that do not justify their complexity. Validation data or cross-validation should determine the regularisation level.

4. Bagging and random forests

Bagging

Bagging, or bootstrap aggregating, trains separate models on bootstrap samples of the training data. A bootstrap sample of size n is formed by sampling n observations with replacement. Approximately 63.2% of the distinct training observations appear in a typical bootstrap sample, while the remaining observations can serve as out-of-bag observations for that model.

For regression, bagging averages predictions:

For classification, it commonly uses majority voting or averaged class probabilities. If individual errors are not perfectly correlated, averaging reduces variance. In the idealised case of B independent predictors with variance σ², the variance of their average is σ²/B. Real trees are correlated, so the reduction is smaller; reducing correlation is therefore important.

Random forests

A random forest combines bagging with random feature selection. At each split, only a randomly selected subset of features is considered. This prevents strong predictors from appearing in every tree and encourages diversity among trees.

A random forest generally follows this procedure:

1. Draw a bootstrap sample.
2. Grow a decision tree on that sample.
3. At each node, randomly select a subset of features.
4. Choose the best split among that subset.
5. Repeat for many trees and aggregate predictions.

The number of candidate features per split, tree depth, minimum leaf size, number of trees, class weighting, and sampling strategy are important design choices. More trees usually stabilise performance but increase computation; they do not necessarily remove bias caused by severely restricted trees.

Out-of-bag evaluation estimates generalisation performance by predicting each training observation only with trees for which that observation was not sampled. It is useful, but it should not replace an independent test set when final performance claims are important.

5. Boosting and gradient boosting

Bagging builds models independently and reduces variance. Boosting builds models sequentially, with later models concentrating on errors made by earlier models. This often reduces bias, but it can overfit noisy data if complexity is not controlled.

AdaBoost intuition

In binary classification, AdaBoost assigns greater weight to observations misclassified by the current weak learner. The next learner focuses more on these difficult cases. The final prediction is a weighted vote. A common learner weight is:

Here, ε_t is the weighted error of learner t, and the formula assumes 0 < ε_t < 0.5. Learners with lower error receive greater weight. AdaBoost can be sensitive to outliers because repeatedly misclassified observations receive increasing emphasis.

Gradient boosting

Gradient boosting constructs an additive model:

Here, F₀ is the initial model, h_m is the tree added at iteration m, M is the number of boosting iterations, and η is the learning rate. The learning rate is dimensionless and controls the contribution of each tree.

For a differentiable loss L(y, F(x)), the next tree is trained to approximate the negative gradient of the loss with respect to current predictions:

The residual-like quantity r_im is called a pseudo-residual. For squared-error loss, L = (y − F)²/2, the negative gradient equals y_i − F_m−1(x_i). Thus, ordinary residual fitting is a special case of gradient boosting.

The principal gradient-boosting hyperparameters are:

• Number of estimators: number of sequential trees.
• Learning rate: contribution of each tree.
• Tree depth or number of leaves: complexity of each weak learner.
• Subsample fraction: fraction of observations used per iteration; values below one introduce stochasticity.
• Regularisation: penalties, shrinkage, minimum leaf sizes, and early stopping.

A smaller learning rate often requires more trees. The combination can improve generalisation, but it increases training time. Early stopping uses validation performance to halt training when additional trees no longer improve the selected metric.

6. Stacking and heterogeneous ensembles

Stacking combines different model families through a meta-model. Base learners may include a regularised linear model, a tree ensemble, and a neural network. Their predictions become inputs to a second-level learner.

A correct stacking procedure must avoid leakage. The meta-model should be trained on out-of-fold predictions: each base learner predicts observations that were not used to train that particular base learner. After generating these predictions, the base learners are refitted on all training data and used to predict new cases. The meta-model then combines the predictions.

A simple regression stack can be expressed as:

Here, f₁, ..., f_q are base learners and g is the meta-learner. Stacking is useful when models make complementary errors. If all base models are similar and highly correlated, stacking may add complexity without meaningful benefit.

7. Comparing ensemble strategies

No method is universally superior. Model selection should consider the data-generating process, sample size, class imbalance, latency, memory, interpretability, and the cost of errors.

8. Evaluation and overfitting control

A reliable workflow separates model development from final evaluation. A typical arrangement is training data for fitting, validation data or cross-validation for hyperparameter selection, and a test set used once for final assessment. When data are temporal, validation should preserve time order. When observations belong to people, firms, patients, or devices, grouped splitting may be necessary to prevent the same entity appearing in both training and validation sets.

For classification, accuracy is:

Precision and recall are:

Here, TP, TN, FP, and FN denote true positives, true negatives, false positives, and false negatives. Accuracy can be misleading under class imbalance. Precision is relevant when false positives are costly; recall is relevant when missing positive cases is costly. Threshold selection should reflect the application’s consequences.

For regression, mean absolute error and root mean squared error are common:

MAE has the same units as the response and weights errors linearly. RMSE also has the response units but gives greater influence to large errors. Metric selection must therefore be tied to operational loss.

Common overfitting controls include limiting depth, increasing minimum leaf size, reducing learning rate, applying early stopping, subsampling observations or features, using cross-validation, and monitoring the gap between training and validation performance. Data leakage is often more damaging than an imperfect algorithm. Preprocessing, feature selection, imputation, and target encoding must be fitted within each training fold.

9. Interpreting feature contributions

Impurity-based importance

For a feature, impurity importance sums its weighted impurity reductions over all nodes where it is used. It is fast but can favour continuous variables or categorical variables with many possible categories. In correlated data, importance may be divided among substitute features or assigned disproportionately to one of them.

Permutation importance

Permutation importance measures the performance decrease after randomly shuffling one feature in a validation set. If the original score is S and the permuted score is S_perm, a decrease for a higher-is-better metric is:

The procedure should be repeated across several random permutations and reported with uncertainty. Correlated predictors can make permutation importance appear small because other variables preserve the information.

Partial dependence and local explanations

Partial dependence estimates the average model response as a feature varies while averaging over other observations. It is most reliable when the displayed feature values are well represented in the data. Extrapolation into unrealistic combinations of correlated features can mislead.

Local additive explanations, such as SHAP-style approaches, allocate a prediction among features relative to a baseline. Their interpretation depends on the background distribution, treatment of feature dependence, and whether the explanation is causal or merely associational. A feature contribution does not establish that changing the feature will change the outcome.

Interpretation should combine global diagnostics, local examples, domain knowledge, and subgroup analysis. Explanations are not substitutes for fairness testing or causal research.

10. Applied case: illustrative credit-risk screening

Background

Consider an illustrative financial institution that wants to estimate whether a small-business loan applicant will become seriously delinquent within 12 months. Available variables include annual revenue, debt-to-income ratio, repayment history, business age, sector, and recent cash-flow volatility.

Problem

The institution needs predictive accuracy, calibrated risk probabilities, an audit trail, and evidence that the system does not unfairly disadvantage protected or vulnerable groups. A single deep tree is easy to display but produces unstable boundaries and may memorise unusual applicants.

Analysis

The data are divided by application date to imitate future deployment. Missing-value treatment and categorical encoding are fitted only on the training period. A shallow tree establishes a transparent baseline. A random forest and a gradient-boosted tree model are then tuned using time-aware validation. Evaluation includes recall at an operational review threshold, precision, calibration, and subgroup error rates rather than accuracy alone.

Approach and solution

The random forest provides a robust benchmark and out-of-bag diagnostics. Gradient boosting produces stronger validation discrimination, but its depth, learning rate, number of estimators, and early-stopping rule are selected using validation data. Probability calibration is assessed on data not used to fit the calibration model. Permutation importance and local explanations are reviewed by risk specialists, with particular attention to proxies for protected characteristics and variables that would not be available at decision time.

The institution adopts a two-stage process: the model identifies applications requiring additional review, while a human decision-maker considers documented evidence and an appeals process. Model predictions, input versions, thresholds, and explanations are logged.

Outcome

The illustrative outcome is not a claim about a real institution: the boosted model improves recall at a fixed review capacity, but it also requires stronger governance and monitoring. Drift monitoring is established for feature distributions, missingness, calibration, subgroup performance, and realised delinquency. The model is periodically revalidated rather than assumed to remain accurate indefinitely.

Learning points

1. The best validation score is not the only deployment criterion.
2. Time-aware and leakage-resistant evaluation is essential.
3. Probability quality and decision thresholds matter as much as ranking.
4. Feature importance does not prove causation or fairness.
5. Human oversight must include documented authority to challenge the model.

11. Professional, ethical, and contemporary considerations

Tree ensembles are widely used in fraud detection, medical risk stratification, predictive maintenance, marketing, supply-chain forecasting, and energy-demand modelling. Their flexibility creates governance responsibilities. Organisations should document training data provenance, target definitions, excluded variables, preprocessing, hyperparameters, validation design, intended use, limitations, and monitoring procedures.

High-stakes applications require attention to privacy, consent, data minimisation, security, fairness, contestability, and applicable data-protection and sector regulations. Removing a protected attribute does not guarantee fairness because other variables may act as proxies. Fairness metrics can conflict, especially when group base rates differ; the chosen criterion should therefore be justified in relation to legal and institutional goals.

Contemporary developments include histogram-based gradient boosting, categorical-aware boosting, distributed training, monotonic constraints, conformal prediction, and automated hyperparameter optimisation. Monotonic constraints can encode domain knowledge, such as requiring predicted risk not to decrease as debt burden increases, but constraints must be justified and validated. Conformal methods can provide prediction sets or intervals under stated exchangeability assumptions; they quantify uncertainty rather than guaranteeing correctness under distribution shift.

Best practice is to begin with a transparent baseline, use a reproducible pipeline, tune through nested or properly separated validation, evaluate operationally relevant metrics, inspect calibration and subgroup behaviour, and monitor the deployed system. Simpler models should be preferred when their performance is adequate and their accountability advantages are substantial.

Chapter Summary

Decision trees recursively partition feature space using impurity reduction or error reduction. Entropy, information gain, Gini impurity, and regression SSE provide formal criteria for selecting splits. Unrestricted trees can overfit, so depth, leaf size, pruning, and complexity penalties are essential.

Bagging reduces variance by averaging models trained on bootstrap samples. Random forests additionally randomise candidate features, reducing correlation between trees. Boosting constructs models sequentially: AdaBoost reweights difficult observations, while gradient boosting fits successive learners to loss gradients. Stacking uses out-of-fold predictions and a meta-model to combine heterogeneous learners.

Reliable application requires leakage-resistant validation, appropriate metrics, calibration, threshold selection, and explicit consideration of operational costs. Feature importance, permutation methods, partial dependence, and local explanations can support interpretation but do not establish causation or fairness. In professional settings, accuracy must be balanced with transparency, privacy, accountability, monitoring, and human oversight.

Key Terms

Decision tree: A recursive model that partitions data through feature-based rules.

Node: A point in a tree at which data are split or a prediction is made.

Leaf: A terminal node containing a final prediction.

Entropy: A logarithmic measure of class uncertainty.

Gini impurity: A measure of class mixture based on squared class probabilities.

Information gain: Reduction in weighted entropy produced by a split.

Pruning: Removal of branches to reduce tree complexity.

Bootstrap sample: A sample formed by sampling observations with replacement.

Bagging: Aggregation of models trained on bootstrap samples.

Random forest: A bagged tree ensemble with random feature selection at splits.

Out-of-bag estimate: Prediction or performance estimate using trees that excluded an observation during bootstrap sampling.

Boosting: Sequential construction of learners that focus on residual errors or difficult cases.

AdaBoost: A boosting method that reweights misclassified observations.

Gradient boosting: Additive modelling that fits learners to negative loss gradients.

Learning rate: Shrinkage parameter controlling each boosting learner’s contribution.

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

Permutation importance: Performance change caused by randomly permuting a feature.

Calibration: Agreement between predicted probabilities and observed frequencies.

Data leakage: Unintended use of information unavailable at prediction time.

Feature contribution: The estimated influence of a feature on a model output, relative to a defined baseline.

Review Questions

Short Answer Questions

1. What is the purpose of a leaf in a decision tree?
2. Distinguish entropy from Gini impurity.
3. Why does bagging generally reduce variance?
4. What is the role of the learning rate in gradient boosting?
5. Why must stacking use out-of-fold predictions?

Long Answer Questions

1. Explain how a classification tree selects a split using information gain, including the role of weighted child impurity.
2. Compare bagging, random forests, and gradient boosting in terms of model construction, bias, variance, and overfitting risk.
3. Explain how pre-pruning, post-pruning, learning-rate reduction, and early stopping control model complexity.
4. Discuss the strengths and limitations of impurity importance, permutation importance, and local explanation methods.
5. Design a validation and governance workflow for a tree ensemble used in a high-stakes application.

Analytical / Application Questions

1. A binary node contains 8 positive and 2 negative observations. Calculate its Gini impurity and explain what the value indicates.
2. Design an experiment to determine whether a random forest or gradient-boosted model is more suitable for an imbalanced fraud-detection problem. Specify splitting, metrics, threshold selection, and leakage controls.
3. A boosted model has excellent training performance but declining validation performance after 300 trees. Analyse possible causes and propose a technically justified response.

Multiple Choice Questions with Answers

Question 1

Which criterion measures the uncertainty of class membership using logarithms?

A. Entropy

B. Mean absolute error

C. Cost-complexity penalty

D. Permutation importance

Correct Answer: A. Entropy

Question 2

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

A. Random target labels

B. Random feature subsets at splits

C. Random validation metrics

D. Random loss functions

Correct Answer: B. Random feature subsets at splits

Question 3

For squared-error regression, the prediction that minimises the sum of squared errors within a leaf is the:

A. Median

B. Mode

C. Mean

D. Maximum

Correct Answer: C. Mean

Question 4

Which method trains models sequentially so that later models address earlier errors?

A. Bagging

B. Boosting

C. One-hot encoding

D. Principal component analysis

Correct Answer: B. Boosting

Question 5

In gradient boosting, the next learner commonly approximates the:

A. Positive feature values

B. Negative gradient of the loss

C. Largest class label

D. Bootstrap sample size

Correct Answer: B. Negative gradient of the loss

Question 6

Why are out-of-fold predictions required when training a stacking meta-model?

A. To ensure the meta-model sees predictions from models that did not train on those observations

B. To increase the number of target labels

C. To remove all feature correlations

D. To guarantee causal interpretation

Correct Answer: A. To ensure the meta-model sees predictions from models that did not train on those observations

Question 7

If TP = 40 and FN = 10, what is recall?

A. 0.40

B. 0.50

C. 0.80

D. 0.90

Correct Answer: C. 0.80

Question 8

Which practice most directly prevents preprocessing leakage during cross-validation?

A. Fit preprocessing once on the complete dataset before splitting

B. Fit preprocessing separately within each training fold

C. Use the test labels during feature selection

D. Increase tree depth

Correct Answer: B. Fit preprocessing separately within each training fold

Question 9

A larger cost-complexity parameter generally encourages a tree with:

A. More leaves

B. Greater depth

C. Fewer leaves

D. More training noise

Correct Answer: C. Fewer leaves

Question 10

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

A. It cannot be computed for tree models

B. It may favour continuous variables or high-cardinality categorical variables

C. It always measures causal effects

D. It requires the response variable to be numerical

Correct Answer: B. It may favour continuous variables or high-cardinality categorical variables