Introduction to Decision Trees

What a decision tree is and how it predicts. The parts of a tree, a tree as a partition of the input space into rectangles, classification and regression trees, how trees are grown greedily, why depth controls overfitting, and the two weaknesses that motivate ensembles, axis-aligned boundaries and instability, worked on a breast cancer dataset of 569 tumors and a diabetes study of 442 patients.

A pathologist examining cells drawn from a breast lump by a fine needle can describe each cell nucleus by its size, shape and texture. The Wisconsin diagnostic breast cancer data (Wolberg, Mangasarian, Street and Street, 1993) records such descriptions for 569 tumors, 212 malignant and 357 benign. For ten characteristics of the nuclei in each image, such as radius, texture and the number of concave points on the outline, it gives the mean, the standard error and the "worst" value, the mean of the three largest, making 30 measurements per tumor. The data ship with scikit-learn. Asked to predict the diagnosis from these measurements, a decision tree with two levels of questions produces this:

A depth-2 classification tree fitted to all 569 tumors. Each box asks one question about one measurement; "yes" goes left. The bottom boxes, the leaves, give the prediction and the training tumors that ended there. The first and last leaves are nearly pure; the second (28 malignant, 18 benign) leans malignant, and the third, with 8 malignant and 9 benign tumors, is close to a coin toss.
A depth-2 classification tree fitted to all 569 tumors. Each box asks one question about one measurement; "yes" goes left. The bottom boxes, the leaves, give the prediction and the training tumors that ended there. The first and last leaves are nearly pure; the second (28 malignant, 18 benign) leans malignant, and the third, with 8 malignant and 9 benign tumors, is close to a coin toss.

The tree reads as a set of rules. A tumor whose worst radius is at most 16.8 and whose worst concave points value is at most 0.136 is predicted benign, and 328 of the 333 training tumors that fit that description were benign. A tumor with a worst radius above 16.8 and a worst texture above 19.9 is predicted malignant, and 171 of 173 were. Four leaves, three questions on a path at most two long, and the tree classifies 536 of the 569 tumors correctly, an accuracy of 0.942 on the data it was fitted to.

This article describes what decision trees are, how they predict and how they are grown in outline, and where they fall short. Regression Trees derives how splits are chosen when the outcome is a number and how a large tree is pruned back, Classification Trees derives the impurity measures used when the outcome is a category, and Random Forests shows how averaging many trees repairs their main weakness.

The parts of a tree

The vocabulary is borrowed from botany, with the tree drawn upside down. The root is the top node, where every observation enters. Each internal node (also called a decision node or split) asks a yes-or-no question about one input, such as "worst radius ≤ 16.8?", and sends the observation down one of two branches according to the answer. A node that asks no question is a leaf or terminal node, and it holds the prediction. The depth of a node is the number of questions between it and the root, and the depth of a tree is the depth of its deepest leaf. The tree above has depth 2. A tree of depth 1, a single question, is called a stump.

Two counts follow from the structure. Each question at most doubles the number of paths, so a binary tree of depth $d$ has at most $2^d$ leaves. And because every internal node has exactly two children, a binary tree with $L$ leaves has exactly $L - 1$ internal nodes: starting from a single leaf, each split turns one leaf into an internal node and adds two new leaves, a net gain of one leaf per split. The breast cancer tree has 4 leaves and 3 internal nodes.

To predict for a new observation, start at the root, answer each question with the observation's own values, and follow the branches until a leaf is reached. Take the first tumor in the data, which was malignant. Its worst radius is 25.38, above 16.8, so it goes right. Its worst texture is 17.33, at most 19.9, so it goes left and lands in the third leaf, which predicts benign because 9 of the 17 training tumors there were benign. The prediction is wrong. The leaf's contents also say how little confidence it deserved: the estimated probability of benign in that leaf is $9/17 = 0.529$, barely better than a coin. A tree reports not only a class but the class proportions in the leaf, and scikit-learn's predict_proba returns exactly those proportions.

Most trees in practice are binary, with two branches per node, as here. Some algorithms allow a categorical input to split into one branch per category, but any such multiway split can be written as a sequence of binary ones, and the binary form avoids fragmenting the data into many small groups at once.

A tree is a partition

Each leaf corresponds to the set of input values that lead to it, and the leaves together cover every possible input exactly once. Because each question compares a single input with a threshold, each of these sets is a box with sides parallel to the axes: a rectangle when there are two inputs, a hyper-rectangle when there are more. A decision tree is therefore a way of cutting the input space into rectangles and making one prediction in each.

