Decision Trees

Overview#

A decision tree learns a sequence of simple, interpretable if/else questions that split data into increasingly pure groups. It's the foundational building block behind Random Forest and Gradient Boosting (covered next in this section), so understanding exactly how a single tree makes its splitting decisions matters even if you rarely deploy one alone. This notebook goes deep into the CART algorithm, impurity measures, the recursive splitting process, pruning strategies, and a thorough treatment of trees' strengths and well-known weaknesses.

1. The CART Algorithm#

Scikit-learn implements CART (Classification and Regression Trees), which builds a binary tree — every split divides data into exactly two groups, based on a single feature and threshold.

Python
CopyAsk AI
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split

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

tree = DecisionTreeClassifier(max_depth=3, random_state=42)
tree.fit(X_train, y_train)

print(f"Test accuracy: {tree.score(X_test, y_test):.3f}")

text
Ask AICopy
CART, at a high level:
1. Start with all training data at the root node
2. For EVERY feature and EVERY possible threshold value, calculate how
   much splitting on that (feature, threshold) pair would reduce impurity
3. Choose the single (feature, threshold) pair that reduces impurity the
   MOST — this becomes the split at this node
4. Recursively repeat steps 1-3 on each of the two resulting child nodes
5. Stop when a stopping condition is met (max depth reached, node is
   pure, too few samples remain, etc.)

2. Impurity Measures, in Full Detail#

Gini impurity#

Python
CopyAsk AI
import numpy as np

def gini_impurity(class_counts):
    """class_counts: array of counts per class in a node"""
    total = sum(class_counts)
    if total == 0:
        return 0
    proportions = np.array(class_counts) / total
    return 1 - np.sum(proportions ** 2)

# A pure node (all one class): impurity = 0
print(gini_impurity([50, 0, 0]))    # 0.0

# A maximally impure node (evenly split across 3 classes): impurity near max
print(gini_impurity([17, 17, 16]))    # ~0.667

# A somewhat impure node
print(gini_impurity([40, 8, 2]))       # ~0.312

text
Ask AICopy
Gini impurity formula: Gini = 1 - sum(p_i²) for each class i

Interpretation: the probability of misclassifying a randomly chosen
element from the node, if it were randomly labeled according to the
class distribution WITHIN that node.

Entropy (information gain)#

Python
CopyAsk AI
def entropy(class_counts):
    total = sum(class_counts)
    if total == 0:
        return 0
    proportions = np.array(class_counts) / total
    proportions = proportions[proportions > 0]   # avoid log(0)
    return -np.sum(proportions * np.log2(proportions))

print(entropy([50, 0, 0]))    # 0.0 — pure node
print(entropy([17, 17, 16]))    # ~1.58 — near-maximum entropy for 3 classes

text
Ask AICopy
Entropy formula: Entropy = -sum(p_i * log2(p_i)) for each class i

Interpretation: borrowed from information theory — the average number of
bits needed to identify a randomly chosen element's class, given the
node's class distribution. Higher entropy = more "surprise"/uncertainty.

Information gain: choosing the actual split#

Python
CopyAsk AI
def information_gain(parent_counts, left_counts, right_counts, impurity_fn=gini_impurity):
    n_parent = sum(parent_counts)
    n_left, n_right = sum(left_counts), sum(right_counts)

    weighted_child_impurity = (
        (n_left / n_parent) * impurity_fn(left_counts) +
        (n_right / n_parent) * impurity_fn(right_counts)
    )
    return impurity_fn(parent_counts) - weighted_child_impurity

# Example: parent has 60 class-A, 40 class-B
parent = [60, 40]
# Candidate split 1: nearly separates the classes
gain_1 = information_gain(parent, [55, 5], [5, 35])
# Candidate split 2: barely separates anything
gain_2 = information_gain(parent, [32, 22], [28, 18])

print(f"Split 1 gain: {gain_1:.4f}")
print(f"Split 2 gain: {gain_2:.4f}")
# The tree greedily picks whichever candidate split, across ALL features
# and ALL thresholds, produces the HIGHEST information gain at each node

Gini vs entropy: does it actually matter?#

Python
CopyAsk AI
tree_gini = DecisionTreeClassifier(criterion="gini", max_depth=3, random_state=42)
tree_entropy = DecisionTreeClassifier(criterion="entropy", max_depth=3, random_state=42)

tree_gini.fit(X_train, y_train)
tree_entropy.fit(X_train, y_train)

print(f"Gini test accuracy: {tree_gini.score(X_test, y_test):.3f}")
print(f"Entropy test accuracy: {tree_entropy.score(X_test, y_test):.3f}")

In practice, Gini and entropy usually produce very similar trees — Gini is slightly faster to compute (no logarithm), which is why it's scikit-learn's default, but the choice rarely has a large practical impact on final performance.

