Decision Trees

How a tree of yes-or-no questions is learned: Gini and entropy, greedy CART splitting, depth and overfitting, pruning, regression trees and instability.

Beginner lesson, about 35 minutes, with interactive demos and a quiz.

What you will learn

Twenty questions with data

Should this loan be approved? Is this transaction fraud? Which patients need a scan first? Many of the decisions made on spreadsheets of data are made, directly or inside a larger model, by a decision tree: a short sequence of yes-or-no questions that a computer learned from examples.

What is it?

A decision tree predicts by asking questions about the input, one at a time, until it reaches an answer. Each internal node asks about one feature (“is the width at most 6.65 cm?”), each branch is an answer, and each leaf holds a prediction: a class for classification, a number for regression. The tree is learned from labelled examples, and learning means choosing which question to ask at each node.

How does it work?

  1. Predicting. Start at the root, answer its question, follow that branch, and repeat until you reach a leaf. The leaf’s prediction is the majority class (or the average value) of the training examples that ended up there.
  2. Learning. Try every possible question on every feature, keep the one that best separates the classes, split the data, and do the same again inside each half. This greedy recipe is CART, from the 1984 book by Breiman, Friedman, Olshen and Stone; Quinlan’s ID3 used the same top-down idea with a different measure of a good question.
  3. Stopping. Left alone, the splitting continues until every leaf is pure. Limits on depth or leaf size, or pruning afterwards, stop the tree memorising its training data.

Each leaf owns a rectangle of the plot: two questions carve the plane into four boxes, and every fruit in a box gets the same answer. The leaf for medium fruits says apple, but only 44 of its 65 training fruits are apples. A deeper tree could split it further, which is where the rest of this lesson begins.

Why does it matter?

Trees handle numbers and categories side by side, need no rescaling of features, and produce rules a person can read and check. A single shallow tree is still used where decisions must be explained, such as clinical triage rules and credit policies. Hundreds of trees combined, as random forests and gradient boosting, remain among the most accurate models for tabular data, which is the subject of the Forests and Boosting lesson.

Prefer to build one yourself? The Decision Tree Builder lets you choose every split by hand, or let CART grow it, and prune it back.

Key takeaways

  • A decision tree predicts by answering a sequence of yes-or-no questions about the features, ending at a leaf.
  • Each leaf predicts the majority class or the average value of the training examples that reach it.
  • Learning a tree means choosing the questions: greedily, one node at a time.

Choosing a split: Gini and entropy

A good question leaves each side of the split as unmixed as possible. Impurity measures turn “unmixed” into a number you can compare.

What is it?

An impurity measure scores how mixed the labels in a node are: 0 when every example has the same class, largest when the classes are evenly mixed. The two standard choices are Gini impurity, used by CART, and entropy, used by ID3 and its successor C4.5. A split’s quality is the drop in impurity from the parent to its children, weighted by how many examples go each way. With entropy the drop is called information gain.

Gini = 1 − Σ pₖ²
Entropy = − Σ pₖ log₂ pₖ
gain = I(parent) − (n_L/n)·I(left) − (n_R/n)·I(right)

pₖ is the share of the node’s examples in class k. n is the parent’s size; n_L and n_R the sizes of its children.

How does it work?

Take ten subscribers: five stayed and five cancelled. The parent node is as mixed as two classes can be, so its Gini impurity is 1 − 0.5² − 0.5² = 0.5 and its entropy is exactly 1 bit. Now try the question “3 or fewer support calls?”. It sends 4 subscribers left, all of whom stayed, and 6 right: 1 stayed, 5 cancelled.

  • Gini. Left is pure: 0. Right is 1 − (1/6)² − (5/6)² = 0.278. Weighted: 0.4 × 0 + 0.6 × 0.278 = 0.167. Gain: 0.5 − 0.167 = 0.333.
  • Entropy. Left: 0. Right: −(1/6)log₂(1/6) − (5/6)log₂(5/6) = 0.650 bits. Weighted: 0.6 × 0.650 = 0.390. Information gain: 1 − 0.390 = 0.610 bits.

The algorithm does this for every threshold on every feature. For a numeric feature, only thresholds between neighbouring values can change the groups, so CART tries the midpoints: with n distinct values there are n − 1 candidates. It keeps the split with the largest gain.

