Decision trees

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 settlements analyst, asked “will this trade fail?”, doesn’t do arithmetic. They ask questions:

Do the settlement instructions match? No? Then it’s risky. Was it booked late? 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 trades in that leaf that failed.

A tree for settlement fails

I trained a small tree (at most 3 questions deep) on 15,000 made-up OTC trades, 5.9% of which failed. These are the features from the regression vs classification post: trade size, an SSI mismatch (the two banks’ standing settlement instructions don’t match), cross-border, new counterparty, and hours booked after the cut-off.

This is the tree it learned. Each leaf shows the share of training trades there that failed:

Read it like a flowchart. A $12m cross-border trade with a new counterparty, clean instructions, booked on time: no mismatch → not late → new counterparty → 8.7% chance of failing.

Notice what the tree found without being told:

The SSI mismatch is the first question. It’s the single most useful thing to know.
“Late” means different things in different places. For clean trades, the tree only worries above 5.2 hours late. For trades that already have a mismatch, 2.5 hours is enough. A straight line can’t do this: it gives each feature one fixed effect everywhere.
Trade size never appears. In this data it doesn’t help, so the tree ignores it.

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 fails from settles. 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}

Symbol	Meaning
$k$	each class, here “settles” and “fails”
$\good{p_k}$	the share of the group in class $k$
$\key{G}$	0 if the group is pure (all one class); higher the more mixed

Plain meaning: pick two trades 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 15,000 training trades: 884 fails (5.89%) and 14,116 settles (94.11%).

\key{G_{\text{all}}} = 1 - (0.9411^2 + 0.0589^2) = 0.1109

Now try splitting on SSI mismatch:

Group	Trades	Fails	Gini
No mismatch	14,240	567	0.0765
Mismatch	760	317	0.4863

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

\begin{aligned} \key{G_{\text{split}}} &= \frac{14{,}240}{15{,}000} \times 0.0765 + \frac{760}{15{,}000} \times 0.4863 \\ &= 0.0972 \end{aligned}

The split lowers impurity by $0.1109 - 0.0972 = 0.0137$ . Splitting on cross-border instead lowers it by only 0.0009, and on new counterparty also by 0.0009. Mismatch wins by a mile, so it becomes the first question. Then the tree repeats the same search inside each group, and keeps going.

Note one surprise: the “mismatch” group (0.4863) is more mixed than the starting group. That’s fine. It’s small, and the big “no mismatch” 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 trade 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 failing trade a higher risk score than a randomly chosen settling trade. 0.5 is a coin flip, 1.0 is perfect.

Max depth	Leaves	Score on training trades	Score on new trades
1	2	0.664	0.669
3	8	0.757	0.758
5	28	0.801	0.810
8	107	0.827	0.797
12	341	0.884	0.696
no limit	1,324	1.000	0.584

The fully grown tree is perfect on training trades and barely better than a coin flip 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 trades 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 trade -> [notional, ssi_mismatch, cross_border, new_counterparty, hours_late]
# y: 1 = failed to settle, 0 = settled
tree = DecisionTreeClassifier(max_depth=3, random_state=0)
tree.fit(X_train, y_train)

print(export_text(tree, feature_names=names))          # the questions, as text
tree.predict_proba([[12.0, 0, 1, 1, 0.0]])[0, 1]       # 0.087 for the example trade
tree.feature_importances_                              # how much each feature helped

Strengths and weaknesses

Strengths	Weaknesses
Easy to explain: it’s a flowchart	Overfits easily if grown deep
Handles “it depends” patterns (interactions) on its own	Unstable: a small change in the data can change the whole tree
No need to scale or transform features	Predictions jump in steps, not smoothly
Ignores features that don’t help	One tree is rarely the most accurate model

That instability, where small changes in data give a very different tree, sounds like a flaw. It’s actually the key to the next three posts. If one tree is unstable, train many trees on slightly different data and average them.

Summary

Idea	Formula / rule	Remember it as
A tree	yes/no questions, leaves give the answer	A learned flowchart
Gini index	$\key{G} = \sum_k \good{\hat{p}_{mk}}(1 - \good{\hat{p}_{mk}}) = 1 - \sum_k \good{p_k^2}$	Chance two random picks differ
Best split	biggest drop in weighted impurity	The question that best separates
Regression tree	split on squared error, leaf = average	Same idea, for numbers
Overfitting	deep tree: perfect on training, poor on new data	Limit depth, test on unseen data

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