Least Squares Regression TreeIt is a commonly used regression tree algorithm.

In order to minimize the square error, it is necessary to traverse the value of each feature in turn and calculate the error of each possible split point. Finally, select the point with the smallest split error and divide the input space into two parts. Recursively repeat the above steps until the split is completed. The tree split by this method is called the least squares regression tree.

This method is relatively complex, especially when looking for split points, because it is necessary to traverse all possible values of the current features. For example, if there are F feature values in total, each feature has N values, and the generated decision tree has S internal nodes, then the time complexity of the algorithm is O(F* N *S).

References

【1】CART Classification and Regression Tree Study Notes (Personal Blog)