3. Regression Trees: A Different Splitting Criterion#

For regression, impurity is instead measured by variance (or, equivalently, mean squared error) within each node.

Python
CopyAsk AI
from sklearn.tree import DecisionTreeRegressor

def mse_impurity(values):
    if len(values) == 0:
        return 0
    return np.var(values)

# A node with all identical values: MSE impurity = 0 (perfectly "pure")
print(mse_impurity([10, 10, 10]))   # 0.0

# A node with spread-out values: higher MSE impurity
print(mse_impurity([5, 15, 25]))      # 66.67

reg_tree = DecisionTreeRegressor(max_depth=3, random_state=42)

The splitting logic is otherwise identical: at each node, try every feature/threshold combination, and pick whichever split most reduces the weighted average variance across the two resulting child nodes. Each leaf then predicts the mean of the training values that ended up in it.

4. Controlling Tree Growth: Pre-Pruning#

An unconstrained tree keeps splitting until every leaf is pure (or has a single sample) — this virtually guarantees overfitting. Pre-pruning (also called early stopping) constrains growth using hyperparameters checked during construction.

Python
CopyAsk AI
DecisionTreeClassifier(
    max_depth=5,                # maximum tree depth
    min_samples_split=20,         # a node needs ≥20 samples to be split further
    min_samples_leaf=10,            # each leaf must have ≥10 samples
    max_leaf_nodes=15,                # caps total number of leaves across the whole tree
    min_impurity_decrease=0.01,         # a split must reduce impurity by at least this much to be made
)

Python
CopyAsk AI
# Demonstrating the effect of max_depth on overfitting
for depth in [1, 3, 5, 10, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=42)
    tree.fit(X_train, y_train)
    train_acc = tree.score(X_train, y_train)
    test_acc = tree.score(X_test, y_test)
    print(f"max_depth={depth}: train={train_acc:.3f}, test={test_acc:.3f}")

text
Ask AICopy
max_depth=1: train=0.746, test=0.694
max_depth=3: train=0.972, test=0.917
max_depth=5: train=1.000, test=0.917
max_depth=10: train=1.000, test=0.889
max_depth=None: train=1.000, test=0.861

The growing gap between training and test accuracy as depth increases without bound is the classic overfitting signature (covered generally in the Statistical Learning Foundations notebook), now visible concretely with tree depth as the complexity dial.

5. Post-Pruning: Cost-Complexity Pruning#

An alternative to constraining growth upfront: grow a full, unconstrained tree, then prune it back afterward, removing branches that don't justify their added complexity.

Python
CopyAsk AI
# Cost-complexity pruning: finds the alpha values at which the optimal
# subtree structure changes
path = DecisionTreeClassifier(random_state=42).cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas

trees = []
for alpha in ccp_alphas:
    tree = DecisionTreeClassifier(random_state=42, ccp_alpha=alpha)
    tree.fit(X_train, y_train)
    trees.append(tree)

train_scores = [t.score(X_train, y_train) for t in trees]
test_scores = [t.score(X_test, y_test) for t in trees]

# Plotting train_scores and test_scores against ccp_alphas reveals where
# test accuracy peaks — that alpha value is typically the best pruning
# strength, balancing tree size against generalization
best_alpha = ccp_alphas[np.argmax(test_scores)]
print(f"Best ccp_alpha: {best_alpha:.5f}")

text
Ask AICopy
ccp_alpha (the cost-complexity parameter) works similarly in spirit to
alpha in Ridge/Lasso regularization: it adds a penalty proportional to
tree size (number of leaves) to the tree's overall impurity score,
encouraging simpler trees unless the added complexity is clearly earning
its keep in reduced impurity.

6. Why Single Trees Are High-Variance Estimators#

Python
CopyAsk AI
# Demonstrating instability: small changes in training data can produce
# noticeably different trees
from sklearn.model_selection import train_test_split

for seed in [1, 2, 3]:
    X_sample, _, y_sample, _ = train_test_split(X_train, y_train, train_size=0.8, random_state=seed)
    tree = DecisionTreeClassifier(max_depth=4, random_state=42)
    tree.fit(X_sample, y_sample)
    print(f"Seed {seed}: root split feature = {tree.tree_.feature[0]}, "
          f"threshold = {tree.tree_.threshold[0]:.2f}")

text
Ask AICopy
Seed 1: root split feature = 6, threshold = 0.79
Seed 2: root split feature = 6, threshold = 0.75
Seed 3: root split feature = 9, threshold = 3.46    <- an entirely
                                                          DIFFERENT root
                                                          feature chosen

This instability — small changes in training data leading to meaningfully different tree structures — is precisely why ensemble methods (Random Forest, Gradient Boosting) exist and are covered separately in this section: averaging many such trees smooths out this instability dramatically, at the cost of losing the single-tree's easy interpretability.

7. Interpretability: The Tree's Biggest Advantage#