The diabetes study used throughout the regression articles shows this in two dimensions. It records ten baseline measurements on 442 patients and a measure of disease progression one year later (Efron, Hastie, Johnstone and Tibshirani, 2004). A depth-2 regression tree fitted to all ten inputs uses only two of them. The root asks whether S5, a blood serum measurement that the scikit-learn documentation describes as possibly the logarithm of the triglycerides level, is at most 4.6. Both branches then ask about body mass index (BMI), with thresholds 26.95 on the low-S5 side and 27.75 on the high-S5 side.

The depth-2 regression tree for the diabetes data drawn as a partition of the (S5, BMI) plane. Each point is a patient, shaded by progression. The tree cuts the plane into four rectangles and predicts the mean progression of the training patients in each: 96 where both S5 and BMI are low, 226 where both are high.
The depth-2 regression tree for the diabetes data drawn as a partition of the (S5, BMI) plane. Each point is a patient, shaded by progression. The tree cuts the plane into four rectangles and predicts the mean progression of the training patients in each: 96 where both S5 and BMI are low, 226 where both are high.

In each region the tree predicts the mean progression of the training patients that fall there: 96.3 for the 171 patients in the low-S5, low-BMI rectangle, 159.7 for the 47 with low S5 and high BMI, 162.7 for the 116 with high S5 and low BMI, and 225.9 for the 108 with both high. Four numbers and three thresholds explain 0.433 of the variation in progression in the training data, an $R^2$ of 0.433, compared with 0.344 for the straight line on BMI alone in Simple Linear Regression.

Written as a formula, a tree with $M$ leaves predicts

$$\hat{f}(x) = \sum_{m=1}^{M} c_m \, \mathbf{1}(x \in R_m),$$

where $R_1, \dots, R_M$ are the rectangles, $c_m$ is the prediction attached to leaf $m$, and $\mathbf{1}(x \in R_m)$ is 1 if $x$ lies in $R_m$ and 0 otherwise (James, Witten, Hastie and Tibshirani, 2021, eq. 8.9). Since exactly one indicator is 1 for any $x$, the sum just picks out the prediction of the region containing $x$. Compare the linear model $f(x) = \beta_0 + \beta_1 x_1 + \dots + \beta_p x_p$, which assumes that the effect of each input is a straight line and adds across inputs. The tree assumes neither. Its predictions are constant within each region and jump at the boundaries, so it can follow a threshold effect, a curve or an interaction (the effect of BMI depending on S5, say) without being told to, at the cost of describing a smooth trend as a staircase.

Classification trees and regression trees

The structure is the same whatever the outcome. What differs is what a leaf predicts and how the quality of a split is measured.

A classification tree predicts a category. Each leaf predicts the most common class among its training observations, and keeps the class proportions as probability estimates. Splits are chosen to make the leaves as pure as possible, close to a single class, using an impurity measure such as the Gini index or entropy, derived in Classification Trees. The breast cancer tree is a classification tree.

A regression tree predicts a number. Each leaf predicts the mean outcome of its training observations, which is the constant that minimizes the squared error within the leaf. Splits are chosen to make the residual sum of squares as small as possible, as derived in Regression Trees. The diabetes tree is a regression tree.

The two share an algorithm, introduced together by Breiman, Friedman, Olshen and Stone (1984) under the name CART, for classification and regression trees. Quinlan's ID3 (1986), from machine learning, grew classification trees by maximizing the information gain, the reduction in entropy produced by a split. scikit-learn's DecisionTreeClassifier and DecisionTreeRegressor follow CART: binary splits, thresholds on numerical inputs, and the Gini index, entropy or squared error as the criterion.

Growing a tree

Finding the best tree outright is hopeless. Even with the number of leaves fixed, the number of ways to partition the data into that many rectangles is astronomically large, and Hyafil and Rivest (1976) proved that constructing optimal binary decision trees is NP-complete, so no efficient exact algorithm is expected to exist. Every practical method instead grows the tree greedily, from the top down, by a procedure James et al. (2021, §8.1.1) call recursive binary splitting:

  1. Start with all the training data in one node.
  2. For every input and every possible threshold on it, measure how much splitting the node there would improve the fit, by RSS for a regression tree or impurity for a classification tree.
  3. Make the single best split, creating two child nodes.
  4. Apply the same procedure to each child, separately, and stop when a stopping rule says so.

