🎯 What You'll Learn

  • Understand the tree structure: root nodes, decision nodes, and leaf nodes for classification and regression
  • Compute Gini impurity and entropy, and understand why these guide split selection
  • Train DecisionTreeClassifier and DecisionTreeRegressor with scikit-learn
  • Visualize a trained tree with plot_tree and export_text
  • Control overfitting using max_depth, min_samples_split, and min_samples_leaf

1 The Decision Tree Intuition

A decision tree mimics how humans naturally make decisions: a series of yes/no questions that narrow down possibilities until you reach a conclusion. "Is the customer's monthly charge above $70?" → Yes → "Is their contract month-to-month?" → Yes → Predict: high churn risk. This flowchart structure is completely transparent — you can follow every path from input to prediction.

Structurally, a decision tree consists of:

  • Root node: the very first split — chosen to be the most informative question across all features
  • Internal (decision) nodes: subsequent split points, each testing one feature against a threshold
  • Leaf nodes: terminal nodes that return a prediction (majority class for classification, mean value for regression)

The same algorithm handles both classification (DecisionTreeClassifier) and regression (DecisionTreeRegressor). The only difference is the split criterion and the leaf prediction.

In [1]:
import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# Quick demo: Iris classification
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# A shallow tree — interpretable
tree = DecisionTreeClassifier(max_depth=3, random_state=42)
tree.fit(X_train, y_train)

print(f"Training accuracy: {tree.score(X_train, y_train):.4f}")
print(f"Test accuracy:     {tree.score(X_test, y_test):.4f}")
print(f"Number of leaves:  {tree.get_n_leaves()}")
print(f"Tree depth:        {tree.get_depth()}")

# Human-readable text representation
print("\n" + export_text(tree, feature_names=iris.feature_names))
# |--- petal length (cm) <= 2.45
# |   |--- class: 0              ← setosa: pure leaf
# |--- petal length (cm) >  2.45
# |   |--- petal width (cm) <= 1.75
# |   |   |--- petal length (cm) <= 4.95
# |   |   |   |--- class: 1
# ...
# A human can verify every rule by reading the output above
🔑
Interpretability Is a First-Class Feature

Decision trees are one of the few ML models that are genuinely interpretable by non-technical stakeholders. A doctor, judge, or loan officer can read a shallow decision tree and understand exactly why a decision was made — and potentially challenge it. This interpretability has real legal and ethical value in high-stakes applications.

2 How Trees Split: Gini Impurity

At each internal node, the algorithm searches every feature and every possible threshold to find the split that best separates the classes. "Best" is defined by a measure of impurity. The default in scikit-learn is Gini impurity.

For a node containing samples from K classes, where pᵢ is the fraction of class i:

Gini = 1 − Σ pᵢ²

A pure node (all samples same class) has Gini = 0 (perfect). An equal split of two classes (50/50) has Gini = 0.5 (worst for binary). The algorithm greedily picks the split that minimises the weighted average child Gini across left and right subtrees.

In [2]:
import numpy as np

def gini_impurity(counts):
    """Compute Gini from a list of class counts."""
    total = sum(counts)
    if total == 0:
        return 0.0
    probs = [c / total for c in counts]
    return 1.0 - sum(p**2 for p in probs)

def weighted_gini(left_counts, right_counts):
    """Weighted Gini after a split: two child nodes."""
    n_left  = sum(left_counts)
    n_right = sum(right_counts)
    n_total = n_left + n_right
    g_left  = gini_impurity(left_counts)
    g_right = gini_impurity(right_counts)
    return (n_left / n_total) * g_left + (n_right / n_total) * g_right

# Before split: 100 samples, 60 class-A, 40 class-B
parent_gini = gini_impurity([60, 40])
print(f"Parent Gini: {parent_gini:.4f}")   # 0.4800

# Split option 1: left=[50A, 10B], right=[10A, 30B]
w1 = weighted_gini([50, 10], [10, 30])
print(f"Split 1 weighted Gini: {w1:.4f}")  # 0.2917  ← better split

