implementation of a basic regression decision tree input data set the input data set must be 1dimensional with continuous labels output the decision tree maps a real number input to a real number output meansquarederror param labels a onedimensional numpy array param prediction a floating point value return value meansquarederror calculates the error if prediction is used to estimate the labels tester decisiontree testlabels np array1 2 3 4 5 6 7 8 9 10 testprediction float6 tester meansquarederrortestlabels testprediction testdecisiontree helpermeansquarederrortesttestlabels testprediction true testlabels np array1 2 3 testprediction float2 tester meansquarederrortestlabels testprediction testdecisiontree helpermeansquarederrortesttestlabels testprediction true train param x a onedimensional numpy array param y a onedimensional numpy array the contents of y are the labels for the corresponding x values train does not have a return value examples 1 try to train when x y are of same length 1 dimensions no errors dt decisiontree dt trainnp array10 20 30 40 50 np array0 0 0 1 1 2 try to train when x is 2 dimensions dt decisiontree dt trainnp array1 2 3 4 5 1 2 3 4 5 np array0 0 0 1 1 traceback most recent call last valueerror input data set must be onedimensional 3 try to train when x and y are not of the same length dt decisiontree dt trainnp array1 2 3 4 5 np array0 0 0 1 1 0 0 0 1 1 traceback most recent call last valueerror x and y have different lengths 4 try to train when x y are of the same length but different dimensions dt decisiontree dt trainnp array1 2 3 4 5 np array1 2 3 4 5 traceback most recent call last valueerror data set labels must be onedimensional this section is to check that the inputs conform to our dimensionality constraints loop over all possible splits for the decision tree find the best split if no split exists that is less than 2 error for the entire array then the data set is not split and the average for the entire array is used as the predictor predict param x a floating point value to predict the label of the prediction function works by recursively calling the predict function of the appropriate subtrees based on the tree s decision boundary decision tres test class staticmethod def helpermeansquarederrortestlabels prediction squarederrorsum float0 for label in labels squarederrorsum label prediction 2 return floatsquarederrorsum labels size def main x np arange1 0 1 0 0 005 y np sinx tree decisiontreedepth10 minleafsize10 tree trainx y testcases np random rand10 2 1 predictions np arraytree predictx for x in testcases avgerror np meanpredictions testcases 2 printtest values strtestcases printpredictions strpredictions printaverage error stravgerror if name main main import doctest doctest testmodnamemeansquarrederror verbosetrue mean_squared_error param labels a one dimensional numpy array param prediction a floating point value return value mean_squared_error calculates the error if prediction is used to estimate the labels tester decisiontree test_labels np array 1 2 3 4 5 6 7 8 9 10 test_prediction float 6 tester mean_squared_error test_labels test_prediction testdecisiontree helper_mean_squared_error_test test_labels test_prediction true test_labels np array 1 2 3 test_prediction float 2 tester mean_squared_error test_labels test_prediction testdecisiontree helper_mean_squared_error_test test_labels test_prediction true train param x a one dimensional numpy array param y a one dimensional numpy array the contents of y are the labels for the corresponding x values train does not have a return value examples 1 try to train when x y are of same length 1 dimensions no errors dt decisiontree dt train np array 10 20 30 40 50 np array 0 0 0 1 1 2 try to train when x is 2 dimensions dt decisiontree dt train np array 1 2 3 4 5 1 2 3 4 5 np array 0 0 0 1 1 traceback most recent call last valueerror input data set must be one dimensional 3 try to train when x and y are not of the same length dt decisiontree dt train np array 1 2 3 4 5 np array 0 0 0 1 1 0 0 0 1 1 traceback most recent call last valueerror x and y have different lengths 4 try to train when x y are of the same length but different dimensions dt decisiontree dt train np array 1 2 3 4 5 np array 1 2 3 4 5 traceback most recent call last valueerror data set labels must be one dimensional this section is to check that the inputs conform to our dimensionality constraints loop over all possible splits for the decision tree find the best split if no split exists that is less than 2 error for the entire array then the data set is not split and the average for the entire array is used as the predictor predict param x a floating point value to predict the label of the prediction function works by recursively calling the predict function of the appropriate subtrees based on the tree s decision boundary decision tres test class helper_mean_squared_error_test param labels a one dimensional numpy array param prediction a floating point value return value helper_mean_squared_error_test calculates the mean squared error in this demonstration we re generating a sample data set from the sin function in numpy we then train a decision tree on the data set and use the decision tree to predict the label of 10 different test values then the mean squared error over this test is displayed
import numpy as np


class DecisionTree:
    def __init__(self, depth=5, min_leaf_size=5):
        self.depth = depth
        self.decision_boundary = 0
        self.left = None
        self.right = None
        self.min_leaf_size = min_leaf_size
        self.prediction = None

    def mean_squared_error(self, labels, prediction):
        
        if labels.ndim != 1:
            print("Error: Input labels must be one dimensional")

        return np.mean((labels - prediction) ** 2)

    def train(self, x, y):
        
        if x.ndim != 1:
            raise ValueError("Input data set must be one-dimensional")
        if len(x) != len(y):
            raise ValueError("x and y have different lengths")
        if y.ndim != 1:
            raise ValueError("Data set labels must be one-dimensional")

        if len(x) < 2 * self.min_leaf_size:
            self.prediction = np.mean(y)
            return

        if self.depth == 1:
            self.prediction = np.mean(y)
            return

        best_split = 0
        min_error = self.mean_squared_error(x, np.mean(y)) * 2

        
        for i in range(len(x)):
            if len(x[:i]) < self.min_leaf_size:
                continue
            elif len(x[i:]) < self.min_leaf_size:
                continue
            else:
                error_left = self.mean_squared_error(x[:i], np.mean(y[:i]))
                error_right = self.mean_squared_error(x[i:], np.mean(y[i:]))
                error = error_left + error_right
                if error < min_error:
                    best_split = i
                    min_error = error

        if best_split != 0:
            left_x = x[:best_split]
            left_y = y[:best_split]
            right_x = x[best_split:]
            right_y = y[best_split:]

            self.decision_boundary = x[best_split]
            self.left = DecisionTree(
                depth=self.depth - 1, min_leaf_size=self.min_leaf_size
            )
            self.right = DecisionTree(
                depth=self.depth - 1, min_leaf_size=self.min_leaf_size
            )
            self.left.train(left_x, left_y)
            self.right.train(right_x, right_y)
        else:
            self.prediction = np.mean(y)

        return

    def predict(self, x):
        
        if self.prediction is not None:
            return self.prediction
        elif self.left or self.right is not None:
            if x >= self.decision_boundary:
                return self.right.predict(x)
            else:
                return self.left.predict(x)
        else:
            print("Error: Decision tree not yet trained")
            return None


class TestDecisionTree:
    

    @staticmethod
    def helper_mean_squared_error_test(labels, prediction):
        
        squared_error_sum = float(0)
        for label in labels:
            squared_error_sum += (label - prediction) ** 2

        return float(squared_error_sum / labels.size)


def main():
    
    x = np.arange(-1.0, 1.0, 0.005)
    y = np.sin(x)

    tree = DecisionTree(depth=10, min_leaf_size=10)
    tree.train(x, y)

    test_cases = (np.random.rand(10) * 2) - 1
    predictions = np.array([tree.predict(x) for x in test_cases])
    avg_error = np.mean((predictions - test_cases) ** 2)

    print("Test values: " + str(test_cases))
    print("Predictions: " + str(predictions))
    print("Average error: " + str(avg_error))


if __name__ == "__main__":
    main()
    import doctest

    doctest.testmod(name="mean_squarred_error", verbose=True)