"Every possible threshold" is a finite list. For an input with $k$ distinct values in a node, only $k - 1$ thresholds give different splits, one between each pair of adjacent values, and implementations place the threshold at the midpoint. That is why the root of the breast cancer tree asks about 16.795 rather than a round number: it lies halfway between two observed worst radii. At the root of that tree the search covers 15,310 candidate thresholds across the 30 inputs. Sorting each input once makes the whole scan fast, as Regression Trees shows.

The method is greedy because each split is chosen for its immediate improvement, with no look-ahead to the splits that might follow. A split that achieves little on its own but would enable two excellent splits below it can be passed over, and Regression Trees constructs an example. Growing a large tree first and then pruning it back, rather than stopping as soon as splits stop helping, is the standard remedy.

Because a split only compares an input with a threshold, the tree depends on the inputs only through their order. Transforming an input by any strictly increasing function, such as a logarithm, changes the thresholds but not which observations fall on each side, so the tree makes the same predictions. Fitted to $\log(1 + x)$ of all 30 breast cancer measurements, a fully grown tree reproduces the original tree's training predictions exactly. Trees therefore need no scaling or standardization of inputs, unlike nearest neighbors or support vector machines, and a few extreme input values do not distort them the way they can distort a least-squares fit.

Depth and overfitting

A tree can always be grown until every leaf is pure or holds a single observation. It then fits the training data perfectly and has learned, along with the real pattern, every accident of the sample. How deep to grow is the central decision in using a tree, and it is an instance of the bias-variance tradeoff: a shallow tree cannot represent much (high bias), and a deep tree represents too much of the particular sample (high variance).

Accuracy of breast cancer trees by maximum depth. Training accuracy (blue) rises to 1.000 by depth 7, where the tree is fully grown with 22 leaves. Ten-fold cross-validated accuracy (orange), an estimate of accuracy on new tumors, peaks at 0.942 at depths 4 and 5 and falls to 0.923 for the fully grown tree.
Accuracy of breast cancer trees by maximum depth. Training accuracy (blue) rises to 1.000 by depth 7, where the tree is fully grown with 22 leaves. Ten-fold cross-validated accuracy (orange), an estimate of accuracy on new tumors, peaks at 0.942 at depths 4 and 5 and falls to 0.923 for the fully grown tree.

The breast cancer data show the pattern clearly. Accuracy on the training data rises with every extra level: 0.923 for a stump, 0.942 at depth 2, 0.979 at depth 3, and 1.000 for the fully grown tree, which stops at depth 7 with 22 leaves. Accuracy estimated by 10-fold Cross-Validation, in which each tumor is predicted by a tree fitted without it, tells a different story: 0.887 for a stump, 0.937 at depth 3, a peak of 0.942 at depths 4 and 5, then a decline to 0.923 for the fully grown tree. The deepest splits are fitting noise. The gap between the two curves measures how much of the training accuracy is illusory, and it is widest for the fully grown tree.

Limiting depth is the simplest control. Others limit the number of observations a node must hold before it can be split, or that each leaf must hold, or the number of leaves. All of these stop growth early. The approach introduced with CART (Breiman et al., 1984), and the one James et al. (2021, §8.1.1) recommend, grows a large tree and then prunes it, choosing how far to prune by cross-validation. Regression Trees derives this cost-complexity pruning in full.

Two weaknesses

Boundaries made of steps

Every boundary a tree draws is made of segments parallel to the axes. When the true boundary between classes is diagonal, the tree can only approximate it with a staircase, and it needs many steps to do so. In a synthetic problem with 500 points spread uniformly over a square and the class determined by whether $x_1 + x_2 > 0$, a single diagonal line separates the classes perfectly.

A depth-4 tree (orange boundary, 13 leaves) fitted to 500 points whose classes are separated by the diagonal (dashed). The tree can only cut parallel to the axes, so it approximates the diagonal with a staircase. Cross-validated accuracy is 0.934 for this tree and 0.996 for logistic regression, whose boundary is a straight line in any direction.
A depth-4 tree (orange boundary, 13 leaves) fitted to 500 points whose classes are separated by the diagonal (dashed). The tree can only cut parallel to the axes, so it approximates the diagonal with a staircase. Cross-validated accuracy is 0.934 for this tree and 0.996 for logistic regression, whose boundary is a straight line in any direction.