Both measures pick “calls ≤ 3.5” here, and in general they usually agree or nearly agree, because both are smooth curves that peak at a 50/50 mix. Gini is slightly cheaper to compute (no logarithms), which is one reason it is the default in libraries such as scikit-learn. Notice also that “bill ≤ £25” and “bill ≤ £82.5” score the same: impurity only sees the counts, not which class is on which side.

Why does it matter?

Impurity is the only thing guiding a tree’s growth, so it shapes everything the tree learns. It explains a common surprise: a split that looks useful to a person, such as one that isolates a small pure group, can score lower than a split that cleans up the bulk of the data. Plain information gain also has a known bias: on a categorical feature with many distinct values (a customer ID, say) it can split every example into its own pure leaf. C4.5 corrects for this with the gain ratio, and CART avoids it by allowing only binary splits.

Key takeaways

  • Gini impurity (1 − Σp²) and entropy (−Σp log₂ p) are 0 for a pure node and largest for an even mix.
  • A split’s gain is the parent’s impurity minus the size-weighted impurity of its children; the tree picks the largest.
  • For a numeric feature only the midpoints between neighbouring values need trying.

Growing the tree: greedy, recursive, and prone to overfit

One good split is easy. A whole tree is built by making the best local choice over and over, without ever looking back.

What is it?

CART grows a tree by recursive binary splitting: find the best split of the root, divide the data, and apply the same procedure to each child as if it were a new dataset. It is greedy: every split is the best one available at that moment, with no regard for what later splits could achieve. Searching for the best tree overall is not an option in practice; even deciding on the smallest tree that fits the data is NP-complete, as Hyafil and Rivest proved in 1976.

How does it work?

A node becomes a leaf when a stopping rule applies. The common ones are:

Pure nodeAll examples share one class (or one value). Nothing left to separate.Maximum depthThe node is already the chosen number of questions from the root.Minimum leaf sizeEvery split would leave a child with fewer examples than the limit.Minimum gainNo split reduces impurity by more than a small threshold.

Each extra level can double the number of leaves, and each leaf rests on fewer examples. Deep enough, a tree carves a tiny box around every mislabelled or unusual training example. Training accuracy keeps rising, while accuracy on new data stalls and then falls. That is overfitting, and depth is the dial that controls it.

On Fruit, test accuracy peaks at depth 4 and falls as the tree keeps splitting. Set the minimum leaf size to 5 and even depth 12 stops at 18 leaves with 88.9% test accuracy: no leaf can be built for a handful of points. Loans, with 8% of its labels flipped at random, behaves the same way more noisily. Rings is cleaner, so a deep tree does little harm there, and the staircase it needs to trace a circle is visible on the plot.

Why does it matter?

Every tree library exposes these stopping rules as hyperparameters (max_depth, min_samples_leaf and so on in scikit-learn), and they are the first thing to tune. Pick them on validation data or by cross-validation, never on training accuracy, which always favours the deepest tree. The same depth dial reappears in ensembles: random forests grow deep trees on purpose, boosting uses shallow ones.

Overfitting and Regularisation: validation curves and the bias-variance trade-off in general.

Key takeaways

  • CART grows a tree greedily: the best split at each node, applied recursively to each child.
  • Stopping rules (depth, leaf size, minimum gain) decide when a node becomes a leaf.
  • Deeper trees always fit the training data better; choose the depth on held-out data.

Pruning: grow big, then cut back

Stopping early has a flaw: a split that looks useless can enable excellent splits below it. CART’s answer is to grow the tree fully, then remove the branches that do not earn their keep.

What is it?

Minimal cost-complexity pruning, introduced in the CART book, scores every subtree T of the full tree by its training error plus a charge for each leaf. For a given penalty α, the pruned tree is the subtree with the lowest score (Breiman et al.).

cost(T) = R(T) + α · |T|

R(T) is the training error rate (the share of training examples misclassified); |T| is the number of leaves; α ≥ 0 is the price of one leaf.

How does it work?

At α = 0 only training error counts, so nothing worth keeping is pruned. As α rises, each leaf has to pay for itself: a branch survives only if it lowers the error rate by more than α for every extra leaf it adds. A branch with 4 leaves that cuts the error from 0.16 to 0.10 adds 3 leaves for 0.06 of error, so it is pruned once α passes 0.02. Raising α step by step gives a nested sequence of ever smaller trees, ending at the root alone. CART then chooses α by cross-validation; scikit-learn exposes the same idea as the ccp_alpha parameter.