# Split option 2: left=[30A, 20B], right=[30A, 20B]  (no improvement)
w2 = weighted_gini([30, 20], [30, 20])
print(f"Split 2 weighted Gini: {w2:.4f}")  # 0.4800  ← no improvement

# Impurity reduction (Gini gain) for each split
print(f"\nGini gain split 1: {parent_gini - w1:.4f}")  # 0.1883 ← choose this
print(f"Gini gain split 2: {parent_gini - w2:.4f}")  # 0.0000 ← useless split

# Verify: pure node
print(f"\nPure node  Gini: {gini_impurity([100, 0]):.4f}")   # 0.0000
print(f"Equal split Gini: {gini_impurity([50, 50]):.4f}")  # 0.5000
print(f"3-class even Gini: {gini_impurity([33, 33, 34]):.4f}")  # ~0.6667

Each internal node in the diagram below is literally an if feature > threshold test. Following a path from the root to a leaf is the same as evaluating a chain of these tests — the leaf at the end is the model's prediction, and its Gini value shows how "pure" (confident) that prediction is:

Yes No Yes No Yes No Yes No Root: tests the most informative feature first petal_width ≤ 0.8 cm ? Pure node: all samples are setosa leaf: Setosa Gini = 0.00 (pure) Internal node: splits the remaining two classes petal_length ≤ 4.9 cm ? Mostly pure leaf leaf: Setosa Gini = 0.00 (pure) Mostly pure leaf leaf: Versicolor Gini = 0.04 Another internal split: separates the last two classes petal_width ≤ 1.75 cm ? Impure leaf: a mix of versicolor and virginica leaf: Versicolor Gini = 0.17 Mostly pure leaf: dominated by virginica leaf: Virginica Gini = 0.04

A depth-3 tree on the Iris dataset. Every internal node (blue/violet) is an if feature ≤ threshold test; following "Yes"/"No" down any path lands on a leaf (green = near-pure, amber = still mixed) that returns the majority class. The root's question — petal width ≤ 0.8cm — perfectly separates setosa in one split, which is why it was chosen first: it has the largest Gini gain of any possible split.

3 Entropy & Information Gain

Entropy is an alternative impurity measure rooted in information theory. It quantifies the uncertainty in a node's class distribution:

Entropy = −Σ pᵢ · log₂(pᵢ)

Information Gain is the reduction in entropy achieved by a split:

IG = Entropy(parent) − weighted average Entropy(children)

Practically, Gini and Entropy usually produce very similar trees. Gini is slightly faster to compute (no logarithm). Choose criterion='entropy' if you want Information Gain explicitly.

In [3]:
import numpy as np

def entropy(counts):
    total = sum(counts)
    if total == 0:
        return 0.0
    result = 0.0
    for c in counts:
        if c > 0:
            p = c / total
            result -= p * np.log2(p)
    return result

def information_gain(parent_counts, left_counts, right_counts):
    n_left  = sum(left_counts)
    n_right = sum(right_counts)
    n_total = n_left + n_right
    parent_entropy  = entropy(parent_counts)
    weighted_child  = (n_left / n_total) * entropy(left_counts) + \
                      (n_right / n_total) * entropy(right_counts)
    return parent_entropy - weighted_child

# Parent: 60 class-A, 40 class-B
parent_e = entropy([60, 40])
print(f"Parent entropy: {parent_e:.4f} bits")  # 0.9710 bits

# Two candidate splits
ig1 = information_gain([60, 40], [50, 10], [10, 30])
ig2 = information_gain([60, 40], [30, 20], [30, 20])
print(f"Information gain split 1: {ig1:.4f}")  # 0.2830 ← better
print(f"Information gain split 2: {ig2:.4f}")  # 0.0000

# Compare Gini vs Entropy in sklearn
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

X_bc, y_bc = load_breast_cancer(return_X_y=True)
X_btr, X_bte, y_btr, y_bte = train_test_split(X_bc, y_bc, test_size=0.2, random_state=42)

