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 are the next posts 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 past months in that leaf that were stress months.

A tree for stress months

I trained a small tree (at most 3 questions deep) on the 3,685 ticker-months of 2019 to 2021 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 the share of training months there that turned out stressed:

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 months 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

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:

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 months: 756 stress (20.52%) and 2,929 calm (79.48%).

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:

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.

An alternative score is entropy, ISLP equation 8.7: $\key{D} = -\sum_k \good{\hat{p}_{mk}} \log \good{\hat{p}_{mk}}$. Mitchell’s Machine Learning (chapter 3) builds his whole tree algorithm on it, using base-2 logs and choosing the split with the biggest drop in entropy, which he calls information gain. In practice it usually picks the same questions as Gini. 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.

The big danger: trees memorise

If you let a tree keep asking questions, it will eventually put every training month 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 months are 2022 and 2023, after the training years.

The fully grown tree is perfect on training months 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

from sklearn.tree import DecisionTreeClassifier, export_text

# X: one row per ticker-day -> the seven features (returns, volatilities, moving-average ratio, Bollinger)
# y: 1 = the next 20 days were a stress month, 0 = calm
tree = DecisionTreeClassifier(max_depth=3, min_samples_leaf=20, random_state=0)
tree.fit(X_train, y_train)

print(export_text(tree, feature_names=names))          # the questions, as text
tree.predict_proba(X_test)[:, 1]                       # 0.03 for calm July 2023, 0.42 for May 2022
tree.feature_importances_                              # 0.87 of it on 20-day volatility

Strengths and weaknesses

That instability sounds like a flaw. The next three posts are built on it. If one tree is unstable, train many trees on slightly different data and average them.

Summary

Next

In the next posts: bias and variance, the trade-off behind overfitting, then bagging, the first way to combine many trees.

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)
• Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997), chapter 3, “Decision Tree Learning”: entropy and information gain
• scikit-learn: decision trees