Recursive Decision Tree Construction

From One Split to a Full Tree: The Power of Recursion

How do we go from finding one split to building a whole tree? The answer lies in a powerful programming concept you're familiar with from your computer science studies: recursion.

A decision tree is inherently a recursive data structure. A tree is composed of a root node and two smaller sub-trees (a left child and a right child). Each of those sub-trees is, in itself, a decision tree.

Our building process will mirror this structure:

1. Start at the root with the entire dataset.
2. Find the best split for the current data.
3. Create a decision node that stores this split information.
4. Apply the same tree-building logic to the left subset of the data to create the left child sub-tree.
5. Apply the same logic to the right subset of the data to create the right child sub-tree.

This process continues until we hit a "base case," which tells the algorithm to stop splitting.

The Importance of Stopping Criteria

If we let our recursive function run indefinitely, it would continue splitting until every single sample is in its own "pure" leaf node. This would result in a tree that perfectly memorizes the training data, including its noise. This is the definition of overfitting, and it would perform poorly on new, unseen data.

To prevent this and to control the complexity of our model, we must define stopping criteria (also known as pre-pruning). These are rules that tell the recursion when to stop growing a particular branch and create a leaf node instead.

Common stopping criteria include:

• Maximum Depth (max_depth): Stop splitting if a branch has reached a predefined number of levels. This is a direct way to limit the tree's overall complexity.
• Minimum Samples for a Split (min_samples_split): Do not split a node if the number of data samples it contains is below a certain threshold. This prevents the model from learning patterns from very small groups of samples, which are likely to be statistical flukes.
• Node Purity: If a node contains samples from only one class, it's "pure." There's no more information to be gained by splitting it, so it naturally becomes a leaf node.

Implementing the Recursive Tree Builder

Let's get to the implementation. Your preference for from-scratch coding will be front and center here. We'll need two main classes: one to represent a single Node and another to orchestrate the building of the DecisionTree.

For a comprehensive walkthrough of the code we're about to write, the following video is an excellent resource.

Step 1: The Node Class

First, we need a simple structure to hold the information for each node in our tree. A decision node needs to know its splitting rule and have pointers to its children. A leaf node just needs to know what class value to predict.

class Node:
    """
    A node in the decision tree.
    
    Attributes:
        feature (int): The index of the feature to split on.
        threshold (float): The threshold for the split.
        left (Node): The left child node.
        right (Node): The right child node.
        value (int): The class label for a leaf node.
    """
    def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None):
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value

    def is_leaf_node(self):
        """Checks if the node is a leaf node."""
        return self.value is not None

The * in the __init__ signature forces value to be a keyword argument (e.g., Node(value=1)), which makes the code more readable when creating leaf nodes.

Step 2: The DecisionTree Class and the _build_tree Function

Now for the main event. We'll create a DecisionTree class. Its fit method will initialize the hyperparameters and start the recursion. The private _build_tree method will contain the core recursive logic.

We'll assume the functions you built in the previous lessons (gini_impurity, information_gain, find_best_split, split_dataset) are available.

import numpy as np
from collections import Counter

# --- Assume functions from previous lessons are here ---
# gini_impurity(y)
# information_gain(parent_y, left_y, right_y)
# split_dataset(X, y, feature_index, threshold)
# find_best_split(X, y)

class DecisionTree:
    def __init__(self, min_samples_split=2, max_depth=100):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth
        self.root = None

    def fit(self, X, y):
        """Starts the tree building process."""
        self.root = self._build_tree(X, y)

    def _build_tree(self, X, y, depth=0):
        """Recursive function to build the tree."""
        n_samples, _ = X.shape
        n_labels = len(np.unique(y))

        # --- Part 1: Check for stopping criteria (Base Cases) ---
        if (depth >= self.max_depth or 
            n_labels == 1 or 
            n_samples < self.min_samples_split):
            
            leaf_value = self._most_common_label(y)
            return Node(value=leaf_value)

        # --- Part 2: Find the best split ---
        best_split = find_best_split(X, y)
        
        # If no profitable split is found, create a leaf
        if not best_split or best_split['gain'] <= 0:
            leaf_value = self._most_common_label(y)
            return Node(value=leaf_value)

        # --- Part 3: Recurse on children ---
        feature_index = best_split['feature_index']
        threshold = best_split['threshold']

        # Split the data
        X_left, y_left, X_right, y_right = split_dataset(X, y, feature_index, threshold)
        
        # Recursively build the left and right subtrees
        left_child = self._build_tree(X_left, y_left, depth + 1)
        right_child = self._build_tree(X_right, y_right, depth + 1)

        # Return the new decision node
        return Node(feature=feature_index, threshold=threshold, left=left_child, right=right_child)

    def _most_common_label(self, y):
        """Helper function to find the majority class in a node."""
        if len(y) == 0:
            return None # Should not happen with good splits
        counter = Counter(y)
        most_common = counter.most_common(1)[0][0]
        return most_common

Let's break down the _build_tree method:

1. Base Cases: It first checks the stopping criteria. Is the depth too great? Is the node already pure? Are there too few samples to split? If any of these are true, it creates a Node with a value (making it a leaf) and the recursion on that branch terminates.
2. Find Split: If it's not a base case, it calls find_best_split to get the best way to partition the current data. If no split improves the purity (gain <= 0), it also becomes a leaf.
3. Recurse: This is the magic. It splits the data according to the best split found and then calls _build_tree on itself for the left and right subsets. Crucially, it increments the depth counter for these calls. The return values of these recursive calls become the left and right children of the current node.

This pattern is standard for building decision trees. You can see it echoed in many implementations.

Conclusion

Congratulations! You have now assembled all the core components and built the recursive function that grows a complete decision tree. This is the most complex part of the algorithm, and understanding how the recursion works is key to understanding decision trees themselves.

Key Takeaways:

• Decision tree construction is a naturally recursive process.
• The _build_tree function acts as the recursive engine, calling itself to create left and right sub-trees.
• Stopping criteria (base cases) like max_depth, min_samples_split, and node purity are essential to terminate the recursion and prevent overfitting.
• A Node class is a convenient way to store information about each point in the tree, whether it's a decision or a leaf.

Preview of the Next Lesson:
We've built a single, powerful decision tree. However, single trees can be sensitive to the specific data they are trained on. A more robust and often more accurate approach is to use an ensemble of trees. In the next lesson, we will begin our journey toward building a Random Forest by first implementing bootstrap sampling ('bagging'), the technique used to create the varied datasets needed to train each tree in the forest.