Definition
How would you guess an animal in five yes-or-no questions?
A decision tree predicts by asking a sequence of feature-threshold questions, from the root to a leaf. CART builds it greedily: at each node it chooses the split that most reduces impurity, measured by Gini impurity or entropy (information gain) for classification, or variance for regression. Trees grow until a stopping rule, and pruning removes branches that don't improve validation performance.
In simple words
At each step, ask the question that splits the group into the purest halves: 'Is the tumour radius above 16?' might send nearly all malignant cases one way. Gini measures mixedness: 0 means everyone in the group has the same label. A tree that keeps splitting until every leaf is pure has memorised the training data.
Why it matters
Trees handle mixed feature types, need no scaling, capture interactions and can be read as rules. They are also the building blocks of random forests and gradient boosting, the strongest methods for tabular data.
Key terms
- Root, internal node and leaf
- The first split, the splits below it, and the end nodes that give predictions.
- Gini impurity
- 1 − Σpₖ²: the chance of mislabelling a random item if labelled by the node's class mix.
- Entropy and information gain
- Entropy −Σpₖ log₂pₖ measures disorder; information gain is its reduction after a split.
- Pre-pruning
- Stopping growth early with limits such as max_depth or min_samples_leaf.
- Cost-complexity pruning
- Growing a full tree, then removing branches whose gain does not justify their size (ccp_alpha).
- Regression tree
- A tree whose leaves predict the average target of the training rows that reach them.
Explained in detail
Choosing splits with numbers
Imagine 10 loan applicants, 6 who repaid and 4 who did not. The root's Gini impurity is 1 − (0.6² + 0.4²) = 0.48. Splitting on "income above ₹30,000" sends 5 applicants left (5 repaid, 0 defaulted, Gini 0) and 5 right (1 repaid, 4 defaulted, Gini 1 − (0.2² + 0.8²) = 0.32). The weighted impurity after the split is 0.5 × 0 + 0.5 × 0.32 = 0.16, a reduction of 0.32. The algorithm tries every feature and threshold, picks the largest reduction, and repeats on each child until a stopping rule is met. Regression trees use the reduction in variance or squared error instead, and each leaf predicts the mean of its rows.
Controlling a tree's complexity
| Hyperparameter | Effect | Typical range |
|---|---|---|
| max_depth | Limits the number of questions on any path | 3 to 15 |
| min_samples_leaf | Each leaf must contain at least this many rows | 5 to 100 |
| min_samples_split | A node needs this many rows to be split | 10 to 200 |
| max_features | Number of features considered at each split | sqrt(p) for forests |
| ccp_alpha | Strength of post-pruning | Chosen by cross-validation |
Trees capture interactions and non-linear patterns automatically, need no scaling and handle mixed feature types, which is why they underpin the most successful tabular methods: random forests and gradient boosting. Their weaknesses are high variance, where a small change in data can change the root split and the whole tree, and axis-aligned splits that approximate diagonal boundaries with staircases. Feature importance from trees, based on total impurity reduction, is biased towards features with many unique values; permutation importance on validation data is more reliable. For explanation, a shallow tree of depth 3 or 4 can be printed and read as plain if-then rules, which makes it popular in medicine and policy.
A familiar scenario is a hospital triage rule: "If oxygen saturation is below 92 per cent, admit; otherwise, if the patient is over 65 and has a fever, observe; otherwise, discharge with advice." Such rules can be learned as a decision tree from past cases and then reviewed by doctors line by line. Banks use similar shallow trees for credit decisions because each refusal can be traced to specific conditions. When accuracy matters more than readability, the same trees become the building blocks of random forests and gradient boosting.
How it works
- For every feature and every candidate threshold, compute the weighted impurity of the two children.
- Choose the split with the largest impurity decrease.
- Recurse on each child until max_depth, min_samples_leaf or purity stops it.
- Prune: limit depth or use cost-complexity pruning (ccp_alpha) chosen by validation.
The maths
- Share of class k in the node
A node holds 6 positives and 4 negatives. Gini = 1 − (0.6² + 0.4²) = 0.48. A split sends 5 positives and 1 negative left, and 1 positive and 3 negatives right.
Left: 1 − ((5/6)² + (1/6)²) = 0.278 (6 samples) Right: 1 − ((1/4)² + (3/4)²) = 0.375 (4 samples) Weighted = 0.6 × 0.278 + 0.4 × 0.375 = 0.317 Decrease = 0.48 − 0.317 = 0.163
In code
The Gini split above computed by hand, then a scikit-learn tree whose depth controls overfitting, with its top rules printed.
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text
def gini(counts):
p = np.array(counts) / sum(counts)
return 1 - np.sum(p ** 2)
parent = gini([6, 4])
weighted = 0.6 * gini([5, 1]) + 0.4 * gini([1, 3])
print(f"Parent Gini {parent:.3f}, children {weighted:.3f}, decrease {parent - weighted:.3f}")
data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(data.data, data.target, test_size=0.3, random_state=0)
print("depth train acc test acc leaves")
for depth in [1, 2, 4, 8, None]:
tree = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(X_tr, y_tr)
print(f"{str(depth):>5} {tree.score(X_tr, y_tr):9.3f} {tree.score(X_te, y_te):8.3f} {tree.get_n_leaves():>6}")
small = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_tr, y_tr)
print(export_text(small, feature_names=list(data.feature_names)))Output
Parent Gini 0.480, children 0.317, decrease 0.163
depth train acc test acc leaves
1 0.930 0.895 2
2 0.960 0.947 4
4 0.977 0.947 10
8 1.000 0.912 19
None 1.000 0.912 19
|--- worst concave points <= 0.14
| |--- worst area <= 952.90
| | |--- class: 1
| |--- worst area > 952.90
| | |--- class: 0
|--- worst concave points > 0.14
| |--- area error <= 13.93
| | |--- class: 1
| |--- area error > 13.93
| | |--- class: 0Try it yourself
Compute Gini
Match each node's class counts to its Gini impurity.
- 10 positives, 0 negatives
- 5 positives, 5 negatives
- 8 positives, 2 negatives
- Three classes, equal shares
Common mistakes
- Growing trees with no depth limit and trusting their training accuracy.
- Reading the first split as the only important feature. Correlated features can swap places.
- Expecting smooth predictions. Trees make step functions.
Check yourself
Summary
- Trees split greedily to reduce Gini or entropy.
- They need no scaling and read as rules.
- Control depth or prune to avoid memorising the data.
Read it. Now try it yourself.
Open the interactive activityFinished reading?
Sources: scikit-learn: Decision trees · James et al., An Introduction to Statistical Learning