GBDT

GBDT，全称Gradient Boosting Decision Tree。

CART

在GBDT中使用的回归树模型为CART。其算法为

[1]对于每个节点处，当前数据集为 $D=\\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\\}$ ，对于每个特征 $j$ ，寻找最优划分节点 $s$ ，使得据此可将 $D$ 划分为 $R_1$ 和 $R_2$ ，满足
$\\min\\limits_{j,s}[\\sum\\limits_{x_i\\in{R_1}}(y_i-c_1)^2+\\sum\\limits_{x_i\\in{R_2}}(y_i-c_2)^2]$
其中
$c_1=\\frac{1}{N_1}\\sum\\limits_{x_i\\in{R_1}}y_i$
$c_2=\\frac{1}{N_2}\\sum\\limits_{x_i\\in{R_2}}y_i$

[2]对于每棵划分出来的子树，递归进行操作[1]，直到满足停止条件。
[3]返回树T。

另外，若是分类树，则其划分依据为最小基尼指数
$Gini(D,A)=\\frac{|D_1|}{|D|}Gini(D_1)+\\frac{|D_2|}{|D|}Gini(D_2)$
当样本数少于既定阈值或样本Gini指数小于既定基尼指数或没有更多特征时则停止划分。这里不详述。
下面讲述剪枝过程。

[1]设 $k=0$ ， $T=T_0$ ， $a=+\\infty$
[2]自下而上对内部节点 $t$ 计算：
$g(t)=\\frac{C_t-C(T_t)}{|T_t|-1}$
$a=min(a,g(t))$
[3]自上而下的访问内部节点 $t$ ，对最小的 $g(t)=a$ 进行剪枝，并对叶节点 $t$ 以多数表决形式决定其类别，得到树 $T$
[4] $k=k+1$ ， $a_k=a$ ， $T_k=T$
[5]如果 $T$ 为非单节点树，返回[3]
[6]对于产生的子树序列 $\\{T_0,T_1,...,T_n\\}$ 分别计算损失，得到最优子树 $T^*$ 并返回。

梯度提升

GBDT作为boosting类模型中的一种，采用迭代的方式对学习器进行优化。假设前一轮迭代得到强学习器 $f_{t-1}(x)$ ，损失函数为 $L(y,f_{t-1}(x))$ ，则本轮迭代目标为寻找CART回归树模型的弱学习器 $h_t(x)$ ，使得本轮损失 $L(y,f_t(x)=f_{t-1}(x)+h_t(x))$