Python
CopyAsk AI
from sklearn.tree import export_text

tree_small = DecisionTreeClassifier(max_depth=3, random_state=42)
tree_small.fit(X_train, y_train)

print(export_text(tree_small, feature_names=load_wine().feature_names))

Architecture & Data Flow
Copy
|--- proline <= 755.00
|   |--- flavanoids <= 1.40
|   |   |--- class: 2
|   |--- flavanoids >  1.40
|   |   |--- class: 1
|--- proline >  755.00
|   |--- color_intensity <= 3.46
|   |   |--- class: 1
|   |--- color_intensity >  3.46
|   |   |--- class: 0

Unlike almost every other model in this course, a shallow decision tree can be read and understood directly, top to bottom, by someone with zero machine learning background — this remains one of its most valuable and distinctive properties, particularly in domains (medicine, credit decisions, legal contexts) where a model's reasoning must be explainable to a human, not just accurate.

8. Handling Different Feature Types#

Python
CopyAsk AI
# Decision trees natively handle numeric splits (threshold comparisons)
# and, unlike distance-based methods (KNN, SVM), require NO feature
# scaling whatsoever — a split on "age > 30" is exactly as easy to find
# whether age is measured in years or milliseconds

tree_unscaled = DecisionTreeClassifier(max_depth=3)
tree_unscaled.fit(X_train, y_train)   # works fine, no StandardScaler needed

text
Ask AICopy
This scale-invariance is a genuine practical advantage of tree-based
methods over KNN, SVM, and regularized linear models (all covered
elsewhere in this course) — one less preprocessing step to worry about,
and one less way for a pipeline to be subtly wrong when new features are
added later.

9. Known Weaknesses#

text
Ask AICopy
1. HIGH VARIANCE / INSTABILITY: as shown above, small data changes can
   produce very different tree structures — addressed by ensembling.

2. AXIS-ALIGNED SPLITS ONLY: every split is a simple threshold on ONE
   feature at a time (e.g. "x1 > 5"), never a diagonal or curved
   boundary. Data whose true decision boundary is diagonal requires many
   small "staircase" splits to approximate, which can hurt both
   generalization and interpretability.

3. GREEDY, NOT GLOBALLY OPTIMAL: at each node, CART picks the locally
   best split WITHOUT considering how it affects splits further down the
   tree — finding the globally optimal tree structure is
   computationally intractable (NP-hard) for any real dataset, so this
   greedy approximation is a practical necessity, not a choice.

4. BIAS TOWARD FEATURES WITH MANY DISTINCT VALUES: features offering many
   possible split points have more opportunities to find a split that
   looks good on the training data by chance, which can subtly bias
   feature importance and split selection.

10. When to Use a Single Decision Tree#

text
Ask AICopy
Use a single tree (rather than an ensemble) when:
- Interpretability is the PRIMARY requirement — a human needs to read
  and understand exactly why a prediction was made
- A quick, rough baseline is needed
- Extremely fast prediction time matters more than best-possible accuracy
- Exploring feature importance and interaction structure visually, as a
  data-understanding step, even if the final model will be an ensemble

Prefer an ensemble (Random Forest / Gradient Boosting) when:
- Predictive accuracy matters more than interpretability
- The dataset is large enough that variance reduction from ensembling
  clearly helps
- You can accept the loss of the single-tree's direct readability

Notes#

• Gini impurity and entropy produce similar results in practice; Gini's computational simplicity (no logarithm) is why it's the default.
• A tree's greedy, node-by-node splitting is a practical necessity, not an oversight — finding the provably optimal tree structure is computationally intractable for real datasets.
• Pre-pruning (constraining growth via hyperparameters) and post-pruning (cost-complexity pruning after full growth) are two different but related strategies for the same underlying goal: controlling overfitting.
• Decision trees require no feature scaling, unlike KNN, SVM, and regularized linear models — a genuine practical convenience.
• A single tree's instability (small data changes → different tree structure) is precisely the motivation for the ensemble methods covered in the next notebooks of this section.

Best Practices Checklist#

• Always constrain tree growth (via max_depth, min_samples_leaf, etc.) rather than letting a tree grow unconstrained
• Use cross-validation to tune pruning hyperparameters, not training accuracy alone
• Consider cost-complexity pruning (ccp_alpha) as an alternative or complement to pre-pruning hyperparameters
• Use export_text or plot_tree to visualize and sanity-check a shallow tree's actual logic, not just its accuracy score
• Remember trees need no feature scaling — don't add an unnecessary StandardScaler step for tree-only pipelines
• Prefer an ensemble method over a single tree whenever predictive accuracy matters more than interpretability
• Keep single trees shallow specifically when interpretability is the goal — a deep tree is no longer easily human-readable
• Be aware that reported feature importances can be subtly biased toward features with many distinct split points