6.1 Decision Trees, Splitting Criteria, and Pruning: Each Leaf Is a Local Constant Region

If equipment-failure risk rises sharply above a load threshold, and bad weather changes that threshold, a linear model needs suitable nonlinear and interaction features. A decision tree can search for these conditions in the data.

A tree recursively partitions the input space. The resulting rules may look like ordinary if statements, but choosing each condition still requires optimizing a split criterion.

Learning Objectives

Understand trees as recursive partitions of feature space;
Correctly compute classification impurity, regression error, and weighted split gain;
Grasp how decision trees select numeric split points and make predictions at leaf nodes;
Distinguish between early stopping and cost-complexity pruning;
Identify the boundaries of trees in terms of stability, extrapolation, probability estimation, and interpretability.

1. The Tree Splits Space into Multiple Regions

Using a binary CART-style tree as an example, a numerical node selects a feature $j$ and a threshold $t$ :

R_{L} = {x : x_{j} \leq t}, R_{R} = {x : x_{j} > t} .

Subsequent nodes continue splitting the left and right regions. When a leaf is reached:

A regression tree typically outputs the mean of the training target values in that leaf;
A classification tree outputs the probability distribution derived from class counts, then selects the class according to a decision rule.

Thus, a standard regression tree provides a constant prediction within each leaf region. The boundaries are formed by a sequence of axis-aligned splits; the tree naturally captures feature-threshold interactions, though slanted boundaries may require many small rectangles to approximate them.

2. How Impurity in Classification Nodes Is Measured

The weight proportion of class $k$ within a node is $p_{k}$ . Common criteria include:

G i n i = 1 - \sum_{k} p_{k}^{2},

E n t r o p y = - \sum_{k} p_{k} \log p_{k} .

Use the convention $0 \log 0 = 0$ . Both criteria vanish for a pure node. Gini is the probability that two independent draws from the node’s weighted class distribution disagree; sampling two rows without replacement would give a different probability.

For regression trees, the criterion often uses the within-node squared-error or variance. If business loss is more aligned with absolute error, Poisson deviance, or other metrics, the appropriate implementation should be used and the definition of leaf values must be carefully examined.

3. Split Gain Must Be Weighted by Child Node Sizes

When a parent node $P$ is split into left and right children $L$ and $R$ , the node size is represented by the total sample weight $W$ :

Δ I = I (P) - \frac{W_{L}}{W_{P}} I (L) - \frac{W_{R}}{W_{P}} I (R) .

An unweighted average gives each child half the influence, even if one contains only a tiny fraction of the total weight. This can overreward a tiny pure leaf. With sample_weight, class proportions and split gain must use weights too; minimum sample count and minimum leaf weight remain separate constraints.

The trainer searches among all valid candidates for the split with the highest gain. This greedy step ensures the best possible split at the current node, but does not guarantee a globally optimal tree structure.

4. Numerical Thresholds Arise from Adjacent Distinct Values

For adjacent distinct values $a < b$ , every threshold $t \in [a, b)$ produces the same training partition under the rule $x \leq t$ . A midpoint is conventional; using $a$ is also valid. Repeating a threshold for duplicate values adds no candidate partition.

This Python 3 / NumPy fragment scans one numeric feature at one node. Supply one-dimensional feature values, comparable class labels, and optional nonnegative weights. Missing values require a separate routing policy. The caller decides whether the returned gain justifies growing the tree.

python

import numpy as np

def weighted_gini(y, weight):
    _, inverse = np.unique(y, return_inverse=True)
    class_weight = np.bincount(inverse, weights=weight)
    probability = class_weight / class_weight.sum()
    return 1.0 - np.sum(probability ** 2)

