A Comparative Deep Dive into CART and Random Forest Models
Classification and Regression Trees (CART) and Random Forests are two of the most widely used machine learning algorithms today, and for good reason. Both are highly flexible, robust models that can be applied to a wide variety of problems with minimal data preprocessing required. However, the two take quite different approaches to learning and have distinct strengths and weaknesses. In this post, we‘ll dive deep into how these algorithms work, explore their tradeoffs, and discuss how to choose the right one for your task.
The Mechanics of CART
At its core, a CART model aims to predict a target variable by learning a series of simple decision rules from the features. It does this through a greedy, top-down process known as binary recursive partitioning.
The algorithm starts with the entire dataset and considers all the features to determine which binary split would lead to the greatest reduction in impurity (a measure of how mixed the target classes are in the subsets created by the split). The data is then partitioned into two branches by this splitting rule, and the process is recursively repeated on each branch.
This continues until a stopping criteria is met, such as a maximum tree depth, minimum number of samples required to consider a split, or when the tree is a perfect classifier of the training data. The end result is a decision tree where each internal node represents a splitting rule, and each leaf represents a predicted class or value.
Some key characteristics of CART to note:
- It‘s a greedy algorithm, always making the locally optimal split at each step. This does not necessarily lead to a globally optimal tree.
- Trees are grown to full depth and then pruned back to prevent overfitting. More advanced pruning techniques leverage a complexity parameter (cp) to find the optimal tradeoff between tree size and accuracy.
- Different measures of impurity can be used, such as Gini impurity, entropy (information gain), or mean squared error (for regression).
- Small changes in the training data can lead to very different trees. CARTs can be unstable, especially when grown deep.
- Splits are always binary (two-way). Features are considered one at a time, so CARTs are not able to learn interactions between features natively.
Despite these limitations, CARTs are widely used in practice due to their simplicity, interpretability, and robustness to outliers and irrelevant features. They form the building blocks of more advanced methods like Random Forests and Gradient Boosted Trees.
Intro to Random Forests
Originally proposed by Leo Breiman in 2001, Random Forests are an ensemble learning method designed to improve the stability and accuracy of CART models. The key idea is to build a large collection of decorrelated trees and average their predictions.
Here‘s a high-level overview of the training algorithm:
- Create a bootstrapped dataset (a random sample with replacement of the original data)
- Build a CART model on this bootstrapped set, but at each node:
- Consider only a random subset of features for splitting (typically sqrt(p) features for classification and p/3 for regression, where p is total number of features)
- Split on the best feature from this subset
- Repeat steps 1 and 2 a number of times (typically 100+) to create a "forest"
- To make a prediction, pass the new data down each tree and take the majority vote (classification) or average (regression) of the tree outputs
By introducing randomness in both the data and feature selection, Random Forests aim to reduce the correlation between the trees. Each tree is a bit worse than a single CART built on all data, but by averaging many decorrelated trees, the variance of the final model is greatly reduced (at the expense of a slight increase in bias).
Some key characteristics of Random Forests:
- Highly parallelizable algorithm, as each tree can be built independently. Easily scales to very large datasets.
- Performs automatic feature selection and can handle datasets with many irrelevant features.
- Robust to outliers and missing data. Can maintain accuracy even when a large proportion of the data is missing.
- Provides a natural way to estimate confidence via the variance of the tree predictions. Useful for applications like anomaly detection.
- Parameters are relatively insensitive to tuning. Tend to work well off-the-shelf.
- Loses interpretability of a single tree. Hard to visualize the model or understand the decisions it‘s making (often considered a "black box").
Random Forests have proven to be a reliable workhorse algorithm, often serving as a strong baseline and even state-of-the-art for some problems like anomaly detection and missing data imputation. Let‘s see them in action!
Case Study: Predicting Iris Species
To illustrate these algorithms, we‘ll use the classic Iris flower dataset. This dataset contains measurements for 150 iris flowers from three different species. Our task is to predict the species based on the flower measurements.
First, let‘s visualize the data to build some intuition:
We can see that the species are fairly separable, especially in the petal dimensions. Setosa seems quite distinct from the other two, while there is some overlap between versicolor and virginica.
Now we‘ll load the necessary libraries and split the data into train and test sets:
library(rpart)
library(randomForest)
library(caret)
data(iris)
set.seed(42)
train.idx <- createDataPartition(iris$Species, p = 0.7, list = FALSE)
train <- iris[train.idx, ]
test <- iris[-train.idx, ]Before building the models, let‘s tune the hyperparameters using 5-fold cross-validation:
# CART
cart.grid <- expand.grid(cp = seq(0.001, 0.1, by = 0.005))
set.seed(42)
cart.cv <- train(Species ~ ., data = train, method = "rpart",
trControl = trainControl(method = "cv", number = 5),
tuneGrid = cart.grid)
plot(cart.cv)
# Random Forest
rf.grid <- expand.grid(mtry = 1:4)
set.seed(42)
rf.cv <- train(Species ~ ., data = train, method = "rf",
trControl = trainControl(method = "cv", number = 5),
tuneGrid = rf.grid)
plot(rf.cv)
It looks like a complexity parameter of around 0.01 is optimal for CART, while using 2 features at each split is best for Random Forest on this data.
Let‘s train the models with these hyperparameters and compare their performance on the test set:
# CART
cart.model <- rpart(Species ~ ., data = train, cp = 0.01)
rpart.plot(cart.model)
cart.pred <- predict(cart.model, newdata = test, type = "class")
confusionMatrix(cart.pred, test$Species)Confusion Matrix and Statistics
Reference
Prediction setosa versicolor virginica
setosa 15 0 0
versicolor 0 13 1
virginica 0 2 14
Overall Statistics
Accuracy : 0.9333
95% CI : (0.8173, 0.9861)
No Information Rate : 0.3333
P-Value [Acc > NIR] : 4.857e-15
Kappa : 0.9
Mcnemar‘s Test P-Value : NA
Statistics by Class:
Class: setosa Class: versicolor Class: virginica
Sensitivity 1.0000 0.8667 0.9333
Specificity 1.0000 0.9667 0.9333
Pos Pred Value 1.0000 0.9286 0.8750
Neg Pred Value 1.0000 0.9355 0.9655
Prevalence 0.3333 0.3333 0.3333
Detection Rate 0.3333 0.2889 0.3111
Detection Prevalence 0.3333 0.3111 0.3556
Balanced Accuracy 1.0000 0.9167 0.9333# Random Forest
rf.model <- randomForest(Species ~ ., data = train, mtry = 2)
rf.pred <- predict(rf.model, newdata = test)
confusionMatrix(rf.pred, test$Species) Confusion Matrix and Statistics
Reference
Prediction setosa versicolor virginica
setosa 15 0 0
versicolor 0 15 0
virginica 0 0 15
Overall Statistics
Accuracy : 1
95% CI : (0.9226, 1)
No Information Rate : 0.3333
P-Value [Acc > NIR] : < 2.2e-16
Kappa : 1
Mcnemar‘s Test P-Value : NA
Statistics by Class:
Class: setosa Class: versicolor Class: virginica
Sensitivity 1.0000 1.0000 1.0000
Specificity 1.0000 1.0000 1.0000
Pos Pred Value 1.0000 1.0000 1.0000
Neg Pred Value 1.0000 1.0000 1.0000
Prevalence 0.3333 0.3333 0.3333
Detection Rate 0.3333 0.3333 0.3333
Detection Prevalence 0.3333 0.3333 0.3333
Balanced Accuracy 1.0000 1.0000 1.0000Both tuned models perform quite well, with CART achieving 93.3% accuracy and Random Forest achieving a perfect 100% on the test set. Let‘s take a look at the learning curves:
We can see that the Random Forest consistently outperforms CART, especially with smaller amounts of training data. It‘s able to achieve high accuracy quite quickly.
Finally, let‘s examine the feature importances from the Random Forest model:
Unsurprisingly, the petal dimensions are the most informative for distinguishing the species, with petal length being the most important by far. This aligns with our intuition from the initial data visualization.
Practical Considerations and Recommendations
We‘ve seen that both CART and Random Forests can be highly effective predictive models. However, there are several factors beyond accuracy to consider when choosing between them:
-
Interpretability: If being able to explain the model‘s decisions is important (e.g. in medical diagnosis or credit approval), CART is usually preferable. The decision rules can be visualized as a binary tree, making it clear how the model arrives at each prediction. Random Forests, on the other hand, are much harder to interpret due to the large number of trees involved.
-
Training time and resources: CARTs are typically much faster to train than Random Forests, especially on large datasets. They also require less memory, as only one tree needs to be stored. Random Forests are more computationally intensive, though their training can be parallelized across cores or machines.
-
Handling of missing data and outliers: Random Forests are naturally robust to missing data and outliers, as each tree only considers a random subset of features and data points. CARTs can be more sensitive, though techniques like surrogate splits can help.
-
Confidence estimates: Random Forests provide a natural way to estimate prediction confidence through the variance of the individual tree outputs. High variance suggests low confidence and could indicate an anomaly or novel data point. CARTs do not provide this out-of-the-box.
-
Feature importances: Random Forests automatically compute feature importances as a byproduct of the training process (the improvement in split criterion attributed to each feature, averaged over all trees). This can be useful for feature selection and understanding the key drivers of the model‘s predictions. Feature importances can be extracted from CARTs as well, but require more work.
As a general rule of thumb, I recommend starting with a Random Forest for most machine learning problems. They tend to perform very well with minimal tuning, and the robustness to noise and missing data is a big advantage in real-world applications. However, if interpretability is crucial or you‘re working with truly massive datasets, CART may be the better choice.
Of course, the best approach is to try both and let the data decide! Train each model using cross-validation, evaluate on a held-out test set, and go with the one that performs best for your specific problem and constraints.
Conclusion
CART and Random Forests are two powerful yet distinct algorithms in the machine learning toolbox. While both learn decision tree models, they differ greatly in how the trees are constructed and combined.
CARTs build a single tree in a greedy fashion, making the locally optimal split at each node. This makes them interpretable and fast to train, but prone to instability and overfitting. Random Forests build a large number of decorrelated trees in parallel and average the results. This reduces variance and increases accuracy, at the cost of interpretability and training time.
In practice, Random Forests often outperform single decision trees, especially on noisy or incomplete data. However, the best model depends on the specific characteristics of the problem and the constraints of the application.
Hopefully this deep dive has given you a better understanding of how these algorithms work and when to use them. As with most things in machine learning, there‘s no one-size-fits-all solution. But armed with a solid grasp of the tradeoffs involved, you‘ll be well-equipped to choose the right tool for your task!
