Decision Trees
A flowchart of yes/no questions learned from data.
How a tree is built
A decision tree makes predictions by asking a sequence of yes/no questions about the features, like a flowchart. To decide whether to approve a loan, a tree might first ask "is the applicant's income above $50,000?". If yes, it follows the left branch and asks another question, perhaps "is their existing debt below $10,000?"; if no, it follows the right branch and asks something different. Each question narrows the possibilities, until the path reaches an end point called a leaf, which gives the prediction.
The interesting part is how the tree chooses its questions from data. It works from the top down. At the start, all the training examples sit together in the root. The algorithm considers every feature and every possible threshold for that feature, and for each candidate question it imagines splitting the examples into the two groups that would answer yes and no. It then picks the question whose two groups are the purest, meaning each group is dominated as much as possible by a single class. It then repeats the same process separately inside each group, and so on, until the groups are pure or some stopping rule is reached. This procedure is called CART (classification and regression trees).
"Purity" is measured by an impurity score, which is zero for a group containing only one class and highest for a group where the classes are evenly mixed. The two standard choices are
where is the fraction of the group belonging to class . For a pure group, one equals 1 and both scores are 0; for a 50/50 group of two classes, the Gini score is 0.5 and the entropy is 1 bit. The quality of a split is the drop in impurity it achieves; with entropy, this drop is called the information gain. Regression trees work the same way, but measure impurity by the variance of the target values in a group, and each leaf predicts the average target of the examples that reach it.
One important property is that the procedure is greedy: at each step it picks the split that looks best right now, without considering whether a less impressive split might enable much better splits later. Searching over all possible trees would be computationally impossible, and the greedy approach works well in practice.
Interactive: this part runs in your browser.
Watch it: How a decision tree grows, one question at a time
A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.
Interactive: this part runs in your browser.
Try it: tree depth
The true pattern is a circle, with 8% label noise. Shallow trees underfit; very deep trees carve tiny boxes around noisy points.
Interactive: this part runs in your browser.
Controlling overfitting & pros/cons
Left to grow without limits, a decision tree keeps splitting until every leaf is pure, which usually means memorising the training data, noise included. Controlling this growth is therefore essential, and there are two approaches.
Pre-pruning stops the tree from growing too far in the first place, by setting limits in advance: a max_depth (how many questions can be asked in a row), a min_samples_leaf (the smallest number of training examples a leaf may contain), a min_samples_split (how many examples a group must have before it may be split), or a max_leaf_nodes. These are hyperparameters, chosen by cross-validation. Post-pruning takes the opposite approach: grow the tree fully, then cut back the branches that don't earn their keep. The standard method, cost-complexity pruning, charges a price for every leaf and keeps only the branches whose improvement in accuracy outweighs their cost; in scikit-learn the price is the ccp_alpha parameter.
Decision trees have a distinctive set of strengths. They are among the most interpretable models: a small tree can be drawn on a page and explained to anyone, which matters in fields such as medicine and lending. They need no feature scaling, because a question like "income above 50,000?" is unaffected by the units. They handle numerical and categorical features together, capture non-linear patterns and interactions between features naturally, and report which features were most useful.
Their weaknesses are equally distinctive. They overfit easily unless pruned. They are unstable: because each split depends on the ones above it, a small change in the training data can change an early split and produce a completely different tree. And their decision boundaries are made of horizontal and vertical segments, so they approximate smooth or diagonal boundaries with blocky staircases.
The instability turns out to be the key to their most successful use. Because individual trees are unstable and high-variance, averaging many different trees cancels out much of that variance, and this is the idea behind random forests and gradient boosting, which are among the most accurate methods for tabular data.
Impurity, information gain: a worked example
A good question splits a mixed group into purer groups. Gini and entropy are just two ways to score how "mixed" a group is: 0 when everyone is the same class, highest when classes are evenly mixed. The tree tries every possible question and picks the one that reduces mixedness the most.
🔤 Symbols in this section
| fraction of the node in class k | |
| entropy of node t (bits, log base 2) | |
| impurity of node t (Gini, entropy or variance) | |
| number of points going left / right | |
| impurity decrease (information gain for entropy) |
This section makes the split criterion precise and works through a complete example, so you can see exactly how a tree compares two candidate questions.
For a node in which a fraction of the examples belong to class , the two impurity measures are
A candidate split sends of the node's examples to a left child and to a right child . Its quality is the weighted impurity decrease, the parent's impurity minus the average impurity of the children, each child weighted by its share of the examples:
The weighting matters: a split that produces one tiny pure child and one large mixed child should not score as well as a split that makes both large children purer. When is entropy, is called the information gain. The algorithm evaluates for every candidate split and chooses the largest.
A worked example. A node contains 10 examples, 5 positive and 5 negative. A candidate split sends 5 examples left, of which 4 are positive and 1 negative, and 5 examples right, of which 1 is positive and 4 negative.
Another candidate split would be scored in exactly the same way, and the larger decrease wins. In practice, Gini and entropy almost always choose the same split; Gini is slightly faster because it avoids logarithms, which is why it is scikit-learn's default.
For regression trees, impurity is the variance of the targets in the node, , and each leaf predicts its mean . Splitting therefore aims to create groups whose target values are as similar as possible. A useful mathematical fact is that all of these impurity measures are concave functions of the class proportions, which guarantees that is never negative: splitting can never make the weighted impurity worse, only equal or better.
Greedy search cost, pruning and feature importance
Growing a tree is greedy and fast, but a fully grown tree memorises noise. Pruning trades training accuracy for simplicity, with a "price per leaf" α. And the built-in feature importance can be misleading, so check importance on held-out data instead.
🔤 Symbols in this section
| training error of tree T | |
| number of leaves | |
| price per leaf (ccp_alpha) | |
| penalised error | |
| cost of finding the best split |
This section looks at three practical details of trees: how fast the best split can be found, how cost-complexity pruning works, and why the default feature-importance scores can mislead.
Finding the best split efficiently. For a numerical feature, the only thresholds worth trying lie between consecutive distinct values, since any threshold in the same gap produces the same split. So the algorithm sorts the examples by that feature, which takes time proportional to , and then sweeps through the sorted list once, moving one example at a time from the right group to the left and updating the class counts as it goes. Each candidate split can then be scored in constant time, so a whole sweep costs time proportional to . Doing this for all features gives a cost of roughly per level of the tree. Finding the single best possible tree, rather than growing one greedily, is an NP-hard problem, which is why every practical algorithm is greedy. Modern libraries such as LightGBM and scikit-learn's histogram-based estimators go further by grouping each feature's values into about 256 bins in advance, which makes split-finding roughly proportional to and much faster on large datasets.
Cost-complexity pruning. Breiman and colleagues proposed judging a subtree by its training error plus a charge for each of its leaves:
When , leaves are free and the full tree is best. As increases, leaves become expensive, and it pays to collapse branches whose improvement in training error is smaller than the cost of their extra leaves. For every value of there is a unique smallest subtree that minimises , and as increases these subtrees are nested, each one a pruned version of the previous. An efficient procedure called weakest-link pruning finds the whole sequence by repeatedly removing the branch that gives the smallest increase in error per leaf removed. We then choose the value of (and therefore the tree) with the best cross-validation score. In scikit-learn, cost_complexity_pruning_path returns the candidate values and ccp_alpha sets the chosen one.
Feature importance. Trees report a feature importance called mean decrease in impurity (MDI), which adds up, over every split that uses a feature, the impurity decrease weighted by the fraction of examples reaching that split. It is free to compute, but it has two weaknesses. It is calculated on the training data, so it rewards features the tree used to fit noise. And it is biased towards features with many distinct values, such as IDs or continuous measurements, because such features offer many more candidate thresholds and therefore more chances to find a split that looks good by luck. More reliable alternatives are permutation importance, which randomly shuffles one feature in held-out data and measures how much the model's score drops, and SHAP values, which share out each individual prediction fairly among the features.
Two more properties are worth knowing. Because splits only compare a feature with a threshold, trees are completely unaffected by any transformation that preserves order, such as taking a logarithm. And many modern implementations handle missing values directly, by learning, at each split, which branch examples with a missing value should follow.
Code: a split finder from scratch, and pruning in scikit-learn
The scratch code finds the best Gini split for one node, exactly as CART does at each step.
import numpy as np
def gini(y):
if len(y) == 0:
return 0.0
p = np.bincount(y) / len(y)
return 1 - np.sum(p ** 2)
def best_split(X, y):
best = (None, None, gini(y)) # (feature, threshold, impurity)
n = len(y)
for j in range(X.shape[1]):
order = np.argsort(X[:, j])
xs, ys = X[order, j], y[order]
for i in range(1, n):
if xs[i] == xs[i - 1]:
continue # no threshold between equal values
left, right = ys[:i], ys[i:]
imp = (i * gini(left) + (n - i) * gini(right)) / n
if imp < best[2]:
best = (j, (xs[i] + xs[i - 1]) / 2, imp)
return best
rng = np.random.default_rng(0)
X = rng.uniform(size=(200, 2))
y = ((X[:, 0] > 0.6) | (X[:, 1] > 0.8)).astype(int)
j, t, imp = best_split(X, y)
print(f"split on feature {j} at {t:.3f}: impurity {gini(y):.3f} -> {imp:.3f}")from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.inspection import permutation_importance
X, y = load_breast_cancer(return_X_y=True, as_frame=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, stratify=y, random_state=0)
full = DecisionTreeClassifier(random_state=0).fit(Xtr, ytr)
path = full.cost_complexity_pruning_path(Xtr, ytr) # candidate alphas
scores = [(a, cross_val_score(DecisionTreeClassifier(ccp_alpha=a, random_state=0),
Xtr, ytr, cv=5).mean()) for a in path.ccp_alphas[:-1]]
best_alpha = max(scores, key=lambda s: s[1])[0]
pruned = DecisionTreeClassifier(ccp_alpha=best_alpha, random_state=0).fit(Xtr, ytr)
print("leaves: full", full.get_n_leaves(), "-> pruned", pruned.get_n_leaves())
print("test acc: full", round(full.score(Xte, yte), 3), " pruned", round(pruned.score(Xte, yte), 3))
print(export_text(pruned, feature_names=list(X.columns), max_depth=2))
imp = permutation_importance(pruned, Xte, yte, n_repeats=10, random_state=0)
top = imp.importances_mean.argsort()[::-1][:5]
print([(c, round(float(v), 3)) for c, v in zip(X.columns[top], imp.importances_mean[top])])Quiz
1. A node containing only one class has Gini impurity…
2. Do decision trees need feature scaling?
3. A main weakness of a single decision tree is…
4. A node with 5 positives and 5 negatives has entropy…
5. Mean-decrease-in-impurity importance is biased toward…
📚 Further reading
Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.
- scikit-learn: Decision trees ↗ Official guide
- An Introduction to Statistical Learning (free book) ↗ James, Witten, Hastie, Tibshirani (Python edition available)