Decision Trees, Live

Why trees are the boring-and-good default

For tabular data — financial features, sensor logs, survey responses, anything that arrives as columns in a CSV — a decision tree (or its ensembles) is almost always either the right answer or the right baseline. They handle missing values, mixed continuous + categorical features, and arbitrary monotone transformations of any feature, without normalisation. Their inductive bias is "constant predictions on axis-aligned regions," which lines up surprisingly well with how human-curated features actually carry information.

The catch: a single tree is too greedy and too jagged. The fix — bagging (random forests) and boosting (XGBoost) — is what makes the family dominate tabular competitions. This article focuses on the single-tree mechanism so the ensemble methods make sense.

The greedy split rule

A CART decision tree builds itself top-down. At each node, it picks the (feature, threshold) pair that maximally decreases the impurity of the children. Standard impurities for classification:

For a candidate split, the impurity drop is $\Delta = I(\text{parent}) - \frac{N_L}{N}I(\text{left}) - \frac{N_R}{N}I(\text{right})$. Search over all features and all candidate thresholds, pick the maximum, recurse on each side. Stop when a node is pure, too small, or hits the depth limit.

Two consequences worth feeling: (1) splits are axis-aligned — the resulting decision regions are unions of rectangles. (2) the algorithm is greedy — a globally-better split sequence may exist but won't be found.

Live: information gain across thresholds

Drag the slider to pick a candidate threshold on a single feature. The two histograms show how the parent (top) splits into left/right children, and the curve below shows the impurity-decrease $\Delta$ over every possible threshold. The tree picks the argmax.

Three things to notice:

• The curve is piecewise-constant: between two adjacent training points, no information is gained or lost by moving the threshold. Practical CART implementations only evaluate the midpoints between adjacent sorted feature values.
• Entropy and Gini agree almost always on the argmax — they differ by at most ~2% on real data. Gini is the default in sklearn because it's slightly cheaper to compute.
• The argmax can be very close to a tie. Tiny changes in training data flip which feature wins — this is the instability that motivates random forests.

Build a tree, click by click

Left-click to add a class-A point (blue), right-click / shift-click for class-B (orange). The tree re-fits at every click. Push max depth up; watch the boundary become increasingly fragmented. Push min samples per leaf up; watch it smooth out.

What you should notice

• Axis-aligned everything. Even the "diagonal" boundaries you see are staircases of vertical and horizontal cuts. This is why decision trees struggle with rotated data — feature engineering / rotated embeddings help.
• Depth ⇆ overfitting. At depth 1 the tree is just a thresholded line; at depth 8 every training point sits in its own leaf. The right depth depends on how noisy the data is.
• Min-samples-per-leaf is the cleanest regulariser. Setting it to 5 forces the tree to ignore single-point outliers; cleaner boundary, slightly higher train error, usually better test error.
• Random forest = many shallow trees voted. Each tree sees a bootstrap sample and a random subset of features per split. The 25-tree ensemble is much smoother than a single deep tree at similar accuracy. This is why it's the everyday tabular workhorse.
• Logistic regression = one straight line. Worst on XOR-shaped data, often best on high-dimensional-but-near-linear tabular tasks.

Regression trees

The same recipe works for regression: replace Gini/entropy with squared-error impurity

At each leaf, predict the mean of the training $y$ values that fell there. The result is a piecewise-constant function of $x$ — terrible for smooth signals (use a GP), but excellent for tabular features where the right level set is itself piecewise-constant.

A subtlety: the split criterion for regression is equivalent to maximising the between-group variance at the split — i.e. an axis-aligned ANOVA. This explains why regression trees can find threshold-effects (e.g. "above 65 mph, fuel economy drops sharply") that linear models miss.

Pruning & the cost-complexity path

Pre-pruning (depth limit, min-samples-per-leaf) is cheap but coarse. Post-pruning is principled: grow a full tree, then collapse subtrees that don't pay for themselves. CART's cost-complexity criterion:

As $\alpha$ increases from 0 to $\infty$, the optimal tree shrinks from the full tree to the root. The cost-complexity path is the sequence of trees you pass through; the recommended way to pick $\alpha$ is cross-validation on this path.

• scikit-learn exposes this via DecisionTreeClassifier(ccp_alpha=α) and cost_complexity_pruning_path.
• Boosted trees rarely use post-pruning — small depth + many trees gives a similar effect with simpler bookkeeping.

Feature importance & its pitfalls

Two ways to score feature importance from a fitted tree:

• MDI (Mean Decrease in Impurity). Sum the weighted impurity decrease over every node that split on that feature. Cheap, default in sklearn — but biased towards high-cardinality features (more possible thresholds = more chances to find a spurious split).
• Permutation importance. Shuffle a feature on the validation set, measure the accuracy drop. Slower but unbiased; recommended for any "which features matter" claim that leaves the lab.
• SHAP TreeExplainer. Exact Shapley values for tree ensembles in polynomial time (Lundberg et al., 2018). The right tool for per-prediction attribution; works for XGBoost / LightGBM out of the box.

What trees are good at — and what they're not

• Tabular features, mixed types. Trees handle categorical and numeric features without normalisation. The default first try on any tabular task.
• Interpretability per prediction. "Predicted class A because feature X > 3.2 and feature Y < 0.7" — a tree gives you that path for free. Useful for explainable systems and audits.
• Strong ensembles. Random Forest, ExtraTrees, Gradient Boosted Trees, XGBoost, LightGBM, CatBoost — all still routinely win Kaggle tabular competitions.
• Bad at: high-dimensional sparse data (text, images), smooth low-dim regression (use a GP), extrapolation outside training range (a tree literally cannot predict beyond min/max in training).
• Inductive bias. Strong axis-aligned staircase prior. If your true decision boundary is a sphere or rotated, you need rotated features or a smoother model.

CART, ID3, C4.5 — the family

• ID3 (Quinlan, 1986) — entropy criterion; categorical features only; one node per category value. Historical; rarely used directly today.
• C4.5 (Quinlan, 1993) — adds continuous features (split = threshold); replaces information gain with gain ratio to fight bias toward high-cardinality features; built-in missing-value handling.
• CART (Breiman et al., 1984) — binary splits only; Gini for classification, squared error for regression; cost-complexity pruning. The default in scikit-learn and most modern libraries.
• Conditional inference trees (Hothorn et al., 2006) — replace the impurity criterion with statistical tests of independence; eliminates the bias toward many-level features. The R party package.

Reading list

• Breiman, Friedman, Olshen, Stone (1984) — Classification and Regression Trees. The original CART book.
• Quinlan (1993) — C4.5: Programs for Machine Learning.
• Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, ch. 9 — best intro-with-math.
• Lundberg & Lee (2017); Lundberg et al. (2018) — SHAP and TreeSHAP for explanation.
• Grinsztajn, Oyallon, Varoquaux (2022) — Why do tree-based models still outperform deep learning on tabular data? The empirical reference.