Decision Trees
A decision tree asks a series of yes/no questions about the features, splitting the data into purer and purer groups until each leaf predicts a single class.
Real-world examples: Medical diagnosis (symptom → test → diagnosis), credit approval (income, debt → approve/deny), customer segmentation.
How a tree grows
At each node, the tree picks the feature and threshold that best separates the classes:
- For each feature, try every possible split threshold
- Measure how "pure" the resulting groups are
- Pick the split that creates the purest children
- Repeat recursively until stopping criteria are met
Intuition
Think of 20 Questions. You ask the most informative question first ("Is it an animal?"), then narrow down based on the answer. A decision tree does the same with features — "Is age > 30?" → "Is income > 50K?" → approve/deny.
A running example
To make every formula concrete, we'll use one small loan-approval dataset for the rest of this lesson. Each applicant has a single feature, age, and a label: 1 = approved, 0 = denied.
| Age | 22 | 25 | 28 | 30 | 33 | 36 | 40 | 45 | 50 | 60 |
|---|---|---|---|---|---|---|---|---|---|---|
| Label | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
There are 5 approvals and 5 denials. The pattern is "older applicants tend to be approved," but it is noisy: a 33-year-old was approved while a 40-year-old was denied. A decision tree has to find the age threshold that best separates approvals from denials.
Impurity measures and split scoring
Gini impurity measures how mixed a node's labels are: , where is the fraction of class in the node. A Gini impurity of 0 means a pure node (one class only); 0.5 is maximum for binary problems. Entropy measures the same mixedness in bits (0 = pure, 1 = 50/50). In practice they produce nearly identical trees — Gini avoids the logarithm so sklearn defaults to it.
Information gain is the parent impurity minus the weighted average child impurity:
The tree tries every candidate threshold and picks the one with the highest gain. Quick check on the root node: with 5 approvals and 5 denials, (maximum impurity — even 50/50). Any split that produces purer children gives positive gain. For the full Gini/entropy formulas, a complete four-step "Age ≤ 31.5" split trace showing , and the gain table across all nine candidate thresholds on the loan-approval dataset, see:
Choosing a decision-tree split
A tree tries every threshold and keeps the one that makes the two sides purest — lowest weighted impurity. A pure group (all one class) has impurity 0.
import numpy as np
def gini(y):
_, counts = np.unique(y, return_counts=True)
p = counts / counts.sum()
return 1 - (p ** 2).sum()
def best_split(X, y):
best_gain = -1
best_feature, best_threshold = None, None
current_impurity = gini(y)
n = len(y)
for feature in range(X.shape[1]):
thresholds = np.unique(X[:, feature])
for threshold in thresholds:
left_mask = X[:, feature] <= threshold
right_mask = ~left_mask
if left_mask.sum() == 0 or right_mask.sum() == 0:
continue
weighted_impurity = (
left_mask.sum()/n * gini(y[left_mask]) +
right_mask.sum()/n * gini(y[right_mask])
)
gain = current_impurity - weighted_impurity
if gain > best_gain:
best_gain = gain
best_feature = feature
best_threshold = threshold
return best_feature, best_threshold
# Running this on our age dataset returns feature 0, threshold ~31.5
# with best_gain == 0.3333 — matching the hand calculation above.
Overfitting and pruning
Left unconstrained, a tree keeps splitting until every leaf is pure — even if that means isolating individual noisy points. On our dataset, a greedy tree would carve out a separate leaf just for the lone denied 40-year-old, reaching 100% training accuracy by memorizing noise. That tree is overfit: it will mislabel the next 40-year-old who does get approved.
The symptom is a gap between training and test accuracy:
| Tree | Train accuracy | Test accuracy |
|---|---|---|
| Unconstrained (deep) | ~1.00 | ~0.75 |
max_depth=2 | ~0.90 | ~0.85 |
High train, much lower test → the tree learned the training set's quirks instead of the underlying pattern.
There are two ways to fight this:
1. Pre-pruning (early stopping). Stop growing before the tree gets too complex:
| Criterion | Effect |
|---|---|
max_depth | Limit tree depth (most important) |
min_samples_split | Require a minimum number of samples to even attempt a split |
min_samples_leaf | Require a minimum number of samples in each resulting leaf |
max_features | Consider only a random subset of features at each node |
2. Post-pruning (cost-complexity pruning). Grow the full tree, then collapse branches whose accuracy gain does not justify their added complexity. sklearn exposes this via the ccp_alpha parameter — larger values prune more aggressively.
# The idiom (for your own X_train / y_train / X_test / y_test):
from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(
max_depth=4,
min_samples_split=10,
min_samples_leaf=5,
random_state=42
)
tree.fit(X_train, y_train)
print(f"Train accuracy: {tree.score(X_train, y_train):.3f}")
print(f"Test accuracy: {tree.score(X_test, y_test):.3f}")
Feature importance
A feature's importance is the total reduction in impurity it causes across all splits:
importances = tree.feature_importances_ # from the fitted tree above
indices = np.argsort(importances)[::-1]
for i in range(min(5, len(indices))):
print(f"Feature {indices[i]}: {importances[indices[i]]:.3f}")
Strengths and weaknesses
| ✅ Strengths | ❌ Weaknesses |
|---|---|
| Highly interpretable | Prone to overfitting |
| No feature scaling needed | Unstable (small data changes → different tree) |
| Handles mixed feature types | Biased toward high-cardinality features |
| Fast training and prediction | Cannot extrapolate (only interpolates) |
| Captures non-linear relationships | Greedy: locally optimal ≠ globally optimal |
The instability problem
Decision trees are highly sensitive to small changes in data. Removing a single training point can completely change the tree structure. This is why ensemble methods (Random Forests, Gradient Boosting) are almost always preferred in practice.
Exercise
A node has 60 positive and 40 negative examples. What is the Gini impurity?
Need a hint?
Gini = 1 - Σ p_k². Here p_pos = 0.6, p_neg = 0.4.
Exercise
Information gain is computed as the reduction in what after a split?
Need a hint?
It measures the decrease in uncertainty.
Exercise
What is the main reason to prune a decision tree?
Need a hint?
Think about what happens to an unpruned tree on test data.
Common mistakes
- Not pruning: An unpruned tree overfits. Always set
max_depthor use pruning. - Using for linear relationships: Decision trees create axis-parallel boundaries. They struggle with diagonal decision boundaries.
- Ignoring class imbalance: Trees can be biased toward majority classes. Use
class_weight='balanced'.
Key takeaways
- Trees split greedily on the feature/threshold that most reduces impurity (Gini or entropy).
- Information gain = parent impurity − weighted child impurity.
- Unconstrained trees overfit; limit
max_depth/min_samples_leafor prune. - Interpretable and scale-free, but high-variance alone — hence ensembles.
Related concepts
- K-Nearest Neighbors: the other non-parametric baseline in this course
- Bagging & Random Forests: averaging many trees to cut variance
- Boosting: building trees sequentially to cut bias