Even α = 0 trims the fully grown tree from 43 leaves to 39, removing splits that do not reduce the number of training errors. The chart moves in steps: whole branches drop out at particular values of α, and between them nothing changes. On Fruit, test accuracy is best around α = 0.004 with 11 leaves; from about 0.006 the tree settles at 5 leaves for a long stretch, a compact model that is nearly as accurate. Here we read test accuracy directly to show the effect; in a real project α comes from cross-validation, and the test set is kept for the final check.

Why does it matter?

Pruning gives a whole family of candidate trees from one fit, ordered from complex to simple, with a single number to tune. A pruned tree is smaller and easier to read, and it usually generalises better than one stopped early by a depth limit. When the goal is a single interpretable tree, grow-then-prune is the standard approach.

Key takeaways

  • Cost-complexity pruning minimises training error plus α times the number of leaves.
  • Raising α removes branches whose error reduction per leaf is smaller than α, giving a sequence of smaller trees.
  • Choose α by cross-validation; growing fully and then pruning avoids stopping before a useful split.

Regression trees

The same machinery predicts numbers. Swap “how mixed are the classes?” for “how spread out are the values?” and everything else stays.

What is it?

A regression tree predicts a number. Each leaf predicts the mean of the training targets that land in it, and splits are chosen to reduce the squared error around those means. This is often called variance reduction: the sum of squared errors in a node is its variance times its size.

reduction = SSE(parent) − SSE(left) − SSE(right)

SSE(S) = Σ (yᵢ − ȳ_S)² over the examples in S. A split is scored by how much it lowers the total.

How does it work?

In the demo below, the 40 training points have a total squared error of 88.1 around their mean. The best first split, at x ≤ 7.93, leaves 48.6 on the left and 8.6 on the right, 57.3 in all: a 35% reduction from a single question. Repeating the search inside each half gives a staircase. With depth d the staircase has up to 2ᵈ steps, and a deep enough tree puts every training point on its own step.

Depth 4 (14 leaves) has the lowest test error, about 0.77. By depth 8 every training point has its own leaf, training error is 0 and test error is back up to 0.91. The noise added to this data has a variance of 0.49, so no model can do better than that on average; the deep tree is chasing it.

Why does it matter?

Regression trees are the building block of gradient boosting, which fits a regression tree to the errors of the model so far, even when the final task is classification. They also show a limitation clearly: a tree cannot extrapolate. Beyond the last training point its prediction is flat, the mean of the last leaf, however steeply the data was rising.

Key takeaways

  • A regression tree predicts the mean of the training targets in each leaf.
  • Splits are chosen to reduce the sum of squared errors (variance reduction).
  • The fit is a staircase: deeper trees fit training data more closely, and predictions are flat beyond the data.

Strengths and weaknesses

Trees have a distinctive personality. Their strengths are why they are everywhere; their weaknesses are why they are rarely used alone.

What is it?

No scaling neededA split only asks which rows fall below a threshold. Rescaling or log-transforming a feature keeps the order, so the tree is unchanged.InterpretableA shallow tree reads as a handful of if-then rules, and each prediction comes with the path that produced it.Axis-aligned boundariesEvery cut is horizontal or vertical. Diagonals and curves become staircases that need many leaves.UnstableA small change in the data can change an early split, and everything below it changes too.

How does it work?

Why scaling does not matter

Multiply every income by 1,000, convert pounds to euros, or take logarithms: any transformation that preserves the order of the values preserves the possible ways to split the rows, so the same groups win. Only the threshold labels change. Distance-based methods such as k-nearest neighbours and gradient-trained models such as neural networks do not have this property.

Why boundaries are staircases

The Loans dataset is generated with a diagonal rule. In the growing demo, the tree can only approximate it with steps, and each step is a leaf resting on a few examples. A better feature, such as debt divided by income, would let one split do the work of many.

Instability, live

The two samples come from the same data and the trees score similarly, yet their regions differ in many places. Over 20 pairs of samples, fully grown trees disagreed on between 5 and 16 of the 72 test applications, typically about 10. Depth-3 trees disagreed less, at the cost of a coarser fit. In statistical terms, a deep tree has low bias and high variance (Hastie et al.).