Cross-validated accuracy for trees grows with depth, from 0.742 for a stump to 0.908 at depth 3 and 0.934 at depth 4 with 13 leaves, and reaches 0.946 for the fully grown tree of 26 leaves. Logistic regression, whose boundary is a single straight line at any angle, reaches 0.996 with three coefficients. The lesson is the one James et al. (2021, §8.1.3) draw: when the true structure is close to linear, a linear model will beat a tree, and when it is made of thresholds and interactions, a tree may beat a linear model. On the diabetes data the linear model wins. Its 10-fold cross-validated $R^2$ on all ten inputs is 0.484, against 0.342 for a pruned regression tree, as Regression Trees shows.

Instability

The second weakness is less visible and more serious. A tree is built from a cascade of choices, each made on the data that reached a node, and a small change in the data can change an early choice and everything below it. James et al. (2021, §8.1.4) call trees "very non-robust" for this reason.

To see how much, draw a bootstrap sample of the breast cancer data, 569 tumors sampled with replacement from the 569, so that some tumors appear twice or more and about a third not at all, and fit a depth-2 tree to it. Repeat 200 times. The tree fitted to the full data splits first on worst radius; the bootstrap trees do so only 13 times in 200. Their root question is worst perimeter 72 times, worst concave points 61 times, mean concave points 30 times and worst area 24 times. Below the root, 21 different measurements appear.

Depth-2 trees fitted to two bootstrap samples of the same 569 tumors. They share no question: one starts from mean concave points, the other from worst concave points, and their second-level questions use four different measurements. Their predictions still agree on most tumors.
Depth-2 trees fitted to two bootstrap samples of the same 569 tumors. They share no question: one starts from mean concave points, the other from worst concave points, and their second-level questions use four different measurements. Their predictions still agree on most tumors.

The differences are partly cosmetic. Worst radius, worst perimeter and worst area all measure the size of the largest nuclei and are almost interchangeable, so trees that split on different ones can make similar predictions. But they are not only cosmetic: two trees grown on two bootstrap samples disagree on the diagnosis of a median 6.3% of the 569 tumors, and on as many as 12.5% for the most different pair. A model whose story changes this much from sample to sample is hard to interpret with confidence, whatever its accuracy.

This variability is what statisticians call the variance of the method, and it is the reason trees are rarely used alone when accuracy matters. Averaging many trees fitted to bootstrap samples reduces it, a method called Bagging, and random forests go further by making the trees less alike before averaging them. Both give up the single readable tree in exchange for accuracy.

When to use a single tree

A single tree earns its place when the model has to be read and checked by people: a triage rule, a screening protocol or a model a regulator will review. Its strengths are those listed by James et al. (2021, §8.1.4): it is easy to explain, by their account even easier than a linear regression, it can be drawn and read by non-experts, and it can handle categorical inputs without indicator variables. It also captures interactions without being told which to look for. A shallow tree is also a good first look at a new dataset, because the variables it chooses and the thresholds it finds are a quick summary of what matters. When prediction accuracy is the goal and interpretation is secondary, an ensemble of trees, random forests or Boosting, is almost always the better choice.

In Python

scikit-learn's tree classes follow the usual fit-and-predict interface, and export_text prints a fitted tree as indented rules.

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text

data = load_breast_cancer()
X, y = data.data, data.target            # y: 0 malignant, 1 benign

tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X, y)
print(export_text(tree, feature_names=list(data.feature_names)))
print(tree.score(X, y))                  # 0.942 on the training data
print(tree.predict_proba(X[:1]))         # leaf proportions for tumor 1: [0.471 0.529]

folds = StratifiedKFold(10, shuffle=True, random_state=0)
for depth in (1, 2, 3, 4, 5, None):      # None grows the tree until its leaves are pure
    model = DecisionTreeClassifier(max_depth=depth, random_state=0)
    print(depth, cross_val_score(model, X, y, cv=folds).mean())

The random_state argument matters even for a single tree: when two splits are equally good, scikit-learn breaks the tie at random, and fixing the seed makes the tree reproducible. The numbers in this article are computed by tools/experiments/data-science/introduction-to-decision-trees.py in the site's repository.

References

  • Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth. record · 3 pages
  • Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407–499. record · 12 pages
  • Hyafil, L., and Rivest, R. L. (1976). Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1), 15–17. record
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
  • Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106. record · 2 pages
  • Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages