CART Algorithm

Classification and Regression Trees

A fundamental algorithm for decision tree learning

Key Idea: Recursive binary partitioning of feature space to create decision rules

What is binary partitioning? Think of it as repeatedly dividing your data into two groups:

"Binary" means we always split into exactly two parts (e.g., "Age > 30" and "Age ≤ 30")
"Partitioning" means dividing the data based on features (like age, income, etc.)
"Recursive" means we keep dividing each group further until we're done

Imagine sorting people into rooms by asking yes/no questions - that's what CART does with data!

Introduction to CART

Classification and Regression Trees

What is CART? A decision tree algorithm that can be used for both classification and regression tasks
Key Idea: Recursive binary partitioning of feature space
Two Types:
- Classification trees (categorical outcomes)
- Regression trees (continuous outcomes)
Advantages:
- Interpretable models
- Handles mixed data types
- No assumptions about data distribution
- Automatically handles feature interactions

Binary Splitting Mechanism

How CART Builds Trees

Recursive Partitioning: Start with all data, split into two subsets
Split Criteria: Find the best feature and threshold that maximizes information gain
Mathematical Form: $x_j \leq t$ vs $x_j > t$ for feature $j$ and threshold $t$
Stopping Conditions:
- Maximum depth reached
- Minimum samples per leaf
- Minimum impurity decrease

Tree Structure

Anatomy of a Decision Tree

Root Node: Contains all training samples
Internal Nodes: Decision points based on feature values
Leaf Nodes: Final predictions
- Classification: Class probabilities or majority class
- Regression: Mean value of samples in the leaf
Decision Path: Root → Internal Nodes → Leaf

Impurity Measures

Classification Trees

Two common impurity measures for classification tasks:

Gini Impurity: $$G = 1 - \sum_{i=1}^{c} p_i^2$$

Where $p_i$ is the proportion of class $i$ in the node

Entropy: $$H = -\sum_{i=1}^{c} p_i \log_2(p_i)$$

Where $p_i$ is the proportion of class $i$ in the node

Goal: Minimize impurity in child nodes after splitting

Impurity Measures

Regression Trees

For regression tasks, we use variance-based measures:

Mean Squared Error (MSE): $$\text{MSE} = \frac{1}{n} \sum_{i=1}^{n} (y_i - \bar{y})^2$$

Where $y_i$ are the target values and $\bar{y}$ is their mean

Alternative measures:

Mean Absolute Error (MAE)
Friedman's Mean Squared Error
Poisson deviance (for count data)

Information Gain

Evaluating Split Quality

Information Gain: $$\text{IG} = \text{Impurity(parent)} - \sum_{j=1}^{k} \frac{n_j}{n} \text{Impurity(child}_j)$$

Where $n_j$ is the number of samples in child $j$

Split Selection:

Evaluate all possible feature-threshold combinations
Choose the split with maximum information gain
Computational complexity: $O(n \cdot m \cdot \log n)$ for $n$ samples and $m$ features

Algorithm Implementation

CART in Practice

Calculate impurity for current node
For each feature, find optimal split threshold
Select split with maximum information gain
Create child nodes and recurse
Assign predictions to leaf nodes

Pseudocode:


                    function BuildTree(data, depth):

                        if StoppingCriteriaMet(data, depth):

                            return LeafNode(data)

                        bestFeature, bestThreshold = FindBestSplit(data)

                        leftData, rightData = SplitData(data, bestFeature, bestThreshold)

                        leftChild = BuildTree(leftData, depth+1)

                        rightChild = BuildTree(rightData, depth+1)

                        return Node(bestFeature, bestThreshold, leftChild, rightChild)


                    # Node function creates a decision node in the tree

                    # function Node(feature, threshold, leftChild, rightChild):

                    #     return {'feature': feature, 'threshold': threshold,

                    #             'left': leftChild, 'right': rightChild, 'isLeaf': false}

Practical Example

Classification Problem

Let's see how CART partitions a 2D feature space for classification:

Decision Boundaries: Notice how CART creates axis-parallel decision boundaries, resulting in a rectangular partition of the feature space.

Decision Path

Following a Sample Through the Tree

Interpretation: Each decision path forms a rule that can be easily understood and explained:
IF age > 30 AND income <= 50K AND education_years > 12 THEN class = 1

Practical Considerations

Working with CART

Feature Scaling: Not required (invariant to monotonic transformations)
Missing Values: Handled through surrogate splits
Computational Efficiency: $O(n \log n)$ per split
Memory Efficiency: Scales well for large datasets
Overfitting: Control through:
- Maximum depth
- Minimum samples per leaf
- Pruning techniques

Pruning

Controlling Complexity

Cost-Complexity Pruning (Minimal Cost-Complexity Pruning):

$$R_\alpha(T) = R(T) + \alpha \cdot |T|$$

Where $R(T)$ is the error of tree $T$, $|T|$ is the number of leaf nodes, and $\alpha$ is the complexity parameter

Pre-pruning: Stop growing the tree early
Post-pruning: Grow a full tree, then prune back
Reduced Error Pruning: Use validation set to evaluate pruning candidates

Key Takeaways

CART Algorithm

CART uses recursive binary splitting to partition feature space
Impurity measures guide optimal split selection:
- Gini impurity or entropy for classification
- MSE for regression
Information gain quantifies the quality of splits
Trees provide interpretable decision rules
Stopping criteria and pruning prevent overfitting
CART forms the foundation for advanced ensemble methods (Random Forests, Gradient Boosting)