Decision Trees and CART

A linear model insists that the world is a weighted sum: two units more of this feature always moves the answer by the same amount, whatever else is going on. Markets are rarely that polite. Momentum works in quiet regimes and reverses in panics; a wide spread means one thing at the open and another at lunch. What you want is a model that can say "it depends" — and a decision tree is the most literal possible version of that.

The mental picture is a hospital triage flowchart. Is the patient conscious? If no, go left. If yes, is the pulse above 120? And so on, until you reach a box with an instruction in it. A decision tree is exactly this, except the questions are chosen automatically, by looking at data, to make each split as informative as possible. CART — Classification And Regression Trees — is the standard recipe for choosing them.

How a split gets chosen

At the root the algorithm sits on all $n$ training rows and considers every candidate question of the form "is feature $j$ below threshold $t$?". For each candidate it splits the rows in two and scores the result with an impurity measure: a number that is zero when a group is perfectly uniform and large when it is a mixed bag. For classification the usual choice is the Gini index,

$$G = 1 - \sum_{k} p_k^2$$

where $p_k$ is the fraction of the group belonging to class $k$. In words: if you drew two rows at random from this group, how often would they disagree? Zero means everyone matches. The split's score is the size-weighted average impurity of the two children, and the winner is whichever question drops it most. Then the algorithm forgets everything else, moves into each child, and repeats. That greed is what makes trees fast and what makes them unstable.

Worked example 1: which question wins?

Ten trading days, five up and five down. The parent impurity is

$$G = 1 - (0.5^2 + 0.5^2) = 0.5$$

the maximum possible for two classes — a completely uninformative group. Now score two candidate questions.

Question A: "was the VIX below 20?" Six days answer yes, of which five were up and one down; four answer no, and all four were down. The children's impurities are $1 - \left(\tfrac{25}{36} + \tfrac{1}{36}\right) = 0.278$ and $1 - (0 + 1) = 0$. Weighting by size:

$$0.6 \times 0.278 + 0.4 \times 0 = 0.167$$

so the impurity drop, the information gain, is $0.5 - 0.167 = 0.333$.

Question B: "was it a Monday?" Five yes days split three up and two down, five no days split two up and three down. Both children score $1 - (0.6^2 + 0.4^2) = 0.48$, so the weighted impurity is $0.48$ and the gain is only $0.02$.

CART picks A, cuts the data there, and starts again inside each side. Note it never reconsiders — even if asking B first would have unlocked a better pair of follow-up questions.

Worked example 2: a regression tree

For a numeric target, impurity is just squared error around the group mean. Five days with returns $1, 2, 3, 9, 10$ (in basis points) have mean $5$ and total squared error

$$16 + 9 + 4 + 16 + 25 = 70$$

Split them into $\{1,2,3\}$ and $\{9,10\}$. The first group has mean $2$ and error $1 + 0 + 1 = 2$; the second has mean $9.5$ and error $0.25 + 0.25 = 0.5$. Total error is $2.5$, a reduction of $67.5$ out of $70$. The tree's prediction is now a step function: $2$ for anything landing in the left leaf, $9.5$ for the right. That is all a regression tree ever outputs — a constant per leaf.

Push the flexibility slider below from shallow to deep. The boundary starts as a crude staircase, becomes sensible, then begins fencing off individual points — the classic overfitting arc.

What this means in practice

Left alone, CART grows until every leaf is pure, which means a training error of zero and a memorised dataset. Two controls stop it: pre-pruning limits (max depth, minimum rows per leaf) and cost-complexity pruning, which grows a big tree and then trims it by minimising $R(T) + \alpha\lvert T\rvert$ — fit plus a fee per leaf, with $\alpha$ chosen by cross-validation.

Single trees are seldom deployed on their own. Their value is as the base learner in ensembles: averaging many decorrelated trees kills their variance (Tree Ensembles in Finance, Random Forests and Out-of-Bag Error), while fitting them sequentially to residuals kills their bias (Gradient Boosting in Finance). The readability of one tree plus the accuracy of a thousand is the reason this family dominates tabular finance data.