def best_numeric_split(x, y, sample_weight=None, min_samples_leaf=1):
    x = np.asarray(x, dtype=float)
    y = np.asarray(y)
    if x.ndim != 1 or y.ndim != 1:
        raise ValueError("x and y must be one-dimensional")
    if not isinstance(min_samples_leaf, (int, np.integer)) or min_samples_leaf < 1:
        raise ValueError("min_samples_leaf must be a positive integer")
    weight = (
        np.ones(len(y), dtype=float)
        if sample_weight is None
        else np.asarray(sample_weight, dtype=float)
    )
    if weight.ndim != 1 or len(x) != len(y) or len(y) != len(weight):
        raise ValueError("x, y and sample_weight must have equal length")
    if not np.all(np.isfinite(x)):
        raise ValueError("x must contain finite values")
    if not np.all(np.isfinite(weight)) or np.any(weight < 0):
        raise ValueError("weights must be finite and nonnegative")
    if len(y) == 0:
        return None
    total_weight = weight.sum()
    if not np.isfinite(total_weight) or total_weight <= 0:
        raise ValueError("total weight must be finite and positive")
    if len(y) < 2 * min_samples_leaf:
        return None

    order = np.argsort(x, kind="mergesort")
    xs, ys, ws = x[order], y[order], weight[order]
    parent = weighted_gini(ys, ws)
    best = None

    for cut in np.flatnonzero(xs[:-1] < xs[1:]):
        left_size = cut + 1
        right_size = len(xs) - left_size
        if left_size < min_samples_leaf or right_size < min_samples_leaf:
            continue

        left_weight = ws[:left_size].sum()
        right_weight = ws[left_size:].sum()
        if left_weight <= 0 or right_weight <= 0:
            continue

        child_impurity = (
            left_weight / total_weight * weighted_gini(ys[:left_size], ws[:left_size])
            + right_weight / total_weight * weighted_gini(ys[left_size:], ws[left_size:])
        )
        gain = parent - child_impurity
        lo, hi = xs[cut], xs[cut + 1]
        threshold = lo / 2.0 + hi / 2.0
        if not lo <= threshold < hi:
            threshold = lo
        if best is None or gain > best["gain"]:
            best = {"threshold": threshold, "gain": gain}

    return best

For x=[1, 2, 3, 4] and y=[0, 0, 1, 1], the function returns threshold 2.5 and gain 0.5. The midpoint calculation avoids overflowing hi - lo; falling back to lo also handles adjacent floating-point values with no representable midpoint.

A mature implementation would use cumulative category weights or cumulative sums to avoid slicing at every candidate threshold and would simultaneously scan across multiple features. Approximate/histogram-based methods first bin continuous values into a finite number of bins, trading a small amount of precision for faster training and reduced memory usage.

5. Leaves Also Have Statistical Issues

In a leaf node, if 9 training samples contain 8 positive instances, the unsmoothed probability is $8 / 9$ . When leaves are small or class distributions are sparse, this estimate can have high variance and often results in outputs of 0 or 1. These issues can be mitigated by:

Increasing min_samples_leaf or equivalent weight constraints;
Limiting the number of leaves or tree depth;
Performing probability calibration on independent calibration data;
Reporting log loss or Brier score stratified by leaf size, group, and time slice.

Class labels are derived from probabilities and thresholds. Even if the tree achieves good classification accuracy, it does not follow that the predicted probabilities are well-calibrated.

6. Early Stopping Is Not the Only Form of Pruning

Pre-pruning limits tree complexity during growth:

max_depth;
min_samples_split and min_samples_leaf;
max_leaf_nodes;
Minimum decrease in impurity;
Constraints on sample or leaf weights.

These thresholds do not have fixed ranges applicable to all datasets and should be selected within a leak-proof validation or cross-validation protocol.

Cost-complexity pruning instead starts with a larger tree and progressively minimizes:

R_{α} (T) = R (T) + α | \tilde{T} |,

where $R (T)$ is the sum of risks at leaf nodes and $| \tilde{T} |$ is the number of leaves. Increasing $α$ leads to smaller subtrees via weakest-link pruning. Candidate pruning paths should be generated within the training fold, and $α$ selected based on validation performance, never by inspecting the test set afterward.

