Random Forest • Extra Trees • Gradient Boosting • Histogram-Based Boosting

Combining many decision trees to improve stability, generalization, and predictive accuracy

Chapter overview

Ensemble classification replaces the idea of relying on one fitted model with a stronger principle: build several related models and combine their predictions. Tree ensembles are especially important because a single decision tree is flexible but unstable. Random forests and Extra Trees create many diverse trees and average them, while gradient boosting constructs trees sequentially so that each stage improves the mistakes left by the current ensemble.

This chapter develops four practical ensemble families. Random forests use bootstrap resampling and random feature selection to decorrelate trees. Extra Trees introduce even more randomization by drawing candidate split thresholds. Gradient boosting adds shallow trees sequentially under a differentiable loss, with the learning rate and number of estimators controlling how aggressively the ensemble adapts. Histogram-based gradient boosting bins continuous features so large tabular datasets can be processed more efficiently and, in scikit-learn, provides native missing-value support.

Learning objectives

• Explain why combining models can reduce variance and improve predictive stability.
• Distinguish averaging ensembles from sequential boosting ensembles.
• Explain bootstrap sampling, random feature selection, voting, and out-of-bag evaluation in a random forest.
• Compare random forests with Extra Trees and explain the effect of randomized split thresholds.
• Describe gradient boosting as sequential correction under a loss function and relate weak learners to ensemble strength.
• Explain the roles of learning_rate, n_estimators, tree depth, and regularization in the bias-variance trade-off.
• Explain why histogram binning accelerates gradient-boosted tree training on larger datasets.
• Use native missing-value handling in histogram-based gradient boosting when appropriate.
• Compare decision trees, random forests, and gradient boosting under one leakage-safe experimental protocol.
• Interpret impurity-based and permutation feature importance cautiously and avoid causal conclusions.

Table 17.1. Chapter structure

17.1 Motivation for ensemble learning

A decision tree can adapt to nonlinear relationships and interactions, but it is sensitive to the exact observations used for training. If a slightly different sample changes the first few splits, the entire downstream tree can change. Ensemble learning addresses this instability by combining the predictions of multiple fitted models instead of trusting one model structure.

17.1.1 Combining multiple models

Figure 17.1. The ensemble principle

The component models are often called base estimators or base learners. In tree ensembles, each base estimator is a decision tree produced under a different sample, feature subset, split randomization, or stage of boosting. The final classifier aggregates these component outputs into one prediction.

Table 17.2. Two major ensemble strategies

17.1.2 Reducing variance

Variance describes sensitivity to the particular training sample. A high-variance model can fit one dataset extremely well but change noticeably when observations are added, removed, or resampled. Deep decision trees are a classic high-variance model family. Averaging several diverse trees can cancel part of this sample-specific noise because an unusual branch that appears in one tree is unlikely to appear in exactly the same form in every tree.

This is why random forests inject randomness at two levels: the training observations are resampled and the candidate features considered at each split are restricted. The goal is not to make every tree maximally accurate by itself. The goal is to create a collection whose averaged prediction generalizes well.

17.1.3 Improving predictive stability

Stability refers to how much the model output changes under reasonable perturbations of the training data or random seed. An ensemble can be more stable than a single tree because the final decision is distributed across many structures. One tree might classify an observation differently after a small resample, while a forest of hundreds of trees may preserve nearly the same average probability.

17.1.4 Increasing model accuracy

Higher accuracy is a possible consequence of ensembling, not an automatic guarantee. A random forest may substantially outperform one unrestricted tree because variance is reduced. Gradient boosting may achieve even higher predictive accuracy on structured tabular data by correcting systematic residual errors. But ensemble gains depend on the dataset, metrics, hyperparameters, leakage control, and evaluation design.

17.2 Random forest

A random forest is an averaging ensemble of decision trees. Each tree is trained with controlled randomness so the trees do not all reproduce the same structure. For classification, the forest combines the trees through class-probability averaging or an equivalent aggregate decision. The resulting model is usually less sensitive to sampling noise than a single deep tree.

Figure 17.2. Random forest training and prediction

17.2.1 Bootstrap samples

A bootstrap sample is created by drawing training observations with replacement. If the training set contains n rows, a bootstrap sample also contains n draws by default, but some original rows can appear more than once and others may not appear at all. Different trees receive different bootstrap samples, which helps create diversity.

17.2.2 Multiple decision trees

