【 GBDT算法】机器学习实例推导计算+公式详细过程（入门必备）

CV_William

14063人浏览 · 2018-12-17 00:12:52

CV_William · 2018-12-17 00:12:52 发布

机器学习【 GBDT算法】

知识准备：
arg 是变元（即自变量argument）的英文缩写。
arg min 就是使后面这个式子达到最小值时的变量的取值
arg max 就是使后面这个式子达到最大值时的变量的取值
例如函数F(x,y):
arg min F(x,y)就是指当F(x,y)取得最小值时，变量x,y的取值
arg max F(x,y)就是指当F(x,y)取得最大值时，变量x,y的取值

一．GBDT概念：

GBDT(Gradient Boosting Decision Tree) 又叫 MART （Multiple Additive Regression Tree)，是一种迭代的决策树算法。由多棵决策树组成，最后把所有树的结论累加起来做决策。它是一个泛化能力较强的算法。GBDT里有三个概念：分别是Regression Decistion Tree、Gradient Boosting、Shrinkage。

1． GB–Gradient Boosting 梯度提升树：

（1）错误思想：求均值就是GBDT。

用三颗决策树预测一个人身高时，决策棵1预测为是1.7米，决策树2预测是1.75米，决策树3预测是1.8米。然后1.7 + 1.75 + 1.8 求均值，这样是不对的。因为只要训练集不变，独立训练三次的三棵树必定完全相同，这样做完全没有意义的。

（2）正确思想：把所有树的结论累加起来做决策

我们在用GBDT做预测的时候，每棵树的数值不是身高的实际数值，而是一个残差值，将残差值累加才是真实身高=。每一棵树学的是之前所有树的残差，这个残差累加后能得到真实值。
例如一个人的身高是1.8米，决策树1预测为1.1米，1.8 - 1.1 = 0.7，那么残差为0.7米。然后决策树2将0.7米拿去训练学习，如果决策树2能把年龄分到0.7米的叶子节点，那累加两棵树的结果：1.1 + 0.7 = 1.8米就是实际身高；如果决策树2的结果是0.5米，那么决策树2将0.5米拿去训练学习，0.7 - 0.5 = 0.2，则还存在0.2米的残差，决策树3继续学。这就是Gradient Boosting的核心思想。

2．DT–Regression Decistion Tree中的树一般是回归树：

我们都知道，决策树可以用于回归和分类。回归树用于预测实数值，用户的身高，体重，年龄，爱好，所在地的天气，湿度，温度，是否有风。分类树用于分类标签值，如气温高，低，适中、用户性别，学历，工作类型。数值相加减是有意义的，1米 + 1.5米 + 1.7米 = 3.2米，标签值相加减是无意义的，如男+男+女=到底是男是女？ GBDT的核心在于累加所有树的结果作为最终结果。虽然调整后也可用于分类，但不代表GBDT的树是分类树。

3、Shrinkage–缩减，循序渐进：

Shrinkage的思想强调的是循序渐进，就好比不能一口吃出一个胖子。每次迭代只走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。

二、算法流程：

1.模型

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree)。提升树模型可以表示为决策树的加法模型：在这里插入图片描述
其中，表示决策树；为决策树的参数；M为树的个数

2.学习过程

回归问题提升树使用以下前向分布算法：
在这里插入图片描述
在前向分布算法的第m步，给定当前模型，需求解

得到，即第m棵树的参数

当采用平方误差损失函数，在这里插入图片描述

其损失变为：在这里插入图片描述
其中,是当前模型拟合数据的残差（residual）。对于平方损失函数，拟合的就是残差；对于一般损失函数（梯度下降），拟合的就是残差的近似值

3.算法

输入：训练数据集在这里插入图片描述
输出：提升树
算法流程：
（1）初始化
（2）对m = 1,2,…，M

1.计算残差在这里插入图片描述

2.拟合残差学习一个回归树，得到在这里插入图片描述
3.更新
4.得到回归问题提升树

在这里插入图片描述

三、实例详解：

如下表所示：一组数据，特征为年龄、体重，身高为标签值。共有5条数据，前四条为训练样本，最后一条为要预测的样本。
　　在这里插入图片描述

