Lesson 5.2: Decision trees, random forests and gradient boosting
Learn how a decision tree chooses its splits, why forests of trees beat a single tree, and how gradient boosting builds a model one correction at a time.
By the end of this lesson you will be able to explain how a decision tree decides where to split, compute the Gini impurity and the gain of a split by hand, say why a single deep tree overfits, describe how a random forest and gradient boosting fix that in two different ways, and choose and tune them sensibly. You will compare two candidate splits on a table of 100 borrowers, see a majority vote of weak models become a strong one, and watch a boosting model shrink its error round by round. You should have read Lessons 4.2 and 4.4, since trees are classifiers judged by the same ideas of probability and overfitting, and Lesson 5.1 for the features they use. The mathematics is proportions and squares.
Linear and logistic regression draw straight lines through the data, and they need you to tell them about curves and interactions. Tree-based models find those on their own. They split the data again and again on questions such as "were there two or more missed payments?" and "is income below ₹3 lakh?", and the answers lead them to a prediction. They handle non-linear patterns and interactions automatically, they do not need scaling, they cope with mixed types of columns, and on the tabular data that fills most business databases, boosted trees are often the most accurate models available. They are the workhorses of credit scoring, fraud detection, churn prediction and demand forecasting.
A decision tree: a flowchart learned from data
A decision tree is a set of yes-or-no questions arranged as a flowchart. Start at the top, the root, ask a question about one feature, follow the answer down a branch to the next question, and continue until you reach a leaf, which holds the prediction. For a default model, a path might read: missed payments two or more, then income below ₹3 lakh, then predict default with probability 0.62.
The learning problem is to choose the questions. The method is greedy and simple. At each node, try every feature and every possible threshold, split the rows into two groups, and keep the split that makes the groups as pure as possible, meaning that each group is mostly one outcome. Then repeat inside each group, until a stopping rule says to halt.
Measuring purity: Gini impurity
To compare splits you need a number for how mixed a group is. The most common choice for classification is Gini impurity. If a group has a proportion p of defaulters, then
Gini = 1 − (p² + (1 − p)²) = 2 × p × (1 − p)
A pure group, with p = 0 or p = 1, has a Gini of 0. A group that is half and half has the maximum of 0.5. Another popular measure is entropy, which behaves very similarly. The gain of a split is the parent's impurity minus the weighted average impurity of the two children, where each child is weighted by its share of the rows.
A worked example
Take 100 borrowers, 30 of whom default. The root group has p = 0.3 and Gini = 2 × 0.3 × 0.7 = 0.42. Two splits are candidates.
Split A: two or more missed payments. The 20 borrowers with two or more missed payments include 14 defaulters, so p = 0.7 and Gini = 2 × 0.7 × 0.3 = 0.42. The other 80 include 16 defaulters, so p = 0.2 and Gini = 2 × 0.2 × 0.8 = 0.32. The weighted impurity is (20 × 0.42 + 80 × 0.32) ÷ 100 = (8.4 + 25.6) ÷ 100 = 0.34. The gain is 0.42 − 0.34 = 0.08.
Split B: income below ₹3 lakh. The 40 low-income borrowers include 18 defaulters, so p = 0.45 and Gini = 2 × 0.45 × 0.55 = 0.495. The other 60 include 12 defaulters, so p = 0.2 and Gini = 0.32. The weighted impurity is (40 × 0.495 + 60 × 0.32) ÷ 100 = (19.8 + 19.2) ÷ 100 = 0.39, and the gain is 0.42 − 0.39 = 0.03.
Predict first: looking at the two splits, which would the tree choose, and what does the size of the gap suggest? Decide before reading on.
It chooses Split A, with a gain of 0.08 against 0.03. The missed-payments question produces a small group that is mostly defaulters, which is a purer separation than the income question gives. The tree then continues inside each child with the same procedure, so the second question can differ in the two branches.
Why a single tree overfits
If you let a tree keep splitting until every leaf is pure, it will fit the training data perfectly, because in the limit each leaf holds a single borrower. That is memorisation. A deep tree has low bias and very high variance, in the language of Lesson 4.4: change a few training rows and the tree can look quite different. The accuracy chart is the familiar picture.
The tree is controlled by its hyperparameters, settings that you choose before training and tune by cross-validation: the maximum depth, the minimum number of rows required to split a node, and the minimum number in a leaf. Restricting them is a way of pruning the tree. A shallow tree is easy to read and explain, which is one reason single trees are still used when a model must be justified to a customer or regulator. But a single tree is a weak predictor and an unstable one. The next two methods turn many such trees into a strong model, by two different routes.
Random forests: averaging many trees
A random forest builds hundreds of trees and averages their predictions. Two sources of randomness make the trees different from each other.
1. Bootstrap samples. Each tree is trained on a random sample of the rows, drawn with replacement, as in the bootstrap of Lesson 2.4. About a third of the rows are left out of any one tree's sample.
2. Random feature subsets. At each split, the tree considers only a random subset of the features, often the square root of their number. This stops every tree from choosing the same strong feature at the top and so makes the trees less alike.
Each tree is deep and overfits on its own, so each has high variance. But their errors are partly independent, and averaging many of them cancels much of the noise while keeping the low bias. Averaging reduces variance without adding bias, which is the whole trick, and it is an example of bagging, short for bootstrap aggregating.
How much can a vote of many imperfect models improve things? Suppose each model is right 60 per cent of the time and, in the ideal case, errs independently of the others. The majority vote of 11 such models is right about 75.4 per cent of the time. The vote of 51 is right about 92.7 per cent, and the vote of 101 about 97.9 per cent. Real trees are correlated, so the gain is smaller, but the direction is the same.
The forest has useful by-products. Because each tree never saw about a third of the rows, you can score those rows with that tree and obtain an honest error estimate for free, called the out-of-bag error. And the forest can report feature importance, a measure of how much each feature contributed to reducing impurity across all the trees.
Treat importance with care. The default impurity-based version is biased towards features with many distinct values, and splits credit between correlated features arbitrarily. A more reliable alternative is permutation importance: shuffle one feature's values in held-out data and measure how much the score drops. Lesson 7.1 develops these methods.
Gradient boosting: learning from mistakes
A forest builds its trees independently and averages them. Gradient boosting builds them one after another, each tree trying to fix the errors the earlier ones left behind. The process, in outline:
1. Start with a simple prediction, such as the average outcome.
2. Compute the errors, called residuals: actual minus predicted.
3. Fit a small tree, often only three to six levels deep, to predict those residuals.
4. Add the tree's output to the prediction, multiplied by a small number called the learning rate.
5. Compute the new residuals and repeat for hundreds of rounds.
The name comes from the fact that, for a general loss, the residuals are replaced by the negative gradient of the loss, so the method is gradient descent carried out in the space of functions.
A worked example with one borrower's loss. The true value is 100, and the starting prediction is the average, 60, leaving a residual of 40. Suppose each tree can capture 75 per cent of the remaining residual, and the learning rate is 0.1. Each round then closes 0.1 × 0.75 = 7.5 per cent of the remaining gap, so the gap is multiplied by 0.925. After 10 rounds the gap is 40 × 0.925 to the power 10 = 18.3. After 50 rounds it is 0.8. With a learning rate of 0.5 the gap is multiplied by 0.625 each round and falls to 0.4 after 10 rounds.
The arithmetic seems to favour a high learning rate, since the error falls faster. The catch is that this error is measured on the training data. A large learning rate with many rounds fits the training noise, just as a deep tree does, and the held-out error turns up. A small learning rate, with the number of rounds chosen by early stopping on a validation set, nearly always generalises better. The three hyperparameters interact: a lower learning rate needs more rounds, and the usual practice is to fix a small learning rate, such as 0.05, and let early stopping pick the number of rounds.
Boosting has other controls that act as regularisation: the depth of each tree, the fraction of rows and of features sampled for each tree, and penalties on leaf values. Modern implementations such as XGBoost, LightGBM and scikit-learn's histogram-based gradient boosting are fast, handle missing values natively and are the usual choice for tabular prediction.
Trees, forests and boosting compared
· Single tree · Random forest · Gradient boostingHow trees are built · One tree · Many trees in parallel, independently · Many small trees in sequence, each fixing the last
Main idea · Split to purify · Average to cut variance · Correct errors to cut bias
Tree size · Any · Deep, overfit individually · Shallow, weak individually
Overfitting risk · High · Low · Moderate, controlled by learning rate and rounds
Tuning effort · Low · Low · Higher
Typical accuracy · Lowest · High · Often highest on tabular data
Explainability · High, you can read the flowchart · Low, needs importance tools · Low, needs importance tools
Handles scale, outliers · Yes · Yes · Yes
Lesson 5.3 develops the contrast between averaging and correcting in more detail, with bagging, boosting and stacking side by side.
Reading a prediction and tuning the knobs
A tree's prediction is easy to follow, and that is worth practising. Consider a depth-3 tree for default. A borrower arrives with two missed payments, income of ₹2.5 lakh and a loan-to-income ratio of 0.9. The root asks about missed payments, and the answer, two or more, sends the borrower to the left branch. That node asks whether income is below ₹3 lakh, which is true, so the borrower goes left again to a node that asks whether loan-to-income exceeds 0.7, also true. The leaf reached held 25 training borrowers, 17 of whom defaulted, so the tree predicts a default probability of 17 ÷ 25 = 0.68. A different borrower follows a different path to a different leaf. Every prediction can be explained as a short list of conditions, which is the main advantage of a single tree.
Forests and boosted models are tuned through a small set of hyperparameters, and knowing the direction of each saves hours of guessing.
Hyperparameter · What it controls · Raising it · Typical remedy forMaximum depth · How many questions deep a tree can go · More flexible, more overfitting · Overfitting: lower it
Minimum rows in a leaf · The smallest group a leaf may hold · Smoother, more cautious trees · Noisy leaves: raise it
Number of trees (forest) · How many trees are averaged · Steadier predictions, slower · Rarely harmful: use enough
Features per split (forest) · How many features each split may consider · Trees more alike, higher variance · Correlated trees: lower it
Learning rate (boosting) · The size of each correction · Faster fit, more overfitting · Overfitting: lower it and add rounds
Number of rounds (boosting) · How many trees are added · Better fit, then overfitting · Choose by early stopping
Row and feature sampling (boosting) · The share of data each tree sees · Less randomness · Overfitting: lower it
A sensible order for a first tuning pass is to fix a small learning rate, set a modest depth between 3 and 6, let early stopping pick the number of rounds, and then adjust the leaf size and the sampling fractions with cross-validation. Resist tuning every knob at once, because with limited data a large search over many settings will find a combination that looks good only by chance, the same multiple-testing problem as in Lesson 2.3.
Practical points
Trees do not extrapolate. A tree predicts the average of the training rows in a leaf, so it can never predict a value outside the range it has seen. For a time series with a trend, a tree-based model will go flat beyond the data, and a linear model or a differenced series is better. Trees can capture interactions, but they need enough data in each leaf, so tiny datasets favour simpler models. Highly imbalanced outcomes need care, and Lesson 7.2 covers that. And as always, tune with cross-validation and report performance on a test set that was never used for tuning.
python
from sklearn.ensemble import RandomForestClassifier, HistGradientBoostingClassifier
from sklearn.tree import DecisionTreeClassifier, exporttext
from sklearn.inspection import permutationimportance
from sklearn.modelselection import crossvalscore
tree = DecisionTreeClassifier(maxdepth=3, minsamplesleaf=50, randomstate=0).fit(Xtrain, ytrain)
print(exporttext(tree, featurenames=list(Xtrain.columns))) # the flowchart, readable
forest = RandomForestClassifier(nestimators=500, minsamplesleaf=5,
oobscore=True, njobs=-1, randomstate=0).fit(Xtrain, ytrain)
print(forest.oobscore) # free error estimate
boost = HistGradientBoostingClassifier(learningrate=0.05, maxiter=1000,
earlystopping=True, validationfraction=0.15,
randomstate=0).fit(Xtrain, ytrain)
for name, m in [("tree", tree), ("forest", forest), ("boosting", boost)]:
print(name, crossvalscore(m, Xtrain, ytrain, cv=5, scoring="rocauc").mean())
imp = permutationimportance(boost, Xvalid, yvalid, nrepeats=10, randomstate=0)
Notice the pieces that guard against overfitting: a limited depth and leaf size for the single tree, the out-of-bag score for the forest, and early stopping for boosting. The final comparison uses cross-validated AUC, a ranking measure that Lesson 6.2 explains.
Common mistakes
Growing one tree without limits. A fully grown tree memorises the training data.
Believing a forest cannot overfit. It overfits less, but leaf sizes and feature leakage still matter.
Using a high learning rate and many rounds. Training error looks great and held-out error rises. Use a small rate and early stopping.
Reading impurity importance as truth. It favours high-cardinality features and splits credit among correlated ones. Use permutation importance on held-out data.
Expecting trees to extrapolate. They stay flat outside the training range.
Scaling features for trees. It changes nothing, though it does no harm.
Tuning on the test set. Tune with cross-validation and keep a final test set untouched.
Treating a tree's rules as causal. A split on missed payments describes a pattern, not a lever.
Key takeaways
A decision tree repeatedly splits the data on the question that makes the groups purest. Gini impurity is 2p(1 − p), and the gain is the parent's impurity minus the weighted impurity of the children.
A single deep tree overfits. Depth, minimum leaf size and pruning control it, at the cost of accuracy.
A random forest averages many deep trees built on bootstrap samples and random feature subsets, which cuts variance. Its out-of-bag error is a free estimate of performance.
Gradient boosting builds shallow trees in sequence, each fitting the remaining errors, scaled by a learning rate. A small learning rate with early stopping generalises best.
Trees need no scaling and capture non-linearity and interactions, but they cannot extrapolate and their importance scores need care.
On tabular data, boosted trees are often the most accurate, and a regularised logistic regression remains the baseline to beat.
Check yourself
1. A group has 40 borrowers, 10 of whom default. What is its Gini impurity?
p = 0.25, so Gini = 2 × 0.25 × 0.75 = 0.375.
2. Why does a random forest choose a random subset of features at each split?
To make the trees less alike, so that averaging them cancels more of their individual errors.
3. With a learning rate of 0.2 and trees that capture 50 per cent of the error, by what factor does the error shrink each round?
1 − 0.2 × 0.5 = 0.9, so it is multiplied by 0.9 each round.
4. A boosted model has a training accuracy of 99 per cent and a validation accuracy of 81 per cent. What should you try?
It is overfitting. Lower the learning rate, use fewer rounds with early stopping, limit tree depth, or sample rows and features.
5. Why might a tree-based model do badly forecasting next year's sales for a growing business?
Trees cannot predict beyond the range of values they saw, so they cannot continue a trend.
Try this
Use a dataset with a yes-or-no outcome, such as the loan data of earlier lessons or a churn file. Set aside forty-five minutes.
1. Split the data into training and test sets. Fit a logistic regression as the baseline and record its test AUC or accuracy.
2. Fit a decision tree with a depth of 3. Print its rules, and write the first two splits in plain words. Compute the Gini gain of the root split by hand from the counts.
3. Fit trees of depth 1 to 10 and plot training and test accuracy, as in the chart. Find the depth where test accuracy peaks.
4. Fit a random forest with 300 trees, and record the out-of-bag score and the test score.
5. Fit a gradient boosting model with a small learning rate and early stopping. Compare its test score with the forest and the baseline.
6. Compute permutation importance on the test data for the best model. Compare it with the model's built-in importance and note any differences.
7. Write a short note: which model won and by how much, whether the gain over logistic regression is worth the loss of explainability, and one feature you would investigate further.
A good result is a table of models with their test scores, a plot of depth against accuracy and a sentence on whether the extra accuracy justifies the extra complexity. The next lesson widens the toolbox with nearest neighbours and support vector machines, and treats the three ways of combining models.
Tags: Data Science Decision trees Random forest Gradient boosting Machine learning