Why does it matter?

Interpretability is only worth something if the explanation is stable. If retraining on slightly different data gives different rules, the rules describe the sample as much as the world. That, together with the staircase boundaries, is why a single tree is chosen mainly when readability matters most, and an ensemble when accuracy does.

Key takeaways

  • Trees need no feature scaling: order-preserving transformations leave the splits unchanged.
  • Boundaries are axis-aligned staircases, so diagonal or curved patterns need many leaves.
  • Trees are unstable: small changes in the data can reshape the whole tree.

Why ensembles fix the instability

If each tree is a noisy opinion, ask many trees and combine their answers.

What is it?

Bagging (bootstrap aggregating) grows many trees, each on its own bootstrap sample, and averages their predictions or takes a vote. Breiman showed that it helps most when the base method is unstable, and named classification and regression trees among the unstable methods. Random forests add one more twist: each split considers only a random subset of the features, so the trees are less alike and their errors cancel better.

How does it work?

The trees in the instability demo disagree about individual applications but are each right most of the time. Averaging keeps what they agree on, the real pattern, and cancels much of what they disagree on, the quirks of each sample. Averaging also smooths the staircase: many slightly different staircases average to something closer to the diagonal. Boosting takes a different route, adding shallow trees one at a time, each fitted to the errors left by the ones before.

Why does it matter?

This is why the tree models that win on tabular data are almost never single trees. The cost is interpretability: a forest of 500 trees cannot be read as rules. The Forests and Boosting lesson builds both kinds of ensemble live and explains how to read their feature importances.

Key takeaways

  • Bagging averages many trees grown on bootstrap samples, cancelling much of their instability.
  • Random forests also randomise the features at each split, so the trees disagree in more independent ways.
  • Ensembles trade the single tree’s readability for accuracy and stability.

Check your understanding

Six situations where trees are used. Each asks you to apply an idea, not just recall it.

Question 1 of 6

A bank trains a decision tree to approve loans with no depth limit. It scores 100% on the training applications and 81% on last month’s new applications. What is the most likely explanation, and the most direct fix?

Next, build and prune your own trees in the Decision Tree Builder, then see how many trees work together in Forests and Boosting.

References

The papers, books and documentation behind the methods and claims in this lesson.

References

  1. [1]

    Classification and Regression Trees(opens in a new tab)

    Leo Breiman, Jerome H. Friedman, Richard A. Olshen & Charles J. Stone, 1984

    Wadsworth (reissued by Routledge/CRC). The CART book: binary splits, the Gini criterion, regression trees, and minimal cost-complexity pruning with the subtree chosen by cross-validation.

  2. [2]

    Induction of Decision Trees(opens in a new tab)

    J. Ross Quinlan, 1986

    Machine Learning 1(1), 81–106. The ID3 algorithm: grow a tree top-down, choosing at each node the attribute with the largest information gain (the drop in entropy).

  3. [3]

    Decision Trees (scikit-learn user guide, section 1.10)(opens in a new tab)

    scikit-learn developers, 2024

    Documentation of a widely used implementation, an optimised version of CART: Gini, entropy and squared-error criteria, stopping parameters, and cost-complexity pruning via ccp_alpha.

  4. [4]

    Constructing Optimal Binary Decision Trees is NP-complete(opens in a new tab)

    Laurent Hyafil & Ronald L. Rivest, 1976

    Information Processing Letters 5(1), 15–17. Finding the smallest tree that fits the data is computationally hard, which is why practical algorithms grow trees greedily.

  5. [5]

    The Elements of Statistical Learning (2nd edition), section 9.2: Tree-based methods(opens in a new tab)

    Trevor Hastie, Robert Tibshirani & Jerome Friedman, 2009

    Springer. Regression and classification trees, node impurity measures, cost-complexity pruning, and the instability of trees. Free PDF from the authors.

  6. [6]

    Bagging Predictors(opens in a new tab)

    Leo Breiman, 1996

    Machine Learning 24, 123–140. Averaging models trained on bootstrap samples; it helps most when the base method is unstable, as decision trees are.

  7. [7]

    Random Forests(opens in a new tab)

    Leo Breiman, 2001

    Machine Learning 45, 5–32. Bagged trees that also consider a random subset of features at each split, so the trees are less alike and their average is more accurate.

Related