7. Decision Trees and Ensemble Learning

Introduction and Context

Decision trees are among the most intuitive predictive models in machine learning. They represent a sequence of questions that divides observations into increasingly homogeneous groups and ends in a prediction. A tree can express rules such as: “If income is high and credit history is strong, approve the application.” This transparency makes trees valuable in domains where explanations matter, including banking, healthcare, insurance, public administration, and marketing.

A single tree, however, is not always a reliable predictor. A deep tree may memorize training data, while a shallow tree may be too simple to capture important relationships. Ensemble learning addresses this weakness by combining multiple models. Bagging reduces variance by fitting models independently on different samples. Random forests add random feature selection to decorrelate trees. Boosting builds models sequentially, concentrating later models on earlier errors. Gradient-boosted machines extend this idea through optimization of a loss function.

This chapter examines the logic, construction, tuning, interpretation, and practical use of these methods. It also considers the central trade-off between predictive performance, interpretability, computational cost, robustness, and business value.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Explain how decision trees partition data and produce predictions.

2. Distinguish classification trees from regression trees.

3. Calculate and interpret impurity measures such as entropy, information gain, and the Gini index.

4. Identify causes of overfitting and apply pruning and complexity controls.

5. Explain bagging, random forests, boosting, and gradient-boosted machines.

6. Select suitable hyperparameters and evaluate ensemble models appropriately.

7. Compare tree-based methods in terms of accuracy, interpretability, scalability, and robustness.

8. Apply tree and ensemble methods to professional and organizational problems.

9. Recognize risks involving bias, leakage, instability, fairness, and explainability.

How a Decision Tree Converts Data into Rules

A decision tree consists of internal decision nodes, branches, and terminal nodes or leaves. At each internal node, the algorithm selects a feature and a split. For a numerical feature, a split may be of the form income less than or equal to 50,000. For a categorical feature, the split may separate one or more categories from the rest. The process continues recursively until a stopping condition is reached.

For classification, a leaf usually predicts the majority class among observations reaching that leaf. It may also provide class probabilities, calculated from the proportions of classes in the leaf. For regression, a leaf commonly predicts the mean response of its observations, although alternative objectives can be used.

The tree is grown by selecting splits that improve node purity. A pure classification node contains observations from only one class. A pure regression node contains responses with little variation. The improvement from a proposed split is generally measured as the parent impurity minus the weighted impurity of its child nodes.

Impurity Measures for Classification

Let a node contain observations from classes with proportions p1, p2, ..., pk. The Gini impurity is:

Gini = 1 − Σ pk²

It is zero when the node is completely pure. For two classes, it reaches its maximum when the classes are equally represented. Gini impurity is computationally efficient and is commonly used in tree algorithms.

Entropy is defined as:

Entropy = −Σ pk log2(pk)

Entropy also equals zero for a pure node and increases as class uncertainty increases. Information gain is the reduction in entropy resulting from a split:

Information Gain = Entropy(parent) − weighted entropy(children)

Gini impurity and entropy often produce similar trees, although they can rank candidate splits differently. The choice between them is usually less important than appropriate pruning, validation, and data preparation.

Splitting in Regression Trees

Regression trees commonly use reduction in squared error. If a node contains responses yi and the leaf prediction is their mean, the within-node sum of squares is:

SSE = Σ(yi − ȳ)²

A useful split substantially reduces the combined SSE of its child nodes. Regression trees therefore create regions in which the response is approximately constant. Their predictions are piecewise constant and may not extrapolate well beyond the range of the training data.

Controlling Tree Complexity

A tree that is allowed to grow until every leaf is pure may represent random noise as if it were a real pattern. This is overfitting: training performance is excellent, but performance on unseen data deteriorates. A very small tree may underfit by failing to represent meaningful interactions.

Complexity can be controlled before or after growth. Pre-pruning limits the tree during construction using parameters such as maximum depth, minimum samples required for a split, minimum samples per leaf, or maximum number of leaves. Post-pruning first grows a relatively large tree and then removes branches that provide insufficient validation benefit. Cost-complexity pruning evaluates a criterion such as:

Rα(T) = R(T) + α|T|

where R(T) measures prediction error, |T| is the number of terminal nodes, and α penalizes model complexity. A larger α produces a smaller tree.

