Constructing, pruning, and validating regression and classification trees

Welcome to the World of Trees!

Hello there! Today, we are diving into one of the most intuitive and visual parts of Exam PA: Decision Trees. If you’ve ever played a game of "20 Questions" or followed a flowchart to troubleshoot your internet connection, you already understand the basic logic of a tree. In this chapter, we’ll learn how to build them, how to stop them from getting too "wild," and how to make sure they work on data they haven't seen before. Don't worry if this seems a bit technical at first—we’ll break it down step-by-step!

1. Building the Tree: Recursive Binary Splitting

When we build a tree, we are trying to divide our data into smaller, more "pure" groups. This process is called Recursive Binary Splitting. Think of it like sorting your laundry: you might first split by color (Whites vs. Colors), then split the colors by fabric type.

How it works (Step-by-Step):

1. Start at the Top: We begin with all our observations in one big group (the Root Node).
2. The Best Split: We look at every single predictor variable and every possible "split point" (e.g., Age < 30 vs. Age ≥ 30).
3. The Goal: We choose the split that results in the greatest reduction in "impurity." We want the resulting groups (the leaves) to be as similar to each other as possible.
4. Repeat: We do this again and again for each of the new branches. This is why it’s "recursive."

Measuring Success (The Math Bit)

How do we know if a split is "good"? It depends on what we are predicting:

For Regression Trees (Predicting a Number):
We use the Residual Sum of Squares (RSS). We want to find the split that minimizes: \( \sum (y_i - \hat{y}_{R})^2 \) Translation: We want the actual values in that group to be as close to the group average as possible.

For Classification Trees (Predicting a Category):
We use measures like the Gini Index or Entropy.
- Gini Index: \( G = \sum_{k=1}^{K} \hat{p}_{mk}(1 - \hat{p}_{mk}) \)
- Entropy: \( D = -\sum_{k=1}^{K} \hat{p}_{mk} \log \hat{p}_{mk} \)
Both of these measures are low if a node is "pure" (meaning almost everyone in that group belongs to the same category).

Quick Review: Splitting is greedy. This means the model makes the best decision for the current step without worrying about whether that split will lead to a better tree five steps down the road.

2. The Danger of Growing Too Large: Overfitting

If we let a tree grow until every single observation is in its own tiny leaf, we will have 0% error on our training data. This sounds great, right? Wrong! This is a classic case of Overfitting.

Analogy: Imagine memorizing every single specific question and answer from a practice exam instead of learning the underlying concepts. When the real exam comes with slightly different questions, you’ll fail because you didn't learn the patterns; you just memorized the noise.

Stopping Rules (Hyperparameters)

To prevent a tree from becoming a giant, overfitted mess, we use "stopping rules":
- minbucket: The minimum number of observations allowed in a leaf. If a split would create a group smaller than this, the split isn't allowed.
- maxdepth: The maximum number of "levels" the tree can have.
- cp (Complexity Parameter): A threshold for how much the error must improve to justify another split.

3. Pruning: Trimming the Tree

Even with stopping rules, it's often better to grow a very large tree first and then "prune" it back. This is called Cost Complexity Pruning (or Weakest Link Pruning).

We use a formula to score the tree: \( R_{\alpha}(T) = R(T) + \alpha |T| \) - \( R(T) \) is the error (like RSS).
- \( |T| \) is the number of terminal nodes (the size of the tree).
- \( \alpha \) (Alpha): This is the "penalty" for complexity.

The Trade-off:
- If \( \alpha = 0 \), the penalty is zero, so we get a huge, complex tree.
- As \( \alpha \) increases, the penalty for having more leaves grows, forcing the tree to become smaller and simpler.

Did you know? In the R package rpart, the complexity parameter cp is directly related to this \(\alpha\). A higher cp means a smaller tree!

4. Validation: Choosing the Best Tree

How do we pick the perfect level of pruning (the best \(\alpha\))? We use K-fold Cross-Validation.

The Process:
1. Split the data into 10 parts (folds).
2. Train the tree on 9 parts and test it on the 10th.
3. Repeat this for different tree sizes.
4. Pick the size that has the lowest cross-validation error.

The 1-SE Rule

On Exam PA, you will often hear about the 1-SE Rule. Instead of picking the absolute best-performing tree, we pick the smallest (simplest) tree whose error is within one standard error of the minimum error.
Why? Because in the actuarial world, we prefer parsimony (simplicity). A simpler model is less likely to overfit and easier to explain to stakeholders!

5. Summary and Key Takeaways

- Trees are built using Recursive Binary Splitting, a "greedy" approach.
- Regression trees minimize RSS; Classification trees minimize Gini or Entropy.
- Overfitting happens when the tree is too complex and captures noise instead of signal.
- Pruning uses Cost Complexity to find a balance between accuracy and simplicity.
- Cross-validation helps us select the best version of the tree.
- Remember: High cp = small tree. Low cp = large tree.

Common Mistake to Avoid: Don't confuse minbucket with minsplit. Minsplit is the number of observations needed to attempt a split, while minbucket is the number of observations that must remain in the resulting leaves.

Keep going! Tree-based models are the foundation for more advanced techniques like Random Forests and Boosting. Master these basics, and you're halfway there!