Mastering Decision Trees and Random Forests for Machine Learning

Introduction to Tree-Based Models

In the landscape of machine learning, decision trees and random forests represent some of the most intuitive yet powerful tools for classification and regression tasks. For university students, mastering these concepts is essential, as they form the backbone of many real-world predictive systems. You will learn how individual trees partition feature spaces and how ensemble methods like random forests mitigate the inherent weaknesses of single trees.

Understanding these models is critical for your exams because they bridge the gap between simple linear models and complex black-box algorithms. By grasping the mechanics of recursive splitting and the logic behind bagging, you will be well-equipped to tackle questions on model variance, bias, and the trade-offs involved in ensemble learning.

The Anatomy of a Decision Tree

A decision tree is a hierarchical structure that performs recursive binary splitting of the feature space. Starting at the root node, the algorithm selects a feature $j$ and a threshold $s$ to partition the data into two subsets. This process repeats until a stopping criterion is met, such as a maximum depth or a minimum number of samples per leaf.

Consider a simple dataset with two features: $x_1$ (e.g., study hours) and $x_2$ (e.g., previous marks). To split a node, we seek to maximise the purity of the resulting child nodes. If we have a node with 10 samples (6 Pass, 4 Fail), the Gini impurity is calculated as:

$$G = 1 - \sum_{c=1}^{C} p_c^2 = 1 - ((6/10)^2 + (4/10)^2) = 1 - (0.36 + 0.16) = 0.48$$

We choose the split that results in the greatest reduction in impurity, known as Information Gain or Gini Gain.

Tree Splitting and Purity Criteria

To build an effective tree, we must quantify the quality of a split. The two most common metrics are Gini Impurity and Entropy. Entropy measures the disorder in a node, defined as $H = -\sum p_c \log_2(p_c)$. A perfectly pure node has an entropy of 0.

Worked Example 1: Calculating Gini Impurity Suppose a node contains 20 samples: 15 Class A and 5 Class B.

1. Calculate the probability of each class: $p_A = 15/20 = 0.75$, $p_B = 5/20 = 0.25$.
2. Apply the Gini formula: $G = 1 - (0.75^2 + 0.25^2) = 1 - (0.5625 + 0.0625) = 0.375$.
3. If a split results in two nodes with Gini values of 0.2 and 0.1, the weighted average impurity is calculated based on the number of samples in each child node to determine the gain.

From Single Trees to Random Forests

Single decision trees are prone to overfitting; they often capture noise in the training data rather than the underlying signal. Random forests solve this by using an ensemble method called bagging (bootstrap aggregating). By training multiple trees on different subsets of the data and different subsets of features, the forest reduces variance without significantly increasing bias.

Worked Example 2: Ensemble Voting Imagine a random forest with 3 trees classifying a new data point:

• Tree 1 predicts: Class A
• Tree 2 predicts: Class B
• Tree 3 predicts: Class A

The final prediction is determined by a majority vote. Since Class A received 2 out of 3 votes, the random forest predicts Class A. This aggregation smooths out the errors of individual trees.

The Role of Randomness

Random forests introduce two layers of randomness. First, each tree is trained on a bootstrap sample of the original dataset (sampling with replacement). Second, at each node split, the algorithm only considers a random subset of features. This decorrelates the trees, ensuring that the forest does not rely too heavily on a single dominant feature, which makes the model more robust to noise.

Common Mistakes

1. Overfitting: Failing to prune trees or set a maximum depth, leading to a model that memorises the training data.
2. Ignoring Feature Correlation: Assuming that adding more trees always improves performance; if trees are highly correlated, the ensemble gain is minimal.
3. Misinterpreting Impurity: Confusing Gini impurity with entropy; while they often yield similar results, they are mathematically distinct and should not be used interchangeably in calculations.

Frequently Asked Questions

What is the main advantage of a random forest over a single decision tree? Random forests significantly reduce variance and prevent overfitting by averaging the predictions of multiple decorrelated trees.

Why do we use bootstrap sampling? Bootstrap sampling ensures that each tree in the forest is trained on a slightly different version of the data, which helps in creating diverse, independent models.

What happens if we do not stop splitting a tree? Without stopping criteria, the tree will continue to split until every leaf contains only one sample, leading to a model with high variance that fails to generalise to new data.

Conclusion

Decision trees and random forests are fundamental pillars of machine learning. By understanding how to measure node purity and how ensemble methods aggregate predictions, you are well-prepared for your assessments. To see these concepts in action, visit MathInstructor AI to generate a free, narrated animated lesson on this topic.