最小二乘回归树 Least squares regression tree

最小二乘回归树是一种常用回归树算法。

为了使平方误差最小,就需要依次对每个特征的取值进行遍历,并计算出当前每一个可能的切分点误差,最后选择切分误差最小的点,并将输入空间切分为两部分,递归上述步骤,直到切分结束,这种方法切分的树被称为最小二乘回归树。

这种方法的复杂度较高,尤其在寻找切分点时,需要遍历当前所有特征的可能取值,如共有 F 个特征值,其中每个特征有 N 个取值,其生成的决策树有 S 个内部节点,则该算法的时间复杂度为 O(F* N *S) 。

参考来源

【1】CART 分类与回归树 学习笔记 (个人博客)