1.初始化弱学习器:

在这里插入图片描述
　　求导：

所以初始化时，r取值为所有训练样本标签值的均值。r=(1.1+1.3+1.7+1.8)/4=1.475，此时得到初始学习器在这里插入图片描述

2.对迭代轮数m=1:

计算负梯度——残差
　　在这里插入图片描述

残差在下表列出：
初始化在这里插入图片描述： r
残差：真实值 - r

此时将残差作为样本的真实值训练f1(x)，即下表数据
在这里插入图片描述
接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征的5开始，到体重特征的70结束，分别计算方差，找到使方差最小的那个划分节点即为最佳划分节点。

以上划分点是的总方差最小为0.0125有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选年龄21。
此时还需要做一件事情，给这两个叶子节点分别赋一个参数，来拟合残差。
在这里插入图片描述
这里其实和上面初始化学习器是一个道理，平方损失，求导，令导数等于零，化简之后得到每个叶子节点的参数r，其实就是标签值的均值。
根据上述划分节点：
样本1，2为左叶子节点，(x1,x2∈R11)，所以r11=(−0.375−0.175)/2=−0.275
样本3，4为右叶子节点，(x3,x4∈R21)，所以r21=(0.225+0.325)/2=0.275
此时可更新强学习器：
在这里插入图片描述
当年龄 < 21岁时，f1 = 1.475 + (-0.275) = 1.2
当年龄 > 21岁时，f1 = 1.475 + 0.275 = 1.75

3.对迭代轮数m=2,3,4,5,…,M:

循环迭代M次，M是人为控制的参数，迭代结束生成M棵树

4.得到最后的强学习器（回归提升树）：

为了方别展示和理解，我们假设Ｍ＝１，根据上述结果得到强学习器：
在这里插入图片描述
如图所示得到只迭代一次，只有一颗树的GBDT：

此时可更新强学习器：
f1 = 1.475 + (-0.275) = 1.2
f1 = 1.475 + 0.275 = 1.75

5.预测样本：

样本在根节点中（即初始学习器）被预测为1.475，样本的年龄为25，大于划分节点21岁，所以被分到了右边的叶子节点，同时被预测为0.275。此时便得到样本的最总预测值为1.75。

四、流程总结：

1.初始化残差，构成弱学习器1。（预测特征所对应得特征值求平均值）

2.计算残差（实际值 - 弱学习器1）。

3.寻找回归树的最佳划分点（阈值）。遍历每个特征的每个特征值作为阈值，通过阈值将数据二分，分别计算方差，找到使方差最小的特征值为最佳二分阈值

4.将二分后的残差值更新为实际值，计算实际值平均值作为残差。构成弱学习器2。

5.合并强学习器。（弱学习器1 + 弱学习器2）

6.满足条件迭代停止。

五、GBDT分析总结：

1.GBDT梯度提升树，就是不断减小残差，不断提高模型效果的优化过程。

2.残差分析，残差越小，方差越小，数据离散化程度越小，那么数据更加趋向一类，从而数据预测更加准确。

3.所谓残差就是boost思想中，关注的那一部分没有分对的数据，然后增加权重，给下一个弱分类器重点关注。所以减小残差就是减小代价。残差趋向于0，就是代价降到最小。

六、公式推导

GBDT梯度提升树算法流程

初始化模型
拟合负梯度，得到每一轮的基学习器。
把所有基学习器叠加，最终得到模型。

$\sum_{i=1} ^ m T(X;\theta_i) \quad$

GBDT损失函数,拟合负梯度

$\gamma_{im} = -[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f = f_{i - 1}} \quad$

平方损失函数

$L(y_i, f(x_i)) = \frac{1}{2}(y_i - f(x_i))^2 \quad$

负梯度的值
$y_i - f_{i - 1}(x_i) \quad$
初始化损失
$f_0(x_i) = \overline{y} \quad$

GBDT分类任务

初始化加法模型

$f_0(x_i) = log(\frac{正样本个数}{负样本个数}) \quad$

log损失函数

