Decision-tree splits and minimum leaf support

Last updated: 5 Oct 20265 min read

tutorial

A decision tree partitions feature space with successive rules; each split should reduce impurity on training data while retaining enough observations in every leaf to limit fragile rules.

Read one split before fitting a forest

A receipt-review team might split claims on the count of prior manual corrections. At a candidate threshold, the left and right child groups have different suspicious-claim fractions. Weighted Gini impurity scores how mixed those groups remain. A lower score than the unsplit parent indicates a training-data improvement. The code searches midpoint thresholds for one feature and returns the best eligible split. It is not a complete recursive tree implementation.

Guard tiny leaves

A threshold isolating one suspicious claim may make a pure child and look attractive on training data, yet fail on new claims. A declared minimum leaf size rejects such splits. Minimum size is a regularization choice, not a universal constant. Tune it in development folds, and inspect whether each leaf has enough positive cases for the intended action. Grouped validation prevents the same customer’s claims from appearing on both sides.

Understand what the tree can and cannot infer

A tree learns associations useful for prediction; a rule on prior corrections does not prove corrections cause fraud. Correlated features can substitute for one another, and a tree can change structure after small data shifts. Limit depth, leaf count or pruning based on a valid validation scheme. Rare-event metrics matter more than impurity alone at deployment.

Handle feature availability and missing values

A prior-correction count computed after review is future information for a pre-review decision. Freeze it at claim submission time. Missing counts need an explicit route in the feature pipeline; replacing them with an all-data median before splitting leaks validation information. The simple code requires complete numeric feature values and binary labels, so it rejects unsupported inputs instead of inventing a branch.

Compare to a baseline under the same clock

A tree may reduce training impurity yet lose to a constant or simple ruleset on a future holdout. Report the selected threshold, child support, holdout precision and recall, analyst capacity, and how the rule behaves by claim type. One split is interpretable; many nested splits can be difficult to maintain when claim categories or logging change. The applied project records the model-choice evidence.

Implementation

def gini(binary_labels):
    if not binary_labels:
        raise ValueError("empty leaf")
    event_rate = sum(binary_labels) / len(binary_labels)
    return 2 * event_rate * (1 - event_rate)

def best_correction_split(feature_and_label, minimum_leaf):
    if minimum_leaf < 2 or len(feature_and_label) < 2 * minimum_leaf:
        raise ValueError("insufficient support")
    if any(label not in (0, 1) for _, label in feature_and_label):
        raise ValueError("binary labels required")
    ordered = sorted(feature_and_label)
    candidates = []
    for position in range(minimum_leaf, len(ordered) - minimum_leaf + 1):
        if ordered[position - 1][0] == ordered[position][0]:
            continue
        left = [label for _, label in ordered[:position]]
        right = [label for _, label in ordered[position:]]
        weighted = (len(left) * gini(left) + len(right) * gini(right)) / len(ordered)
        midpoint = (ordered[position - 1][0] + ordered[position][0]) / 2
        candidates.append((weighted, midpoint, len(left), len(right)))
    if not candidates:
        raise ValueError("no supported split")
    return min(candidates)

claims = [(0, 0), (1, 0), (2, 0), (3, 1), (4, 1), (5, 1)]
impurity, correction_cutoff, left_count, right_count = best_correction_split(claims, 2)
assert correction_cutoff == 2.5
assert impurity == 0
assert (left_count, right_count) == (3, 3)

Performance and operating cost

Sorting N rows costs O(N log N). The direct list-slicing candidate loop is O(N²) time and O(N) transient space; cumulative class counts reduce the scan after sorting to O(N). Full trees multiply work across nodes and features.

Common Mistakes

Do not accept a pure training leaf with one case as stable evidence.
Do not interpret a split rule as a causal effect.
Do not evaluate a tree on claims from customers already present in training.