Each bootstrap sample is used to fit a decision tree. Forest trees are often allowed to grow relatively deep because the ensemble will average their predictions. A single deep tree may overfit strongly, but hundreds of diverse deep trees can still produce a stable aggregate. Parameters such as max_depth, min_samples_leaf, and max_leaf_nodes remain available when stronger regularization is needed.

The number of trees is controlled by n_estimators. Increasing n_estimators usually makes the aggregate prediction more stable until the performance plateaus. It also increases training time, prediction time, and model size. Unlike tree depth, adding more trees normally does not create the same kind of overfitting curve; the main practical question is when additional trees stop producing a useful improvement.

17.2.3 Random feature selection

If every tree could consider every feature at every split, a very strong predictor might dominate the root of most trees, making the forest highly correlated. Random forests therefore consider only a random subset of features at each candidate split. The max_features parameter controls the size of that subset. For classification, sqrt is a common default because it creates substantial diversity while preserving informative choices.

Table 17.3. Sources of diversity in a random forest

17.2.4 Majority voting and probability averaging

A simplified classroom explanation says that the trees vote for a class and the majority wins. In scikit-learn’s RandomForestClassifier, the class probabilities predicted by the individual trees are averaged, and the final class is selected from those averaged probabilities. This distinction matters when leaf class distributions are not pure.

17.2.5 Training a random forest

17.2.6 Out-of-bag evaluation

Out-of-bag evaluation uses observations that were not included in a tree’s bootstrap sample. For each training observation, the forest can aggregate predictions only from trees for which that observation was out of bag. These predictions provide an internal estimate of generalization without creating a separate validation split for that specific purpose.

In scikit-learn, set oob_score=True together with bootstrap=True. The fitted classifier exposes oob_score_ and oob_decision_function_. The OOB estimate is useful for quick diagnostics and for following forest convergence, but it does not replace a carefully designed test set, group-aware split, temporal validation, or cross-validation when the data structure requires them.

17.2.7 Feature importance

A fitted random forest exposes impurity-based feature_importances_. The importance of a feature accumulates the weighted impurity reduction produced by splits using that feature across the ensemble. This can be useful for exploratory ranking, but it is model-specific and can favor continuous or high-cardinality variables with many possible split points. Correlated features can also divide or substitute for one another’s importance.

Permutation importance provides a more model-agnostic alternative. It measures how much a chosen evaluation score deteriorates when one feature is randomly permuted while the others remain unchanged. It should be computed on validation or test-like data rather than only on the training data.

17.3 Extra Trees

Extremely Randomized Trees, implemented by ExtraTreesClassifier, form another ensemble of randomized decision trees. Like random forests, they use random subsets of candidate features. The main additional randomization is the split threshold: instead of exhaustively searching the best threshold for each candidate feature, random thresholds are drawn and the best among those randomized candidates is selected.

Figure 17.3. Random forest versus Extra Trees at a split

17.3.1 Increased split randomness

Extra randomness can decorrelate the fitted trees even when they see the same training observations. This can lower variance further, although the additional randomness can increase bias because the algorithm may not choose the locally optimal threshold available for the current node.

17.3.2 Differences from random forests

Table 17.4. Random forest and Extra Trees

17.3.3 Speed and variance considerations

Random threshold generation can reduce the amount of split-search work, so Extra Trees may train faster than a comparable random forest on some datasets. The exact runtime depends on sample size, feature count, tree depth, data representation, number of estimators, hardware, and parallelism. The stronger randomization also means that Extra Trees should not automatically be described as “better” or “worse”; it should be evaluated under the same cross-validation and resource constraints as the random forest.

17.4 Gradient boosting

Gradient boosting builds an additive model sequentially. The first stage creates an initial prediction. Each later tree is fitted to improve the current ensemble according to the selected loss function. Instead of averaging many independent trees, the algorithm constructs a coordinated sequence in which later stages focus on remaining errors.

Figure 17.4. Sequential correction in gradient boosting

17.4.1 Sequential correction of errors

For squared-error regression, boosting is often introduced as fitting residuals. For classification, the underlying formulation is more general: each stage fits a tree to the negative gradient of the classification loss with respect to the current model score. The practical intuition remains useful—new trees concentrate on aspects of the data that the current ensemble handles poorly.

17.4.2 Weak learners

