How does the CART algorithm build regression trees?

Question

AcadiFi · Accepted Answer

CART (Classification and Regression Trees) builds a decision tree by recursively partitioning the feature space into rectangular regions, predicting a constant (mean for regression, mode/probability for classification) within each region. The algorithm greedily selects splits that maximally reduce impurity. Algorithm for regression trees: (1) At the root node, consider all features and all possible split points. For a feature Xⱼ with candidate split value s, divide data into left (Xⱼ ≤ s) and right (Xⱼ > s) groups. (2) Compute the reduction in residual sum of squares (RSS) if we make this split: baseline RSS = Σ(yᵢ − ȳ)², after split RSS = Σ_left(yᵢ − ȳ_left)² + Σ_right(yᵢ − ȳ_right)². Pick the feature-split pair that maximizes RSS reduction. (3) Apply recursively to each child node until stopping criteria are met. (4) Stopping criteria: minimum samples per leaf, maximum tree depth, minimum RSS improvement, or pure nodes. ```mermaid flowchart TB R[Root
All Data] --> L1{DTI > 35?} L1 -->|Yes| R1[Right Node] L1 -->|No| L2{Score > 720?} L2 -->|Yes| L3[Leaf
Default 2%] L2 -->|No| L4[Leaf
Default 8%] ``` Example: Rosebank Bank predicts loan default rates using income, DTI, credit score. CART might first split on credit score at 680 (biggest variance reduction), then within the low-score branch split on DTI at 40%, creating leaves with different default rates. The final tree is interpretable: IF score < 680 AND DTI > 40% THEN predicted default rate = 18%. Critical issue — pruning. A fully grown tree overfits training data. Cost-complexity pruning uses a penalty α to remove branches: minimize RSS + α × (number of leaves). Cross-validation selects optimal α. CART advantages: interpretability, handles non-linear relationships and interactions automatically, no need for feature scaling, handles missing data. Disadvantages: high variance (small data changes yield very different trees), step function predictions (discontinuities), bias toward features with many unique values. These limitations motivate ensemble methods like random forests and boosted trees — covered in the CFA ML curriculum.

How does the CART algorithm build regression trees?

Master Level II with our CFA Course

Related Questions

Practice Questions