Decision Trees

How decision trees partition the feature space, greedy top-down induction, impurity measures (entropy, Gini, misclassification error), information gain and gain ratio worked step by step, splitting numeric attributes, regression trees with variance reduction, stopping rules and pruning, overfitting, and ensembles built from trees (bagging, random forests, boosting).

How a decision tree predicts

A decision tree asks a sequence of simple questions about one feature at a time ("Outlook = sunny?", "age < 30?"). Internal nodes test a feature, branches are outcomes, and leaves hold a prediction (a class, or a number for regression). The tree partitions the feature space into axis-aligned rectangles.

The classic "play tennis" tree: each root-to-leaf path is an IF–THEN rule.

Growing a tree: greedy top-down induction

Start with all training data at the root.
For every feature (and threshold), measure how much a split would reduce impurity.
Split on the best one; recurse on each child.
Stop when a node is pure, too small, too deep, or no split helps.

This greedy recursive partitioning (ID3, C4.5, CART) is fast but not globally optimal (finding the optimal tree is NP-hard).

Impurity measures

For a node with class proportions $p_1, \dots, p_K$ :

Measure	Formula	Two classes, maximum
Entropy	$H = -\sum_kp_k\log_2p_k$	1 at $p = 0.5$
Gini impurity	$G = 1 - \sum_kp_k^2$	0.5 at $p = 0.5$
Misclassification error	$1 - \max_kp_k$	0.5 at $p = 0.5$

Entropy and Gini are smooth and usually pick similar splits; misclassification error is too insensitive for growing trees.

Information gain

\text{Gain}(S, A) = H(S) - \sum_{v\in\text{values}(A)}\frac{\lvert S_v\rvert}{\lvert S\rvert}H(S_v).

Gain ratio (C4.5) divides by the split information to avoid favouring many-valued attributes; Gini gain (CART) uses $G$ in place of $H$ and makes binary splits.

Numeric features

Sort the values; candidate thresholds are midpoints between consecutive distinct values (only class-changing boundaries matter for entropy). Evaluate each threshold like a binary attribute.

Regression trees

Leaves predict the mean target of their examples; splits minimise the total squared error (variance reduction):

\text{choose } (j, t) \text{ minimising } \sum_{i\in L}(y_i - \bar y_L)^2 + \sum_{i\in R}(y_i - \bar y_R)^2.

Overfitting and pruning

A tree grown until every leaf is pure has zero training error and high variance. Controls:

Pre-pruning (early stopping): max depth, minimum samples per leaf/split, minimum impurity decrease.
Post-pruning: grow fully, then remove subtrees that do not improve validation performance — reduced-error pruning, or cost-complexity pruning (minimise $\text{error} + \alpha\cdot\lvert\text{leaves}\rvert$ , with $\alpha$ chosen by cross-validation).

Strengths and weaknesses

Strengths	Weaknesses
interpretable rules; easy to visualise	unstable: small data changes can change the tree a lot (high variance)
no feature scaling needed; handles mixed types	axis-aligned splits approximate diagonal boundaries poorly
captures interactions and non-linearity	greedy; can overfit without pruning
fast prediction ( $O(\text{depth})$ )	piecewise-constant regression

Ensembles of trees

Method	Idea	Mainly reduces
Bagging	train trees on bootstrap samples; average/vote	variance
Random forest	bagging + a random subset of features at each split (decorrelates trees); out-of-bag error estimate for free	variance
Boosting (AdaBoost, gradient boosting, XGBoost)	add shallow trees sequentially, each fitting the current errors/residuals	bias (and variance)