Definition
A decision tree predicts by asking a sequence of yes/no questions about single features — is ? or is Outlook = Sunny? — until it reaches a leaf, which outputs the majority class (classification) or the mean target (regression) of the training points that ended there.
At a glance
- Task
- Classification and regression
- Input → output
- → the prediction stored in the leaf falls into
- Learns
- a feature and threshold per internal node; a value (or class distribution) per leaf
- Split criterion
- entropy / information gain (ID3, C4.5), Gini impurity (CART), variance / MSE (regression)
- Training
- greedy, top-down; about per level with pre-sorted features
- Prediction
- comparisons
- Hyperparameters
- max depth, min samples per split / leaf, criterion, pruning strength α
- Assumes
- nothing about distributions; decision boundaries are axis-aligned
The problem
Many real decisions look like rules: if income < 30k and debt > 10k, then high risk. A linear model cannot express thresholds and interactions like this without hand-made features. We want a model that discovers such rules from data — and that a person can read and audit.
Anatomy of a tree
Vocabulary
- Root node
- the first question; it sees the whole training set
- Internal node
- a question feature threshold? (numeric) or feature = value? (categorical)
- Branch
- one answer to a node's question; it routes a subset of the data to a child
- Leaf
- a node with no question; it stores the prediction
- Depth
- number of questions on the longest root-to-leaf path
- Rule
- the conjunction of answers along one root-to-leaf path
Definition
A pure node contains training points of only one class. Its impurity is 0 by every measure — there is nothing left to separate — so a pure node always becomes a leaf. The whole algorithm is a search for questions that make the children purer than their parent.
Measuring impurity
To pick a question we need a number that says how mixed a node is. Let be the fraction of points in node that belong to class . Three measures are used; all are 0 for a pure node and largest for an even mix.
- entropy of node S, in bits
- fraction of class in (with )
Entropy is the average number of bits needed to encode the class of a random point from the node. For two classes it ranges from 0 (pure) to 1 bit (50/50); with classes the maximum is . Example: 9 Yes and 5 No gives bits.
- Gini impurity of node S
Gini impurity is the probability that two points drawn at random (with replacement) from the node have different classes — equivalently, the error rate if you labelled points randomly according to . It ranges from 0 to (0.5 for two classes). Same 9/5 node: .
Misclassification error is the error of predicting the majority. It is what we ultimately care about, but it is a poor splitting criterion: it is piecewise linear, so many splits that clearly improve purity leave it unchanged.
node: 6 A / 14 B · mixed
Information gain: scoring a split
A split sends the parent's points into children . We score it by how much impurity it removes, weighting each child by its share of the points — a tiny pure child should not count as much as a large one.
- the attribute (or threshold test) being split on
- subset of where takes value
- weight: fraction of the parent's points sent to that child
The second term is the weighted child entropy (the "remainder"). Information gain is how many bits of uncertainty about the label the question removes, on average. With Gini, the same recipe gives the Gini decrease . The greedy rule is simply: pick the split with the largest gain.
Worked example: should we play tennis?
The classic dataset from Quinlan's ID3 paper: 14 days, four categorical features, and whether tennis was played. 9 days are Yes and 5 are No, so the root entropy is bits.
| Day | Outlook | Temp | Humidity | Wind | Play |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| 3 | Overcast | Hot | High | Weak | Yes |
| 4 | Rain | Mild | High | Weak | Yes |
| 5 | Rain | Cool | Normal | Weak | Yes |
| 6 | Rain | Cool | Normal | Strong | No |
| 7 | Overcast | Cool | Normal | Strong | Yes |
| 8 | Sunny | Mild | High | Weak | No |
| 9 | Sunny | Cool | Normal | Weak | Yes |
| 10 | Rain | Mild | Normal | Weak | Yes |
| 11 | Sunny | Mild | Normal | Strong | Yes |
| 12 | Overcast | Mild | High | Strong | Yes |
| 13 | Overcast | Hot | Normal | Weak | Yes |
| 14 | Rain | Mild | High | Strong | No |
Gain of Outlook at the root
- 1Split by value: Sunny 2 Yes / 3 No, Overcast 4 Yes / 0 No, Rain 3 Yes / 2 No.
- 2Child entropies: ; — a pure node.
- 3Weighted child entropy: .
- 4Information gain: bits.
| Attribute | Children (Yes/No) | Weighted entropy | Information gain | Gini decrease |
|---|---|---|---|---|
| Outlook | Sunny 2/3 · Overcast 4/0 · Rain 3/2 | 0.694 | 0.247 | 0.116 |
| Humidity | High 3/4 · Normal 6/1 | 0.789 | 0.152 | 0.092 |
| Wind | Weak 6/2 · Strong 3/3 | 0.892 | 0.048 | 0.031 |
| Temp | Hot 2/2 · Mild 4/2 · Cool 3/1 | 0.911 | 0.029 | 0.019 |
So the root asks about Outlook. The Overcast branch is pure and becomes a Yes leaf. The other two branches recurse on their own subsets, with Outlook removed from the candidates:
The recursion
- Sunny (5 days)
- . Humidity: High 0/3, Normal 2/0 — both children pure, gain (the maximum possible). Temp gains 0.571, Wind 0.020. → split on Humidity.
- Rain (5 days)
- . Wind: Weak 3/0, Strong 0/2 — both pure, gain . Temp and Humidity each gain only 0.020. → split on Wind.
- Result
- 5 leaves, all pure, using 3 of the 4 features. Temperature is never asked.
| # | Outlook | Temp | Humidity | Wind | Play |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| 3 | Overcast | Hot | High | Weak | Yes |
| 4 | Rain | Mild | High | Weak | Yes |
| 5 | Rain | Cool | Normal | Weak | Yes |
| 6 | Rain | Cool | Normal | Strong | No |
| 7 | Overcast | Cool | Normal | Strong | Yes |
| 8 | Sunny | Mild | High | Weak | No |
| 9 | Sunny | Cool | Normal | Weak | Yes |
| 10 | Rain | Mild | Normal | Weak | Yes |
| 11 | Sunny | Mild | Normal | Strong | Yes |
| 12 | Overcast | Mild | High | Strong | Yes |
| 13 | Overcast | Hot | Normal | Weak | Yes |
| 14 | Rain | Mild | High | Strong | No |
- 1id3(S, attrs):
- 2 if S is pure: return leaf
- 3 H(S) ← −Σ p log₂ p
- 4 for each attribute A:
- 5 gain(A) ← H(S) − Σ |Sᵥ|/|S|·H(Sᵥ)
- 6 split on A* = argmax gain
- 7 for each value v: id3(Sᵥ, attrs − A*)
Root: 14 days (9 Yes / 5 No). H = −9/14·log₂(9/14) − 5/14·log₂(5/14) = 0.940 bits.
Read off the rules: if Outlook = Overcast → play; if Sunny and Humidity = Normal → play; if Rain and Wind = Weak → play; otherwise don't. Each one is a root-to-leaf path.
Numeric features: choosing a threshold
For a numeric feature the question is . Only thresholds between consecutive sorted values can change the split, so CART sorts the values and tries every midpoint — candidates per feature — keeping the one with the best gain. With pre-sorting, one feature is scanned in by moving points from right to left one at a time and updating class counts.
The algorithm, step by step
Grow(node)
- 1Stop? If the node is pure, has fewer than
min_samples_splitpoints, or is atmax_depth, make it a leaf: predict the majority class (and store the class proportions). - 2Search. For every feature and every candidate threshold (or category), compute the weighted child impurity.
- 3Choose. Keep the split with the largest impurity decrease. If even the best one decreases impurity by less than
min_impurity_decrease, make a leaf instead. - 4Recurse on each child with the subset of points routed to it.
- 1grow(node):
- 2 if pure or depth = max: leaf
- 3 for each feature f, threshold t:
- 4 score ← weighted Gini(L, R)
- 5 split on best (f, t)
- 6 grow(L); grow(R)
Root: 40 points (20 A / 20 B), Gini = 1 − (0.50² + 0.50²) = 0.500.
This is greedy: each split is the best one now, not necessarily the best for the final tree — finding the optimal tree is NP-hard. Greedy works well in practice, and ensembles fix most of its weaknesses.
Regression trees
For a numeric target, a leaf predicts the mean of its points, and impurity is their variance (mean squared error around that mean). The split criterion becomes variance reduction:
| Split | Left mean (var) | Right mean (var) | Weighted var | Reduction |
|---|---|---|---|---|
| x ≤ 1.5 | 5.00 (0.00) | 14.80 (58.16) | 48.47 | 13.34 |
| x ≤ 2.5 | 5.50 (0.25) | 17.00 (48.50) | 32.42 | 29.39 |
| x ≤ 3.5 | 5.33 (0.22) | 21.00 (0.67) | 0.44 | 61.36 |
| x ≤ 4.5 | 9.00 (40.50) | 21.50 (0.25) | 27.08 | 34.72 |
| x ≤ 5.5 | 11.60 (59.44) | 21.00 (0.00) | 49.53 | 12.27 |
The fitted function is a step function: constant within each leaf. More depth means more, narrower steps.
Overfitting and pruning
Left alone, a tree keeps splitting until every leaf is pure — 100% training accuracy, with the last splits fitting noise. Two remedies:
Controlling complexity
- Pre-pruning
- stop early:
max_depth,min_samples_leaf,min_samples_split,max_leaf_nodes,min_impurity_decrease. Cheap, but may stop before a split that would have enabled a great one below it. - Post-pruning
- grow the full tree, then cut back subtrees that don't pay for themselves on held-out data.
- training error (or impurity) of tree T
- number of leaves
- price per leaf; larger α → smaller tree
Cost-complexity pruning (CART) charges per leaf. As grows from 0, the subtree whose removal costs the least error per leaf saved is pruned first, giving a nested sequence of ever-smaller trees. Pick by cross-validation — scikit-learn exposes it as ccp_alpha.
In code
1import numpy as np23def entropy(y):4 p = np.bincount(y) / len(y)5 p = p[p > 0]6 return -(p * np.log2(p)).sum()78def gini(y):9 p = np.bincount(y) / len(y)10 return 1 - (p ** 2).sum()1112def best_split(X, y, impurity):13 parent, best = impurity(y), (0.0, None, None) # (gain, feature, threshold)14 for j in range(X.shape[1]):15 v = np.unique(X[:, j])16 for t in (v[:-1] + v[1:]) / 2: # midpoints17 L = X[:, j] <= t18 child = (L.sum() * impurity(y[L]) + (~L).sum() * impurity(y[~L])) / len(y)19 if parent - child > best[0]:20 best = (parent - child, j, t)21 return best2223def grow(X, y, impurity=entropy, depth=0, max_depth=3, min_leaf=1):24 gain, j, t = best_split(X, y, impurity)25 if depth == max_depth or impurity(y) == 0 or j is None or len(y) < 2 * min_leaf:26 return {"leaf": np.bincount(y).argmax(), "n": len(y)}27 L = X[:, j] <= t28 return {"feature": j, "threshold": t, "gain": gain,29 "left": grow(X[L], y[L], impurity, depth + 1, max_depth, min_leaf),30 "right": grow(X[~L], y[~L], impurity, depth + 1, max_depth, min_leaf)}3132def predict(node, x):33 while "leaf" not in node:34 node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]35 return node["leaf"]1import pandas as pd2from sklearn.tree import DecisionTreeClassifier, export_text34df = pd.DataFrame({5 "Outlook": "Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain".split(),6 "Temp": "Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild".split(),7 "Humidity": "High High High High Normal Normal Normal High Normal Normal Normal High Normal High".split(),8 "Wind": "Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong".split(),9 "Play": "No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No".split(),10})11X = pd.get_dummies(df.drop(columns="Play"))12tree = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(X, df.Play)13print(export_text(tree, feature_names=list(X.columns)))1415# Choosing the pruning strength on real data:16# path = DecisionTreeClassifier().cost_complexity_pruning_path(X_train, y_train)17# then cross-validate over path.ccp_alphasUse when
- +Every prediction must be explainable — the path is a readable rule.
- +Mixed numeric and categorical features; no scaling needed; thresholds and interactions found automatically.
- +You need a fast baseline, or the building block for random forests and gradient boosting.
Avoid when
- −You need accuracy from a single model: a deep tree overfits, a shallow one underfits.
- −Stability matters: a small change in the data can produce a completely different tree.
- −The true boundary is smooth or diagonal: axis-aligned splits approximate it with a staircase.
- −You need to extrapolate: a regression tree can never predict outside the range of its training targets.
Where it's used
Medical triage & credit policy
Rules that must be audited and explained to regulators or patients.
Feature exploration
The first few splits reveal which variables matter most, and at which thresholds.
Business rules
Turn historical decisions into explicit if-then logic.
Inside ensembles
Random forests, XGBoost, LightGBM and CatBoost are all built from trees.
Check yourself
A node holds 8 points, 4 of each class. Its entropy and Gini impurity are…
Check yourself
A parent has entropy 1.0. A split sends 6 points to a pure child and 2 points to a 50/50 child. The information gain is…
Check yourself
Why does C4.5 use the gain ratio instead of raw information gain?
Check yourself
Which preprocessing does a decision tree require?
Remember
- ✓Impurity measures how mixed a node is: entropy (bits), Gini, or variance for regression. A pure node has impurity 0 and becomes a leaf.
- ✓Information gain = parent impurity − size-weighted child impurity; greedily split on the largest gain.
- ✓Weighted child entropy equals the tree's training cross-entropy, so maximizing gain minimizes log-loss.
- ✓Numeric features: try midpoints between sorted values. Categorical: one branch per value (ID3) or binary groupings (CART).
- ✓Limit depth / leaf size or prune with cost-complexity α; use ensembles when you need accuracy.