CART (Classification and Regression Trees) › Formula - Regression

The mathematical foundation of CART for regression problems focuses on minimizing variance (or equivalently, mean squared error) at each split. Unlike classification, where we measure impurity, regression trees aim to create leaf nodes with the lowest possible variance in the target variable.

For regression problems, CART uses the mean squared error (MSE) to evaluate the quality of a split. The MSE measures the average squared difference between the predicted values and the actual target values in a node.

We start with the basic MSE formula for a node:

$$MSE(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y})^2$$

where:

• $MSE(S)$ is the mean squared error for node $S$ (the average squared deviation of target values from their mean)
• $|S|$ is the number of samples in node $S$ (total count of data points in this node)
• $y_i$ is the target value for sample $i$ (the actual observed response value for the $i$-th sample in node $S$)
• $\bar{y}$ is the mean target value in the node (the average of all target values in node $S$)
• $i \in S$ indicates summation over all samples in node $S$

The mean target value $\bar{y}$ is calculated as:

$$\bar{y} = \frac{1}{|S|} \sum_{i \in S} y_i$$

where:

• $\bar{y}$ is the mean target value (the arithmetic average of all target values in node $S$, which becomes the prediction for this node)
• $\frac{1}{|S|}$ is the normalization factor (ensures we compute the average rather than the sum)
• $\sum_{i \in S} y_i$ is the sum of all target values in node $S$

The reason we use squared differences is to penalize larger errors more heavily than smaller ones. This ensures that the algorithm prioritizes splits that create more homogeneous groups in terms of their target values. When all samples in a node have the same target value (complete homogeneity), the MSE equals zero.

To find the best split, we calculate the weighted sum of the MSEs of the resulting child nodes:

$$MSE_{split}(S) = \frac{|S_L|}{|S|} \cdot MSE(S_L) + \frac{|S_R|}{|S|} \cdot MSE(S_R)$$

where:

• $MSE_{split}(S)$ is the weighted mean squared error after splitting node $S$ (the combined MSE of both child nodes, weighted by their sizes)
• $S_L$ is the left child node after the split (the subset of samples that satisfy the split condition)
• $S_R$ is the right child node after the split (the subset of samples that do not satisfy the split condition)
• $|S|$ is the number of samples in the parent node $S$ (total samples before splitting)
• $|S_L|$ is the number of samples in the left child node (samples satisfying the split condition)
• $|S_R|$ is the number of samples in the right child node (samples not satisfying the split condition, where $|S_L| + |S_R| = |S|$)
• $\frac{|S_L|}{|S|}$ and $\frac{|S_R|}{|S|}$ are the weights (proportions of samples going to each child node, so larger child nodes have more influence on the overall MSE measure)

The algorithm selects the split that minimizes this weighted MSE. This makes intuitive sense: we want splits that create child nodes with as low variance as possible in their target values.

An alternative and equivalent approach is to use variance instead of MSE. The variance for a node is calculated as:

$$Var(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y})^2$$

where:

• $Var(S)$ is the variance of the target variable in node $S$ (identical to MSE, measuring spread of target values)
• All other symbols have the same meaning as in the MSE formula above

For a split, we calculate the weighted sum of the variances of the child nodes:

$$Var_{split}(S) = \frac{|S_L|}{|S|} \cdot Var(S_L) + \frac{|S_R|}{|S|} \cdot Var(S_R)$$

where:

• $Var_{split}(S)$ is the weighted variance after splitting node $S$ (the combined variance of both child nodes, weighted by their sizes)
• $Var(S_L)$ is the variance of the left child node (calculated as $\frac{1}{|S_L|} \sum_{i \in S_L} (y_i - \bar{y}_L)^2$)
• $Var(S_R)$ is the variance of the right child node (calculated as $\frac{1}{|S_R|} \sum_{i \in S_R} (y_i - \bar{y}_R)^2$)
• All other symbols have the same meaning as defined previously

The variance reduction for a split is:

$$Variance\_Reduction = Var(S) - Var_{split}(S)$$

where:

• $Variance\_Reduction$ is the reduction in variance achieved by the split (the decrease in variance from parent to weighted child nodes, with higher values indicating better splits)
• $Var(S)$ is the variance of the parent node before splitting
• $Var_{split}(S)$ is the weighted variance after splitting

The algorithm selects the split that provides the maximum variance reduction, which is equivalent to minimizing the weighted MSE.

The algorithm evaluates all possible splits for each feature and selects the one that provides the maximum variance reduction. For a continuous feature with values $x_1, x_2, ..., x_n$, we consider splits of the form $x \leq t$ for all possible thresholds $t$. For categorical features, we consider all possible subsets of categories.

The information gain (or variance reduction) for a split is:

$$Gain = Var(S) - \frac{|S_L|}{|S|} \cdot Var(S_L) - \frac{|S_R|}{|S|} \cdot Var(S_R)$$

where:

• $Gain$ is the variance reduction (the decrease in variance achieved by the split, with higher values indicating better splits)
• $Var(S)$ is the variance of the parent node $S$ before splitting
• $\frac{|S_L|}{|S|} \cdot Var(S_L)$ is the weighted variance contribution of the left child node
• $\frac{|S_R|}{|S|} \cdot Var(S_R)$ is the weighted variance contribution of the right child node
• The right-hand side can be rewritten as $Var(S) - Var_{split}(S)$, showing this is equivalent to the variance reduction formula above

The algorithm selects the split with the maximum gain.

The MSE and variance measures are monotonically decreasing as we make better splits. This property ensures that the algorithm chooses splits that improve the overall model quality.

The variance functions are convex, meaning that the weighted average of variances from child nodes is less than or equal to the parent node's variance. This ensures that splitting does not increase the overall variance.

For each feature, the algorithm must evaluate all possible split points. For continuous features with $n$ unique values, this requires $O(n)$ evaluations. For categorical features with $k$ categories, it requires evaluating $2^{k-1} - 1$ possible splits, making it computationally expensive for high-cardinality categorical features.

where:

• $n$ is the number of unique values for a continuous feature (the distinct values that could serve as split thresholds)
• $O(n)$ represents linear computational complexity (evaluating each unique value as a potential split point)
• $k$ is the number of categories for a categorical feature (the distinct category labels)
• $2^{k-1} - 1$ is the number of possible binary partitions of $k$ categories (exponential growth with the number of categories)