GBDT

### 决策树的分类
决策树分为两大类，分类树和回归树
- 分类树用于分类标签值，如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面；
- 回归树用于预测实数值，如明天的温度、用户的年龄、网页的相关程度；

两者的区别：
- 分类树的结果不能进行加减运算，晴天 晴天没有实际意义；
- 回归树的结果是预测一个数值，可以进行加减运算，例如 20 岁 3 岁=23 岁。
- GBDT 中的决策树是回归树，预测结果是一个数值，在点击率预测方面常用 GBDT，例如用户点击某个内容的概率。

> GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。

> 对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

### GBDT 概念
GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升决策树。

要理解 GBDT，首先就要理解这个 B(Boosting)
>Boosting 是一族可将弱学习器提升为强学习器的算法，属于集成学习（ensemble learning）的范畴。Boosting 方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断要好。通俗地说，就是"三个臭皮匠顶个诸葛亮"的道理。

基于梯度提升算法的学习器叫做 GBM(Gradient Boosting Machine)。理论上，GBM 可以选择各种不同的学习算法作为基学习器。GBDT 实际上是 GBM 的一种情况。

为什么梯度提升方法倾向于选择决策树作为基学习器呢？(也就是 GB 为什么要和 DT 结合，形成 GBDT) 决策树可以认为是 if-then 规则的集合，易于理解，可解释性强，预测速度快。同时，决策树算法相比于其他的算法需要更少的特征工程，比如可以不用做特征标准化，可以很好的处理字段缺失的数据，也可以不用关心特征间是否相互依赖等。决策树能够自动组合多个特征。

不过，单独使用决策树算法时，有容易过拟合缺点。所幸的是，通过各种方法，抑制决策树的复杂性，降低单颗决策树的拟合能力，再通过梯度提升的方法集成多个决策树，最终能够很好的解决过拟合的问题。由此可见，梯度提升方法和决策树学习算法可以互相取长补短，是一对完美的搭档。

至于抑制单颗决策树的复杂度的方法有很多，比如限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量、吸收 bagging 的思想对训练样本采样（subsample），在学习单颗决策树时只使用一部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样一部分特征、在目标函数中添加正则项惩罚复杂的树结构等。

### 提升树Boosting Tree
梯度提升树(GBDT)是提升树的一种改进，我们先介绍一下提升树。
> 在提升树模型中，每棵树拟合的都是残差，所有树对于某一个样本的预测结果的累加值应该趋近于真实值。

### 梯度提升树(GBDT)原理
> GBDT的改变在于，它不再是拟合残差，而是拟合损失函数的负梯度值

拟合残差比较好理解，但是拟合负梯度值怎么理解呢？
我的理解是，梯度值也能反映出残差，残差越大，梯度值越大，残差越小，梯度值也越小。

实际上也类似于梯度下降的方法，即便前进的幅度没有可解释性，但是只要我前进的方向和幅度没有问题，就可以得出最后的结果。(前进幅度没有问题，指的是相差较大时幅度要大，相差较小时幅度要减小)

> **负梯度计算公式**
> ```latex
> -g = -[\frac{\partial L(y, y_i) }{\partial y_i}]\mid _{y_i=f_{t-1}(x_i) }
> ```

选择不同的损失函数，会得到不同的负梯度值。
如果选择平方损失函数：
```latex
L(y, y_i) = \frac{1}{2} (y-y_i)^2
```
则负梯度为：
```latex
-g = (y-y_i)
```
此时我们发现，负梯度就是残差。
> 因此我们知道：
> - 对于回归问题，由于使用的是平方差损失函数，因此GBDT拟合的就是残差；
> - 如果使用GBDT处理分类问题，二分类和多分类的损失函数是对数损失函数，拟合的就不再是残差；

### 参考
> [GBDT 算法：原理篇](https://zhuanlan.zhihu.com/p/53980138)
> [GBDT算法原理以及实例理解](https://ranmaosong.github.io/2019/04/27/ML-GBDT/)