Decision Trees — Gini, Entropy, Splits

Why this session exists

A decision tree turns a table into a sequence of questions. Each internal node asks whether one feature crosses a threshold; each leaf stores a prediction. A small tree can be traced exactly, making it a useful way to understand nonlinear decisions before studying forests and boosting.

The hard part is choosing the questions. A greedy learner optimizes the next split, not the whole future tree. That makes training practical but creates blind spots and instability. We will calculate impurity reductions, implement a finite-numeric classification tree, inspect a prediction path, and compare depth and leaf-size controls without assuming every deep tree overfits or every shallow tree generalizes.

Prerequisites

Know array slicing, recursion, classification and evaluation and bias–variance reasoning. A feature matrix has shape $(n,d)$ and a one-dimensional label vector has length $n$. The scratch implementation requires nonempty finite numeric features and comparable class labels. Missing values, native categorical splits, sample weights and regression are separate extensions, not silently supported inputs.

(a) Intuition · 5 min

“Twenty questions” is a useful analogy, with one correction: a good split need not divide rows in half. It should improve the target distribution in the children. Isolating a small but pure class can be useful; an equal-sized split with identical class proportions gains nothing.

The three ideas to own before we code

1. Partition rows with one feature threshold at a time.
2. Score a candidate with the sample-weighted child impurity, not an unweighted average of children of different sizes.
3. Stop or prune according to explicit capacity and support rules. Pure training leaves are not proof of reliable probabilities on new data.

A tree partitions numeric feature space into axis-aligned regions. A leaf predicts a constant: a class distribution for classification or, under squared loss, the mean target for regression. Diagonal boundaries may need a staircase of rectangles. A linear model can represent some such boundaries much more compactly, while a tree can express threshold interactions without manually enumerating all feature products.

A brief history

The algorithm families differ in ways that still affect implementation. As summarized in the scikit-learn tree guide: ID3 uses greedy information-gain choices over categorical features and can create multiway branches; C4.5 extends the approach to continuous attributes and rule/pruning procedures; CART builds binary classification or regression trees.

Scikit-learn uses an optimized CART-style implementation, not an implementation of every feature of the original CART book. Its DecisionTreeClassifier accepts numerical arrays; nominal string categories need an explicit encoding. Some scikit-learn tree configurations support missing values, but that does not make the scratch implementation below missing-value aware. These distinctions are more useful than unsupported claims about which algorithm dominated every competition.

One tree's anatomy

This is an illustrative rule tree, not a claim about the exact fitted Iris tree or its sample counts. Every depicted leaf is reachable.

For petal length 4.8 and width 1.6: the first answer is no, the second yes, and the third yes, reaching versicolor. At exact equality 4.95, this diagram's “less than” rule takes the no branch. The scratch program uses this same strict comparison; scikit-learn uses <= with its learned thresholds. In exact arithmetic, a midpoint separates distinct observed values. In floating-point arithmetic it can round to the lower value; with strict < that would miss the intended partition. The code then uses the upper value as the threshold, so the lower value goes left and the upper value goes right. Boundary conventions still matter at inference.

The depth of a root-only leaf is zero. A depth-one tree is a stump with one split and up to two leaves. A depth-$D$ binary tree has at most $2^D$ leaves; few rows or early stopping can produce many fewer.

Impurity — three flavours

For class proportions $p_k$ at a node,

Gini is zero for a pure node and has maximum $1-1/K$ for $K$ equally represented classes. Entropy is zero for purity and has maximum $\log_2K$. The special values 0.5 and 1 apply to binary, balanced nodes only. Gini avoids logarithms; neither criterion is universally superior.

For squared-error regression, impurity is $V=\frac1n\sum_i(y_i-\bar y)^2$. The mean minimizes squared residuals because differentiation of $\sum_i(y_i-c)^2$ yields $c=\bar y$. Other regression criteria have different optimal leaf values: absolute-error leaves use medians, for example.

For a split into children $L,R$,

Worked classification split. A parent contains four positives and four negatives, so Gini is 0.5. A split produces a three-positive/one-negative child and a one-positive/three-negative child. Each child's Gini is $1-(3/4)^2-(1/4)^2=0.375$. Weighted child impurity is 0.375 and gain is 0.125. With entropy, parent impurity is 1 bit, each child about 0.8113 bits, gain about 0.1887 bits. Numeric gains depend on the criterion; do not compare them as if they were the same scale.

Worked regression split. Targets $[0,2,8,10]$ have mean 5 and variance 17. Splitting into $[0,2]$ and $[8,10]$ gives child means 1 and 9 and variance 1 each, so the reduction is 16. Those mean values, not a class majority, become the leaf predictions.

Why impurity rather than immediate classification accuracy?

