Decision Trees: Splitting Criteria, Pruning and Interpretability

A doctor triaging patients asks a sequence of questions: Is the temperature above 38.5 °C? Is breathing laboured? Is the patient under five? Each answer narrows the possibilities. A decision tree learns such a sequence of questions automatically from data. Trees are interpretable, handle mixed feature types with little preprocessing, and — combined into ensembles — power the most successful models for tabular data.

Structure#

A decision tree consists of:

• Internal nodes that test a feature (e.g. $x_j \le t$);
• Branches for the outcomes of the test;
• Leaves that output a prediction — the majority class (classification) or the mean target (regression) of training examples reaching that leaf.

A tree partitions the feature space into axis-aligned rectangles, each with a constant prediction.

Learning a tree: greedy recursive splitting#

Finding the optimal tree is NP-hard, so algorithms like CART (Classification and Regression Trees) grow trees greedily:

1. At the current node, consider every feature $j$ and every candidate threshold $t$.
2. Choose the split that most reduces impurity.
3. Recurse on each child until a stopping condition is met.

Impurity measures#

For a node with class proportions $p_1, \dots, p_K$:

Gini impurity — the probability of misclassifying a random example if labelled randomly according to the node's class distribution:

Entropy:

Both are zero for a pure node and maximal for a uniform mix. The quality of a split into children $L$ and $R$ is the weighted impurity decrease:

With entropy, $\Delta$ is the information gain. In practice Gini and entropy produce very similar trees; Gini is slightly faster to compute. For regression trees, impurity is the variance (MSE) within the node.

Overfitting and how to control it#

A tree grown until every leaf is pure memorises the training data — high variance. Controls:

Pre-pruning (early stopping): limit max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, or require a minimum impurity decrease.

Post-pruning: grow a large tree, then prune back. CART's cost-complexity pruning minimises

where $R(T)$ is the training error and $|T|$ the number of leaves. Increasing $\alpha$ yields a nested sequence of smaller trees; choose $\alpha$ by cross-validation.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text

X, y = load_breast_cancer(return_X_y=True, as_frame=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, stratify=y, random_state=0)

full = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)
print("unpruned: leaves =", full.get_n_leaves(), " test acc =", round(full.score(X_te, y_te), 3))

path = full.cost_complexity_pruning_path(X_tr, y_tr)
best_alpha = max(path.ccp_alphas[:-1], key=lambda a: cross_val_score(
    DecisionTreeClassifier(random_state=0, ccp_alpha=a), X_tr, y_tr, cv=5).mean())
pruned = DecisionTreeClassifier(random_state=0, ccp_alpha=best_alpha).fit(X_tr, y_tr)
print("pruned:   leaves =", pruned.get_n_leaves(), " test acc =", round(pruned.score(X_te, y_te), 3))
print(export_text(pruned, feature_names=list(X.columns), max_depth=3))

The pruned tree is much smaller, usually at least as accurate, and readable as a set of rules.

Strengths#

• Interpretable (when small): a doctor or manager can follow the logic.
• No scaling needed: splits depend only on the ordering of values.
• Handles non-linearity and interactions automatically.
• Mixed data types and (in some implementations) missing values.
• Fast prediction: $O(\text{depth})$.

Weaknesses#

• High variance: small data changes can produce a completely different tree.
• Axis-aligned boundaries: a diagonal boundary requires a staircase of many splits.
• Greedy: a split that looks poor now may enable excellent splits later (XOR-type patterns).
• Biased impurity: features with many distinct values offer more candidate splits and can be over-selected.
• Poor extrapolation in regression: predictions are constant outside the training range.

Feature importance#

Summing the impurity decrease contributed by each feature over all splits gives mean decrease in impurity (MDI) importance. It is fast but biased towards high-cardinality features. Permutation importance on validation data — shuffle a feature and measure the drop in performance — is more reliable.