Decision Trees and Impurity Splitting

Shift one training point across a threshold and a tree can restructure entirely: a different root split, different children, a visibly different model with nearly identical accuracy. That instability is not a bug in the fitting procedure. It is the direct consequence of greedy, discrete decisions, and it is the property every ensemble method is built to exploit or suppress.

A decision tree partitions feature space into axis-aligned boxes and predicts a constant in each. Fitting means choosing the partition, and finding the optimal one is NP-hard, so every practical algorithm is greedy: pick the single best split now, recurse, never reconsider.

What "best split" means

At a node with class proportions \(p_k\), the two standard impurity measures are

A split is scored by the impurity of the parent minus the weighted impurity of the children, and the algorithm takes the maximum over every feature and every candidate threshold. For a continuous feature, sorting the values and sweeping the threshold makes this \(O(n \log n)\) per feature per node, since impurity statistics update incrementally as points cross the boundary.

Gini and entropy agree on the chosen split the overwhelming majority of the time; both are concave, both are maximised at uniform class proportions, and both are zero on a pure node. Gini is marginally cheaper because it avoids logarithms. The choice between them is not where model quality is decided, and treating it as a tuning knob is misplaced effort.

For regression the analogue is variance reduction, which is squared-error impurity, and the node prediction is the mean of the targets in it.

Why a single tree is unstable

Two structural facts explain most of the behaviour.

Greedy splits compound. The root split is chosen on the full data, and every subsequent decision is conditional on it. A near-tie at the root, common when two features carry similar signal, propagates into a completely different subtree structure. The model is high-variance in the bias-variance sense: small data perturbations produce large changes in the fitted function.

Splits are axis-aligned. A boundary at 45 degrees in two correlated features has to be approximated by a staircase, requiring many splits to represent something a single linear term captures exactly. Trees are not rotation-invariant, and rotating the feature space genuinely changes what they can learn cheaply. This is a real limitation on smooth, rotated structure, and simultaneously the property that makes them robust to monotone feature transformations: replacing a feature by its log changes no split ordering at all, so no scaling, no standardisation, and no skew correction is ever needed.

Impurity-based importance is biased

The default feature_importances_ in most libraries sums impurity decrease attributable to each feature. It systematically favours high-cardinality and continuous features, because a feature with more candidate thresholds gets more chances to find a spuriously good split. A pure-noise continuous column will out-rank a genuinely informative binary one on small data.

Permutation importance, measured on held-out data, avoids this class of bias by asking what actually degrades when a feature is shuffled, at the cost of one extra pass per feature. It has its own failure with correlated features, where shuffling one leaves the information available through its correlate and both look unimportant.

When it breaks

Extrapolation is impossible by construction. Predictions are constants on boxes, so beyond the range of the training data a tree returns the value of the nearest leaf, forever. For a time trend or any target with drift, this is fatal, and no amount of ensembling repairs it: a random forest of trees that cannot extrapolate also cannot extrapolate. Differencing or explicitly modelling the trend outside the tree is the standard fix.

Depth is the wrong complexity knob alone. A depth-12 tree can have anywhere from 13 to 4,096 leaves depending on how balanced it is. Minimum samples per leaf and minimum impurity decrease control effective complexity more directly, and cost-complexity pruning, which grows a full tree and then prunes back with a penalty \(\alpha\) per leaf, is more principled than a depth cap chosen by hand.

Class imbalance distorts splitting. With a 1:1000 ratio, impurity barely moves for splits that isolate the minority class, so the greedy search never selects them and every leaf predicts the majority. Class weights inside the impurity calculation address it; resampling addresses it while breaking calibration.

Missing values need an explicit policy. Trees have no natural handling. Surrogate splits (CART), sending missing to whichever side reduces loss (XGBoost's learned default direction), and treating missing as its own category are three different decisions with different behaviour when the missingness pattern shifts between training and serving.