Decision trees

Summary

A decision tree predicts a constant value within each terminal feature region. Training chooses threshold splits greedily, using a stated criterion and stopping rules.

Task: the diagram has four circles, class zero, and four triangles, class one. Candidate root $x_{1} \leq 4$ puts three circles and one triangle left; one circle and three triangles go right. Calculate its Gini reduction and predict a new point $(6, 2)$ after the right-only child split $x_{2} \leq 3$ .

The drawn split is a candidate, not a proven best threshold among unenumerated alternatives.

The algorithm (CART, Breiman et al., 1984)

Enumerate allowed feature thresholds, usually midpoints between distinct ordered numeric values.
Route $x_{j} \leq t$ left and $x_{j} > t$ right; reject candidates violating leaf constraints.
Choose maximum sample-weighted impurity reduction, then recurse under the stopping rules.

This local choice need not produce the globally best tree.

Learning objective: map each root-to-leaf rule path to one axis-aligned region of feature space and its constant leaf prediction.

Rules become regions

The second split affects only the root's right-hand region

Derivation

the solid root split routes every point. The dashed child test cuts only the right region. Intersecting the path's predicates gives its leaf region and constant empirical class fraction. The highlighted point follows “no, then yes” to R1. Sources: scikit-learn's formulation and The Elements of Statistical Learning.

Check: Why is the second split applied only on the right side of the root boundary?

Read it this way: The root sends every x<=0 point to A. Splitting y on the right branch changes only the x>0 region.
Does changing y above one move any x<=0 point out of A?

Split criteria

For class proportions $p_{k}$ , Gini impurity is $I = 1 - \sum_{k} p_{k}^{2}$ . Use

Δ I = I (p a r e n t) - \frac{n _{L}}{n} I (L) - \frac{n _{R}}{n} I (R) .

State	Calculation	Gini
Parent	$1 - (1/2)^{2} - (1/2)^{2}$	$0.5$
Each root child	$1 - (3/4)^{2} - (1/4)^{2}$	$0.375$
Weighted root children	$(4/8) (0.375) + (4/8) (0.375)$	$0.375$

Root improvement is $0.5 - 0.375 = 0.125$ . The right child separates three triangles from one circle, leaving total weighted impurity $(4/8) (0.375) = 0.1875$ . Point $(6, 2)$ reaches that pure-triangle R1 leaf, with empirical triangle fraction $1$ .

Sample weights matter: a separate pure child of size three and impurity- $0.32$ child of size five give weighted impurity $0.2$ . An unweighted mean gives $0.16$ , incorrectly treating unequal child sizes equally.

Entropy $- \sum_{k} p_{k} lo g p_{k}$ gives entropy information gain, not the same numerical quantity as Gini reduction. For regression, a leaf mean minimizes its summed squared error.

Stopping and pruning

New task: require at least four samples per leaf. The 4/4 root remains legal; its proposed 3/1 right split does not. Check: $(6, 2)$ now receives the unsplit right leaf’s triangle fraction $3/4$ , not $1$ . Use when: tiny leaves provide insufficient support or excessive variance.

New task: predict numeric targets with $x_{1} = [1, 2, 5, 6]$ , $y = [1, 1, 3, 3]$ , and threshold $4$ . Replace class fractions and Gini with means and squared residuals. Check: the unsplit mean $2$ has SSE $4$ ; leaf means $1$ and $3$ give SSE zero. Use when: the output is a continuous response.

Depth, minimum leaf size, purity, and improvement limits stop growth. Cost-complexity pruning compares subtrees using $R (T) + α ∣ l e a v es (T) ∣$ ; select $α$ using validation, not test outcomes.

Failure: either first axis split on four XOR corners has zero gain, although a depth-two tree separates them. Stopping on nonpositive immediate gain can miss that interaction.

Reconstruct: at $x_{1} = 4$ exactly, does the right child inspect $x_{2}$ ?

Answer

No. The $\leq$ rule routes left; a child test applies only to the region reaching it.

Strengths and weaknesses

Paths provide explicit rules and can represent interactions through successive splits. Strictly increasing numeric transformations preserve candidate partitions when ordering and implementation arithmetic are preserved. Rotated boundaries may require many axis-aligned regions; feature engineering or oblique tests changes that representation. Small data changes can change selected splits. Neither a single tree nor an ensemble has a universal production ranking.

Categorical features

One-hot encoding and native categorical splitting define different candidate partitions and costs. Arbitrary integer codes impose an ordering that may not match category meaning. Target-based category statistics require leakage controls. Library algorithms, including CatBoost’s ordered statistics, are not interchangeable with simply sorting all categories by target mean.

Common pitfalls

Missing-value routing needs an explicit supported strategy: imputation, learned default directions, or surrogate splits, depending on implementation. Do not assume every tree accepts missing or categorical values. Empirical leaf fractions are not guaranteed calibrated probabilities for new populations. Feature importance can reflect split-selection biases; evaluate stability and held-out perturbations before interpreting it.

Random forests. Bagged ensembles of trees.
Gradient boosting. Boosted ensembles of trees.