$L(y_i, f(x_i)) = y_i log(p_i) + (1 - y_i) log(1 - p_i) \quad$

$p_i = \frac{1}{1 + e^{-f(x_i)}} \quad$

负梯度值

$y_i - \frac{1}{1 + e^{- f_{i - 1} (x_i)}} \quad$

AdaBoost分类

input：训练集：弱学习器为M个
output：最终的强学习器 $G (x)$

${(x_1, y_1), (x_2, y_2), (x_3, y_3), …, (x_n, y_n)}, y \in {-1, +1} \quad$

1.初始化样本权重

$D_1 = (w_{11}, w_{12},w_{13}, …, w_{1N}) w_{1i} = \frac{1}{N}, i = 1, 2, 3, …, N \quad$

2.对于 $m = 1, 2, 3, \dots, M$

(1)使用具有权值分布 $D_m$ 的训练数据训练模型，得到弱学习器 $G_m (x)$

(2)计算 $G_m (x)$ 的分类误差率

$e_m = \sum_{i=1} ^ N w_{mi} I(G_m (x_i) \not= y_i) \quad$

(3)计算弱学习器的系数

$\alpha_m = \frac{1}{2} log \frac{1 - e_m}{e_m} \quad$

(4)更新训练集的权值

$D_{m + 1} = (w_{m + 1, 1}, …, w_{m + 1, i}, …, w_{m + 1, N}) \quad$

$w_{m + 1, i} = \frac{w_{mi}}{Z_m} exp(-\alpha_m y_i G_m(x_i)), i = 1, 2, 3, …,N \quad$

上式中， $Z_m$ 是规范因子

$Z_m = \sum_{i=1} ^ N w_{mi} exp(-\alpha_m y_i G_m(x_i)) \quad$

3.构建线性组合基分类器

$\sum_{m=1} ^ M \alpha_m G_m (x) \quad$

4.得到强分类器

$sign[\sum_{m=1} ^ M \alpha_m G_m (x)]$

AdaBoost回归

input：训练集：弱学习器为M个
output：最终的强学习器 $G (x)$

${(x_1, y_1), (x_2, y_2), (x_3, y_3), …, (x_n, y_n)}, y \in R \quad$

1.初始化样本权重

$D_1 = (w_{11}, w_{12},w_{13}, …, w_{1N}) w_{1i} = \frac{1}{N}, i = 1, 2, 3, …, N \quad$

2.对于 $m = 1, 2, 3, \dots, M$

(1)使用具有权值分布 $D_m$ 的训练数据训练模型，得到弱学习器 $G_m (x)$

(2)计算$ G_m (x) $的回归误差率

$e_m = \sum_{i=1} ^ N w_{mi} \frac{(y_i - G_m)^2}{E{2}_m} \quad$

上式中
$Em=max∣yi−Gm∣,i=1,2,3,…,NE_m = max |y_i - G_m|, i = 1, 2, 3, …, N \quad$

(3)计算若学习器的系数 $αm\alpha_m$

$\alpha_m = \frac{e_m}{1 - e_m} \quad$

(4)更新训练集的权值

$w_{m + 1, i} = \frac{w_{mi}}{Z_m} \alpha^{1 - e_{mi}}_m \quad$

上式中， $Z_m$ 是规范因子

$Z_m = \sum_{i=1} ^ N w_{mi} \alpha^{1 - e_{mi}}_m \quad$

4.得到强分类器

$\sum_{m=1} ^ M (ln(\frac{1}{a_m})) g(x) = [\sum_{m=1} ^ M (ln(\frac{1}{a_m}))] g(x) \quad$

上式中 $g (x)$ 是所有 $αmGm(x),m=1,2,3,…,M\alpha_m G_m(x), m = 1, 2, 3,…, M$ 的中位数

欢迎大家交流学习，任何问题都可以留言

参考资料：

https://blog.csdn.net/molu_chase/article/details/78111148
https://blog.csdn.net/google19890102/article/details/51746402
https://blog.csdn.net/a819825294/article/details/51188740
http://blog.csdn.net/zpalyq110/article/details/79527653

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