Hyperparameters should be selected through cross-validation rather than by examining performance on the test set. A practical workflow separates data into training, validation or cross-validation, and final test components. The test set should be used only after model selection is complete.

From One Tree to Many: Ensemble Learning

An ensemble combines several predictive models to obtain a stronger overall predictor. The benefit depends on two conditions: the individual models should be reasonably accurate, and their errors should not be perfectly correlated. If all models make exactly the same errors, averaging them adds little value.

Bagging

Bagging, or bootstrap aggregating, creates several bootstrap samples by sampling training observations with replacement. A separate tree is trained on each sample. For classification, predictions are combined by majority vote; for regression, they are averaged.

Bagging reduces variance because an unstable estimator, such as a deep decision tree, is averaged across many samples. Some observations are omitted from each bootstrap sample. These out-of-bag observations can be used to estimate prediction error without creating a separate validation set, although cross-validation may still be preferable for extensive tuning.

Bagging does not necessarily reduce bias. If the underlying trees are systematically too simple or if important variables are absent, averaging will not correct the problem.

Random Forests

A random forest is a bagged collection of decision trees with an additional source of randomness. At each split, the tree considers only a randomly selected subset of features rather than all available features. This reduces correlation among trees. The final prediction is obtained by voting or averaging.

Important random forest parameters include:

• Number of trees: More trees generally stabilize performance, but increase computation until the error converges.
• Number of candidate features per split: Smaller values decorrelate trees but may weaken individual trees.
• Maximum depth and minimum leaf size: These regulate the complexity of each tree.
• Bootstrap sampling: This determines how training cases are selected.

Random forests usually require little feature scaling and can capture nonlinear effects and interactions. They are effective for mixed types of structured data, although categorical variables often need appropriate encoding depending on the implementation. Feature importance may be estimated using impurity reduction or permutation importance. Impurity-based importance can be biased toward variables with many possible split points; permutation importance is often more informative but can also be distorted by correlated predictors.

Boosting

Boosting builds a sequence of weak or moderate learners. Each new learner is trained to improve the current ensemble. In classification, later learners may focus on observations that previous learners classified incorrectly. In regression, they may focus on residual errors.

The learning rate controls the contribution of each new learner. A small learning rate usually requires more trees but can improve generalization. The number of boosting iterations and the learning rate must be considered together. Deep base trees produce complex interactions and can overfit; shallow trees provide gradual additive improvements.

AdaBoost is an early boosting algorithm that increases the weights of misclassified observations. Although influential, it may be sensitive to noisy labels and extreme observations because those cases receive increasing attention.

Gradient-Boosted Machines

Gradient boosting frames ensemble construction as numerical optimization. Suppose the model at step m−1 is Fm−1(x). A new tree hm(x) is fitted to the negative gradient of the loss function with respect to current predictions. The model is updated as:

Fm(x) = Fm−1(x) + ηhm(x)

where η is the learning rate. For squared-error regression, the negative gradient is closely related to the residual. Other loss functions support classification, robust regression, ranking, and probability estimation.

Gradient-boosted machines are powerful because they can model nonlinearities, interactions, and complex decision boundaries. Modern implementations such as XGBoost, LightGBM, and CatBoost improve speed, regularization, handling of missing values, or categorical-variable support. Their performance depends strongly on tuning and on preventing leakage during preprocessing and validation.

Common controls include the number of boosting rounds, learning rate, maximum tree depth, minimum child weight or leaf size, row subsampling, feature subsampling, and regularization penalties. Early stopping monitors validation performance and stops training when additional iterations no longer improve the objective.

A Practical Modelling Workflow

A defensible tree-based modelling project begins with a precise target definition and an understanding of how predictions will be used. The analyst should establish the prediction time, available information, decision costs, and acceptable error types before fitting a model.

Data should then be divided in a way that reflects deployment. Random splitting may be inappropriate for time-dependent data, repeated customers, households, patients, or transactions. Grouped or temporal validation may be necessary. Leakage occurs when a predictor contains information that would not be available at prediction time, including post-outcome variables, target-derived aggregates, or preprocessing performed using the full dataset.

A simple pruned tree provides a valuable baseline because it is easy to inspect. Bagging and random forests can then be compared with boosting methods. Evaluation should use metrics aligned with the task. Classification may require accuracy, balanced accuracy, precision, recall, F1 score, ROC-AUC, PR-AUC, log loss, or calibration. Regression may use MAE, RMSE, R-squared, or a cost-specific loss. When classes are imbalanced, accuracy alone can be seriously misleading.

