Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 218 / 3 / a

The classification form of CART starts with the root rectangle $R=[0,1{]}^2$. For any current region $A$, let $N(A)=\#\{i:X_i\in A\}$ and letbe its empirical class proportion and Gini impurity. A candidate axis-aligned split $X_j\le s$ partitions $R$ into $U$ and $V$. Its impurity change isAmong all coordinates and thresholds between consecutive observed coordinates, CART chooses a split minimizing $Q$, then applies the same recursive partitioning independently to the children until a stopping rule is met. Each terminal region predicts its majority class. Pruning may then select a smaller subtree by penalizing the number of leaves.

For the resulting classifier $\hat{C}$, the training error iswhile its prediction error is $R(\hat{C})=\mathbb{P}\{\hat{C}(X_{new})\ne Y_{new}\}$ for an independent observation drawn from the target population.