Decision Trees: Splits, Pruning, and Instability

A decision tree sends each input through a sequence of tests such as “is age at most 40?” Each test examines one feature; this is an axis-aligned split. The starting node is the root, and the terminal regions are leaves. A classification leaf returns class proportions and predicts the most frequent class; a standard regression leaf returns a constant value. Small trees are easy to inspect, but their structure can change substantially when the training data change.

Choosing a split

With the default best-split search and all features available, a CART-style tree considers valid thresholds along each feature at the current node. It chooses the largest immediate decrease in impurity, without planning the later splits. Here \(p_k\) is the fraction of the node’s training rows belonging to class \(k\). Gini impurity is \(1-\sum_k p_k^2\), and entropy is \(-\sum_k p_k\log_2 p_k\), with \(0\log_2 0=0\). Both are zero for a pure node containing only one class. The split gain is the parent impurity minus the children’s average impurity, weighted by their row counts.

For example, a node containing four positive and four negative rows has Gini impurity \(1-(4/8)^2-(4/8)^2=0.5\). A split into children containing (3 positive, 1 negative) and (1 positive, 3 negative) gives impurity \(1-(3/4)^2-(1/4)^2=0.375\) in each child. The gain is \(0.5-(4/8)0.375-(4/8)0.375=0.125\). The algorithm compares this gain with the other available splits.

Numeric feature scaling is usually unnecessary for trees: positive affine rescaling preserves the possible training-row partitions in exact arithmetic. Floating-point rounding can still change ties or candidate thresholds. Categorical support depends on the implementation; scikit-learn’s DecisionTreeClassifier requires categories to be numerically encoded. Arbitrary integer codes impose an order, so one-hot encoding is often appropriate for unordered categories.

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score

X, y = make_classification(n_samples=800, n_features=8, n_informative=5,
                           random_state=0)
for crit in ("gini", "entropy", "log_loss"):
    m = DecisionTreeClassifier(criterion=crit, max_depth=4, random_state=0).fit(X, y)
    cv = cross_val_score(DecisionTreeClassifier(criterion=crit, max_depth=4,
                                                random_state=0), X, y, cv=5).mean()
    print(f"{crit:9s} cv {cv:.4f}  first split: feature {m.tree_.feature[0]}"
          f" at {m.tree_.threshold[0]:.4f}  leaves {m.get_n_leaves()}")
# gini      cv 0.8313  first split: feature 2 at 0.0353  leaves 13
# entropy   cv 0.8375  first split: feature 2 at 0.0353  leaves 14
# log_loss  cv 0.8375  first split: feature 2 at 0.0353  leaves 14

All three settings choose feature 2 at 0.0353 for the root in this run. Gini and entropy can choose different splits; agreement here is an observation, not an identity. In scikit-learn, entropy and log_loss name the same Shannon-entropy criterion, which explains their matching results. Mean five-fold accuracy differs by about 0.6 percentage points between Gini and entropy here. The root and leaf counts describe fits on all 800 rows, while each cross-validation score comes from separately fitted fold models. Depth, minimum leaf size, and pruning also merit validation.

With the default squared-error regression criterion, each leaf predicts the mean of its training targets. Other criteria can use different summaries; absolute error uses the median. Standard constant-leaf regression trees approximate a slope with steps. With one input feature, predictions stay constant beyond the outermost split thresholds. With several features, holding the others fixed gives the same behavior along one axis, but changing other coordinates can still route a point to another leaf.

Controlling growth

Without growth limits, a tree continues splitting until leaves are pure or no valid split remains. Identical feature rows with conflicting labels cannot be separated, so perfect training accuracy is not guaranteed. Deep trees can fit accidental patterns in noisy samples. Growth constraints such as max_depth, min_samples_leaf, and min_impurity_decrease stop some splits early. Post-pruning removes branches from a tree that has already been grown; it can also be combined with growth limits.

Cost-complexity pruning trades training fit against leaf count through \(R(T)+\alpha|T|\), where \(T\) is a candidate subtree and \(|T|\) its number of leaves. In scikit-learn, \(R(T)\) is the sum of leaf impurities weighted by the fraction of training sample weight reaching each leaf; it is not the misclassification rate. A larger \(\alpha\) charges more for each leaf. For example, reducing \(R(T)\) by 0.006 at the cost of two extra leaves improves this objective only when \(2\alpha<0.006\).

For a fixed grown tree, weakest-link pruning produces a nested path of subtrees: increasing alpha removes branches without adding new ones. This optimization searches subtrees of that tree, not all possible tree structures. It can retain a weak initial split when the useful branches beneath it justify their combined cost. Whether it predicts better than growth constraints is an empirical question. The pruning documentation describes the weighted-impurity objective and path.

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score

for a in (0.0, 0.002, 0.005, 0.010, 0.030):
    m = DecisionTreeClassifier(ccp_alpha=a, random_state=0).fit(X, y)
    cv = cross_val_score(DecisionTreeClassifier(ccp_alpha=a, random_state=0),
                         X, y, cv=5).mean()
    print(f"alpha {a:6.3f}  leaves {m.get_n_leaves():4d}  depth {m.get_depth():2d}"
          f"  train {m.score(X, y):.4f}  cv {cv:.4f}")