for criterion in ['gini', 'entropy']:
    dt = DecisionTreeClassifier(criterion=criterion, max_depth=5, random_state=42)
    dt.fit(X_btr, y_btr)
    print(f"criterion='{criterion:7s}': train={dt.score(X_btr, y_btr):.4f}  test={dt.score(X_bte, y_bte):.4f}")
# criterion='gini   ': train=0.9890  test=0.9298
# criterion='entropy': train=0.9890  test=0.9298  ← nearly identical
💡
Gini vs Entropy: Which to Use?

In practice they produce almost identical trees and nearly the same accuracy. Use Gini (the default) unless you have a specific reason not to. Entropy is slightly more expensive to compute (requires log₂) but can produce marginally better-balanced trees on some problems. The hyperparameter that matters far more is max_depth.

4 Regression Trees

For regression, the mechanism is the same but the criterion changes. Instead of impurity, we minimize mean squared error (MSE) — equivalently, we maximize variance reduction. The leaf prediction is the mean of all target values that fall in that leaf.

In [4]:
from sklearn.tree import DecisionTreeRegressor
from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_absolute_error, r2_score
import numpy as np

housing = fetch_california_housing()
X_h, y_h = housing.data, housing.target
X_htr, X_hte, y_htr, y_hte = train_test_split(X_h, y_h, test_size=0.2, random_state=42)

print(f"{'max_depth':>12}  {'Train R²':>10}  {'Test R²':>10}  {'Test MAE':>10}")
print("-" * 50)
for depth in [None, 3, 5, 7, 10, 15]:
    reg = DecisionTreeRegressor(max_depth=depth, random_state=42)
    reg.fit(X_htr, y_htr)
    r2_train = r2_score(y_htr, reg.predict(X_htr))
    r2_test  = r2_score(y_hte, reg.predict(X_hte))
    mae_test = mean_absolute_error(y_hte, reg.predict(X_hte))
    depth_label = str(depth) if depth else 'None(full)'
    print(f"{depth_label:>12}  {r2_train:>10.4f}  {r2_test:>10.4f}  {mae_test:>10.4f}")

# max_depth  Train R²   Test R²   Test MAE
# None(full) 1.0000     0.5998    0.4362  ← perfect train, poor test = overfit
#          3 0.5867     0.5629    0.5598
#          5 0.8089     0.6771    0.4218
#          7 0.9259     0.7051    0.3876  ← best test performance
#         10 0.9838     0.6712    0.4106
#         15 0.9990     0.6148    0.4280  ← overfit again

# A depth-7 tree achieves a good test R² without memorizing training data

5 Training a Decision Tree with scikit-learn

Here is a complete training and evaluation workflow for DecisionTreeClassifier, including the key hyperparameters you'll use in practice:

In [5]:
import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report, confusion_matrix

np.random.seed(42)
X, y = make_classification(
    n_samples=5000, n_features=15, n_informative=8,
    n_redundant=4, n_clusters_per_class=2, random_state=42
)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42)

# Full, unconstrained tree — will overfit
tree_full = DecisionTreeClassifier(random_state=42)
tree_full.fit(X_train, y_train)
print(f"Unconstrained — Train: {tree_full.score(X_train, y_train):.4f}  "
      f"Test: {tree_full.score(X_test, y_test):.4f}  "
      f"Depth: {tree_full.get_depth()}")

# Constrained tree — better generalization
tree_pruned = DecisionTreeClassifier(
    max_depth=8,           # limits tree depth
    min_samples_split=20,  # a node needs ≥20 samples to be split
    min_samples_leaf=10,   # each leaf must have ≥10 samples
    max_features=0.8,      # consider 80% of features at each split
    criterion='gini',
    random_state=42
)
tree_pruned.fit(X_train, y_train)
print(f"Pruned         — Train: {tree_pruned.score(X_train, y_train):.4f}  "
      f"Test: {tree_pruned.score(X_test, y_test):.4f}  "
      f"Depth: {tree_pruned.get_depth()}")

