Decision Trees, in depth: CART impurity, split search, cost-complexity pruning and a worked example

What a tree computes

Formally, a tree partitions the input space into disjoint regions R₁...R_M and predicts a constant c_m in each. For regression the best constant under squared error is the mean of the training targets in the region; for classification it is the class distribution, whose most likely class is the prediction. Because each split tests one feature against one threshold, the regions are axis-aligned boxes, and the prediction surface is a step function.

Finding the optimal tree of a given size is NP-hard, so CART grows greedily: at each node it picks the single split that most reduces impurity, recurses on the two children, and stops by rule. Greedy growth is why trees are fast to train and also why they are unstable, a theme that returns below.

Impurity: Gini, entropy and squared error

Impurity measures how mixed a node is. For a node whose class proportions are p_k, the two classification measures are:

• Gini impurity: G = 1 - Σ p_k². It is the probability that two rows drawn at random from the node have different labels. For two classes it peaks at 0.5 when the node is half and half.
• Entropy: H = -Σ p_k log₂ p_k. It peaks at 1 bit for a 50/50 binary node. Its reduction is called information gain.
• Squared error for regression: the variance of targets in the node. Reducing it is equivalent to choosing the split that most reduces the sum of squared errors around each child's mean.

A split sends n_L rows left and n_R right. Its quality is the parent impurity minus the size-weighted child impurity: gain = I(parent) - (n_L/n) I(L) - (n_R/n) I(R). Gini and entropy pick the same split most of the time. Gini is slightly cheaper to compute, which is why it is scikit-learn's default. Misclassification error, 1 - max p_k, is a poor growing criterion because it is flat over many splits that clearly improve purity, though it is a natural measure for pruning.

The split search and its cost

For a numeric feature, only thresholds between consecutive distinct sorted values can change the partition, so the search sorts the node's rows by the feature once and sweeps left to right, moving one row at a time from the right child to the left and updating class counts incrementally. Each candidate costs O(1) to evaluate, so one feature costs O(n log n) for the sort plus O(n) for the sweep, and a node costs O(d n log n) over d features. Summed over a balanced tree's levels, total training is roughly O(d n log² n), which is why trees train in seconds on millions of rows.

def gini_from_counts(counts, n):
    return 1.0 - sum((c / n) ** 2 for c in counts) if n else 0.0

def best_split(X, y, n_classes, min_leaf=1):
    # Return (gain, feature, threshold) for the best binary split of one node.
    n = len(y)
    total = [0] * n_classes
    for label in y:
        total[label] += 1
    parent = gini_from_counts(total, n)
    best = (0.0, None, None)
    for f in range(len(X[0])):
        order = sorted(range(n), key=lambda i: X[i][f])
        left, right = [0] * n_classes, total[:]
        for pos in range(n - 1):
            i = order[pos]
            left[y[i]] += 1
            right[y[i]] -= 1
            a, b = X[i][f], X[order[pos + 1]][f]
            nl = pos + 1
            if a == b or nl < min_leaf or n - nl < min_leaf:
                continue                       # no threshold between equal values
            child = (nl * gini_from_counts(left, nl) + (n - nl) * gini_from_counts(right, n - nl)) / n
            if parent - child > best[0]:
                best = (parent - child, f, (a + b) / 2)
    return best

def grow(X, y, n_classes, depth=0, max_depth=5, min_leaf=1):
    gain, f, t = best_split(X, y, n_classes, min_leaf)
    if f is None or depth == max_depth:
        return {"leaf": True, "counts": [y.count(k) for k in range(n_classes)]}
    L = [i for i in range(len(y)) if X[i][f] <= t]
    R = [i for i in range(len(y)) if X[i][f] > t]
    return {"leaf": False, "feature": f, "threshold": t,
            "left": grow([X[i] for i in L], [y[i] for i in L], n_classes, depth + 1, max_depth, min_leaf),
            "right": grow([X[i] for i in R], [y[i] for i in R], n_classes, depth + 1, max_depth, min_leaf)}

Production libraries avoid re-sorting at every node, handle sample weights, and visit features in random order, so equally good splits can differ between runs unless random_state is fixed.

Worked example: twelve loans

Twelve loan applications have two features, income_k (thousands) and prior_default (0 or 1), and a label, 1 if the loan defaulted. Six of the twelve defaulted, so the root Gini is 1 - 0.5² - 0.5² = 0.5. The incomes of the defaulters are 22, 25, 28, 30, 35 and 48; the repayers earn 31, 40, 46, 52, 58 and 65. Prior default is 1 for incomes 22, 28, 35, 48 and 52.

The best split is income at most 30.5, the midpoint between 30 and 31. Its left child is pure, four defaults, and becomes a leaf. The right child holds eight rows with two defaults, Gini 1 - 0.25² - 0.75² = 0.375. Within it, splitting on prior default sends five rows with no defaults one way and three rows with two defaults the other, weighted Gini (3/8) x 0.444 = 0.167, a gain of 0.208. The remaining mixed node, incomes 35, 48 and 52, splits at 50 into two defaulters and one repayer, and the tree now classifies every training row correctly.

That last split is the warning. It isolates one applicant who earned 52 thousand and repaid despite a prior default. Is income above 50 truly protective for people with a prior default, or is this one lucky borrower? With one row there is no way to tell, and a fully grown tree always ends up answering questions like that with a confident leaf. Running the same data through scikit-learn 1.8.0 reproduces this tree, split for split, and its pruning path is the subject of the next section.

