Decision trees: a model made of yes/no questions

Decision trees are covered in sections 8.1 and 8.2 of An Introduction to Statistical Learning. They matter for two reasons. On their own, they are one of the easiest models to explain to a business user. And they are the building block of the strongest everyday models in finance: bagging, random forests and boosting, which come later in this series.

The linear regression post drew a straight line. A tree does something different: it asks questions.

The idea: twenty questions

A good risk manager, asked “will next month be rough?”, doesn’t do arithmetic. They ask questions:

Has the market been jumpy lately? Yes? Then it’s risky. Has it also been falling? Yes? Even riskier.

A decision tree is exactly that, learned from data. Each node asks one yes/no question about one feature. Each answer sends you down a branch. At the bottom, each leaf gives the prediction: for classification, the share of the past rows in that leaf that had a stress month ahead.

A tree for stress months

I trained a small tree (at most 3 questions deep) on the 3,685 rows of 2019 to 2021 (one per ticker per trading day) from the regression vs classification post, 20.5% of which were followed by a stress month (next 20 days’ volatility above 30% a year). The seven features are the ones from that post: the last 1-, 5- and 20-day returns, the 5- and 20-day volatility, the price against its 20-day average, and the Bollinger position.

This is the tree it learned. Each leaf shows how many training rows ended up there, and the share of them that had a stress month ahead:

Read it like a flowchart. SPY in late July 2023, with 20-day volatility of 7.7%: not above 35% → not above 23% → not above 17% → the calm leaf, a $\key{3\%}$ chance of a stress month (it came in at 11%). SPY in May 2022, volatility 35.2% and down 11.9% on the month: above 35% → 5-day volatility 40.8%, not above 50% → not above 41% → $\key{42\%}$ (it came in at 29%, just under the line).

Notice what the tree found without being told:

• Recent volatility is the first question. It’s the single most useful thing to know, and the tree asks about it again and again at different levels.
• “Falling” only matters in the middle. For rows already at 23 to 35% volatility, a 9% fall turns a 24% chance into 71%. In calm months the tree never asks about returns at all. A straight line can’t do this: it gives each feature one fixed effect everywhere.
• Four of the seven features never appear. The 1- and 5-day returns, the moving-average ratio and the Bollinger position didn’t help once volatility was known, so the tree ignores them.

How it picks the questions: Gini impurity

At each step the tree tries every feature and every possible cut-off, and keeps the question that best separates stress from calm. To score “how mixed” a group is, it uses the Gini index. An Introduction to Statistical Learning (ISLP) writes it as equation 8.6:

the impurity score: G (Gini) and D (entropy)the class shares in a group

$$\key{G} = \sum_{k=1}^{K} \good{\hat{p}_{mk}}\left(1 - \good{\hat{p}_{mk}}\right)$$

where $\good{\hat{p}_{mk}}$ is the share of group (region) $m$ that belongs to class $k$. Because the shares add up to 1, this is the same number as the form scikit-learn’s documentation uses:

$$\key{G} = \sum_k \good{p_k} - \sum_k \good{p_k^2} = 1 - \sum_k \good{p_k^2}$$

Plain meaning: pick two months at random from the group. $\key{G}$ is the chance they belong to different classes. A pure group scores 0. A 50/50 group scores 0.5, the maximum for two classes.

Worked example: the first question

All 3,685 training rows: 756 with a stress month ahead (20.52%) and 2,929 calm (79.48%).

$$\key{G_{\text{all}}} = 1 - (0.7948^2 + 0.2052^2) = 0.3261$$

For a number like volatility, the tree also has to choose a cut-off; it tries every value in the data and keeps the best. For 20-day volatility the best cut-off is 35.3%:

The score of a split is the weighted average of its groups’ Gini, weighted by group size:

$$\begin{aligned} \key{G_{\text{split}}} &= \frac{3{,}152}{3{,}685} \times 0.2082 + \frac{533}{3{,}685} \times 0.4028 \\[10pt] &= 0.2363 \end{aligned}$$

The split lowers impurity by $0.3261 - 0.2363 = 0.0898$. The best cut-off on 5-day volatility lowers it by 0.0790, on the 20-day return by $\key{0.0474}$, and on the Bollinger position by only 0.0051. The 20-day volatility wins, so it becomes the first question. Then the tree repeats the same search inside each group, and keeps going.

One thing to notice: the “above 35.3%” group (0.4028) is more mixed than the starting group. That’s fine. It’s small, and the big “calm” group became much purer. The weighted average is what counts.

For regression trees (predicting a number), the score is the spread of the numbers in each group, measured by squared error, and each leaf predicts the average of its training values.

Entropy, the other score, and the settings that stop a tree

Gini is one way to score how mixed a group is. Entropy (ISLP equation 8.7, $\key{D} = -\sum_k \good{\hat{p}_{mk}} \log \good{\hat{p}_{mk}}$) is the other; ISLP notes the two are “quite similar numerically”, and they usually pick the same questions. Mitchell’s Machine Learning (chapter 3) builds his whole tree algorithm on entropy. For a group that is a fraction $p$ one class and $1 - p$ the other:

Some books measure entropy in bits (base-2 logarithm) and some in nats (natural logarithm); the numbers differ, the winning split does not. Information gain, Mitchell’s name for the drop in entropy, is the parent’s entropy minus the weighted entropy of the children; a tree picks the split with the largest gain, the same recipe as the Gini drop above. A split never makes the weighted impurity worse, so a tree keeps splitting until a setting stops it:

Two more facts about how a tree sees the world. It needs no scaling: a split asks whether a value is above or below a threshold, so taking logs or standardising changes nothing. And it captures thresholds and interactions on its own, which is where it beats a straight line. A made-up target that is a sum of three steps, $8[x_1 > 0] + 5[x_2 > 0] + 3[x_3 > 0]$ plus a sliver of slope (each bracket is 1 when the condition is true and 0 when it is not, so the target jumps by 8 when $x_1$ crosses zero), gives a fully grown tree a test RMSE of 0.21 and a linear model 2.52; a target that is a plain weighted sum of the same three inputs gives the line 0.06 and the tree 7.79. Each wins where the truth has its shape.

The big danger: trees memorise

If you let a tree keep asking questions, it will eventually put every training row in its own leaf, and be “perfect” on the data it has seen. I trained trees of different depths and scored them with AUC: the chance that the model gives a randomly chosen stress month a higher risk score than a randomly chosen calm one. 0.5 is a coin flip, 1.0 is perfect. The test rows are from 2022 and 2023, after the training years.

The fully grown tree is perfect on training rows and barely better than the one-question stump on new ones. It learned the noise in its training data, like a student who memorised last year’s exam answers. This is overfitting, and it’s the subject of the bias and variance post.

In practice you stop the tree early by limiting max_depth or the minimum number of rows in a leaf (min_samples_leaf), and choose the limit by testing on data the tree hasn’t seen.

The code

Sixteen made-up rows with two features, typed in by hand so it runs as pasted (pip install scikit-learn). X_train holds the features of each row, y_train the answer for each row (1 if a stress month followed), and X_new three rows the tree has not seen:

from sklearn.tree import DecisionTreeClassifier, export_text

# Each row is one stock on one day: [volatility of the last 20 days (% a year),
#                                    return over the last 20 days (%)]
X_train = [[ 8,  2], [10, -1], [12,  3], [14, -2], [16,  1], [18, -3],   # calm
           [12, -8], [15, -9],                                  # calm, but fell
           [25,  2], [27, -1], [28,  4],                                 # jumpy, not falling
           [26, -11], [29, -12], [31, -10],                              # jumpy and falling
           [38, -4], [42,  1], [45, -8], [50, -15]]                      # very jumpy
# y_train: 1 if the month that followed was a stress month (volatility above 30%), else 0
y_train = [0, 0, 0, 0, 0, 0,
           0, 0,
           0, 0, 0,
           1, 1, 1,
           1, 1, 1, 1]

tree = DecisionTreeClassifier(max_depth=3, random_state=0)
tree.fit(X_train, y_train)

print(export_text(tree, feature_names=["vol_20d", "ret_20d"]))   # the questions it learned

X_new = [[9, 1], [27, -10], [40, 0]]       # calm; jumpy and falling; very jumpy
print(tree.predict_proba(X_new)[:, 1])     # chance of a stress month, one per row
print(tree.feature_importances_)           # how much each feature mattered (adds up to 1)

It prints the tree as text. The first question is about volatility (vol_20d <= 28.50), and the return is asked about only for rows that are not already very volatile, the same shape as the real tree above. Then [0. 1. 1.]: no stress after the calm row, stress after the other two. Then the importances, about 0.79 for volatility and 0.21 for the return. With only sixteen rows every leaf is pure, so the chances are 0 or 1; on real data they are shares like the 3% and 42% above.

The script behind the real numbers

The tree, the Gini arithmetic and the depth table come from examples/decision-trees/decision_tree.py, which runs on all seven features of the blog’s five tickers. To run it yourself, clone the examples repo: its README has a three-command Docker setup, or run uv run decision-trees/decision_tree.py. The line against the tree on made-up steps is in examples/machine-learning-in-ten-ideas/ten_ideas.py.

Strengths and weaknesses

That instability sounds like a flaw. Bagging, random forests and boosting, later in the series, are built on it. If one tree is unstable, train many trees on slightly different data and average them.

Summary

References

• James, Witten, Hastie, Tibshirani and Taylor, An Introduction to Statistical Learning, with Applications in Python (Springer, 2023), section 8.1: classification error (equation 8.5), Gini index (8.6), entropy (8.7), and why the two are “quite similar numerically” (8.1.2)
• Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997), chapter 3, “Decision Tree Learning”: entropy and information gain
• scikit-learn: decision trees