y_pred = tree_pruned.predict(X_test)
print("\nClassification Report:")
print(classification_report(y_test, y_pred))

# Feature importances
feature_imp = pd.Series(
    tree_pruned.feature_importances_,
    index=[f'feature_{i}' for i in range(X.shape[1])]
).sort_values(ascending=False)
print("\nTop 5 feature importances:")
print(feature_imp.head(5).round(4))

6 Visualizing Decision Trees

One of the biggest advantages of decision trees is that you can look at the model. Scikit-learn provides two tools: plot_tree for a graphical visualization and export_text for a text-based one you can print or log.

In [6]:
import matplotlib.pyplot as plt
from sklearn.tree import plot_tree, export_text
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris()
tree_viz = DecisionTreeClassifier(max_depth=3, random_state=42)
tree_viz.fit(iris.data, iris.target)

# ── Graphical plot ──
fig, ax = plt.subplots(figsize=(16, 8))
plot_tree(
    tree_viz,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,              # color nodes by majority class
    rounded=True,             # rounded box corners
    max_depth=3,              # how deep to visualize
    fontsize=9,
    ax=ax
)
plt.title("Iris Decision Tree (max_depth=3)", fontsize=14)
plt.tight_layout()
plt.savefig('iris_tree.png', dpi=150, bbox_inches='tight')

# ── Text representation ── (easier to read in a terminal or notebook)
text_tree = export_text(tree_viz, feature_names=list(iris.feature_names))
print(text_tree)
# |--- petal length (cm) <= 2.45
# |   |--- class: setosa
# |--- petal length (cm) >  2.45
# |   |--- petal width (cm) <= 1.75
# |   |   |--- petal length (cm) <= 4.95
# |   |   |   |--- petal width (cm) <= 1.65
# |   |   |   |   |--- class: versicolor
# |   |   |   |--- petal width (cm) >  1.65
# |   |   |   |   |--- class: virginica
# ...

# ── Reading a tree node ──
# Each node shows:
# - The test condition (feature ≤ threshold)
# - Gini impurity
# - Number of samples reaching this node
# - Class distribution [n_class0, n_class1, ...]
# - Majority class
💡
Keep Depth ≤ 4 for Human Readability

A tree with depth 10 has up to 2¹⁰ = 1024 leaves. No human can audit that. For presentations, stakeholder reports, or regulatory compliance, keep max_depth=3 or max_depth=4. For model performance, use Random Forests (next lesson) — they combine many deep trees to get the accuracy without sacrificing stability.

7 Controlling Overfitting

Without constraints, a decision tree grows until every leaf contains exactly one training sample — perfectly memorizing the training data with zero training error but terrible generalization. The key hyperparameters for controlling this are:

The clearest way to see overfitting in a tree is to watch its decision regions as max_depth increases. Because a tree only ever asks "is feature ≤ threshold?", every split is a straight, axis-aligned line — the decision boundary is built entirely out of rectangles. At depth 1 (a "stump") there is exactly one split. As depth grows, the tree carves the space into smaller and smaller boxes, until at high depth it draws a box around individual noisy points it has memorized:

Max Depth 2

max_depth = 2 — a single rectangular region per class; still underfitting the curved boundary.

Train vs. test accuracy across every depth from 1–8, for the currently selected dataset. Watch the gap widen as depth increases.

In [7]:
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.datasets import load_breast_cancer
import numpy as np

X_bc, y_bc = load_breast_cancer(return_X_y=True)
X_btr, X_bte, y_btr, y_bte = train_test_split(X_bc, y_bc, test_size=0.2, random_state=42)

hyperparams = [
    # (max_depth, min_samples_split, min_samples_leaf)
    (None,  2,   1),   # default — no constraints → overfit
    (5,     2,   1),
    (5,    20,   5),
    (5,    20,  10),
    (3,    20,  10),
]

