xgboost相关问题

XGBoost、GBDT超详细推导

珍藏版 | 20道XGBoost面试题

1.xgboost 怎么计算特征重要度？还有什么特征选择的方法？

xgboost 中以每个特征在模型中被用作分裂结点的次数作为特征的重要度。
通常来说，从两个方面考虑来选择特征：
（1）特征是否发散：如果一个特征不发散，例如方差接近于0，也就是说样本在这个特征上基本上没有差异，这个特征对于样本的区分并没有什么用。
（2）特征与目标的相关性：这点比较显见，与目标相关性高的特征，应当优选选择。除方差法外，本文介绍的其他方法均从相关性考虑。

根据特征选择的形式又可以将特征选择方法分为如下3种：
（1）Filter：过滤法。按照发散性或者相关性对各个特征进行评分，设定阈值或者待选择阈值的个数，选择特征。比如：相关系数法，计算各个特征对目标值的相关系数。卡方检验，计算自变量对因变量的相关性。互信息法，也是评价自变量对定性因变量的相关性。
（2）Wrapper: 包装法。根据目标函数（通常是预测效果评分）的好坏，每次选择若干特征，或者排除若干特征。
（3）Embedded: 嵌入法先使用某些机器学习的算法和模型进行训练，得到各个特征的权值系数，根据系数从大到小选择特征。类似于Filter方法，但是要通过训练来确定特征的优劣。比如xgboost 就是这种方法，还有logistic也是这种方法。

2.xgboost 怎么选择分裂结点？xgboost 中被用来进行分裂的特征还会再次用作结点吗？

在节点分裂的时候通过计算每个特征的信息增益来选择信息增益大的特征进行分裂。已经用过的特征还有可能再次用到，在xgboost 中用的是回归树，比如某次分裂 >0.2 的分为一边，<= 0.2 分为另一边。在下面的节点中，>0.2 的部分还有可能分为 >0.5 和 <=0.5，所以用过的特征还会继续用。而在决策树中，用过的特征才不会再用。
随机森林在构造每棵树的一个节点时：随机有放回的选择样本；随机无放回地选择特征。

3.xgboost 有哪些防止过拟合的方法？

主要有下面的四种方式：
（1）early_stopping_rounds: 设置 early stopping，提前结束训练。
（2）减小 max_depth：减小树的深度，实际上就是减少模型的参数，降低模型的拟合能力。
（3）加入正则项：用于控制模型的复杂度。正则项中包括了树的叶子节点个数，每个叶子节点上输出的score的L2模的平方和。从bias-variancetrade off 角度来讲，正则项降低了模型的variance,使模型输出更加简单，防止过拟合。这也是 xgboost 优于 gbdt 的一个特性。
（4）列采样、行采样：借鉴随机森林的做法，支持列采样，不仅防止过拟合，同时还减少计算量。这是xgboost由于gbdt的另一点。（为什么行采样和列采样就能够防止过拟合？dropout为什么能够防止过拟合？dropout相当于对多个网络（每个网络的特征不同）进行了bagging，而在bagging中，每个模型都有不同的过拟合，对多个模型求平均之后不同的过拟合之间会有一定的相互抵消。）

4.xgboost, lightGBM 和 gbdt 有什么区别？他们的 loss 一样吗？算法的层面有什么区别？

首先是 xgboost 和 gbdt 的联系和区别， xgboost 是在 gbdt 的基础上发展来的，相比 gbdt,xgboost的速度更快，同时xgboost的性能一般都会比 gbdt 更好一点。
（1）xgboost 的本质和 gbdt 一样，都是采用 boosting 的计算方式；gbdt 是以回归树作为基本模型，每次迭代都是先算出当前的结果和实际值的残差，下一个模型就是去拟合这个残差。在gbdt中，基本模型是回归树，但是在xgboost中，还支持线性模型。
（2）在 xgboost 中加入了正则项。主要包括两个方面：一是树的叶子数；一是每个叶子结点上输出的score的L2模的平方和。
（3）列抽样。xgboost 借鉴随机森林的方法，加入了列抽样，不但能够降低过拟合，同时还能够减少计算。
（4）上面两个方法使得 xgboost 具备更好的防止过拟合能，所以xgboost的性能一般都比gbdt要好一些。此外，在速度上，xgboost要远远快于gbdt。主要是xgboost实现了并行处理。xgboost的并行处理是指在特征处理上。在进行分裂的时候，需要计算每个特征的信息增益，xgboost实现了并行计算各个特征的信息增益，从而提升了计算速度。xgboost灾计算最佳分裂节点的时候需要预先将特征的取值进行排序（注意是对取值排序），排序之后保存排序的结果。
（5）此外，在进行优化求解的时候，xgboost对代价函数进行二阶泰勒展开，同时用到了一阶，二阶求导。而 gbdt 只用了一阶导数。

