Decision Trees: Splitting Criteria & Pruning

A decision tree predicts by asking a sequence of feature questions. Each internal node partitions its current observations; each leaf estimates a class distribution or numeric response. Axis-aligned splits can combine into nonlinear boundaries and automatically express interactions: a split on pressure below one temperature threshold need not apply above it.

Greedy partitioning #

For classification with class proportions $p_k$ in node $t$, common impurities are

$$H(t)=-\sum_k p_k\log p_k$$

and

$$G(t)=1-\sum_kp_k^2.$$

Both are zero for a pure node and larger when classes mix. For candidate split producing children $t_L,t_R$, impurity decrease is

$$\Delta I=I(t)-\frac{n_L}{n_t}I(t_L)-\frac{n_R}{n_t}I(t_R).$$

The algorithm searches candidate feature thresholds and chooses the greatest immediate decrease. This is greedy: it does not guarantee the globally best tree, and a weak first split can block a better later structure.

For regression, leaves commonly predict their mean and splits reduce squared error or absolute deviation. A piecewise-constant tree cannot extrapolate a trend beyond observed leaves.

Worked Gini split #

A parent contains four positives and six negatives, so

$$G_{parent}=1-0.4^2-0.6^2=0.48.$$

A threshold creates equal-size children: left has four positives and one negative, right has five negatives. Their impurities are $1-0.8^2-0.2^2=0.32$ and 0. Weighted child impurity is $0.5(0.32)+0.5(0)=0.16$, so the decrease is 0.32.

That looks strong, but it could isolate a batch ID or post-outcome code. Split quality measures association in the node, not causal validity or future availability.

Why a fully grown tree overfits #

As splitting continues, leaves contain fewer observations. Eventually a tree can isolate individual labels using accidental thresholds. Training impurity falls monotonically, while estimates in tiny leaves have high variance. Small perturbations to data can change an early split and therefore the entire subtree.

Pre-pruning limits depth, leaf count, minimum samples, or minimum impurity decrease. Post-pruning first grows a larger tree and then minimizes a cost-complexity objective such as

$$R_\alpha(T)=R(T)+\alpha|T|,$$

where $R(T)$ is leaf error/impurity and $|T|$ is the number of leaves. Validation selects $\alpha$. Pruning removes branches whose fit improvement is not worth their complexity.

Representation still matters #

Monotone rescaling does not change the order of numeric thresholds, so trees usually need no standardization. But representation choices remain decisive:

• One-hot encoding lets a tree combine categories only through multiple splits; native categorical partitioning may search subsets directly.
• High-cardinality features offer many candidate splits and greater opportunity for chance improvement.
• Missing values require explicit routing or learned default directions.
• Continuous variables with many distinct values may be favored over low-cardinality categories by some criteria.

Thresholds are data-dependent discontinuities. A tiny measurement change around a split can flip the entire downstream path even when physical risk changes smoothly.

Probabilities and class imbalance #

A leaf probability is often the observed class fraction in that leaf. Deep leaves make extreme, poorly calibrated estimates. Class weights change the fitted objective and leaf proportions; they do not automatically convert scores into deployment probabilities. Minimum leaf size, smoothing, and separate calibration can help.

Accuracy-oriented impurity can ignore a rare but costly class. Use task-relevant weights and validate recall, precision, cost, and segment behavior. Do not infer fairness or safety from a compact tree diagram.

Interpretation boundaries #

A shallow tree can explain its own prediction path: which encoded thresholds led to a leaf. It does not explain causation, and an individual path can be unstable under retraining. Global impurity-based feature importance is biased toward variables with many potential split points and spreads/steals credit among correlated features.

Counterexample: two redundant sensors measure the same condition. The tree chooses sensor A first and gives it nearly all importance; retraining may choose B with identical predictions. “A caused the decision” is an artifact of greedy tie-breaking.

When trees fit #

Trees are effective for tabular data with nonlinear thresholds, mixed interactions, and limited preprocessing. A single tree is attractive when rule extraction and low-latency evaluation matter, provided pruning and stability checks support it. When predictive accuracy dominates, bagged or boosted tree ensembles usually reduce the variance or bias of one tree—but sacrifice the fiction that one displayed tree represents the whole model.