墨滴

仰止

V1

2022/12/08阅读：22主题：默认主题

GBDT学习笔记

GBDT在业界是经常使用的一个算法，面试也经常会问到些八股，不过我做NLP，所以感觉被问的还不算多，但考虑到自己对这个算法的各种原理理解的不够深入，所以还是决定做一下相关的笔记。

结构原理

首先，GBDT的全称为梯度提升决策树，显然这里的boosting（提升）就是我们所熟悉的模型集成的一个思想，另外RF（随机森林）使用的是bagging的集成思想。

GBDT的base model为CART树（卡特树），也就是说GBDT就是CART树经过boosting集成的方式得到的一个集成算法。

1、决策树介绍

这里先对几个决策树进行介绍，常见的决策树有：

  • ID3决策树
  • C4.5决策树
  • CART树

ID3

它们之间最大的不同就是以什么指标来进行特征选择，其中ID3以信息增益来进行特征选择。特征A对训练集D的信息增益G(D,A)，定义为集合D的信息熵H(D)，与特征A给定条件下D的条件熵H(D|A)之差。

ID3的缺点：

  • 偏向于取值较多的特征
  • 对训练样本的质量的依赖性强

C4.5

特征选择标准为：信息增益比

n表示特征A的取值个数，C4.5的缺点：

  • 偏向于取值较少的特征
  • 分而治之，局部最优

CART

全称为分类与回归树

分类：输出离散值，以基尼系数作为特征选择的指标

回归：输出是连续值，以平方误差作为特征选择的指标

GBDT中用的是回归树，下面看看CART树的伪代码：

输入：训练数据集D={( , ),...,( , )}，其中Y是连续变量

输出：提升树f(x)

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉树：

（1）选择最优切分变量j与切分点s，求解

遍历变量j，对固定的切分变量j扫描切分点s，选择使达到最小值的(j,s)对

（2）用选定对(j,s)划分区域并决定相应的输出值：

，

（3）继续对两个子区域调用步骤（1）（2），直到满足停止条件

（4）将输入空间划分为M个区域 ,..., ，生成决策树

表示指示函数，当 时，I=1；否则为0

2、GBDT相关介绍

GBDT的算法计算流程如下：

（1）初始化弱学习器

（2）对m=1,2,...,M，进行如下操作：

  • 对每个样本计算负梯度，（当损失函数为mse时，也被称作残差）

  • 将得到的负梯度作为样本新的真实值，并将数据( , ),i=1,2,...,N作为下棵树的训练数据，得到一棵新的回归树 ，其对应的叶子节点区域为 ，j=1,2,...,J，其中J为回归树的叶子节点个数

  • 对叶子区域j=1,2,...,J计算最佳拟合值

  • 更新弱学习器

  • 得到最终的学习器

需要注意的是，GBDT拟合的是负梯度，当损失函数为mse时，负梯度的计算结果与残差的计算结果相等，此时拟合残差才成立

码一个关于GBDT的ppt：

http://www.ccs.neu.edu/home/vip/teach/MLcourse/4_boosting/slides/gradient_boosting.pdf

如何使用

对于GBDT已经被sklearn封装好了，如果只是掉包的话，可以通过下面实现： 

from sklearn.ensemble import GradientBoostingRegressor
estimator=GradientBoostingRegressor(random_state=10)

关于GBDT的源码，在网上也可以搜到很多，总体的实现也就是一个定义、训练和预测三个部分，定义的话根据n_estimators定义多个CART树，训练过程中对负梯度进行拟合就可以了。

假设我们已经实现了CART树的定义，在此基础上实现GBDT

from CARTRegression import CARTRegression
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np

class GBDT:
  def __init__(self,n_estimators=3):
    self.trees=[]
    self.n_estimators=n_estimators
  
  def fit(self,x,y):
    residual=y
    for i in range(self.n_estimators):
      model=CARTRegression()
      model.fit(x,residual)
      self.trees.append(model)
      pred=model.predict(x)
      residual-=pred
  
  def predict(self,x):
    y=np.zeros(x.shape[0])
    for model in self.trees:
      new_pred=np.array(model.predict(x))
      y+=new_pred
    return y
  
def MSE(pred,true):
  r=0
  for i in range(len(pred)):
    r+=(pred[i]-true[i])**2
  return r

代码参考：

CART部分： https://github.com/lipengyuer/DataScience/blob/master/src/algoritm/CARTRegression.py

GBDT部分 https://github.com/lipengyuer/DataScience/blob/master/src/algoritm/GBDTRegression.py

3、GBDT的剪枝

关于GBDT的剪枝自己没有尝试过，不过在平时做算法题时，使用递归时通常会使用剪枝的操作，代码实现原理应该是相同的

决策树剪枝一般是为了提升模型的泛化能力，有预剪枝和后剪枝两种

预剪枝

在生成决策树的过程中，计算当前划分是否能带来模型泛化能力的提升，如果不能则停止树的生长。判断方式如下：

  • 当树达到一定深度时，停止树的生长
  • 当到达当前节点的样本数量小于某个阈值时
  • 计算每次分裂在验证集的效果，当小于某个阈值时，停止

后剪枝

先生成决策树，然后从最底层向上计算是否需要剪枝。剪枝的过程是将子树删除，用一个叶子节点替代，后剪枝也可以通过在验证集上的准确率进行判断，如果剪枝后准确率有所提升，则剪枝。

相比于预剪枝，后剪枝的泛化能力更强，但是时间开销更大

后剪枝方法：

  • 错误率剪枝
  • 悲观剪枝
  • 代价复杂度剪枝
  • 最小误差剪枝
  • CVP/OPP

相关总结

GBDT在面试中常问到的有：boosting的集成方式、拟合目标以及与其他树模型的一些对比，如RF、XGB等

分类：

人工智能

标签：

机器学习

作者介绍

仰止
V1