TreesGENERALFRAMEWORK-SPECIFICSIMULATED

How a Tree Chooses a Split

Gini, entropy or variance reduction score each candidate cut; the greedy search picks the best one at each node and recurses. Stopping rules are the only thing between that and a leaf per point.

Target & data What to measure What must stay true ▶ Decision Tree Visualizer

The problem, the obvious approach, and why it breaks

Every lesson starts where the work starts: someone has a problem, and the first model that comes to mind looks fine offline.

The question

How does a tree decide which feature and which threshold to split on, why does growing it to completion memorise the data, and what does that imply for scaling and for categoricals?

The problem

A retailer's churn tree splits first on customer_id_hash, then on signup_month, and achieves near-perfect training accuracy. The analyst is proud of the top split until someone asks what a hash of the customer id could possibly mean for churn.

The obvious approach

Let the tree decide what matters. Grow it fully, look at the top splits to learn what drives churn, and prune later if it overfits.

Why it breaks

The split criterion rewards any cut that makes the children purer. A feature with a million distinct values can always find a cut that isolates a pure group, so the greedy search chooses the id hash — not because it means anything but because high cardinality makes purity cheap.

How it breaks — usually after the offline metric looked fine

The split criterion rewards any cut that makes the children purer. A feature with a million distinct values can always find a cut that isolates a pure group, so the greedy search chooses the id hash — not because it means anything but because high cardinality makes purity cheap.
Grown to completion, the tree keeps splitting until each leaf is pure, which on real data means a leaf per point or per handful of points. Training accuracy is trivially perfect; the tree is a memory of the training set (Overfitting).
The "insight" from the top splits is an artefact of the criterion's bias toward cardinality, and the retention team acts on it.

Problem→Target→Data→Representation→Split→Model→Training→Evaluation→Validation→Deployment→Inference→Monitoring→Drift→Retraining

What is being predicted, and from what data

This domain leads with these two. A target nobody defined precisely is a label nobody can trust, and a dataset nobody can describe is a model nobody can debug.

Target

Predict whether a subscriber cancels in the next billing cycle. The label is the cancellation event, observed at the end of the cycle.
The decision is which customers get a retention offer; the model must rank real risk, not identify individuals it has seen.

Data

One example is one subscriber-cycle with usage aggregates, plan, tenure, support contacts, and — because it was in the table — a hashed customer id and the signup month.
Around a million rows. Usage features are heavy-tailed; plan has six values; the id hash has a million; signup month has a hundred and twenty.

How it actually works

Precisely enough to predict its behaviour — not a framework API.

At a node holding a set of rows, the algorithm considers every feature and, for each, every threshold between consecutive sorted values. For each candidate it computes the impurity of the two children, weighted by their sizes, and chooses the candidate with the largest reduction from the parent's impurity. Then it recurses into each child.
The impurity measures are interchangeable in spirit. Gini: 1 − Σ p_k², the chance two random rows from the node disagree. Entropy: −Σ p_k log p_k, information needed to encode a row's class. Variance (regression): the mean squared deviation from the node's mean label. All are zero for a pure node and largest for a maximally mixed one; the gain is parent impurity minus size-weighted child impurity.
Two properties follow. The search only compares values *within* a feature, so a monotone transform of any feature changes nothing — trees do not need scaling. And a feature with more distinct values offers more candidate cuts and more chances to find a purity gain by accident, so the criterion is biased toward high-cardinality features, which is why the id hash won.

Scoring a candidate cut

A split is a feature and a threshold. To score it, send each row of the node left or right, compute the impurity of each child, weight by child size, and subtract from the parent's impurity. The larger the drop, the better the split. Do that for every feature and every threshold between adjacent sorted values, and take the best. That is the whole search at one node.

For Gini on a two-class node, a child that is all one class scores zero and a fifty-fifty child scores one half. The parent is mixed; a good split sends the churners mostly one way and the rest the other, so both children are purer than the parent. Variance reduction for regression is the same arithmetic with squared deviations from the mean in place of class proportions.

Gini gain for one candidate threshold

