Decision TreesOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

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:

  1. For each feature, try every possible split threshold
  2. Measure how "pure" the resulting groups are
  3. Pick the split that creates the purest children
  4. 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.

Age22252830333640455060
Label0000110111

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: IG=1−∑kpk2I_G = 1 - \sum_k p_k^2, where pkp_k is the fraction of class kk 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:

IG=I(parent)−(nLnI(left)+nRnI(right))\text{IG} = I(\text{parent}) - \left(\frac{n_L}{n}I(\text{left}) + \frac{n_R}{n}I(\text{right})\right)

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, Gini(root)=1−(0.52+0.52)=0.5\text{Gini}(\text{root}) = 1 - (0.5^2 + 0.5^2) = 0.5 (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 IG≈0.33\text{IG} \approx 0.33, and the gain table across all nine candidate thresholds on the loan-approval dataset, see:

Deep dive
Decision Tree: Information Gain
Includes runnable notebook

Choosing a decision-tree split

best≤ threshold> threshold
gini impurity0.077
min impurity0.077

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.

Python
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:

TreeTrain accuracyTest 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:

CriterionEffect
max_depthLimit tree depth (most important)
min_samples_splitRequire a minimum number of samples to even attempt a split
min_samples_leafRequire a minimum number of samples in each resulting leaf
max_featuresConsider 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.

Python
# 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:

Importance(j)=∑splits on jnnodentotal⋅ΔGini\text{Importance}(j) = \sum_{\text{splits on } j} \frac{n_{\text{node}}}{n_{\text{total}}} \cdot \Delta \text{Gini}
Python
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 interpretableProne to overfitting
No feature scaling neededUnstable (small data changes → different tree)
Handles mixed feature typesBiased toward high-cardinality features
Fast training and predictionCannot extrapolate (only interpolates)
Captures non-linear relationshipsGreedy: 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

  1. Not pruning: An unpruned tree overfits. Always set max_depth or use pruning.
  2. Using for linear relationships: Decision trees create axis-parallel boundaries. They struggle with diagonal decision boundaries.
  3. 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_leaf or prune.
  • Interpretable and scale-free, but high-variance alone — hence ensembles.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Decision TreesLinear & Logistic Regress…Entropy & KL DivergenceK-Nearest NeighborsBagging & Random ForestsBoostingThe Bias–Variance TradeoffAlgorithms from ScratchDecision Tree: Informatio…Concordance: the c-statis…