Decision Trees are a non-parametric supervised learning method used for both classification and regression tasks. Unlike parametric models, they make no assumptions about the underlying data distribution.
A decision tree has a hierarchical structure composed of:
The key appeal of decision trees lies in their interpretability: the model can be visualized as a flowchart of if-then rules, making it easy to understand and explain predictions. They require no feature scaling, handle both numerical and categorical features, and naturally capture non-linear relationships and feature interactions.
The CART (Classification and Regression Trees) algorithm builds classification trees via recursive binary splitting. At each internal node, the algorithm searches for the best split — a feature \(j\) and a threshold \(s\) — that minimizes an impurity measure in the resulting child nodes.
Let \(p_k\) denote the proportion of observations belonging to class \(k\) in a given node, with \(K\) total classes.
The Gini Index measures the probability of misclassifying a randomly chosen element:
\[ G = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2 \]
The Gini Index equals 0 when all observations belong to a single class (pure node) and reaches its maximum when classes are equally distributed.
Entropy quantifies the disorder or uncertainty in a node:
\[ H = -\sum_{k=1}^{K} p_k \log_2(p_k) \]
Like the Gini Index, entropy is 0 for a pure node and maximal for uniform class distributions.
The simplest impurity measure:
\[ E = 1 - \max_k(p_k) \]
This measure is less sensitive to changes in class probabilities and is therefore less commonly used for tree growing (but useful for pruning).
The quality of a split is evaluated via Information Gain, defined as the reduction in impurity from parent to children:
\[ \text{Information Gain} = H(\text{parent}) - \sum_{c \in \{L, R\}} \frac{n_c}{n_{\text{parent}}} H(\text{child}_c) \]
where \(n_c\) is the number of observations in child node \(c\) and \(n_{\text{parent}}\) is the total number in the parent node. The split that maximizes Information Gain (or equivalently, minimizes the weighted child impurity) is selected.
For regression tasks, the tree predicts a continuous value. The feature space is partitioned into \(J\) distinct regions \(R_1, R_2, \ldots, R_J\), and for each region the prediction is the mean of the training observations falling in that region:
\[ \hat{y}_{R_j} = \frac{1}{|R_j|} \sum_{i \in R_j} y_i \]
The objective is to find the partition that minimizes the Residual Sum of Squares (RSS):
\[ \text{RSS} = \sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2 \]
At each split, we choose the feature \(j\) and threshold \(s\) that define two half-planes:
\[ R_1(j,s) = \{X \mid X_j \leq s\} \quad \text{and} \quad R_2(j,s) = \{X \mid X_j > s\} \]
and we seek \(j\) and \(s\) that minimize:
\[ \sum_{i: x_i \in R_1(j,s)} (y_i - \hat{y}_{R_1})^2 + \sum_{i: x_i \in R_2(j,s)} (y_i - \hat{y}_{R_2})^2 \]
Finding the globally optimal tree partition is computationally infeasible (NP-hard). Therefore, decision trees use a greedy top-down approach known as recursive binary splitting:
This greedy procedure does not guarantee a globally optimal tree but is computationally tractable with complexity \(O(n \cdot p \cdot \log n)\) per split when features are pre-sorted.
A fully grown tree (one that perfectly classifies training data) will typically overfit — it captures noise in the training set and generalizes poorly to unseen data. Pruning addresses this by reducing the tree's complexity.
Rather than using early stopping criteria, the preferred approach is to grow a large tree \(T_0\) and then prune it back. Cost-complexity pruning defines a penalized objective:
\[ C_\alpha(T) = \sum_{m=1}^{|T|} \sum_{i \in R_m} (y_i - \hat{y}_m)^2 + \alpha |T| \]
where:
When \(\alpha = 0\), the full tree \(T_0\) is optimal. As \(\alpha\) increases, there is a penalty for having too many leaves, leading to smaller subtrees.
The optimal \(\alpha\) is selected using k-fold cross-validation:
The high variance and instability of individual decision trees motivates the development of ensemble methods that combine multiple trees to produce more robust predictions:
The fundamental insight is that while a single tree is a weak learner with high variance, an ensemble of many trees can achieve the performance of a strong learner by averaging out individual errors:
\[ \text{Var}\left(\frac{1}{B}\sum_{b=1}^{B} T_b(x)\right) = \rho \sigma^2 + \frac{1-\rho}{B}\sigma^2 \]
where \(\rho\) is the pairwise correlation between trees and \(\sigma^2\) is the variance of a single tree. As \(B \to \infty\), the second term vanishes, and reducing \(\rho\) (via random feature subsets) directly reduces ensemble variance.