1import numpy as np
2 
3def gini(y):
4    # y: 0/1 labels at a node
5    if len(y) == 0:
6        return 0.0
7    p = y.mean()
8    return 1.0 - p**2 - (1 - p)**2
9 
10def gain(x, y, threshold):
11    left, right = y[x < threshold], y[x >= threshold]
12    n = len(y)
13    weighted = (len(left) / n) * gini(left) + (len(right) / n) * gini(right)
14    return gini(y) - weighted
15 
16def best_split(X, y):
17    best = (0.0, None, None)                       # (gain, feature, threshold)
18    for j in range(X.shape[1]):
19        xs = np.unique(X[:, j])
20        for t in (xs[:-1] + xs[1:]) / 2:           # midpoints between sorted values
21            g = gain(X[:, j], y, t)
22            if g > best[0]:
23                best = (g, j, t)
24    return best

Notice what the loop iterates over: the *distinct values* of each feature. A feature with a million distinct values gets a million chances per node to find a lucky cut; a feature with six gets five. Nothing in the criterion corrects for that, which is the cardinality bias in one line.

Why full depth is a lookup table

Recursion stops on its own only when a node is pure or has one row. On real data with label noise, purity is reached by isolating individual rows, so the natural end state is a leaf per point — training impurity zero, training accuracy perfect, and each leaf's "rule" is the path to one customer. The visualiser at /ml/tree shows held-out accuracy peaking at a modest depth and falling as the tree keeps cutting.

Stopping rules interrupt that. Maximum depth bounds the number of questions; minimum rows per leaf forbids isolating a handful; minimum gain refuses splits that barely help. Each is a way of saying "a region this small is noise, not a rule", and each is a hyperparameter with a validation-chosen value.

Stopping rules and how each one fails

Trigger	Symptom	Cause	Response
No stopping rule	Training accuracy perfect; held-out accuracy poor; thousands of leaves	Recursion continued to purity, isolating individual rows	Choose depth and leaf size on validation; the visualiser's depth curve is the shape to look for
Max depth too low	Both accuracies mediocre and equal; important interaction absent	The tree ran out of questions before it could express plan × tenure	Raise depth until validation stops improving, then stop
Min leaf size too high	A small high-churn plan never gets its own leaf	The segment has fewer rows than the minimum and cannot be split out	Lower the minimum or model the segment separately; check per-segment quality
Identifier-shaped feature present	Top split on a hash or a month; perfect training fit	High cardinality made pure children cheap to find	Remove or coarsen the feature; verify with permutation importance

No scaling needed; categoricals need care

The search compares each feature only against thresholds drawn from its own values, so replacing revenue with log-revenue, or dollars with cents, produces exactly the same sequence of splits. This is why trees are indifferent to scaling and to monotone transforms — a genuine convenience, and the reason a feature pipeline for a tree ensemble can be much simpler than one for a linear model.

Categoricals are the opposite. A one-hot encoding turns one column into many binary ones, and the tree must spend a level per value to express "plan is A or C". A high-cardinality categorical one-hot encoded is both slow to search and a memorisation risk per value. Grouping rare levels, out-of-fold target encoding, or native categorical splitting are the options, and each carries a leakage discipline.

leakageplan_target_enc (mean churn rate per plan)Target encoding fitted on the rows it encodes

looks like A sensible replacement for one-hot: each plan value becomes the average churn rate among subscribers on that plan, computed over the training set.

why it leaks Each row's own label contributed to the mean it is encoded with. For a rare plan with three rows, the encoded value is nearly the row's own label, and the tree splits on it as if it were a feature.

offline

Training and in-sample validation both improve; the rare-plan rows are classified almost perfectly by a feature that contains their answer.

production

At serving time the encoding is the historical plan mean, which does not contain the new subscriber's label; the model over-trusts a feature that was far more informative in training than it is now.

fix Compute the encoding out-of-fold — each row encoded with the mean from the other folds — and freeze the full-training-set means into the artifact for serving; smooth rare levels toward the global mean.

when this feature is fine When the encoded statistic is computed strictly from rows *before* the encoded row in time and the same as-of computation runs at serving, the feature is a legitimate historical aggregate (Aggregation Features).

How to build it

Most important first.

