Unlike hyperplanes and support vector machines that construct continuous geometric manifolds across vector spaces, Decision Trees operate through hierarchical logical rules. Originating from Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone’s 1984 classic Classification and Regression Trees (CART), tree-based models recursively partition high-dimensional feature spaces into orthogonal, axis-aligned hyper-rectangles. In doing so, they provide completely interpretable, invariant decisions across arbitrary scale transformations.
1. The Geometry of Orthogonal Space Partitioning
Let instance space $mathcal{X} subseteq mathbb{R}^d$ be partitioned into $M$ disjoint regions $R_1, R_2, dots, R_M$. A decision tree models the predictive function as a piecewise constant assignment:
$$f(x) = sum_{m=1}^M c_m mathbb{I}(x in R_m)$$
where for regression, $c_m = text{mean}(y_i mid x_i in R_m)$, and for classification, $c_m = argmax_k p_{mk}$ where $p_{mk}$ is the empirical proportion of class $k$ in node $m$.
Because determining the globally optimal partition of $M$ regions across $d$ dimensions is strictly NP-complete (Hyafil & Rivest, 1976), trees are constructed via greedy top-down recursive binary splitting.
2. Node Impurity Metrics: Entropy vs Gini
At any internal node $m$ containing dataset $D_m$ with $|D_m|$ samples and class distributions $p_{mk} = frac{1}{|D_m|} sum_{i in D_m} mathbb{I}(y_i = k)$ for $k = 1, dots, K$, the split quality is evaluated by an Impurity Function $I(m)$:
- Shannon Entropy: Derived from information theory, measuring the average surprise of the distribution:
$$I_E(m) = H(p_m) = -sum_{k=1}^K p_{mk} log_2 p_{mk}$$
The corresponding reduction in entropy achieved by a split is the Information Gain.
- Gini Impurity (CART): The expected probability of misclassification if a sample was randomly labeled according to the empirical distribution of the node:
$$I_G(m) = sum_{k=1}^K p_{mk} (1 – p_{mk}) = 1 – sum_{k=1}^K p_{mk}^2$$
Gini reaches its global minimum of 0 when the node is purely homogeneous ($p_{mk} = 1$), and peaks at $1 – 1/K$ under uniform randomness.
- Mean Squared Error (Regression Trees):
$$I_{text{MSE}}(m) = frac{1}{|D_m|} sum_{i in D_m} (y_i – bar{y}_m)^2$$
3. The Greedy Splitting Rule
At each step, the algorithm scans across all $d$ features $j in {1, dots, d}$ and all possible split threshold values $s in mathbb{R}$, partitioning node $m$ into left and right children:
$$R_L(j, s) = {x mid x_j le s}, quad R_R(j, s) = {x mid x_j > s}$$
The optimal split $(j^*, s^*)$ maximizes the weighted impurity reduction (gain):
$$Delta I(m; j, s) = I(m) – left( frac{|D_L|}{|D_m|} I(D_L) + frac{|D_R|}{|D_m|} I(D_R) right)$$
4. Overfitting Dynamics & Minimal Cost-Complexity Pruning
A fully unconstrained tree will recursively split until every leaf node contains exactly one sample ($I(m) = 0$). While training error is identically zero, this tree suffers from catastrophic variance. Constraining growth purely via local stopping heuristics (e.g., minimum gain thresholds) fails because a seemingly uninformative split can unlock a decisive split in the subsequent level (the parity/XOR problem).
CART resolves this by growing a massive unconstrained tree $T_0$ and subsequently applying Minimal Cost-Complexity Pruning. We define the cost-complexity criterion for any subtree $T subseteq T_0$:
$$mathcal{C}_alpha(T) = sum_{m in text{leaves}(T)} |D_m| I(m) + alpha |text{leaves}(T)|$$
where $alpha ge 0$ is a complexity tuning parameter penalizing tree size. By sweeping $alpha$ from 0 to $infty$, Breiman et al. proved that there exists a nested sequence of subtrees $T_0 supset T_1 supset T_2 dots supset {root}$ containing the optimal subtree for any $alpha$. Selecting $alpha^*$ via $k$-fold cross-validation identifies the tree that achieves the optimal bias-variance equilibrium.
