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

前言

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

问题:分割点如何确定

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

• 1、基本的查找分割点的穷举算法
  这样的算法又被称为精确贪婪算法，在计算分割点的过程中，它会去查找进入当前分支的每一个样本的每一个特征值，计算它们的增益，其实就是穷举，利用每个分割点来计算增益，增益最小的就作为真正的切割点，这样计算量会特别大，如果你的样本有100万，就要计算100万次，似乎有点疯狂，sklearn和单机版xgboost都支持这种算法。不过这种算法要求在一开始的时候先把所有样本按照特征值排好序，并计算好它们的一阶导数和二阶导数，这样才能快速地计算增益，选定分割的候选节点。

• 2、效率极高的分位点算法
  以上算法在其他基于决策树的算法中是常用的，但是这样做的结果就是运算量极大，即使在xgboost中通过率先排序及计算梯度向量，在实施过程中的计算量仍旧非常大，尤其是样本量足够大的时候，因此xgboost中使用的是基于Weighted Quantile Sketch分位点算法。xgboost所使用的分位点算法，其核心思想是根据特征的分布取其分位点，这些分位点将作为分割点将整个特征区间划分为多个段，所有特征值将进入对应分段，由分位点代替其真实特征值，其本质就是连续特征的分段离散，随后获取梯度向量，找出最佳分割点。这个分位点算法要讲解清楚估计能写好几篇博客，大家就先了解一下，本文不做详述。

问题: 划分区域问题

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

问题:预测值如何确定

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

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

问题: 多分类的问题

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

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

损失函数

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

• 1、分类问题的损失函数
  （1）、指数损失函数，表达式为
  $$L(y,f(x))=exp(?yf(x))$$
  （2）、对数损失函数，分为二元分类和多元分类两种：
  二分类为$$L(y,f(x))=log(1+exp(?yf(x)))$$
  多分类为
  $$\begin{gathered} 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))} \end{gathered}$$
• 2、回归问题的损失函数
  （1）、均方差回归损失函数，表达式为：$$L(y,f(x))=(y?f(x){)}^2$$
  （2）、绝对损失函数$$L(y,f(x))=|y?f(x)|$$
  对应的梯度误差为：$$sign(y_i?f(x_i))$$
  （3）、Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下：
  （4）、分位数损失。它对应的是分位数回归的损失函数，表达式为：
  $$L(y,f(x))=\sum _{y>=f(x)}\theta |y?f(x)|+\sum _{y<f(x)}(1?\theta )|y?f(x)|$$
  其中$\theta$为分位数，需要我们在回归前指定。对应的负梯度误差为：
  $$r(y_i,f(x_i))=\{\begin{array}{rlr}\theta & & y>=f(x)\\ 1?\theta & & y<f(x)\end{array}$$

参考博客

XGBoost中分位点算法快速查找分割点

梯度提升树(GBDT)原理小结