Growing and stopping

There are two ways to stop a tree memorizing noise. Pre-pruning stops growth early using limits:

Pre-pruning is fast but short-sighted: a split with little gain can enable valuable splits below it, as with XOR-like interactions where neither feature helps alone. Post-pruning grows the full tree and then removes branches that do not pay for themselves, which is what CART was designed around. The general picture of complexity against error is covered in the bias-variance article.

Cost-complexity pruning

Cost-complexity pruning scores every subtree T by R(T) + α|T|, where R(T) is the total impurity of its leaves, each weighted by its share of training rows, and |T| is the number of leaves. Breiman's original formulation used misclassification cost for R; scikit-learn uses the weighted impurity of the chosen criterion, so the numbers here are weighted Gini. For each internal node t, the effective alpha is (R(t) - R(T_t)) / (|T_t| - 1): the impurity the branch removes, per extra leaf it adds. Repeatedly cutting the node with the smallest effective alpha, the weakest link, produces a nested sequence of trees from the full tree down to the root.

In the worked example, the node with incomes 35, 48 and 52 holds 3/12 of the rows at Gini 0.444, so R(t) = 0.111 and its pure children have R = 0; effective alpha 0.111 over one extra leaf. It is the weakest link and goes first. Next, the prior-default node holds 8/12 of the rows at Gini 0.375, R(t) = 0.25, against a now two-leaf subtree with R = 0.111: alpha (0.25 - 0.111) / 1 = 0.139. Finally the root, R = 0.5 against 0.25, alpha 0.25. scikit-learn's cost_complexity_pruning_path returns exactly alphas 0, 0.111, 0.139 and 0.25. Choose among them by cross-validation, not by training error.

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

base = DecisionTreeClassifier(random_state=0)
alphas = base.cost_complexity_pruning_path(X_train, y_train).ccp_alphas[:-1]   # drop the root-only tree
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=0)
scores = [cross_val_score(DecisionTreeClassifier(random_state=0, ccp_alpha=a),
                          X_train, y_train, cv=cv, scoring="roc_auc").mean() for a in alphas]
best_alpha = alphas[int(np.argmax(scores))]
model = DecisionTreeClassifier(random_state=0, ccp_alpha=best_alpha).fit(X_train, y_train)

A common refinement is the one-standard-error rule: pick the largest alpha whose cross-validated score is within one standard error of the best, trading a little accuracy for a simpler, more stable tree. Fold design matters as much as the search; see cross-validation fold design for grouped and time-ordered data.

Practical details in scikit-learn

• Missing values. Since scikit-learn 1.3, DecisionTreeClassifier and DecisionTreeRegressor accept NaN: for each threshold the splitter tries sending all missing rows left and then right and keeps the better. It does not use surrogate splits, the classic CART approach found in R's rpart.
• Categorical features. The scikit-learn tree treats every feature as numeric, so one-hot or ordinal encode first. High-cardinality categories one-hot encoded produce many weak features; target encoding with out-of-fold statistics often works better, if you guard against leakage.
• Class imbalance. class_weight='balanced' reweights impurity so that the minority class is not ignored. Leaf probabilities from a single deep tree are coarse and overconfident; calibrate them if you use them as probabilities, as explained in model calibration.
• Monotonic constraints. Since 1.4, monotonic_cst forces the prediction to rise or fall with a feature, useful where regulation or common sense requires it, such as risk never falling as debt rises. It is not supported for classification when the training data has missing values.
• Reading the tree. export_text and plot_tree show the rules. Impurity-based feature_importances_ are biased toward features with many distinct values; prefer permutation importance on held-out data.

Failure modes

Trees fail in characteristic ways, and each has a recognizable symptom.

• Instability. Remove a few rows and the root split can change, and with it the whole tree. If people read the rules, check stability by refitting on bootstrap samples and comparing the top splits.
• No extrapolation. A regression tree predicts a training-set mean in every leaf, so it can never predict above the highest target it has seen. Trees on trending data, such as prices over time, flatten at the edge.
• Staircase boundaries. A diagonal boundary such as x₁ > x₂ needs many axis-aligned splits. Adding the engineered feature x₁ - x₂ fixes it in one.
• Overfitting. A training accuracy near 100% with a much lower validation score is the classic sign; the overfitting article covers how to measure the gap honestly.
• Leakage looks like genius. A shallow tree that splits first on an identifier or a post-outcome field and scores near-perfectly is almost always leaking. Trees find leaks faster than any other model.

When a single tree is the right model

A single pruned tree is the right choice when the model must be read, audited or turned into business rules, when the data is small, or when you need a fast baseline. It is rarely the most accurate tabular model. Random forests average decorrelated deep trees to cut variance, and gradient boosting fits shallow trees to residuals to cut bias; both trade readability for accuracy and reuse every idea above.

What to do next

1. Implement best_split from this article and reproduce the worked example's 0.25 root gain.
2. Fit DecisionTreeClassifier(random_state=0) on your own tabular data and compare training and validation scores to see the overfitting gap.
3. Compute cost_complexity_pruning_path, cross-validate each alpha and apply the one-standard-error rule.
4. Print the pruned tree with export_text and check every top split for leakage.
5. Refit on five bootstrap samples and compare the top splits to judge stability.
6. Replace impurity importance with permutation importance on held-out data.
7. Benchmark the pruned tree against a random forest and a gradient-boosted model before choosing.