# alpha  0.000  leaves   67  depth 14  train 1.0000  cv 0.8438
# alpha  0.002  leaves   41  depth 14  train 0.9788  cv 0.8500
# alpha  0.005  leaves   21  depth  9  train 0.9400  cv 0.8513
# alpha  0.010  leaves    8  depth  5  train 0.8675  cv 0.8400
# alpha  0.030  leaves    3  depth  2  train 0.8175  cv 0.7950

The full-data unpruned fit has 67 leaves and training accuracy 1.0. At \(\alpha=0.005\), that fit has 21 leaves and training accuracy 0.94. The corresponding fold models achieve the highest mean validation accuracy among the five candidates shown, 0.8513. Their leaf counts need not equal 21. Increasing alpha to 0.030 lowers mean validation accuracy to 0.7950, about 5.6 percentage points below the best row.

The best mean validation score exceeds the unpruned score by about 0.75 percentage points in this run. This does not establish a general size of pruning benefit or guarantee a gain from an ensemble. If these scores are used to select alpha, assess the selected procedure on an untouched test set or through nested cross-validation.

Instability

A tree’s structure is decided by discrete choices. A small change in the data can change which split has the largest gain, altering the rows and candidate splits considered further down the tree. The following experiment holds the estimator’s random seed fixed and changes the training sample through bootstrap resampling: it draws the same number of rows with replacement, so some rows repeat and others are omitted.

import numpy as np
from collections import Counter
from sklearn.tree import DecisionTreeClassifier

rng = np.random.default_rng(0)
n = 400
a = rng.normal(size=n)
b = a + 0.3 * rng.normal(size=n)                # nearly the same information as a
c = rng.normal(size=n)
X2 = np.column_stack([a, b, c])
y2 = (a + b > 0).astype(int)

base = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X2, y2)
print(f"full data root feature: {base.tree_.feature[0]}")

picks = []
for _ in range(20):
    idx = rng.choice(n, size=n, replace=True)
    picks.append(DecisionTreeClassifier(max_depth=2, random_state=0)
                 .fit(X2[idx], y2[idx]).tree_.feature[0])
counts = {int(k): v for k, v in Counter(picks).items()}
print(f"root feature over 20 bootstraps: {counts}")
# full data root feature: 1
# root feature over 20 bootstraps: {0: 8, 1: 12}

Across twenty bootstrap resamples the root uses feature 0 eight times and feature 1 twelve times. The two features carry similar information, so different training samples can favor different root splits. These frequencies describe resampling from this particular dataset; they are not probabilities that either feature is the correct scientific explanation.

This makes structural stability relevant when interpreting a readable tree. A changed root need not cause a large change in predictions when the features are near-copies. The code measures root choices only; to measure predictive instability, compare the fitted trees on the same independent inputs.

Bagging averages predictions from models fitted to bootstrap samples. At a fixed input, for an average of \(M\) equally variable scalar predictions across repeated training samples, each with variance \(v\) and pairwise correlation \(\rho\), the variance is \(v[\rho+(1-\rho)/M]\). Disagreement can help averaging reduce variance, but bias and shared errors still matter. Even a linear fit can be unstable on an ill-conditioned design; the benefit of bagging depends on the fitting procedure and data, not just the model’s name.

What impurity importance measures

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

rng = np.random.default_rng(1)
n = 2000
y3 = rng.integers(0, 2, n)                      # independent random labels
X3 = np.column_stack([rng.integers(0, 2, n),    # 2 levels
                      rng.integers(0, 10, n),   # 10 levels
                      rng.integers(0, 100, n),  # 100 levels
                      rng.normal(size=n)])      # continuous
X_tr, X_te, y_tr, y_te = train_test_split(X3, y3, test_size=0.4, random_state=0)
t = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)
print("train and test accuracy:", round(t.score(X_tr, y_tr), 4),
      round(t.score(X_te, y_te), 4))
print("impurity importance:", np.round(t.feature_importances_, 4))
pi = permutation_importance(t, X_te, y_te, scoring="accuracy",
                            n_repeats=20, random_state=0)
print("permutation importance:", np.round(pi.importances_mean, 4))
# train and test accuracy: 1.0 0.5025
# impurity importance: [0.0453 0.1482 0.2648 0.5418]
# permutation importance: [ 0.0015 -0.0012 -0.0032 -0.0052]

The labels were generated independently of all four features, so there is no population predictive signal. Nevertheless, the fitted tree assigns positive impurity importance to every feature, with values 0.0453, 0.1482, 0.2648, and 0.5418 in this run. The tree’s training accuracy is 1.0, but its held-out accuracy is 0.5025. The held-out permutation values fluctuate near zero. Their finite-sample signs and ordering do not establish useful signal or harmful effects.

