XGBoost与LightGBM总结
问：XGBoost做了哪些优化？[*]GBDT在优化时只用到一阶导；xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导。
[*]Xgboost采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，带来了不必要的开销。
level-wise growth
[*]采用了以下三种降低过拟合的方法：
[*]在代价函数里显示的加入了正则项，用于控制模型的复杂度，降低过拟合，提高模型的泛化能力。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。
[*]Shrinkage（缩减），相当于学习速率（xgboost中的 https://www.zhihu.com/equation?tex=%5Ceta ）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间，降低过拟合。
[*]列抽样（column/feature subsampling）。xgboost借鉴了随机森林的做法，支持列抽样(分裂只选取一部分特征)，不仅能降低过拟合，还能减少计算。
[*]对缺失值的处理：对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。在按照特征分裂的时候，相当于增加了一个默认的分裂方向：如果该样本的特征缺失，则样本被分入默认的叶子节点。
default的分裂方向(红色)
[*]学习缺失值的方法：假如特征有两个值，那么缺失的一类会被通过 [(A, missing), B] 和 分别算损失，选取损失小的一侧作为default。预测时把missing的样本归入损失小的default方向里。
[*]xgboost工具支持并行。注意，并行不是tree粒度的并行，是在特征层面上的。决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
[*]XGBoost使用的是预排序(pre-sort)算法，能够更精确的找到数据分隔点；LightGBM使用的是histogram算法，占用的内存更低，数据分隔的复杂度更低。
问：LightGBM做了哪些优化？
[*]LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合。因此引入了一个阈值进行限制，防止过拟合。
leaf-wise growth
[*]直方图算法的基本思想是先把连续的浮点特征值离散化成 k个整数，同时构造一个宽度为k的直方图。把连续的浮点特征值离散化为k个整数（分桶的思想，桶称为bin）比如[0,0.1)→0, [0.1,0.3)→1
[*]然后根据直方图的离散值，遍历寻找最优的分割点。在XGBoost中需要遍历所有离散化的值，而在这里只要遍历k个直方图的值。
直方图算法
[*]但是，基于直方图的算法对于稀疏的数据不如pre-sorted的算法。因此又提出了两个优化方法：
[*]GOSS(gradient-based one side sampling) 单边梯度抽样算法，对梯度小的样本随机抽样，用剩下的样本去估计信息增益，以此来选择特征。
[*]EFB(exclusive feature bundling) 互斥特征捆绑。互斥特征指的是不同时出现的特征(rarely take nonzero values simultaneously)。以此来减少特征的个数。
问：LightGBM是如何处理类别特征的？
我们知道，LightGBM可以直接处理类别特征，而不需要对类别特征做额外的one-hot encoding。那么LGB是如何实现的呢？
LGB采用了many-vs-many的方法，也就是说，把在分裂的时候把可以 https://www.zhihu.com/equation?tex=feature_k%3D1+%7C%7C+feature_k%3D2+ 分到二叉树的一侧，其余的类别值分到另一侧。对于一个 https://www.zhihu.com/equation?tex=k 个取值的离散变量，有 https://www.zhihu.com/equation?tex=2%5E%7Bk-1%7D+-+1 种分裂方法，朴素的分裂方法复杂度是 https://www.zhihu.com/equation?tex=O%282%5Ek%29 。LGB采用了优化的算法，得到了 https://www.zhihu.com/equation?tex=O%28k+%2A+log%28k%29%29 的复杂度：
具体来说，LGB在枚举分割点之前，先把直方图按每个类别的均值进行排序；然后按照均值的结果依次枚举最优分割点。
按照label均值进行排序
上图中，对某个离散特征的abc三个取值进行排序，排序的方法是取值的平均数。
问：XGBoost是如何计算特征重要性的？
有三个参数可以用于评估特征重要性：
1. 次数权重weight ：该特征在所有树中被用作分割样本的总次数。
2. 增益gain ：该特征在其出现过的所有树中产生的平均增益。
3. 覆盖cover ：该特征在其出现过的所有树中的平均覆盖范围。覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。
Reference:
关于sklearn中的决策树是否应该用one-hot编码？
LightGBM 相关知识理解
算法面试系列文章：
页:
[1]