Set stopping rules and choose them on validation: maximum depth, minimum rows per leaf, minimum impurity decrease. These are the tree's regularisation (Regularisation).
Remove identifiers and near-identifiers before growing anything. A feature whose cardinality approaches the row count is a memorisation device, not a signal (Feature Selection).
Handle high-cardinality categoricals deliberately: group rare values, use target encoding fitted inside the fold, or use an implementation with native categorical support — never naive one-hot into a tree that will spend depth on each value (Categorical Encoding, Target Encoding).
Read split importance with the cardinality bias in mind; prefer permutation importance on held-out data over impurity-based importance when the features differ in cardinality (Permutation Importance).

What to measure

Which number actually maps to the decision — and which numbers look relevant and are not.

Held-out accuracy against depth and leaf size — the number the stopping rules are chosen on. Training accuracy at full depth is always perfect and says nothing.
Per-feature cardinality alongside impurity importance. A feature that is both high-cardinality and high-importance is suspect until permutation importance confirms it.
Do not measure "purity of leaves" as quality. A pure leaf with three rows in it is the definition of memorisation.

What must stay true after deployment

The field this whole domain exists for. A model is a set of assumptions with weights attached; these are the ones a monitor or a test should be checking.

Assumptions

No feature at serving time functions as an identifier of a training row; new categorical values are mapped to a defined group rather than to an arbitrary branch.
The label rate within each leaf remains close to what it was at training; a leaf whose rows drift in behaviour keeps its old constant until retrain.
The categorical vocabulary is stable enough that grouped rare values remain rare and the encodings remain fitted to something real.

How to verify — offline, online, and over time

Offline: the depth and leaf-size sweep on held-out data; a cardinality audit of every feature the tree splits on; permutation importance compared to impurity importance.
Online: monitor the share of serving rows that hit unseen categorical values and the branch they take; and per-leaf outcome rates as labels arrive against the leaf constants.
Over time: re-run the audit at each retrain. New columns join tables without asking, and the next identifier-shaped feature arrives silently.

What can go wrong

Failure modes in production

The id hash is removed and signup_month takes over — a hundred and twenty values that happen to correlate with cohort quality; still a proxy for the individual, still spent on isolation rather than on a rule.
Minimum leaf size is set, and rare plans with fewer rows than the minimum can never be split on; the tree is blind to the segment that churns most.
Target encoding of a categorical is fitted on the full training set rather than out-of-fold, and the encoded value leaks each row's own label into its feature; the tree finds it immediately (Preprocessing Leakage).

What the recommended approach costs

Stopping rules trade fit for generalisation and there is no free setting: a minimum leaf size that stops memorisation also prevents a real small segment from getting its own leaf.
Grouping rare categorical values loses information about them; the alternative — letting the tree isolate them — is memorisation. Target encoding recovers some of it at the cost of leakage discipline.
The greedy search is why trees are fast to grow and why they miss interactions that no single split reveals; exhaustive search over pairs is exponential and nobody does it.

Misreads

"The tree found that the id hash predicts churn." The criterion found that a million distinct values can be cut into pure groups. That is a property of cardinality, not of churn.
"Trees need scaled inputs like everything else." The split search compares a feature to thresholds drawn from its own values; any monotone rescaling gives the same tree. Scaling is wasted work for a tree and required for a penalised linear model.
"Impurity importance tells us what matters." It tells us which features were split on most, weighted by gain, and it is biased toward the features with the most candidate cuts.

Where this applies

ML advice is stated as universal far more often than it is. These labels say what each claim is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.

GENERALGreedy impurity-reduction with axis-aligned thresholds is how every mainstream tree learner grows, so the memorisation-at-full-depth and the cardinality bias appear in every library; only the stopping-rule names differ.
FRAMEWORK-SPECIFICNative categorical handling — splitting a category set into two groups directly rather than one-hot — exists in some implementations (LightGBM, CatBoost, recent XGBoost) and not in classic CART; where it exists it changes the high-cardinality advice from "avoid" to "use it, but the split search over subsets has its own overfitting risk".
SIMULATEDThe Decision Tree Visualizer computes real Gini splits on seeded 2D points; its depth-by-depth accuracy curves show the memorisation mechanism and are not a measurement on any subscriber data.

Where the depth lives

This domain teaches the model and hands the rest off by name.

DSAbinary-tree