Misclassification impurity is $1-\max_k p_k$. It is piecewise linear, not a step function of the majority identity: an 80%-positive leaf has accuracy 80%, while a 95%-positive leaf has accuracy 95%. The relevant failure is that weighted child accuracy can remain unchanged when every child has the same majority.

For example, split an 80%-positive parent into equal-sized children with positive fractions 0.7 and 0.9. Majority-class accuracy stays $(0.7+0.9)/2=0.8$. Parent Gini is 0.32, weighted child Gini is $(0.42+0.18)/2=0.30$, so Gini recognizes a 0.02 improvement in separation. Concavity gives nonnegative gain when child class distributions average to the parent; strictly concave Gini/entropy give positive gain when those distributions differ. This makes them more sensitive local surrogates, not guarantees of future test accuracy.

How a split is picked — the greedy loop

At each node, enumerate features and midpoints between distinct sorted observed values. Partition rows for each candidate, reject candidates violating minimum leaf size, compute weighted impurity, and keep the largest gain. Recurse with the chosen subsets. Ties in this implementation go to the first enumerated candidate; a library can randomize feature order and choose differently.

No lookahead means a positive-gain stopping rule can miss interactions. On the four equally weighted XOR rows, either root feature produces two 50/50 children, so root gain is zero, yet a depth-two tree can classify all four rows. Our implementation intentionally stops at nonpositive gain and fails on this fixture. Scikit-learn may allow zero-gain splits and solve it. “Greedy trees must always fail XOR” is too broad: the stopping policy matters.

The brute-force code repeatedly constructs masks and recomputes class counts. There are at most $d(n-1)$ candidate thresholds per node; rescanning labels makes it at least quadratic in node sample count, with additional sorting/counting overhead. Efficient implementations update counts as sorted boundaries move. Whole-tree cost also depends on depth, balance, sorting and implementation—not a universal $O(nd)$ training bound. Prediction cost is proportional to the visited path length, worst-case linear in a degenerate tree's size.

(c) Hands-on · 25 min

The full program implements a classification tree and uses the bundled Iris data for a small validation sweep. A final test set stays untouched until depth selection is finished. The mathematical fixtures include pure/mixed nodes, a known best split, duplicate rows, leaf-size constraints and the explicit XOR limitation.

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text
 
 
def gini(y):
    if len(y) == 0:
        return 0.0
    _, counts = np.unique(y, return_counts=True)
    return 1 - np.sum((counts/len(y))**2)
 
 
def entropy(y):
    if len(y) == 0:
        return 0.0
    _, counts = np.unique(y, return_counts=True)
    p = counts/len(y)  # observed classes have positive counts; no log epsilon needed
    return -np.sum(p*np.log2(p))
 
 
def best_split(X, y, min_leaf=1, impurity=gini):
    n, d = X.shape
    parent, best = impurity(y), None
    for j in range(d):
        values = np.unique(X[:, j])
        for lo, hi in zip(values[:-1], values[1:]):
            t = lo/2 + hi/2  # avoids overflow from lo + hi
            if t <= lo:
                t = hi  # strict < still separates adjacent representable values
            left = X[:, j] < t
            nl = int(left.sum())
            if nl < min_leaf or n-nl < min_leaf:
                continue
            gain = parent - (nl*impurity(y[left])+(n-nl)*impurity(y[~left]))/n
            if best is None or gain > best[2]:
                best = (j, float(t), float(gain))
    return best
 
 
def build(X, y, max_depth=5, min_leaf=1, impurity=gini, depth=0):
    X, y = np.asarray(X, dtype=float), np.asarray(y)
    if X.ndim != 2 or len(X) == 0 or X.shape[1] == 0 or y.shape != (len(X),):
        raise ValueError('nonempty 2D features and matching 1D labels required')
    if not np.isfinite(X).all() or min_leaf < 1:
        raise ValueError('finite features and positive min_leaf required')
    if max_depth is not None and max_depth < 0:
        raise ValueError('max_depth must be nonnegative or None')
    labels, counts = np.unique(y, return_counts=True)
    node = {'label': labels[counts.argmax()], 'n': len(y)}
    if len(labels) == 1 or len(y) < 2*min_leaf or (max_depth is not None and depth >= max_depth):
        return node
    split = best_split(X, y, min_leaf, impurity)
    if split is None or split[2] <= 1e-12:
        return node
    j, t, gain = split
    mask = X[:, j] < t
    node.update(feature=j, threshold=t, gain=gain,
        left=build(X[mask], y[mask], max_depth, min_leaf, impurity, depth+1),
        right=build(X[~mask], y[~mask], max_depth, min_leaf, impurity, depth+1))
    return node
 
 
def predict_one(node, x):
    while 'feature' in node:
        node = node['left'] if x[node['feature']] < node['threshold'] else node['right']
    return node['label']
 
 
