Recursion in context with decision trees

Viewed 21

So I am struggling with understanding recursion in the context of decision trees. I have looked at two different codes from two different websites: Example 1 and Example 2. This is a part of the code from the first example:

class DecisionTreeClassifier():
def __init__(self, min_samples_split=2, max_depth=2):
    ''' constructor '''
    
    # initialize the root of the tree 
    self.root = None
    
    # stopping conditions
    self.min_samples_split = min_samples_split
    self.max_depth = max_depth
    
def build_tree(self, dataset, curr_depth=0):
    ''' recursive function to build the tree ''' 
    
    X, Y = dataset[:,:-1], dataset[:,-1]
    num_samples, num_features = np.shape(X)
    
    # split until stopping conditions are met
    if num_samples>=self.min_samples_split and curr_depth<=self.max_depth:
        # find the best split
        best_split = self.get_best_split(dataset, num_samples, num_features)
        # check if information gain is positive
        if best_split["info_gain"]>0:
            # recur left
            left_subtree = self.build_tree(best_split["dataset_left"], curr_depth+1)
            # recur right
            right_subtree = self.build_tree(best_split["dataset_right"], curr_depth+1)
            # return decision node
            return Node(best_split["feature_index"], best_split["threshold"], 
                        left_subtree, right_subtree, best_split["info_gain"])
    
    # compute leaf node
    leaf_value = self.calculate_leaf_value(Y)
    # return leaf node
    return Node(value=leaf_value)

I can't wrap my head around how the information about the split decisions and thresholds are "saved" while performing the recursion. In both of the codes they return only one node after the recursion is done, but how can this node store the whole tree, when it is only one node? Should not a tree be able to contain many nodes?

Since the recursion is performed before the making of the node, how is the information about the different split decisions and thresholds "stored" before making the node? This might be some stupid questions but I am really struggling with understanding this concept and was hoping if someone had a good explanation that could help me visualize what happens during the recursion.

0 Answers
Related