Boosting commonly uses shallow decision trees as weak learners. A weak learner is not expected to solve the entire classification problem independently. Its role is to contribute a modest, structured improvement that becomes useful after many stages are combined. Tree depth therefore has a different interpretation than in a single decision tree: shallow trees often work well because the sequence can gradually build complex decision boundaries.

Table 17.5. Tree depth in boosting

17.4.3 Learning rate

The learning rate scales the contribution of each new tree. A smaller learning_rate means the ensemble changes more cautiously at each stage and usually needs more estimators. This shrinkage can improve generalization because no single tree is allowed to dominate the fit. A large learning rate reaches a strong training fit quickly but can overshoot useful structure or overfit earlier.

17.4.4 Number of estimators

n_estimators controls how many boosting stages are added in GradientBoostingClassifier. Too few stages leave systematic errors uncorrected. Too many can fit noise, especially when individual trees are deep or the learning rate is high. Validation curves or cross-validation help identify a useful region.

17.4.5 Inspecting the number of stages

GradientBoostingClassifier exposes staged prediction methods that make it possible to evaluate the partially built ensemble after each boosting iteration. This is useful for understanding when validation performance stops improving.

17.4.6 Tree depth and interactions

The max_depth parameter controls the depth of each regression tree used internally by GradientBoostingClassifier. A depth-1 tree can represent one main split at a stage, while deeper trees can model conditional interactions. Because hundreds of stages can be added, moderate depths often provide enough flexibility for tabular classification without making every stage excessively complex.

17.4.7 Bias-variance trade-off

Table 17.6. Gradient boosting complexity controls

17.5 Histogram-based gradient boosting

Traditional gradient boosting repeatedly evaluates ordered feature values while constructing trees. Histogram-based gradient boosting first bins continuous values into a limited number of discrete intervals. Split search then operates on compact bin statistics rather than sorting every raw feature value at every node. This can make training substantially faster on larger datasets.

Figure 17.5. Histogram-based split search

17.5.1 Efficient processing of larger datasets

The computational advantage becomes important when the dataset contains many thousands of observations or more. Scikit-learn’s user guide notes that HistGradientBoostingClassifier can be orders of magnitude faster than GradientBoostingClassifier when sample sizes are above tens of thousands. For small datasets, the traditional implementation can remain competitive because binning itself approximates the available split points.

The number of boosting iterations is controlled by max_iter rather than n_estimators. Other important controls include learning_rate, max_leaf_nodes, max_depth, min_samples_leaf, l2_regularization, and early_stopping.

17.5.2 Handling continuous variables

Continuous features are quantized into bins. Observations in the same bin are treated together during split search, which reduces the cost of evaluating candidate thresholds. The model still learns nonlinear tree-based relationships; the bins are an internal computational representation rather than a requirement that the analyst manually discretize every feature.

17.5.3 Missing-value support

HistGradientBoostingClassifier has native support for NaN values. During training, the tree grower learns whether missing observations should be sent to the left or right child at each split according to the gain. At prediction time, missing values follow the learned direction. This can remove the need for a separate numerical imputation step when NaN has a meaningful and stable interpretation in the data pipeline.

17.5.4 Traditional versus histogram gradient boosting

Table 17.7. Two scikit-learn gradient boosting implementations

17.6 Comparing ensemble methods

Random forests, Extra Trees, gradient boosting, and histogram gradient boosting all use collections of trees, but they solve different modeling problems. Forest methods emphasize diversity and averaging. Boosting emphasizes sequential correction. The best choice depends on predictive accuracy, data size, missingness, interpretability expectations, latency, memory, training budget, and tuning capacity.

17.6.1 Random forest for robust general performance

A random forest is often a strong first nonlinear ensemble for tabular data. It requires relatively little feature scaling, tolerates complex interactions, offers straightforward parallel training across trees, provides OOB diagnostics, and usually reduces the instability of a single tree. It is therefore an excellent benchmark when a decision tree is too variable but a heavily tuned boosting system is not yet justified.

17.6.2 Gradient boosting for high predictive accuracy

Gradient boosting is often highly competitive on structured tabular datasets because later stages can focus on systematic errors left by earlier stages. The benefit comes with more interacting hyperparameters and a sequential training process. Learning rate, number of stages, tree complexity, subsampling, regularization, and early stopping should be validated carefully rather than selected from training performance.

17.6.3 Interpretability and computation trade-offs

