CART (Classification and Regression Trees) › Formula - Classification

The mathematical foundation of CART revolves around finding the optimal split that minimizes impurity for classification or variance for regression. Let's walk through these concepts step by step.

For classification problems, CART uses the Gini impurity measure to evaluate the quality of a split. The Gini impurity measures how often a randomly chosen element would be incorrectly labeled if it were randomly labeled according to the distribution of labels in the subset.

We start with the basic Gini impurity formula for a node:

$$Gini(S) = 1 - \sum_{i=1}^{c} p_i^2$$

where:

• $Gini(S)$ is the Gini impurity for node $S$ (a measure of impurity ranging from 0 for pure nodes to a maximum value when classes are evenly distributed)
• $S$ represents the set of samples at the current node (the subset of training data that reaches this node)
• $c$ is the number of classes (total number of distinct class labels in the classification problem)
• $p_i$ is the proportion of samples belonging to class $i$ in the set $S$ (calculated as $p_i = \frac{n_i}{|S|}$ where $n_i$ is the number of samples of class $i$ and $|S|$ is the total number of samples in node $S$)
• $i$ is the class index (ranging from 1 to $c$)

The reason we square the probabilities is to penalize nodes where the class distribution is mixed. When all samples belong to the same class (complete purity), $p_i = 1$ for one class and $p_i = 0$ for all others, making $Gini(S) = 1 - 1^2 = 0$. When classes are evenly distributed, the Gini impurity reaches its maximum.

To find the best split, we calculate the weighted average of the Gini impurities of the resulting child nodes:

$$Gini_{split}(S) = \frac{|S_L|}{|S|} \cdot Gini(S_L) + \frac{|S_R|}{|S|} \cdot Gini(S_R)$$

where:

• $Gini_{split}(S)$ is the weighted Gini impurity after splitting node $S$ (the combined impurity 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 impurity measure)

The algorithm selects the split that minimizes this weighted Gini impurity. This makes intuitive sense: we want splits that create child nodes with as pure class distributions as possible.

For regression problems, CART minimizes the variance (or equivalently, the mean squared error) of the target variable within each leaf node. 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$ (a measure of how spread out the target values are around 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 mean squared error is essentially the same as variance, just without the division by $|S|$:

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

where:

• $MSE(S)$ is the mean squared error for node $S$ (the sum of squared deviations from the mean, used as an alternative to variance)
• $(y_i - \bar{y})^2$ is the squared deviation of sample $i$ from the mean (measures how far each sample's target value is from the node's average)

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

$$MSE_{split}(S) = MSE(S_L) + MSE(S_R)$$

where:

• $MSE_{split}(S)$ is the total mean squared error after splitting node $S$ (the sum of MSEs from both child nodes)
• $MSE(S_L)$ is the mean squared error of the left child node (calculated as $\sum_{i \in S_L} (y_i - \bar{y}_L)^2$)
• $MSE(S_R)$ is the mean squared error of the right child node (calculated as $\sum_{i \in S_R} (y_i - \bar{y}_R)^2$)

This is equivalent to the weighted variance approach used in classification, but since we're dealing with continuous values, we use the sum of squared deviations from the mean.

The algorithm evaluates all possible splits for each feature and selects the one that provides the maximum reduction in impurity or variance. 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 = Impurity_{parent} - Impurity_{split}$$

where:

• $Gain$ is the information gain (the reduction in impurity achieved by the split, with higher values indicating better splits)
• $Impurity_{parent}$ is the impurity of the parent node before splitting (either Gini impurity for classification or variance for regression)
• $Impurity_{split}$ is the weighted impurity after splitting (the combined impurity of both child nodes)

For classification, this becomes:

$$Gain = Gini(S) - Gini_{split}(S)$$

where:

• $Gini(S)$ is the Gini impurity of the parent node $S$ before splitting
• $Gini_{split}(S)$ is the weighted Gini impurity after splitting (calculated as $\frac{|S_L|}{|S|} \cdot Gini(S_L) + \frac{|S_R|}{|S|} \cdot Gini(S_R)$)

For regression, this becomes:

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

where:

• $Var(S)$ is the variance of the parent node $S$ before splitting
• $\frac{|S_L|}{|S|} \cdot Var(S_L)$ is the weighted variance of the left child node
• $\frac{|S_R|}{|S|} \cdot Var(S_R)$ is the weighted variance of the right child node

The algorithm selects the split with the maximum gain.

The Gini impurity 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 impurity functions are convex, meaning that the weighted average of impurities from child nodes is less than or equal to the parent node's impurity. This ensures that splitting does not increase the overall impurity.

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)