Classification and regression trees, from Breiman, Friedman, Olshen and Stone's 1984 book, split the data repeatedly on one feature at a time. At each node the algorithm searches every feature and every possible cut point, and takes the split that most reduces impurity.
How does CART choose a split?
For classification the standard impurity measure is the Gini index, 1 − Σp_i², which is 0 when a node is pure and 0.5 at a two-class even split. A candidate split is scored by the weighted average of its children's impurities, and the improvement is the parent's impurity minus that average. Take a node of 40 firms, 16 of which outperformed, so its Gini is 0.4800. One candidate split sends 18 firms left (12 outperform, Gini 0.4444) and 22 right (4 outperform, Gini 0.2975), for a weighted impurity of 0.3636 and a gain of 0.1164. A second candidate splits 25 and 15 for a weighted impurity of 0.4587 and a gain of 0.0213. The first wins, and the arithmetic is short enough to do in a meeting.
For regression the criterion is the reduction in the sum of squared errors, and the prediction at a leaf is the mean of the training values in it. Entropy, −Σp_i log p_i, is a common alternative to Gini and rarely changes which split is chosen.
Advertisement
What are the strengths and weaknesses of a decision tree?
Two properties make trees attractive to analysts. They are genuinely readable, since a fitted tree is a set of nested rules a portfolio manager can argue with. And they capture interactions without being told to, because every split after the first is conditional on the ones above it.
The complexity dials are depth, minimum samples per leaf and minimum impurity decrease, and letting them run free is how a single tree destroys itself. A tree grown until every leaf is pure has memorised the training set: its training error is zero, its structure changes completely when one observation is added, and its out-of-sample performance is often worse than a linear model's. Trees are also unstable in a specific way that matters, since a small change to the data can flip the first split, and the entire structure below it then changes. Pruning back with cross-validated cost-complexity is the classical fix. The modern fix is to stop using one tree.