A small single tree can be explained as explicit rules. An ensemble containing hundreds of trees cannot be interpreted in the same direct way even though each component is a tree. Global importance, permutation importance, partial dependence, accumulated local effects, SHAP-style explanations, and local surrogate tools can summarize behavior, but they are explanations of a complex system rather than a replacement for a simple rule list.

Table 17.8. Practical comparison of tree classifiers

17.6.4 A compact decision guide

Table 17.9. Which model should I try?

Practical lab — Compare a decision tree, random forest, and gradient boosting classifier

Students compare three tree-based classifiers under one controlled binary-classification experiment. The Breast Cancer Wisconsin diagnostic dataset is used because it is built into scikit-learn, contains only numerical features, and allows the lab to focus on model behavior rather than data acquisition. The exercise is educational and must not be interpreted as a clinical decision system.

Lab objectives

• Create stratified training, validation, and test subsets.
• Train one constrained decision tree, one random forest, and one gradient boosting classifier.
• Compare training and validation accuracy, balanced accuracy, ROC AUC, runtime, and model complexity.
• Inspect the random forest out-of-bag score without using it as the only model-selection criterion.
• Plot validation ROC curves for the three models.
• Select a model using a predeclared validation rule before touching the final test set.
• Refit the selected configuration on development data and perform one final test evaluation.
• Explain why the most accurate model is not automatically the best operational model.

Table 17.10. Practical lab design

Step 1 — Load the dataset and tools

Step 2 — Create protected subsets

Step 3 — Define three comparable models

These settings are intentionally moderate rather than extensively tuned. The goal of the first comparison is to understand model-family behavior. A later extension can tune each family with cross-validation under a controlled search budget.

Step 4 — Train and collect validation metrics

Step 5 — Compare overfitting gaps

• Which model has the largest gap between training and validation accuracy?
• Does the random forest reduce the instability expected from a single tree?
• Does gradient boosting improve validation ranking performance without producing an excessive gap?
• Would a very high training score change your selection if validation performance were weaker?

Step 6 — Inspect the random forest OOB estimate

The two numbers do not need to be identical. They are based on different prediction sets and sampling mechanisms. The purpose is to see whether the OOB estimate gives a plausible internal diagnostic consistent with held-out validation behavior.

Step 7 — Plot validation ROC curves

Step 8 — Add structural diagnostics

Model complexity cannot be reduced to one universal number. A single depth-4 tree, 400 independently fitted forest trees, and 250 sequential boosting stages represent different computational and explanatory structures. Record these differences rather than comparing only predictive scores.

Step 9 — Apply a predeclared selection rule

For this lab, select the model with the highest validation ROC AUC. If two models differ by less than 0.005 ROC AUC, prefer the one with the higher validation balanced accuracy. If both metrics are effectively tied, prefer the simpler or faster operational choice and document the reason.

Step 10 — Refit the selected model on development data

Step 11 — Evaluate the selected model once on test data

Step 12 — Inspect feature importance using a common method

Because the three model families expose different internal structures, permutation importance provides a common post-hoc comparison method. Compute it on validation-like or final evaluation data only after deciding what interpretive question you are asking.

Required student interpretation

1. Compare the validation ROC AUC and balanced accuracy of the three candidate models. Which model ranked first under the declared rule?

2. Compare each model’s training and validation accuracy. Which model shows the strongest evidence of overfitting?

3. How close is the forest OOB score to its validation accuracy? What does the difference suggest?

4. Does the ensemble advantage come mainly from variance reduction, sequential error correction, or both?

5. How much extra fitting time did the ensembles require relative to the decision tree?

6. If the random forest and gradient boosting model are practically tied, which would you deploy and why?

7. Why would direct inspection of one small tree remain easier than explanation of a forest or boosting ensemble?

8. Why is permutation importance more comparable across the three candidate families than their internal importance mechanisms?

9. Why should the final test set be evaluated only after the selection rule has been frozen?

10. Write a 250–350 word recommendation that considers predictive performance, stability, computation, interpretability, and the limitations of this educational dataset.

Expected observations

• The constrained decision tree is usually the easiest model to explain but may have a larger training-validation sensitivity than the forest.
• The random forest usually produces a more stable validation score than a single tree because many randomized trees are averaged.
• Gradient boosting can be highly competitive because later stages focus on systematic errors left by earlier stages.
• The OOB estimate should be treated as an internal diagnostic rather than a replacement for a protected final test set.
• Training time and artifact size increase when hundreds of trees are stored.
• A small difference in ROC AUC may be less important than simpler deployment, faster prediction, lower memory use, or clearer explanations.
• Feature importance rankings can change across model families because they summarize different fitted decision structures.