def predict(node, X):
    return np.asarray([predict_one(node, row) for row in X])
 
 
def print_tree(node, names, indent=''):
    if 'feature' not in node:
        print(indent, 'predict', node['label'], 'support', node['n'])
        return
    print(indent, names[node['feature']], '<', round(node['threshold'], 4))
    print_tree(node['left'], names, indent+'  yes: ')
    print_tree(node['right'], names, indent+'  no: ')
 
 
def leaves(node):
    return [node] if 'feature' not in node else leaves(node['left'])+leaves(node['right'])
 
 
assert gini(np.array([0, 0])) == 0
assert np.isclose(gini(np.array([0, 1])), .5)
assert np.isclose(entropy(np.array([0, 1])), 1)
fixture_X = np.arange(4.).reshape(-1, 1)
fixture_y = np.array([0, 0, 1, 1])
assert best_split(fixture_X, fixture_y) == (0, 1.5, .5)
assert np.array_equal(predict(build(fixture_X, fixture_y), fixture_X), fixture_y)
assert all(n['n'] >= 2 for n in leaves(build(fixture_X, fixture_y, min_leaf=2)))
assert 'feature' not in build(np.zeros((2, 1)), np.array([0, 1]))
xor_X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
xor_y = np.array([0, 1, 1, 0])
assert 'feature' not in build(xor_X, xor_y, max_depth=2)
adjacent_X = np.array([1., np.nextafter(1., np.inf)]).reshape(-1, 1)
adjacent_y = np.array([0, 1])
assert np.array_equal(predict(build(adjacent_X, adjacent_y), adjacent_X), adjacent_y)
 
X, y = load_iris(return_X_y=True)
Xd, Xt, yd, yt = train_test_split(X, y, test_size=.2, stratify=y, random_state=42)
Xr, Xv, yr, yv = train_test_split(Xd, yd, test_size=.25, stratify=yd, random_state=43)
candidates = []
for depth in [1, 2, 3, 5, None]:
    tree = build(Xr, yr, max_depth=depth, min_leaf=2)
    tr, va = np.mean(predict(tree, Xr)==yr), np.mean(predict(tree, Xv)==yv)
    candidates.append((va, depth))
    print('depth', depth, 'train', tr, 'validation', va, 'leaves', len(leaves(tree)))
best_depth = max(candidates, key=lambda row: row[0])[1]
final = build(Xd, yd, max_depth=best_depth, min_leaf=2)
print('selected depth', best_depth, 'test', np.mean(predict(final, Xt)==yt))
print_tree(final, ['sepal length', 'sepal width', 'petal length', 'petal width'])
reference = DecisionTreeClassifier(max_depth=best_depth, min_samples_leaf=2, random_state=42).fit(Xd, yd)
print('sklearn test', reference.score(Xt, yt))
print(export_text(reference, feature_names=['sepal length', 'sepal width', 'petal length', 'petal width']))

What each block does

The impurity functions count only observed classes, so entropy never logs a zero probability and needs no arbitrary epsilon. min_leaf rejects a candidate that would make either child too small; checking only parent size would implement something closer to min_samples_split, not a minimum leaf-size guarantee.

Each node stores its majority label even before splitting, using sorted-label order to resolve ties. Recursion always reduces the sample set, and identical-feature contradictory-label rows become an impure leaf. max_depth=None is genuinely unbounded by a depth parameter; the old substitute of depth 20 was not. The positive-gain stop and finite numeric contract still limit what can be learned.

The depth sweep reports validation results without promised Iris percentages. The library comparison uses the selected depth and leaf size, but exact structures and probabilities need not match because thresholds, precision, ties and zero-gain handling differ. A printed small tree is an exact explanation of its own decision rule, not a causal explanation of the world.

Why single trees overfit

A sufficiently flexible tree can isolate noisy observations when feature values allow it. Contradictory labels at identical inputs cannot all be memorized by a deterministic feature-only tree, and pure nodes can stop with many samples. Thus “unlimited depth always creates one leaf per row and terrible validation accuracy” is false.

max_depth caps path length; min_samples_leaf imposes support per leaf; min_samples_split limits when a node is eligible to split. In scikit-learn, min_impurity_decrease uses the node's weight relative to the entire training set, not just the local gain used in the scratch code. Tune those choices on validation, not by declaring depth 5–10 universally safe.

Cost-complexity pruning considers

Scikit-learn uses total sample-weighted leaf impurity for $R(T)$. For a branch rooted at $t$, replacing its subtree by a leaf trades reduced leaf count against increased impurity; the weakest-link effective alpha is the increase in impurity divided by the number of removed leaves. cost_complexity_pruning_path supplies candidate alphas. Select an alpha using development folds; do not fit a pruning path on final test labels. Ensembling is a different response: it aggregates multiple learned partitions rather than pruning one.

