Press "Enter" to skip to content

GBDT算法实例分析

声明: 本文仅为个人学习GBDT算法的记录,如有错误或不专业的地方请指教! 源码实现参考Github项目: GBDT_Simple_Tutorial

 

GBDT简介

 

GBDT的全称是 Gradient Boosting Decision Tree ,梯度提升决策树,它在普通决策树的基础上添加了梯度提升方法,从1颗决策树演变为多颗决策树,逐步提升学习精度。

 

网上有大量介绍GBDT的文章,大部分都是讲原理和推公式,公式推导是算法的精髓,自己亲自推导一遍,更有感觉。

 

但考虑到算法的复杂度,不妨先从源码实现的角度理解算法流程,再反过来理解公式推导,似乎效率更高,因此本文尝试通过实例一探GBDT算法的奥秘。

 

预测身高

 

已知4组包含年龄、体重、身高的数据,根据年龄、体重预测身高,训练数据如下:

 

 

id age weight label
15201.1
27301.3
321701.7
430601.8

 

测试数据如下:

 

 

id age weight label
52565?

 

由于预测目标身高是一个 连续值 ,本题属于回归问题,如果预测目标是离散值(如性别,男 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
15201.11.475
27301.31.475
321701.71.475
430601.81.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
15201.11.475-0.375
27301.31.475-0.175
321701.71.4750.225
430601.81.4750.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
11.11.475-0.3751.4475
21.31.475-0.1751.4475
31.71.4750.2251.5025
41.81.4750.3251.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
11.11.4751.362
21.31.4751.362
31.71.4751.587
41.81.4751.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
52565?

 

根据age=25,获取每棵树对应叶子节点的 预测值 ,如下:

决策树编号 叶子节点预测值
10.275
20.2475
30.2227
40.2005
50.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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注