Hyperparameter search may use grid search, randomized search, or Bayesian optimization. The final model should be evaluated on untouched data and compared with a business baseline. A model that improves AUC but does not improve decisions, profit, service quality, or risk control may have limited practical value.

Interpretation and Model Comparison

A single shallow tree offers global rule-based interpretability. A forest or boosted model is less directly readable, but interpretation remains possible through feature importance, partial dependence, individual conditional expectation, and local explanation methods such as SHAP values.

These tools must be interpreted carefully. A feature can appear important because it is correlated with a causal variable, because it acts as a proxy for a protected characteristic, or because of data leakage. A partial-dependence plot describes average model behaviour and may be misleading when predictors are strongly correlated. Local explanations explain a model output, not necessarily the true causal reason for an outcome.

The choice among models is therefore multidimensional:

• Interpretability: A small tree is easiest to communicate; ensembles require explanation tools and governance.
• Predictive accuracy: Boosting often performs strongly on structured tabular data, though results are data-dependent.
• Robustness: Bagging and random forests are generally less sensitive to small data changes than a single tree. Boosting may be sensitive to noise and tuning.
• Scalability: Efficient boosting libraries can handle large datasets, but computational requirements vary with rows, features, trees, and depth.
• Maintenance: A simple model may be easier to monitor, retrain, audit, and implement.
• Business value: The appropriate model maximizes useful decisions under operational, legal, ethical, and financial constraints.

Illustrative Case Study: Predicting Small-Business Loan Default

Background

A fictional regional lender, Meridian Finance, wants to improve early screening of small-business loan applications. The organization has historical application records, repayment outcomes, business characteristics, credit history, requested amount, and banking behaviour. The objective is to identify applications with elevated default risk while preserving access to credit for viable firms.

Situation and Problem

The existing scorecard is a manually specified logistic model. It is stable and explainable but may not capture interactions, such as the combined effect of short business age and high requested debt. The lender asks an analytics team to determine whether tree-based models can improve ranking and decision quality.

Analysis

The team first defines the prediction point as the date of application. Variables created after approval, including later missed payments and collections activity, are excluded. Because default rates vary over time, the team uses earlier applications for training and a later period for testing. This prevents information from the future entering model development.

A shallow classification tree is fitted as an interpretable baseline. It identifies a few broad risk segments but has lower discrimination than the existing scorecard. A bagged tree model improves stability. A random forest further improves ranking by considering diverse subsets of financial and business variables. A gradient-boosted model achieves the strongest validation performance, particularly in identifying high-risk applications, but its results vary when depth is increased excessively.

The team uses class-weighted learning and evaluates recall, precision, PR-AUC, calibration, and expected financial loss rather than accuracy alone. Thresholds are selected according to the lender’s capacity for manual review. SHAP-based explanations are used to provide case-level reasons, while a separate fairness review examines whether error rates differ across legally protected or potentially vulnerable groups.

Approach and Solution

The lender adopts a constrained gradient-boosted model for ranking applications, together with a transparent policy layer. Applications in a low-risk band receive streamlined processing; high-risk cases are declined or subjected to additional review; intermediate cases are manually assessed. The model is retrained periodically, and monitoring tracks feature drift, approval rates, calibration, subgroup performance, and realized defaults.

Outcome

The illustrative deployment improves prioritization of manual reviews and reduces unnecessary review of clearly low-risk cases. The lender does not rely on the model as an unquestionable automated authority. Instead, it combines model output with documented policies, human review, appeal mechanisms, and ongoing monitoring.

Learning Points

The case demonstrates that the most accurate model is not automatically the best organizational choice. Time-aware validation, leakage prevention, cost-sensitive metrics, explainability, fairness testing, and operational integration are essential. It also shows why a model’s probability estimates and decision thresholds must be evaluated separately.

Challenges, Risks, and Common Mistakes

Tree algorithms can be unstable: small changes in data may produce different branches. Ensembles reduce some instability but do not eliminate it. High-cardinality categorical variables, missing-data mechanisms, noisy labels, and duplicated records can distort results.

A frequent mistake is to tune many hyperparameters against the test set. This converts the test set into part of the training process and creates optimistic estimates. Another is to interpret feature importance as causation. Analysts may also use accuracy for severely imbalanced outcomes, ignore calibration, or assume that random train-test splitting is always valid.