Impurity importance sums the training-sample-weighted impurity decreases from splits on a feature, then normalizes across features. It measures the share of recorded impurity reduction, not the number of times a feature was used. A feature with more distinct values offers more chances for a favorable split by accident. At a node with \(m\) distinct numeric values there are at most \(m-1\) separating thresholds before constraints and numerical handling; a binary feature offers at most one.

Impurity-based importances in tree ensembles can retain this preference for high-cardinality features. A held-out permutation importance instead measures the drop in a chosen score after shuffling one column for a fixed fitted model. Here the score is accuracy. Correlated features can complicate that interpretation, and shuffling can create unrealistic combinations. SHAP values answer another question about attribution of model predictions; they do not automatically establish predictive usefulness or causality. Always identify the model, data, and score behind an importance value.

Exercises

1. Approximating a diagonal boundary. Compare a decision tree against logistic regression on a diagonal boundary, across increasing depths and sample sizes.

Compare the depth needed for a given validation accuracy and how the result changes with sample size.

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score

rng = np.random.default_rng(0)
for n in (200, 2000, 20_000):
    X = rng.uniform(-1, 1, (n, 2))
    y = (X[:, 0] + X[:, 1] > 0).astype(int)     # a diagonal boundary
    lin = cross_val_score(LogisticRegression(), X, y, cv=5).mean()
    row = " ".join(
        f"d{d}:{cross_val_score(DecisionTreeClassifier(max_depth=d, random_state=0), X, y, cv=5).mean():.4f}"
        for d in (2, 4, 8, 16))
    print(f"n={n:6d}  logistic {lin:.4f}   tree {row}")
# n=   200  logistic 0.9650   tree d2:0.8500 d4:0.9000 d8:0.9050 d16:0.9050
# n=  2000  logistic 0.9940   tree d2:0.8725 d4:0.9410 d8:0.9755 d16:0.9760
# n= 20000  logistic 0.9989   tree d2:0.8671 d4:0.9524 d8:0.9916 d16:0.9928

2. Weak first splits and useful interactions. Build data where neither binary feature alone reduces population impurity, but their interaction determines the label, and compare constraint-based trees against a fully grown one that is cost-complexity pruned.

Compare the four growth and pruning settings. Does allowing deeper growth recover the interaction despite the noise features?

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score

rng = np.random.default_rng(1)
n = 4000
a = (rng.random(n) < 0.5).astype(int)
b = (rng.random(n) < 0.5).astype(int)
X = np.column_stack([a, b, rng.normal(size=(n, 2))])
y = (a ^ b)                                     # XOR: neither feature alone helps

for name, tree in (
        ("min_impurity_decrease=0.01", DecisionTreeClassifier(
            min_impurity_decrease=0.01, random_state=0)),
        ("max_depth=1", DecisionTreeClassifier(max_depth=1, random_state=0)),
        ("max_depth=2", DecisionTreeClassifier(max_depth=2, random_state=0)),
        ("grown then pruned", DecisionTreeClassifier(
            ccp_alpha=0.001, random_state=0))):
    print(f"{name:28s} cv {cross_val_score(tree, X, y, cv=5).mean():.4f}")
# min_impurity_decrease=0.01   cv 0.5100
# max_depth=1                  cv 0.5095
# max_depth=2                  cv 0.6072
# grown then pruned            cv 0.9092

3. Whether imputation costs you depends on the model. On data where the missingness pattern is the only signal, compare mean imputation with and without an indicator, for logistic regression and for a random forest, against native NaN handling.

Measure the indicator’s accuracy gain for each fitted procedure and compare with native missing-value handling.

import numpy as np
from sklearn.ensemble import HistGradientBoostingClassifier, RandomForestClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.impute import SimpleImputer
from sklearn.pipeline import Pipeline
from sklearn.model_selection import cross_val_score

rng = np.random.default_rng(0)
n = 4000
y = rng.integers(0, 2, n)
value = rng.normal(size=n)                      # the value carries no signal
missing = rng.random(n) < np.where(y == 1, 0.55, 0.10)   # the pattern does
X = np.column_stack([value, rng.normal(size=(n, 3))])
X[missing, 0] = np.nan

pipe = lambda m, ind: Pipeline([("i", SimpleImputer(strategy="mean",
                                                    add_indicator=ind)), ("m", m)])
print(f"{'model':22s} {'mean impute':>12} {'+ indicator':>12}")
for name, m in (("logistic regression", LogisticRegression(max_iter=2000)),
                ("random forest", RandomForestClassifier(n_estimators=200,
                                                         random_state=0))):
    a = cross_val_score(pipe(m, False), X, y, cv=5).mean()
    b = cross_val_score(pipe(m, True), X, y, cv=5).mean()
    print(f"{name:22s} {a:12.4f} {b:12.4f}")
print(f"{'HistGB (native NaN)':22s} "
      f"{cross_val_score(HistGradientBoostingClassifier(random_state=0), X, y, cv=5).mean():12.4f}")
# model                   mean impute  + indicator
# logistic regression          0.5138       0.7213
# random forest                0.6817       0.6900
# HistGB (native NaN)          0.6832