lightGBM 是后来提出来的，从我自己的使用来看，LGB 的性能和 xgboost 差不多，但是速度却快好多倍。
参考：快的不要不要的lightGBM

首先，xgboost 存在下面一些缺点：
（1）每次迭代都要读取整个数据集（抽样后的数据集），耗时耗内存
（2）在计算最佳分裂节点的时候需要预先对特征的取值进行排序，排序完后还要保存。虽然一共只计算了一次，之后直接读取结果，但是比较耗费内存呀。
（3）在计算分裂节点的时候需要遍历每一个候选节点，然后计算信息增益，耗时。
（4）生成的树是 level-wise（逐层生成）的，我们设定了 max_depth 之后，每棵树都要生长到设定好的深度，就算有些树在某些节点分裂之后效果没有提升了仍然要继续分裂，耗时。

针对xgboost的缺点，lightGBM 提出了两个主要技术：
（1）丢掉梯度（数值）小的数据（单边梯度采样）：就是删除大量只具有小梯度的数据，只利用剩下的高梯度数据，从而减少了计算开销。首先对于要进行分裂的特征的所有取值按照绝对值大小进行排序，选择最大的一部分数据，然后再随机选择一些较小的数据（为了保持数据分布不变），丢弃其他数值小的样本。这样就能极大地减少计算。
（2）互斥稀疏特征绑定：使用连通图的方式选择出互斥性大的特征进行绑定，从而降低特征的维度，减少计算。
此外，LGB生成的树是 leaf-wise 的，带深度限制的叶子生长策略，在生成树的过程中，只要达到树的叶子数就终止生长，而不需要达到设定的深度。
上面可以看出，lightGBM 通过丢弃减少样本数量和合并减少特征数量，此外，还不用死磕到特定的深度才停止，这极大的减少了计算量，所以lightGBM 的速度要远远快于 xgboost。

5.梯度提升方法和普通的提升方法有什么区别？

• AdaBoost

  • 重视重点样本：提高前一轮弱分类器分错的样本的权重，是这些样本在本轮的弱分类器分类中得到更大的重视。

  • 性能好的g权重更大：对于分类准确率好的弱分类器，权值更大一些。每一轮弱分类器都统计一下分错率，然后根据这个分错率来计算弱分类器的权重。

• 提升树：拟合当前模型的残差。（下面以回归问题的提升树算法为例）

  • step1：找到所有的切分点

  • step2：遍历所有的切分点，计算对应的最小平方损失

  • step3：在 step2 中我们找到一个切分点使得损失最小，这就是得到的第一个函数。根据它，计算每一个样本的残差，然后继续拟合这个残差。

  • step4：最后，将每一次得到的函数进行累加，就是最后得到的模型。

• 梯度提升树

  • 对于一般的损失函数，往往每一步优化都不那么容易，因此提出了梯度提升算法。该算法利用最速下降的近似方法，关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树

• 所以在提升树中，每一轮都是建立一棵回归树去拟合残差（yi-pi）；而在梯度提升树中，每一轮去拟合的是负梯度方向。

• 拟合梯度实际上是为了拟合残差，只不过是通过一种近似方法更加好求而已。

• 我们常用的有平方损失（回归问题）和交叉熵损失（分类问题），可以看到算出来的负梯度都是残差的近似值。

  • 平方 loss：

  • log loss：

6.GBDT二分类的推导？

• Step1：明确输入输出

  • 给定一个数据，我们要预测它属于正类的概率，所以模型输出的是概率。

• Step2：确定 loss

  • 设输出样本i的概率为pi，那么损失函数为

• Step3：优化 loss

  • 通过迭代的方式，每次去拟合负梯度：

    • （1）第一棵树为根节点，输出一个常数 c1

    • （2）迭代：a.计算负梯度；b.用回归树拟合负梯度；c.更新输出

    • （3）不断迭代

• 注意在叶子进行分裂的时候需要对特征的所有划分点进行扫描，所以在扫描之前就要先对特征进行排序，然后根据相邻两个值取中点作为划分点