= Solution
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 let
$$
\widehat p(A)=\frac{\#\{i:X_i\in A,\,Y_i=\text{circle}\}}{N(A)},
\qquad
G(A)=\widehat p(A)(1-\widehat p(A))
$$
be its empirical class proportion and <Gini impurity>. A candidate axis-aligned split $X_j\leq s$ partitions $R$ into $U$ and $V$. Its impurity change is
$$
Q=\frac{N(U)}{N(R)}G(U)
+\frac{N(V)}{N(R)}G(V)-G(R).
$$
Among 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 $\widehat C$, the <training error> is
$$
\widehat R_{train}=\frac19\sum_{i=1}^9
\mathbf1_{\{\widehat C(X_i)\ne Y_i\}},
$$
while its <prediction error> is $R(\widehat C)=\mathbb P\{\widehat C(X_{new})\ne Y_{new}\}$ for an independent observation drawn from the target population.
Back to article page
