一种回归决策树的快速遍历划分算法

备忘录的思想快速寻找最优划分

问题的提出

众所周知,建立CART树有一个关键步骤:遍历数据空间中的所有划分界限,寻找最优切分特征$\alpha$与阈值$c$,以最小化分出的两个集合的方差,也就是下面这个式子:

其中, $\bar{y_1},\bar{y_2}$分别是$x_i[\alpha]<c,x_i[\alpha]>c$样本点的y均值.

问题在于,经典的CART树要遍历所有划分界限,上面的最小化式就需要计算$n_{sample} \times n_{feature}$次,而使用备忘录的思想,并将最小化式化简,可以极大地提升性能.

算法思路

首先,拎出一个方差式来变形

那么,对一个切分特征$\alpha$与阈值$c$的划分(假设依据$x_i[\alpha]<c$划分为了L,R两个集合):

由于$\sum{y^2}$对任意划分都相同,故我们现在只需要$\max\limits_{\alpha,c}{[\frac{(\sum_{(x,y) \in L}{y})^2}{n_{L}}+\frac{(\sum_{(x,y) \in R}{y})^2}{n_{R}}]}$得到这个式子以后,我们就知道了,每一次迭代,只需要获知两个集合中样本点个数和样本点y的和就足够了,而无需重新计算方差,由此就可以使用备忘录的思想了,能获得极大性能提升.

算法代码:

完整决策树见: cquai-ml/DecisionTreeRegressor

def _build_tree(self, X, y, cur_depth, parent, is_left):
    if cur_depth == self.max_depth:
        self._build_leaf(X, y, cur_depth, parent, is_left)

    best_gain = -np.inf
    best_feature = None
    best_threshold = None
    best_left_ind = best_right_ind = None

    sum_all = np.sum(y)
    step = lambda x, y, a: (x + a, y - a)

    for i in range(X.shape[1]):  # for features
        sum_left, sum_right = 0, sum_all
        n_left = 0
        n_right = X.shape[0]
        ind = np.argsort(X[:, i])

        for j in range(ind.shape[0] - 1):  # for all sample
            # step by step
            sum_left, sum_right = step(sum_left, sum_right, y[ind[j]])
            n_left, n_right = step(n_left, n_right, 1)

            cur_gain = (
                sum_left * sum_left / n_left + sum_right * sum_right / n_right
            )
            if cur_gain > best_gain:  # found better choice
                best_gain = cur_gain
                best_feature = i
                best_threshold = X[ind[j], i]
                best_left_ind, best_right_ind = ind[: j + 1], ind[j + 1 :]
    
    # ...
    
本文总字数: 1314