print(f"{'max_depth':>12}  {'min_split':>10}  {'min_leaf':>10}  {'Train':>8}  {'Test':>8}  {'CV±std':>12}")
print("-" * 72)
for md, ms, ml in hyperparams:
    dt = DecisionTreeClassifier(max_depth=md, min_samples_split=ms, min_samples_leaf=ml, random_state=42)
    dt.fit(X_btr, y_btr)
    train_acc = dt.score(X_btr, y_btr)
    test_acc  = dt.score(X_bte, y_bte)
    cv_scores = cross_val_score(dt, X_bc, y_bc, cv=5, scoring='accuracy')
    depth_label = str(md) if md else 'None'
    print(f"{depth_label:>12}  {ms:>10}  {ml:>10}  {train_acc:>8.4f}  {test_acc:>8.4f}  {cv_scores.mean():>6.4f}±{cv_scores.std():.4f}")

# max_depth  min_split  min_leaf  Train     Test       CV±std
# None              2         1   1.0000    0.9386     0.9280±0.0142  ← overfit
# 5                 2         1   0.9956    0.9298     0.9282±0.0143
# 5                20         5   0.9582    0.9386     0.9315±0.0117
# 5                20        10   0.9516    0.9474     0.9368±0.0112  ← best
# 3                20        10   0.9429    0.9298     0.9262±0.0165
Hyperparameter What it controls Effect when increased
max_depth Maximum levels in the tree More complex model, higher variance
min_samples_split Min samples to consider splitting a node Simpler model, fewer small splits
min_samples_leaf Min samples required in each leaf Simpler model, more regularized leaves
max_features Fraction of features to consider per split Less randomness; closer to full search
max_leaf_nodes Upper bound on total leaves More complex; build with best-first splits

8 Feature Importance

Decision trees provide a natural measure of feature importance: the total weighted impurity reduction contributed by each feature across all splits, normalized to sum to 1. Features used near the root (early splits) typically have higher importance because those splits affect more samples.

In [8]:
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

X_bc, y_bc = load_breast_cancer(return_X_y=True)
feature_names = load_breast_cancer().feature_names

X_btr, X_bte, y_btr, y_bte = train_test_split(X_bc, y_bc, test_size=0.2, random_state=42)

dt = DecisionTreeClassifier(max_depth=5, min_samples_leaf=10, random_state=42)
dt.fit(X_btr, y_btr)

# Feature importances — automatically normalized to sum to 1
importances = pd.Series(dt.feature_importances_, index=feature_names)
importances_sorted = importances.sort_values(ascending=False)

print("Top 10 feature importances (impurity-based):")
print(importances_sorted.head(10).round(4))
# worst concave points    0.5423  ← used at the root, dominates
# worst radius            0.1102
# worst area              0.0876
# ...

# Bar plot
plt.figure(figsize=(10, 6))
importances_sorted.head(10).sort_values().plot(kind='barh', color='steelblue')
plt.title('Top 10 Feature Importances — Breast Cancer Tree')
plt.xlabel('Importance (weighted impurity reduction)')
plt.tight_layout()
plt.savefig('dt_importance.png', dpi=150, bbox_inches='tight')
⚠️
Impurity-Based Importance Is Biased Towards High-Cardinality Features

A numerical feature with 1000 unique values has more split opportunities than a binary feature — so it can appear more important purely by chance. For unbiased feature importance, use permutation importance (from sklearn.inspection import permutation_importance) which directly measures how much test-set performance drops when a feature is randomly shuffled.

🌍

Real-World Spotlight: Telecom Customer Churn — Reading the Tree

A telecom company trains a decision tree on historical customer data to understand what drives churn. The tree is deliberately kept shallow (max_depth=5) to produce human-readable, auditable rules that the customer retention team can act on directly.

In [9]:
import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text, plot_tree
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
import matplotlib.pyplot as plt

np.random.seed(42)
n = 5000

