梯度提升树（GBDT）的问题思考

小咪咪 2021-12-12 10:41 283阅读 0赞

### 前言 ###

提升树很多地方都没有详细讲解，所以我学的过程中有一些疑惑，这里把一些问题说清楚，了解清楚，希望让自己和他们都能熟悉。

#### 问题:分割点如何确定 ####

《统计学习方法》这本书中并没有详细讲解这个问题，但似乎默认就是穷举，我上网查了一些资料，有一些说法：

*  1、基本的查找分割点的穷举算法  
    这样的算法又被称为精确贪婪算法，在计算分割点的过程中，它会去查找进入当前分支的每一个样本的每一个特征值，计算它们的增益，其实就是穷举，利用每个分割点来计算增益，增益最小的就作为真正的切割点，这样计算量会特别大，如果你的样本有100万，就要计算100万次，似乎有点疯狂，sklearn和单机版xgboost都支持这种算法。不过这种算法要求在一开始的时候先把所有样本按照特征值排好序，并计算好它们的一阶导数和二阶导数，这样才能快速地计算增益，选定分割的候选节点。
 *  2、效率极高的分位点算法  
    以上算法在其他基于决策树的算法中是常用的，但是这样做的结果就是运算量极大，即使在xgboost中通过率先排序及计算梯度向量，在实施过程中的计算量仍旧非常大，尤其是样本量足够大的时候，因此xgboost中使用的是基于Weighted Quantile Sketch分位点算法。xgboost所使用的分位点算法，其核心思想是根据特征的分布取其分位点，这些分位点将作为分割点将整个特征区间划分为多个段，所有特征值将进入对应分段，由分位点代替其真实特征值，其本质就是连续特征的分段离散，随后获取梯度向量，找出最佳分割点。这个分位点算法要讲解清楚估计能写好几篇博客，大家就先了解一下，本文不做详述。

#### 问题: 划分区域问题 ####

在GBDT算法公式中，有很多的划分区域，当时很诧异，因为在《统计学习方法》书中举例说明了这个算法，在这个例子中生成的决策树就两层树，一层是根节点，一层是两个子树，并没有继续延伸下去，所以我一开始以为只生成两棵树，这跟算法公式中并不相同，后面咨询了刘建平老师，他给的解释就是这不是只有两层树结构的决策树，而是多层，这样的话，样本就被划分为多个区域，每一个区域都有一个预测值，这也符合算法公式。

#### 问题:预测值如何确定 ####

在确定分割点的时候要计算误差，回归算法里用平方误差，分类算法里直接判断，计算误差首先要清楚我们确定一个分割点的时候，就相当于把样本分成了两个部分，每个部分就是一个分支，每个分支都有一个预测值，这个预测值是如何得到的呢？

*  回归算法  
    回归算法中可以求分支上样本标签的平均值。
 *  分类算法  
    分类更回归一样的流程，可以把暑促

#### 问题: 多分类的问题 ####

首先我们假设我们的问题有k个分类情况，多分类问题的解决可以有两种方式：

*  1、把一个分类拎出来，其他分类作为该分类的反面，这样就要计算k个GBDT算法模型。
 *  2、有多分类问题的GBDT算法，其中计算除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。这个可以去参考[梯度提升树(GBDT)原理小结][GBDT]。

#### 损失函数 ####

分类和回归用到的损失函数不太一样，区分主要有：

*  1、分类问题的损失函数  
    （1）、指数损失函数，表达式为  
     L ( y , f ( x ) ) = e x p ( − y f ( x ) ) L(y,f(x))=exp(-yf(x)) L(y,f(x))=exp(−yf(x))  
    （2）、对数损失函数，分为二元分类和多元分类两种：  
    二分类为 L ( y , f ( x ) ) = l o g ( 1 + e x p ( − y f ( x ) ) ) L(y,f(x))=log(1+exp(-yf(x))) L(y,f(x))=log(1\+exp(−yf(x)))  
    多分类为  
     L ( y , f ( x ) ) = − ∑ k = 1 K y k ∗ l o g ( p k ( x ) ) p k ( x ) = e x p ( f k ( x ) ) ∑ l = 1 K e x p ( f l ( x ) ) L(y,f(x))=-\\sum\_\{k=1\}^\{K\}y\_k\*log(pk(x))\\\\ pk(x)=\\frac\{exp(f\_k(x))\}\{\\sum\_\{l=1\}^\{K\}exp(f\_l(x))\} L(y,f(x))=−k=1∑Kyk∗log(pk(x))pk(x)=∑l=1Kexp(fl(x))exp(fk(x))
 *  2、回归问题的损失函数  
    （1）、均方差回归损失函数，表达式为： L ( y , f ( x ) ) = ( y − f ( x ) ) 2 L(y,f(x))=(y-f(x))^2 L(y,f(x))=(y−f(x))2  
    （2）、绝对损失函数 L ( y , f ( x ) ) = ∣ y − f ( x ) ∣ L(y,f(x))=|y-f(x)| L(y,f(x))=∣y−f(x)∣  
    对应的梯度误差为： s i g n ( y i − f ( x i ) ) sign(y\_i-f(x\_i)) sign(yi−f(xi))  
    （3）、Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下：  
    （4）、分位数损失。它对应的是分位数回归的损失函数，表达式为：  
     L ( y , f ( x ) ) = ∑ y > = f ( x ) θ ∣ y − f ( x ) ∣ + ∑ y < f ( x ) ( 1 − θ ) ∣ y − f ( x ) ∣ L(y,f(x))=\\sum\_\{y>=f(x)\}\\theta|y-f(x)|+\\sum\_\{y<f(x)\}(1-\\theta)|y-f(x)| L(y,f(x))=y>=f(x)∑θ∣y−f(x)∣\+y<f(x)∑(1−θ)∣y−f(x)∣  
    其中 θ \\theta θ为分位数，需要我们在回归前指定。对应的负梯度误差为：  
     r ( y i , f ( x i ) ) = \{ θ y > = f ( x ) 1 − θ y < f ( x ) r(y\_i,f(x\_i)) =\\left\\\{ \\begin\{aligned\} \\theta &&y>=f(x) \\\\ 1-\\theta && y<f(x) \\end\{aligned\} \\right. r(yi,f(xi))=\{ θ1−θy>=f(x)y<f(x)

### 参考博客 ###

[XGBoost中分位点算法快速查找分割点  
][XGBoost_]  
[梯度提升树(GBDT)原理小结][GBDT]

[GBDT]: https://www.cnblogs.com/pinard/p/6140514.html#!comments
[XGBoost_]: https://blog.csdn.net/weixin_39750084/article/details/83216127