声明: 本文仅为个人学习GBDT算法的记录,如有错误或不专业的地方请指教! 源码实现参考Github项目: GBDT_Simple_Tutorial
GBDT简介
GBDT的全称是 Gradient Boosting Decision Tree ,梯度提升决策树,它在普通决策树的基础上添加了梯度提升方法,从1颗决策树演变为多颗决策树,逐步提升学习精度。
网上有大量介绍GBDT的文章,大部分都是讲原理和推公式,公式推导是算法的精髓,自己亲自推导一遍,更有感觉。
但考虑到算法的复杂度,不妨先从源码实现的角度理解算法流程,再反过来理解公式推导,似乎效率更高,因此本文尝试通过实例一探GBDT算法的奥秘。
预测身高
已知4组包含年龄、体重、身高的数据,根据年龄、体重预测身高,训练数据如下:
id | age | weight | label |
1 | 5 | 20 | 1.1 |
2 | 7 | 30 | 1.3 |
3 | 21 | 70 | 1.7 |
4 | 30 | 60 | 1.8 |
测试数据如下:
id | age | weight | label |
5 | 25 | 65 | ? |
由于预测目标身高是一个 连续值 ,本题属于回归问题,如果预测目标是离散值(如性别,男 or 女)就是一个分类问题。
初始学习器
训练数据data有4个字段,id字段无意义,age、weight作为feature字段,label是标签值。
首先构造初始学习器f_0,取训练样本标签值的均值 = (1.1+1.3+1.7+1.8) / 4 = 1.475。 如下所示:
id | age | weight | label | f_0 |
1 | 5 | 20 | 1.1 | 1.475 |
2 | 7 | 30 | 1.3 | 1.475 |
3 | 21 | 70 | 1.7 | 1.475 |
4 | 30 | 60 | 1.8 | 1.475 |
学习器可以理解为预测结果,此处之所以取均值是公式推导得到的,后面给出推导链接~
初始学习器f_0将所有样本都预测为1.475,误差很大,需要调整。
训练 决策树
设定决策树数量为5,意味着要训练5颗决策树,也可以不设置数量上限,一直训练下去直到精度不再提升。
先构建第1颗决策树,首先计算每个样本的 残差 (residual), 残差 = 标签值 – 预测值 ,即 data[“res_1”] = data[“label”] – data[“f_0”],如下:
id | age | weight | label | f_0 | res_1 |
1 | 5 | 20 | 1.1 | 1.475 | -0.375 |
2 | 7 | 30 | 1.3 | 1.475 | -0.175 |
3 | 21 | 70 | 1.7 | 1.475 | 0.225 |
4 | 30 | 60 | 1.8 | 1.475 | 0.325 |
res_1列表示每个样本的预测残差,GBDT的目标就是 拟合残差 ,将 残差作为标签值 来构造决策树。
有age、weight两个特征可以训练,每个特征各有4个唯一值,共有8个特征值可以作为决策树的分支条件(决策树可以理解为多个if/else组成的分支判断)。
对8个特征值分别计算损失值,比如以 (‘age’, 7) 作为分支条件, age<7 的放入左分支(1个样本), age>=7 的放入右分支(3个样本),左右分支的损失计算方法为:
(1)计算分支包含节点的标签值(残差)的 均值
(2)(每个节点标签值-均值)的 平方和
左分支有1个节点,损失为0。 右分支有3个节点,均值=(-0.175+0.225+0.325)/3 = 0.125,差值的平方和=0.14。 总损失为0.14。
对8个特征值分别计算总损失,使用 总损失最小的特征值 作为分支条件,如下:
(‘—-划分特征:’, ‘age’)
划分值:5.000,左节点损失:0.000,右节点损失:0.327,总损失:0.327
划分值:7.000,左节点损失:0.000,右节点损失:0.140,总损失:0.140
划分值:21.000,左节点损失:0.020,右节点损失:0.005,总损失:0.025
划分值:30.000,左节点损失:0.187,右节点损失:0.000,总损失:0.187
(‘—-划分特征:’, ‘weight’)
划分值:20.000,左节点损失:0.000,右节点损失:0.327,总损失:0.327
划分值:30.000,左节点损失:0.000,右节点损失:0.140,总损失:0.140
划分值:70.000,左节点损失:0.260,右节点损失:0.000,总损失:0.260
划分值:60.000,左节点损失:0.020,右节点损失:0.005,总损失:0.025
(‘–最佳划分特征:’, ‘age’)
(‘–最佳划分值:’, 21)
创建根结点,使用特征值age=21作为分支条件,将样本1、2放入左子节点,样本3、4放入右子节点。
根据二叉树的递归特性,可以对子节点继续添加分支条件。 本文为便于描述,设置树的最大层数为2,因此每个叶子节点包含2个样本,如下:
每个叶子节点的 预测值 =包含样本的标签值的均值。
比如左叶子的预测值= (-0.375 – 0.175) / 2 = -0.275,右叶子的预测值 = (0.225 + 0.325) / 2 = 0.275。 训练好的决策树包含 分支条件、叶子节点的预测值以及关联的样本索引 。
更新学习器
训练好一颗决策树后,可以在上个学习器的基础上得到一个新学习器,计算公式为:
data[“f_1”] = data[“f_0”] + 学习率 * 叶子节点预测值
其中data[“f_0”]表示初始学习器,data[“f_1”]表示基于第一颗决策树的新学习器,学习率用于减缓学习速度,可设为0.1。
更新流程为:
遍历当前决策树的所有叶子节点
获取每个叶子节点的预测值、关联的样本索引
对每个关联的样本更新学习器
比如左叶子的预测值为-0.275,关联样本1和2, 则 样本1、2的 f_1 = 1.475 + 0.1 * -0.275 = 1.4475。
右叶子的预测值为0.275,关联样本3和4, 则样本3、4的 f_1 = 1.475 + 0.1 * 0.275 = 1.5025。
id | label | f_0 | res_1 | f_1 |
1 | 1.1 | 1.475 | -0.375 | 1.4475 |
2 | 1.3 | 1.475 | -0.175 | 1.4475 |
3 | 1.7 | 1.475 | 0.225 | 1.5025 |
4 | 1.8 | 1.475 | 0.325 | 1.5025 |
得到新的学习器f_1后,再次计算每个样本的残差, data[“res_2”] = data[“label”] – data[“f_1”] ,创建第2颗决策树对残差 res_2 进行拟合。
得到第2颗决策树后,再更新学习器 f_2, 反复训练5颗决策树 后,训练结束。
5颗决策树如下:
训练样本的n个学习器如下:
id | label | f_0 | f_1 | f_2 | f_3 | f_4 | f_5 |
1 | 1.1 | 1.475 | … | … | … | … | 1.362 |
2 | 1.3 | 1.475 | … | … | … | … | 1.362 |
3 | 1.7 | 1.475 | … | … | … | … | 1.587 |
4 | 1.8 | 1.475 | … | … | … | … | 1.587 |
f_5是基于5颗决策树的最终预测结果, 根据学习器的计算公式:
data[“f_1”] = data[“f_0”] + 学习率 * 叶子节点预测值
……
data[“f_5”] = data[“f_4”] + 学习率 * 叶子节点预测值
提供 初始学习器f_0 ,以及 5颗决策树的信息 ,可以得到f_5的值,实现新数据预测。
预测
测试数据为:
id | age | weight | label |
5 | 25 | 65 | ? |
根据age=25,获取每棵树对应叶子节点的 预测值 ,如下:
决策树编号 | 叶子节点预测值 |
1 | 0.275 |
2 | 0.2475 |
3 | 0.2227 |
4 | 0.2005 |
5 | 0.1804 |
预测值 = 1.475 + 0.1 * (0.275 + 0.2475 + 0.2227 + 0.2005 + 0.1804) = 1.587。
总结
(1)GBDT为梯度提升决策树,是在提升树的基础上实现梯度提升。 提升树以 拟合残差 为目标,GBDT用损失函数的负梯度作为提升树残差的近似值。 用平方损失函数作为GBDT的损失函数时, 平方损失函数的负梯度等于残差值 。
部分公式推导参考csdn博客,链接:
https://blog.csdn.net/lgh1700/article/details/100074370
(2) 机器学习算法一般涉及到 大量的数据处理,需要一定的耐心和 思考才能理清头绪 。 本文仅介绍GBDT回归算法的实现,分类算法与之稍有差异,总体流程是一致的。
Be First to Comment