# Synthetic telecom dataset
df = pd.DataFrame({
    'tenure_months':    np.random.randint(1, 72, n),
    'monthly_charge':   np.random.uniform(20, 120, n).round(2),
    'num_services':     np.random.randint(1, 8, n),
    'contract_type':    np.random.choice([0, 1, 2], n, p=[0.5, 0.3, 0.2]),  # 0=monthly,1=annual,2=biennial
    'tech_support':     np.random.randint(0, 2, n),
    'num_complaints':   np.random.poisson(0.8, n).clip(0, 5),
})
# Realistic churn probability
churn_prob = (
    0.35 * (df['monthly_charge'] / 120) +
    0.30 * (1 - df['tenure_months'] / 72) +
    0.20 * (df['num_complaints'] / 5) +
    0.15 * (1 - df['contract_type'] / 2)
)
df['churned'] = (np.random.rand(n) < churn_prob).astype(int)
print(f"Churn rate: {df['churned'].mean():.1%}")

feature_cols = ['tenure_months', 'monthly_charge', 'num_services',
                'contract_type', 'tech_support', 'num_complaints']
X = df[feature_cols].values
y = df['churned'].values

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42)

# Deliberately shallow for interpretability
dt_churn = DecisionTreeClassifier(max_depth=5, min_samples_leaf=50, random_state=42)
dt_churn.fit(X_train, y_train)

print(f"\nTraining accuracy: {dt_churn.score(X_train, y_train):.4f}")
print(f"Test accuracy:     {dt_churn.score(X_test, y_test):.4f}")
print(f"\n{classification_report(y_test, dt_churn.predict(X_test), target_names=['Retained', 'Churned'])}")

# Human-readable rules
print("\nDecision rules:")
print(export_text(dt_churn, feature_names=feature_cols))
# |--- monthly_charge <= 70.00
# |   |--- tenure_months <= 12
# |   |   |--- num_complaints <= 1
# |   |   |   |--- class: Retained
# |   |   |--- num_complaints > 1
# |   |   |   |--- class: Churned     ← high-risk: new + complaints
# |   |--- tenure_months > 12
# |   |   |--- class: Retained
# |--- monthly_charge > 70.00
# |   |--- contract_type <= 0         ← month-to-month AND high charge
# |   |   |--- class: Churned         ← highest churn risk group
# ...

# Feature importances
feat_imp = pd.Series(dt_churn.feature_importances_, index=feature_cols)
print("\nFeature importances:")
print(feat_imp.sort_values(ascending=False).round(4))

The tree exposed three actionable insights: (1) customers on month-to-month contracts with monthly charges >$70 are the highest-risk group; (2) new customers (<12 months tenure) with complaints need immediate intervention; (3) longer-tenured customers are largely self-retaining regardless of charge. The retention team can now run targeted campaigns for each identified segment.

✍️ Practice Exercises

  1. Train an unconstrained DecisionTreeClassifier on the Titanic dataset (from Lesson 4). Record training and test accuracy. Then add max_depth=5, min_samples_leaf=20 — how do train and test accuracy change?
  2. Manually compute Gini impurity for a node with 80 class-A samples and 20 class-B samples. Then compute the weighted Gini after splitting into [70A, 5B] and [10A, 15B].
  3. Use export_text to print a depth-3 tree trained on the Wine dataset (from sklearn.datasets import load_wine). Can you write the decision rules in plain English?
  4. Compare feature_importances_ from a single tree vs permutation_importance on the breast cancer dataset. Do they agree on the top features?

📚 Primary Source for This Lesson

scikit-learn: Decision Trees
The official guide covers the CART algorithm, feature importance computation, and multi-output trees. For theory, see Breiman et al. (1984) Classification and Regression Trees — the seminal text that defined the field. Hastie, Tibshirani & Friedman, Chapter 9 is also excellent for the statistical perspective.

💬 Getting 100% training accuracy with terrible test accuracy? Confused about what Gini impurity actually measures? Paste your situation — your tutor can walk you through the tree's decisions node by node.