Constructing and pruning decision trees

Welcome to the World of Decision Trees!

In this section, we are going to learn how to actually "grow" a decision tree and, perhaps more importantly, how to "trim" it so it works perfectly on new data. Think of a decision tree like a real plant: if you let it grow wild without any maintenance, it becomes a tangled mess that's hard to deal with. But if you prune it carefully, it becomes a beautiful, useful tool for making predictions.

Decision trees are a favorite for actuaries because they are easy to explain to stakeholders (like your boss or a client) and they mirror the way humans often make decisions. Let’s dive in!

Quick Review: Remember that a decision tree splits your data into different groups (called nodes) based on the values of your input variables. The final groups at the bottom are called leaves or terminal nodes.

Step 1: Building the Tree (Recursive Binary Splitting)

When we start building a tree, we use a process called Recursive Binary Splitting. Don't let the name scare you—it's actually quite simple when you break it down.

1. Recursive: We repeat the process over and over for each resulting branch.
2. Binary: Each split only results in two branches (e.g., "Yes" or "No").
3. Splitting: We are dividing the data into smaller groups.

The "Greedy" Approach:
Building a tree is a greedy algorithm. This means at every step, the computer looks for the single best split it can make right now to improve the model. It doesn't look ahead to see if a slightly "worse" split now might lead to a much better split later. It's living in the moment!

How do we decide which split is "best"?

It depends on what we are trying to predict:

For Regression Trees (Predicting a Number):
We want to minimize the Residual Sum of Squares (RSS). We want the data points in each resulting leaf to be as close to the average value of that leaf as possible. The formula looks like this:
\( RSS = \sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2 \)
Translation: We want to minimize the total squared "errors" across all our final regions (\( R_j \)).

For Classification Trees (Predicting a Category):
We want the resulting groups to be "pure." If a leaf contains 100% "Category A" and 0% "Category B," it is perfectly pure. We usually measure this using the Gini Index or Entropy. Lower values mean the group is more "pure."

Did you know? The Gini Index is often called a measure of node impurity. If the Gini Index is 0, the node is perfectly pure (everyone in the group is the same category).

Summary Takeaway: We build trees from the top down, one split at a time, choosing the split that reduces error (RSS) or impurity (Gini/Entropy) the most at that specific moment.

Step 2: The Danger of Growing Too Large

If we keep splitting the data until every single person in our dataset has their own private leaf, we will have a 0% error rate on our training data. But there’s a big problem: Overfitting.

Overfitting is when the tree learns the "noise" or random quirks of your specific dataset rather than the actual patterns. An overfitted tree is like a student who memorizes the exact answers to a practice exam but doesn't understand the underlying math—when the real exam comes with different numbers, they fail!

The Bias-Variance Tradeoff:
- A huge, complex tree has High Variance (it changes wildly if you change the data slightly).
- A tiny tree with only one split has High Bias (it's too simple to catch the real patterns).

Step 3: Pruning the Tree (Cost-Complexity Pruning)

To fix overfitting, we grow a very large tree and then "prune" it back to find a smaller subtree. But we can't just pick subtrees at random—there are too many possibilities! Instead, we use Cost-Complexity Pruning (also known as Weakest Link Pruning).

We use a special score to decide which branches to cut. The formula for the score is:
\( \sum_{m=1}^{|T|} \sum_{i \in R_m} (y_i - \hat{y}_{R_m})^2 + \alpha|T| \)

Let’s break this formula down into "Actuary-speak":
1. The first part \( \sum \sum (y_i - \hat{y}_{R_m})^2 \) is just the RSS (how well the tree fits the data).
2. The second part \( \alpha|T| \) is the Penalty.
- \( |T| \) is the number of terminal nodes (leaves). More leaves = more complexity.
- \( \alpha \) (alpha) is the tuning parameter. It's a number we choose that controls how much we "punish" the tree for being too complex.

How \(\alpha\) works:
- If \( \alpha = 0 \): There is no penalty! We just get the huge, original tree.
- If \( \alpha \) is very large: The penalty is huge! We will end up with a very small tree (maybe even just one node).
- As we increase \( \alpha \) from zero, branches get pruned away one by one in a specific, predictable order.

Memory Aid: Think of \( \alpha \) as a "Tax" on leaves. If the tax is low, the tree can afford many leaves. If the tax is high, the tree must downsize to stay "profitable."

Summary Takeaway: Pruning helps us find a balance between a tree that is too simple and a tree that is too complex. We use the tuning parameter \(\alpha\) to control this balance.

Step 4: Choosing the Best Alpha (\(\alpha\))

How do we know which value of \(\alpha\) to use? We use K-Fold Cross-Validation!

1. Split your data into \( K \) parts (folds).
2. For each value of \(\alpha\), build the tree on some folds and test it on the remaining fold.
3. Pick the \(\alpha\) that gives the lowest average error on the test folds.

Common Mistake to Avoid: Don't pick the \(\alpha\) that makes the tree look best on your training data. Always use validation data or cross-validation to pick \(\alpha\). Otherwise, you are back to overfitting!

Step-by-Step Process Recap

Don't worry if this feels like a lot. Here is the standard recipe for building a great tree:
1. Use Recursive Binary Splitting to grow a large tree on the training data. (Stop only when nodes are very small).
2. Apply Cost-Complexity Pruning to find a sequence of best subtrees as a function of \(\alpha\).
3. Use K-Fold Cross-Validation to choose the best \(\alpha\).
4. Return to the subtree from Step 2 that corresponds to your chosen \(\alpha\).

Final Quick Review Box

- Growing strategy: Top-down, Greedy, Recursive Binary Splitting.
- Regression Goal: Minimize RSS.
- Classification Goal: Minimize Gini Index or Entropy.
- The Problem: Large trees overfit (high variance).
- The Solution: Pruning using a penalty term \(\alpha|T|\).
- Tuning: Use Cross-Validation to select the best \(\alpha\).

You've got this! Decision trees are just about making the best splits possible and then cleaning up the mess afterward to make sure the model stays "smart" for new data.