Building Decision Trees

A decision tree carves the predictor space into rectangles and assigns each rectangle a single prediction. The hard part is not the geometry; it is knowing when to stop slicing.

A tree partitions the predictor space $X_1, \dots, X_p$ into $J$ non-overlapping rectangles $R_1, \dots, R_J$. For any test point, you walk down the tree, answer each yes/no question, and land in exactly one rectangle. The prediction inside $R_j$ is a single number (regression) or a single class label (classification).

Internal nodes ask a question of the form "Is $X_k < s$?" for a numeric predictor or "Is $X_k \in A$?" for a categorical one. Terminal nodes (leaves) hold the prediction. The depth from root to leaf is the number of questions a test point answers.

KEY: A tree with $|T|$ leaves makes exactly $|T|$ distinct predictions. Doubling leaves doubles the resolution of the fitted surface, and roughly doubles the variance.

Practitioners wanted a partitioning method that a non-statistician could read off a diagram and that could be fit on a workstation in seconds.

Common mistakes

• Using classification error rate to grow a classification tree. It is too coarse to detect purity gains. Use Gini or cross-entropy for splitting; reserve error rate for final pruning comparisons.
• Confusing $\alpha$ with a regularization on coefficients. In trees, $\alpha$ penalizes the number of leaves, not parameter magnitudes. Larger $\alpha$ means smaller tree, not smaller numeric splits.
• Trying every subtree. A tree with 20 leaves has astronomically many subtrees. The weakest-link algorithm produces only the nested sequence, and one of those subtrees is optimal for any $\alpha$.

Bottom line

• Trees grow top-down by recursive binary splitting, choosing at each node the predictor and cutpoint that maximally reduces a loss function on the training data.
• Regression trees split to minimize residual sum of squares (RSS); classification trees split to minimize Gini index or cross-entropy, not classification error rate.
• A fully grown tree overfits. The cure is cost-complexity (weakest-link) pruning: penalize the tree by $\alpha |T|$ and shrink it as $\alpha$ rises.
• Choose $\alpha$ by K-fold cross-validation. The chosen $\alpha$ corresponds to one subtree in the nested sequence produced by weakest-link pruning.

Exam shortcut

If a question asks which impurity measure is used to grow a classification tree, the answer is Gini or cross-entropy, not classification error. If a question gives you training RSS at several tree sizes and an $\alpha$, compute $\text{RSS} + \alpha|T|$ for each and pick the minimum. If the prompt mentions cross-validation in a tree context without specifying what is being tuned, the answer is almost always the cost-complexity parameter $\alpha$.

The full lesson (about 4,095 words, 27 min read) adds 4 worked examples, all 7 common mistakes, a self-check, free in the app.

Learning objectives

• 4a

Browse all free Exam SRM lessons or jump into free Exam SRM practice questions.