Lab deliverables

• A reproducible notebook containing the protected split and three candidate models.
• A comparison table containing training accuracy, validation accuracy, balanced accuracy, ROC AUC, fit time, and overfitting gap.
• The random forest out-of-bag score and a short explanation of OOB evaluation.
• One validation ROC curve containing all three models.
• The declared model-selection rule and selected model name.
• One final test confusion matrix and classification report for the selected model only.
• A top-10 permutation-importance ranking with an interpretation caution.
• A 250–350 word recommendation comparing accuracy, stability, computation, and interpretability.

Extension challenges

• Add ExtraTreesClassifier and HistGradientBoostingClassifier to the comparison while keeping the same validation protocol.
• Replace the single validation set with StratifiedKFold cross-validation and report mean plus standard deviation for each metric.
• Create a controlled search over n_estimators and max_features for the random forest.
• Create a learning_rate × n_estimators experiment for gradient boosting and visualize the validation surface.
• Compare impurity-based forest importance with permutation importance and explain disagreements.
• Inject NaN values into selected numerical features and compare explicit median imputation with HistGradientBoostingClassifier native missing-value handling.
• Measure prediction latency and serialized model size in addition to predictive metrics.
• Repeat the comparison across several random split seeds and report performance variability.

Chapter summary

Ensemble classification improves on the limitations of a single decision tree by combining multiple trees. Random forests create diversity with bootstrap samples and random feature subsets, then average predictions. This design usually reduces variance and provides a useful out-of-bag diagnostic. Extra Trees adds another source of diversity by selecting from randomized split thresholds, which can reduce tree correlation and sometimes improve computational efficiency at the cost of additional bias.

Gradient boosting follows a different strategy. Trees are added sequentially so that each stage improves the current ensemble under the selected loss. The learning rate controls how strongly each stage contributes, the number of estimators controls how long boosting continues, and tree depth controls the complexity of each correction. These choices jointly determine the bias-variance trade-off. Histogram-based gradient boosting accelerates split search by binning continuous features and is especially attractive for larger tabular datasets; in scikit-learn it also supports NaN values natively.

Model choice should be based on honest validation rather than algorithm reputation. A random forest is a strong robust nonlinear benchmark. Gradient boosting can provide excellent predictive accuracy but needs careful tuning and sequential training. Extra Trees is worth comparing when stronger randomization is useful. Histogram gradient boosting is a practical option when sample size or missing values make it advantageous. Interpretability, runtime, memory, stability, probability quality, and deployment cost belong in the decision alongside the primary metric.

Table 17.11. Key terms

Knowledge check

1. Why can averaging many decision trees reduce variance?

2. Why would training identical trees on identical data fail to create a useful ensemble?

3. What is a bootstrap sample, and how does it create out-of-bag observations?

4. Why does a random forest restrict the candidate features considered at each split?

5. How does scikit-learn combine class predictions in RandomForestClassifier?

6. What is an OOB score, and why does it not replace a carefully designed test set?

7. How does Extra Trees introduce more randomness than a random forest?

8. Why can Extra Trees reduce variance while potentially increasing bias?

9. What does it mean for gradient boosting to build trees sequentially?

10. Why are shallow trees often suitable weak learners for boosting?

11. How are learning_rate and n_estimators related?

12. What happens when boosting trees are made too deep?

13. Why can histogram-based gradient boosting train faster on large tabular datasets?

14. How does HistGradientBoostingClassifier handle NaN values?

15. When would you prefer a random forest over gradient boosting even if their validation scores were similar?

16. Why is a forest harder to interpret directly than a depth-4 decision tree?

17. Why should impurity-based feature importance not be interpreted as causality?

18. What experimental controls are required for a fair comparison of a tree, forest, and boosted model?

Instructor notes and suggested timing

Table 17.12. Suggested teaching plan

Reference note

Implementation details in this chapter were aligned with the scikit-learn 1.9.0 stable documentation for ensemble methods, including RandomForestClassifier, ExtraTreesClassifier, GradientBoostingClassifier, and HistGradientBoostingClassifier. Students should check the documentation for the installed scikit-learn version when reproducing examples in another environment.