Boosting may overfit when trees are too deep, the learning rate is too large, iterations are excessive, or the data contain substantial noise. Random forests can be computationally expensive and may produce poor probability calibration without calibration procedures. Extrapolation is weak in ordinary regression trees and tree ensembles: predictions generally remain within learned response regions.

Missing values require explicit consideration. Some implementations learn default split directions, whereas others require imputation. Imputation must be fitted within each training fold to avoid leakage. Feature engineering and encoding must follow the same rule.

Ethical, Governance, and Professional Considerations

A predictive model can reproduce historical discrimination even when protected attributes are removed. Proxy variables, such as geographic or behavioural features, may encode sensitive information. Fairness should therefore be assessed in relation to the decision context, legal requirements, and affected groups. There is no universally optimal fairness metric; improving one measure may worsen another when base rates differ.

Organizations should document the target definition, data sources, excluded variables, validation design, performance by subgroup, intended use, limitations, and model version. Access controls and privacy safeguards are necessary when training data contain personal or confidential information. Automated decisions should provide appropriate notice, review, and contestability where regulation or professional standards require them.

Model governance also includes monitoring for drift. A model can deteriorate when customer behaviour, economic conditions, policies, or data collection processes change. Monitoring should cover data quality, missingness, prediction distributions, calibration, discrimination, subgroup outcomes, and business results.

Current Developments and Best Practice

Recent developments include highly optimized gradient-boosting libraries, native treatment of categorical features, monotonic constraints, quantile and distributional objectives, and integration with automated machine-learning systems. Monotonic constraints can enforce domain expectations, such as ensuring that predicted risk does not decrease when a debt ratio increases, subject to the model design.

Best practice is to:

1. Begin with a transparent baseline and a clearly defined decision problem.

2. Use validation that reflects deployment, including time or group structure where necessary.

3. Tune depth, learning rate, number of trees, sampling, and regularization jointly.

4. Use early stopping and nested or carefully separated validation when searching extensively.

5. Evaluate discrimination, calibration, subgroup performance, and business cost.

6. Investigate leakage, duplicates, missingness, and feature availability at prediction time.

7. Use interpretation methods as aids to investigation, not substitutes for causal reasoning.

8. Document assumptions, model versions, thresholds, limitations, and monitoring plans.

9. Prefer the simplest model that meets the required performance and governance standard.

Chapter Summary

Decision trees recursively partition observations into increasingly homogeneous regions and produce class or numerical predictions at terminal leaves. Gini impurity, entropy, information gain, and error reduction guide split selection. Tree depth, leaf size, pruning, and regularization control the balance between underfitting and overfitting.

Bagging averages trees trained on bootstrap samples and mainly reduces variance. Random forests add random feature selection, reducing correlation among trees. Boosting constructs models sequentially, while gradient boosting fits new learners to loss-function gradients. Learning rate, tree depth, number of iterations, subsampling, and early stopping are central controls.

Tree ensembles are powerful for nonlinear structured-data problems, but their value depends on appropriate validation, leakage prevention, metric selection, calibration, interpretability, fairness, governance, and operational fit. Predictive performance must be considered alongside robustness, scalability, maintainability, and business consequences.

Key Terms

Decision tree: A recursive model that partitions data through decision rules.

Node: A point in a tree where a split is made or a prediction is produced.

Leaf: A terminal tree region containing the final prediction.

Classification tree: A tree used to predict categorical outcomes.

Regression tree: A tree used to predict numerical outcomes.

Gini impurity: A measure of class mixture based on the probability of incorrect classification.

Entropy: A measure of uncertainty in a class distribution.

Information gain: The reduction in entropy produced by a split.

Pruning: Removing branches to reduce unnecessary model complexity.

Overfitting: Learning noise or sample-specific patterns that do not generalize.

Bagging: Combining models trained independently on bootstrap samples.

Bootstrap sample: A sample created by drawing observations with replacement.

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

Random forest: An ensemble of bagged trees using random feature subsets at splits.

Boosting: Sequentially combining learners so later learners improve earlier errors.

Gradient boosting: Boosting that fits new learners to the negative gradient of a loss function.

Learning rate: The factor controlling each new learner’s contribution.

Early stopping: Ending iterative training when validation performance ceases to improve.

