GBDT

简介

GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，在传统机器学习算法中，GBDT算的上TOP3的算法。想要理解GBDT的真正意义，那就必须理解GBDT中的Gradient Boosting 和Decision Tree分别是什么？

分类树和回归树

1.分类树

分类树使用信息增益或增益比率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。

以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1)，按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

2.回归树

回归树使用最大均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。

回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即(每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

Decision Tree：CART回归树

GBDT使用的决策树都是CART数回归树，无论是处理回归问题还是二分类以及多分类。

为什么不用CART分类树呢？

因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。

CART回归树的评价指标：平方误差

为什么CART回归时的评价指标不再使用Gini、熵等不纯度指标？

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

Graident Boosting:梯度提升树

梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树

提升树 Boosting Tree

提升树就是通过不断建立树来不断拟合前一个问题的残差来不断接近目标。

先来个通俗理解：假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。

当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，Friedman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。

Graident Boosting:梯度提升树

核心：利用损失函数的负梯度作为提升树算法中的残差的近似值。

下面我们来看一下负梯度具体的样子，第t轮的第i个样本的损失函数的负梯度为：

那么对于分类问题呢？二分类和多分类的损失函数都是logloss，下面以回归问题为例对GBDT算法进行讲解。

常见问题：

1.GBDT和Xgboost的区别？

1.损失函数上在GBDT的损失函数上XGboost加入了正则化项

2.优化方法上 GBDT在优化上只使用一阶导数的信息，而XGBoost则对代价函数进行了二阶的展开。

3.基分类器的支持上 GBDT只支持CART数作为基分类器，XGBoost在其基础上加入了线性分类器

4.Xgboost加入了shrinkage策略。在完成一次迭代后会将叶子节点的权值乘以该系数削弱了每棵树的影响，使后面的数拥有更大的学习空间

5.列抽样借鉴了随机森林的做法，支持列抽样，不仅能防止过拟合还能减少计算

6.缺失值自动处理对于有缺失值的样本，XGBoost可以自动学习出分裂方向

7.计算特征增益时并行预先对特征值进行排序，保存成block结构，后面的迭代重复使用这个结构

2.lightgbm和Xgboost的区别在哪里？

lightgbm基本原理和Xgboost一样，在框架上做了一些优化

1.xgboost采用的level-wise的分裂策略，而lightgbm采用的是leaf-wise的策略，区别是xgboost对每一层节点做无差别的分裂，可能有些节点的信息增益非常小，对结果影响不大，但是依然进行分裂；leaf-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂。明显leaf-wise更容易过拟合，陷入高度较高的深度中，因此lightgbm更应该注意对深度进行限制

2.lightgbm使用histgram的决策树算法，而xgboost使用exact算法，hostgram算法在内存和计算代价上都有不小的优势

3.lightgbm采用直方图加速计算

4.并行化。

a.特征并行化

一般的特征并行化都并行化都采用将数据进行垂直切分，然后分割后的数据分散到各个worker，各个worker计算器拥有的数据上计算 best split point，然后汇总得到最优切点。这种方式在数据量很大的时候效率提升有限

lightgbm采用直接将全量数据分散到每个worker，然因此最优的特征分裂结果不需要传输到其他worker中，只需要将最优特征以及分裂点告诉其他worker，worker随后本地自己进行处理。

b.数据并行化

传统的数据并行算法，首先水平切分数据集，每个worker基于数据集构建局部特征直方图（Histogram），归并所有局部的特征直方图，得到全局直方图，找到最优分裂信息，进行数据分裂。

LightGBM算法使用Reduce Scatter并行算子归并来自不同worker的不同特征子集的直方图，然后在局部归并的直方图中找到最优局部分裂信息，最终同步找到最优的分裂信息。

除此之外，LightGBM使用直方图减法加快训练速度。我们只需要对其中一个子节点进行数据传输，另一个子节点可以通过histogram subtraction得到。

参考文献：https://blog.csdn.net/zpalyq110/article/details/79527653