7. Missing Values and Categorical Features Depend on Implementation

"The tree naturally supports missing values" is not a universal truth. Different libraries may:

Reject NaN values and require the pipeline to impute them first;
Assign a default split direction for missing values in each split;
Use surrogate splits to handle missingness;
Treat missing values as a separate category or introduce an additional indicator feature.

At deployment time, it's essential to distinguish between "truly unknown" and "data collection chain failures." Changes in missingness patterns themselves can indicate distribution shift.

Categorical variables cannot be arbitrarily mapped to integers. Encoding with red=1, blue=2, green=3 introduces artificial ordering. Techniques like one-hot encoding, target encoding, and native categorical splits each have distinct statistical and implementation requirements, particularly target encoding, which must be fitted within each fold.

8. Advantages and Limitations of a Single Tree

Advantages:

Does not require standardization of numerical features;
Can represent thresholds and higher-order interactions;
Small trees can be translated into clear, interpretable rules;
Exact candidate partitions depend on order and survive strictly increasing transforms in exact arithmetic; bins and floating-point rounding can change this.

Limitations:

Slight data changes can alter upper-level splits, leading to structural instability;
Local constant predictions within leaves often lack reliable extrapolation;
Deep trees tend to fragment noise into small leaves;
Axis-aligned partitions are inefficient for smooth or diagonal boundaries;
"Being used for splitting" does not imply causal importance.

Interpretability is not automatically granted by model type. A tree with hundreds of leaves is difficult for humans to understand manually; rules also depend on preprocessing steps, missing value handling, and the training data distribution.

Common Misconceptions

Trees don’t need math: They optimize impurity or loss at each node.
Every observed value needs a separate threshold test: Adjacent distinct values define candidate partitions; duplicates do not add new ones.
Trees are naturally robust to missing values: Whether support is provided and how missing values are routed depends on the implementation.
A depth of 3–6 is optimal: Capacity must be determined by data volume, noise levels, loss function, and validation protocol.
Smaller trees are always more interpretable: Interpretability also depends on feature semantics, preprocessing steps, and model stability.

Exercise

Manually compute the Gini impurity, entropy, and split gains for a three-class node with two candidate splits.
Add cumulative class weights to best_numeric_split to avoid redundant counting of each candidate split.
Compare pre-pruning and cost-complexity pruning within the same cross-validation setup.
Generate data with a diagonal boundary and observe how tree depth and number of leaf nodes grow.

Summary

Decision trees split the feature space greedily into local regions. To understand them correctly, you must see the splitting criterion, candidate search, leaf value estimation, and complexity control together, rather than as a sequence of intuitive rules alone.

The main challenge with a single tree is high variance. The next lesson explores how many slightly different trees can jointly make predictions, examines why averaging works, and identifies which errors it cannot eliminate.

Chapter 1: Propositional Logic: From Requirement Sentences to Decidable Formulas

Chapter 2: Sets and Operations: Describing Object Scope via Membership

Chapter 3: Direct Proof, Contrapositive, and Case Analysis: Building Verifiable Reasoning Chains

Chapter 4: Recursive Definitions and Mathematical Induction: Proving Along the Construction Process

Chapter 5: Binary Relations: Properties, Composition, and Closure

Chapter 6: Counting Principles: Addition, Multiplication, Inclusion-Exclusion, and the Pigeonhole Principle

Chapter 7: Graph Models and Traversal: First Define Edges, Then Choose Representation

Chapter 8: Probability Space and Conditional Probability: First Build the Model, Then Update Your Judgment

Chapter 9: Divisibility, Congruence, and Euclid's Algorithm: The Fundamental Structure of Integers

Chapter 10: Vectors and Inner Products: Turning Objects into Comparable Coordinates

Chapter 11: Limits, Derivatives, and the Chain Rule: Describing Local Change

Chapter 12: Self-Information, Entropy, and Coding: How Uncertainty Becomes Bits