1. CART树的生成算法

输入: 训练数据集X,样本标签y
输出:回归树f(x)

1.1. 步骤

  1. 若D中所有实例属于同一类CkC_k,则T为单结点树,并将类CkC_k作为该结点的类标记,返回T
  2. 对每个特征feature的每个取值value,将y分为R1R_1R2R_2两个集合,因为现在还不是真正的split,只是要计算split后的基尼指数,只需要用到split之后的y
    y1(feature,value)={yixi(feature)value}y2(feature,value)={yiyi(feature)>value} \begin{aligned} y_1(feature, value) = \{y_i | x_i^{(feature)} \le value\} \\ y_2(feature, value) = \{y_i | y_i^{(feature)} \gt value\} \end{aligned}
  3. 计算y1y_1y2y_2的基尼指数之和

Gini(p)=Kpk(1pk)=1Kpk2 Gini(p) = \sum^K p_k(1-p_k) = 1 - \sum^Kp_k^2

  1. 选择基尼指数计算结果最小的(feature, value)作为当前的最优划分
  2. 基于最优划分生成2个子结点,将数据分配到两个子结点中
  3. 对子结点递归调用CART算法

2. 代码

def gini(y):
    ySet = set(y)
    ret, n = 1, y.shape[0]
    for yi in ySet:
        ret -= (y[y==yi].shape[0]/n)**2
    return ret

def CART(X, y):
    # 若D中所有实例属于同一类{% math %}C_k{% endmath %}
    if len(set(y))==1:
        # 将类{% math %}C_k{% endmath %}作为该结点的类标记
        return y[0]
    bestGini = np.inf
    # 对每个特征feature的每个取值value
    for feature in range(X.shape[1]):
        for value in set(X[:,feature]):
            # 将X分为{% math %}R_1{% endmath %}和{% math %}R_2{% endmath %}两个集合
            y1 = y[X[:,feature]<= value]
            y2 = y[X[:,feature]> value]
            # 计算{% math %}R_1{% endmath %}和{% math %}R_2{% endmath %}的基尼指数之和
            sumGini = gini(y1) + gini(y2)
            # 选择基尼指数计算结果最小的(feature, value)作为当前的最优划分
            if sumGini < bestGini:
                bestFeature, bestValue, bestGini = feature, value, sumGini
    # 基于最优划分生成2个子结点,将数据分配到两个子结点中
    node = {'feature':bestFeature,
            'value':bestValue,
            'left':CART(X[X[:,bestFeature]<= bestValue], y[X[:,bestFeature]<= bestValue]),
           'right':CART(X[X[:,bestFeature]> bestValue], y[X[:,bestFeature]> bestValue])}
    return node

results matching ""

    No results matching ""