(d) Production reality · 15 min

Ordering, representation and explanation trade-offs

Threshold trees generally need no standard scaling: positive affine rescaling preserves the order of observed values and corresponding partitions. Strictly monotone transformations preserve candidate training partitions in exact arithmetic, but nonlinear transforms can move an interpolated threshold differently for unseen values between observations; finite precision and histogram binning add further qualifications. “No scaling usually needed” is the useful practical rule, not exact invariance of every future prediction under every transformation.

Nominal integer codes impose an ordering on numeric threshold trees. A split can group contiguous codes, not arbitrary subsets. Permuting category codes can therefore change a shallow tree's fit. One-hot encoding or an estimator's explicit categorical support is a modeling choice. Missing values require a declared policy; do not assume the raw array contract handles them.

Regression leaves predicting means remain within their training-target range and extrapolate as piecewise constants outside observed feature ranges. This makes a plain regression tree a poor representation of an indefinitely increasing trend. Linear extrapolation can also be wrong; it merely encodes a different assumption.

A small tree offers readable if/then paths and automatic threshold interactions, but nearby training samples can change which root split wins. A linear model gives compact additive coefficients, yet collinearity can make those unstable too. An ensemble can improve validation quality while making a single global rule harder to state. Post-hoc feature attributions are model- and assumption-dependent, not substitutes for causal evidence or regulatory review.

Greedy importance is not scientific importance

Impurity importance aggregates weighted training impurity reductions attributed to each feature. A high-cardinality noise feature has many chances to achieve a lucky split. Test this by adding random columns to both training and validation matrices with consistent column schemas, fitting only on training, and comparing held-out behavior across seeds. A shallow tree can also be distracted by noise; no fixed depth guarantees immunity.

Permutation importance measures the score change after disrupting a feature for a fixed model and evaluation dataset. Correlated substitutes can mask individual importance; neither permutation nor SHAP magically identifies causal variables. The official permutation guide states these limitations explicitly.

Where this shows up in the rest of the plan

Random forests diversify tree fits with row bootstraps and feature choices. Boosting fits trees to a changing correction target. Feature engineering determines which partitions are easy to express. Tree-based tabular models are useful candidates, not guaranteed winners over all neural or linear alternatives.

(e) Recall + stretch · 10 min

1. Gini formula and maximum? Answer: $1-\sum p_k^2$, with maximum $1-1/K$; 0.5 only for balanced binary labels.
2. Entropy versus Gini? Answer: both quantify class mixture; entropy uses negative weighted log probabilities. Their gains can select different splits and are not numerically interchangeable.
3. How is a split chosen? Answer: enumerate valid feature/threshold candidates, minimize sample-weighted child impurity, then recurse under a stated stopping policy.
4. Why overfit? Answer: flexible partitions can adapt to finite-sample noise. They need not produce one leaf per observation, and a deep tree need not always fail validation.
5. Three controls? Answer: depth, minimum leaf support and pruning; distinguish a minimum parent sample count from a minimum child count.
6. Scaling? Answer: usually unnecessary for threshold trees, but encoding and missing-value handling remain substantive. Exact invariance claims require care about finite precision and thresholds on unseen inputs.
7. Regression change? Answer: use an appropriate target loss, such as variance for squared error, and predict leaf means. The classification code is not already a regression implementation.
8. CART, ID3, C4.5? Answer: binary classification/regression trees versus categorical information-gain multiway trees versus extended continuous/rule/pruning capabilities, as discussed above.
9. Why try ensembles for tabular data? Answer: they combine useful threshold interactions while controlling individual-tree instability or adding corrections. Benchmark the actual task; mixed strings, missingness and imbalance are not automatically solved by every implementation.
10. Stretch: depth two scores 65%, desired 90%. Answer: inspect train/validation gap, baseline, labels and splits before promising feasibility. If representation is too rigid, try deeper or engineered features; if the gap is large, test stronger support/pruning or additional representative data. Increasing depth to “cure variance” is not the default remedy, and no curve establishes that 90% is attainable.

Explain-out-loud test

Trace the diagram's 4.8/1.6 example, compute the 0.125 Gini gain by hand, and explain the XOR counterexample. Then state exactly which code line enforces minimum leaf size. A heading about impurity is not understanding until those calculations and paths are reproducible.

What comes next

Continue to Random Forest & Bagging, using the same split reasoning while introducing row resampling, per-node feature sampling and out-of-bag accounting.

Sources and execution boundary

Checked 2026-10-07: scikit-learn 1.7 tree formulation, algorithms and pruning and permutation importance. The scratch and sklearn programs are bounded CPU checks on fixtures and bundled Iris data. They do not prove a globally optimal tree, production accuracy, medical utility or explanation compliance; the diagram is an illustrative rule tree, not a rendered fitted-model benchmark.