Feature importance: An estimate of how much a predictor contributes to model behaviour.

Data leakage: Use of information during training that would not be available at prediction time.

Review Questions

Short Answer Questions

1. What is the purpose of a terminal leaf in a decision tree?

2. How does Gini impurity differ conceptually from entropy?

3. Why does bagging reduce variance?

4. What additional randomness distinguishes a random forest from ordinary bagging?

5. What is the role of the learning rate in gradient boosting?

Long Answer Questions

1. Explain how a classification tree selects a split using impurity reduction, with a suitable numerical illustration.

2. Discuss pre-pruning and post-pruning as methods of controlling decision-tree complexity.

3. Compare bagging, random forests, AdaBoost, and gradient-boosted machines.

4. Explain how hyperparameter tuning and validation should be designed for a time-dependent prediction problem.

5. Discuss why predictive accuracy alone is insufficient when selecting a model for credit-risk decisions.

Analytical / Application Questions

1. A highly accurate forest performs poorly when deployed because its predictors include information recorded after the outcome. Diagnose the problem and propose a corrected validation and feature-design process.

2. A company must choose between a shallow tree with slightly lower AUC and a gradient-boosted model with higher AUC but weaker interpretability. Develop a decision framework using risk, cost, governance, and operational factors.

3. A fraud dataset has 1 percent fraud cases and a classifier achieves 99 percent accuracy by predicting no fraud. Identify appropriate evaluation metrics and explain how threshold selection should be linked to business costs.

22. Multiple Choice Questions with Answers

Question 1

Which change most directly reduces the variance of a fully grown decision tree?

A. Using a single deeper tree

B. Averaging predictions from trees trained on bootstrap samples

C. Removing all validation data

D. Increasing the learning rate

Correct Answer: B. Averaging predictions from trees trained on bootstrap samples

Question 2

A node contains two classes in equal proportions. Which statement is correct?

A. Its Gini impurity is zero

B. Its entropy is zero

C. It has greater uncertainty than a pure node

D. It must be a regression node

Correct Answer: C. It has greater uncertainty than a pure node

Question 3

What distinguishes a random forest from ordinary bagging of decision trees?

A. Random forests use no trees

B. Random forests select a random subset of features at each split

C. Random forests always use shallow stumps

D. Random forests do not use sampling

Correct Answer: B. Random forests select a random subset of features at each split

Question 4

In gradient boosting, the next tree is generally trained to:

A. Duplicate the predictions of the first tree

B. Predict the negative gradient or current errors under the chosen loss

C. Maximize the number of features

D. Remove the validation set

Correct Answer: B. Predict the negative gradient or current errors under the chosen loss

Question 5

What is a likely consequence of increasing boosting-tree depth excessively?

A. Guaranteed elimination of bias and variance

B. Greater risk of overfitting

C. Automatic calibration improvement

D. No change in model complexity

Correct Answer: B. Greater risk of overfitting

Question 6

Why is a time-based split preferable to a random split in many forecasting applications?

A. It guarantees higher accuracy

B. It prevents future information from entering training

C. It eliminates missing values

D. It makes all classes equally frequent

Correct Answer: B. It prevents future information from entering training

Question 7

Which evaluation approach is most appropriate for a severely imbalanced fraud problem?

A. Accuracy alone

B. The proportion of majority-class predictions

C. Metrics such as precision, recall, PR-AUC, and cost-based performance

D. Training error only

Correct Answer: C. Metrics such as precision, recall, PR-AUC, and cost-based performance

Question 8

Why can impurity-based feature importance be misleading?

A. It cannot be calculated for trees

B. It may favour variables with many possible split points

C. It always measures causality

D. It is independent of the fitted model

Correct Answer: B. It may favour variables with many possible split points

Question 9

What is data leakage in a tree-based modelling project?

A. Using too few trees

B. Using information unavailable at prediction time during model development

C. Having correlated predictors

D. Pruning a tree

Correct Answer: B. Using information unavailable at prediction time during model development

Question 10

Which consideration best supports choosing a simpler tree instead of a more accurate ensemble?

A. The simpler tree always has lower bias

B. The decision requires transparent, auditable rules and the performance difference has limited business value

C. Ensembles cannot handle numerical variables

D. A simple tree never overfits

Correct Answer: B. The decision requires transparent, auditable rules and the performance difference has limited business value