Recursive Partitioning Algorithm
What you'll learn: How decision trees are built from the top down by repeatedly splitting data until stopping conditions are satisfied.
The Core Idea
The recursive partitioning algorithm is the engine that constructs a decision tree. It's called "recursive" because it applies the same splitting logic over and over to smaller and smaller subsets of data, and "partitioning" because each split divides the data into distinct groups.
Think of organizing a messy closet: you first split clothes into categories (shirts vs pants), then recursively split each category further (short-sleeve vs long-sleeve shirts), continuing until each group is small or homogeneous enough that further splitting isn't useful.
The Algorithm Steps
- Start at the root with all training data
- Find the best split using your chosen criterion (Information Gain, Gini Index, or variance reduction)
- Partition the data into subsets based on that split
- Recurse: Apply steps 2-3 to each new child node
- Stop when a termination condition is met:
- All samples in a node have the same label
- Maximum depth reached
- Minimum samples per node threshold met
- No split improves the impurity measure sufficiently
Why "Greedy"?
The algorithm is greedy because at each step it chooses the locally best split without considering future splits. It doesn't backtrack or look ahead—it commits to whatever split maximizes immediate impurity reduction. This makes it fast but not guaranteed to find the globally optimal tree.
The Result
Each recursive call creates branches until leaf nodes contain predictions: class labels (classification) or mean values (regression). The entire tree structure emerges naturally from this repeated splitting process.
Key Takeaway: Recursive partitioning builds decision trees top-down by greedily choosing the best split at each node and recursing on the resulting partitions until stopping criteria halt further division.