Tree-based Models

How Decision Trees Think

A decision tree partitions the feature space into axis-aligned rectangular regions using a sequence of if-then rules. Each internal node tests one feature; each leaf node gives a prediction. You can read the learned rules in plain English — making trees the most interpretable ML model class.

🌿

Interpretability by design. A tree trained with max_depth=3 produces 7 rules at most. You can literally print them out, hand them to a domain expert, and get meaningful feedback. That's rare in ML.

Splitting Criteria

Gini Impurity

The probability that a randomly chosen element would be incorrectly labelled if labelled randomly according to the class distribution in the node:

Gini Impurity$$G(D) = 1 - \sum_{k=1}^K p_k^2$$$p_k$: fraction of samples in class $k$. $G=0$: perfectly pure node. $G=0.5$: maximally impure binary node (50/50 split). Used by CART (scikit-learn default).

Entropy and Information Gain

Entropy from information theory — measures the average surprise or disorder in a node:

Entropy & Information Gain$$H(D) = -\sum_{k=1}^K p_k\log_2 p_k \qquad \text{IG}(D,f) = H(D) - \sum_v \frac{|D_v|}{|D|}H(D_v)$$Choose the feature $f$ and split threshold that maximises $\text{IG}$. Used by ID3 and C4.5.

Python

import numpy as np

def gini(p):
    return 1 - np.sum(p**2)

def entropy(p):
    p = p[p > 0]
    return -np.sum(p * np.log2(p))

# Compare impurity measures
p_pure    = np.array([1.0, 0.0])    # all class 0
p_mixed   = np.array([0.5, 0.5])    # 50/50
p_skewed  = np.array([0.9, 0.1])    # 90/10

print(f"Pure    — Gini: {gini(p_pure):.3f}  Entropy: {entropy(p_pure):.3f}")
print(f"Mixed   — Gini: {gini(p_mixed):.3f}  Entropy: {entropy(p_mixed):.3f}")
print(f"Skewed  — Gini: {gini(p_skewed):.3f}  Entropy: {entropy(p_skewed):.3f}")

The CART Algorithm

For every feature $j$ and every possible split threshold $t$: compute weighted Gini impurity of the two child nodes after splitting on $(j, t)$.
Choose $(j^*, t^*)$ that minimises weighted child impurity (= maximises impurity reduction).
Split the node, recurse on each child.
Stop when node is pure, depth limit reached, or samples too few.
Leaf prediction: majority class (classification), mean value (regression).

Full Example

Python

from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor, export_text, plot_tree
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
import matplotlib.pyplot as plt

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

# Compare depth settings
for depth in [None, 5, 3, 2]:
    dt = DecisionTreeClassifier(max_depth=depth, criterion="gini", random_state=42)
    cv = cross_val_score(dt, X, y, cv=5).mean()
    dt.fit(X_train, y_train)
    print(f"max_depth={str(depth):4s}  Train acc: {dt.score(X_train, y_train):.3f}  "
          f"Test acc: {dt.score(X_test, y_test):.3f}  CV acc: {cv:.3f}")

# Print the learned rules (interpretable!)
best_dt = DecisionTreeClassifier(max_depth=3).fit(X_train, y_train)
print("
Learned Decision Rules:")
print(export_text(best_dt, feature_names=load_iris().feature_names))

# Visualise the tree
fig, ax = plt.subplots(figsize=(16, 6))
plot_tree(best_dt, feature_names=load_iris().feature_names,
          class_names=load_iris().target_names, filled=True, fontsize=9, ax=ax)
plt.tight_layout(); plt.show()

Pruning Strategies

max_depthHard limit on tree depth. Most effective. Start with 3–5, tune via CV.

min_samples_splitMinimum samples to split a node. Prevents tiny, meaningless splits.

min_samples_leafEvery leaf must have at least $k$ samples. Prevents single-point leaves.

ccp_alpha (cost-complexity)Post-pruning parameter. Removes subtrees whose impurity reduction doesn't justify their size. Tune via CV.

Python

import numpy as np

# Cost-complexity pruning path
dt_full = DecisionTreeClassifier(random_state=42)
path = dt_full.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas[:-1]   # remove the last (trivial) tree

cv_scores = []
for alpha in ccp_alphas:
    dt = DecisionTreeClassifier(ccp_alpha=alpha, random_state=42)
    cv_scores.append(cross_val_score(dt, X, y, cv=5).mean())

best_alpha = ccp_alphas[np.argmax(cv_scores)]
print(f"Best ccp_alpha: {best_alpha:.6f}  CV acc: {max(cv_scores):.4f}")

Feature Importance

Python

import pandas as pd
import matplotlib.pyplot as plt

importances = pd.Series(best_dt.feature_importances_, index=load_iris().feature_names)
importances.sort_values().plot.barh(color="#4a8fa8")
plt.xlabel("Mean Decrease in Gini Impurity")
plt.title("Decision Tree Feature Importance")
plt.tight_layout(); plt.show()

Summary

Trees partition feature space with axis-aligned splits. Human-readable rules.
Gini impurity: $1 - \sum p_k^2$. Entropy: $-\sum p_k\log_2 p_k$. Both measure node disorder.
CART greedily picks the split minimising weighted child impurity. Fast, but can overfit.
Control overfitting with max_depth, min_samples_leaf, or ccp_alpha.
Feature importance = mean decrease in impurity across all splits on that feature.