GBDT的参数，哪些影响过拟合

参数：
（1）n_estimators: 也就是弱学习器的最大迭代次数，或者说最大的弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。默认是100。在实际调参的过程中，我们常常将n_estimators和下面介绍的参数learning_rate一起考虑
（2）learning_rate， float，默认= 0.1,学习率缩小了每棵树的贡献learning_rate。在learning_rate和n_estimators之间需要权衡
（3）subsample: 即我们在原理篇的正则化章节讲到的子采样，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间，默认是1.0，即不使用子采样
（4）loss: 即我们GBDT算法中的损失函数。分类模型和回归模型的损失函数是不一样的。
对于分类模型，有对数似然损失函数”deviance”和指数损失函数”exponential”两者输入选择。默认是对数似然损失函数”deviance”。在原理篇中对这些分类损失函数有详细的介绍。一般来说，推荐使用默认的”deviance”。它对二元分离和多元分类各自都有比较好的优化。而指数损失函数等于把我们带到了Adaboost算法。
对于回归模型，有均方差”ls”, 绝对损失”lad”, Huber损失”huber”和分位数损失“quantile”。默认是均方差”ls”。一般来说，如果数据的噪音点不多，用默认的均方差”ls”比较好。如果是噪音点较多，则推荐用抗噪音的损失函数”huber”。而如果我们需要对训练集进行分段预测的时候，则采用“quantile”
（5）alpha：这个参数只有GradientBoostingRegressor有，当我们使用Huber损失”huber”和分位数损失“quantile”时，需要指定分位数的值。默认是0.9，如果噪音点较多，可以适当降低这个分位数的值
（6）min_samples_split， int或float，默认为2,拆分内部节点所需的最少样本数：如果为int，则认为min_samples_split是最小值。如果为float，min_samples_split则为分数， 是每个拆分的最小样本数。ceil(min_samples_split n_samples)
（7）min_samples_leaf， int或float，默认值= 1,在叶节点处所需的最小样本数。仅在任何深度的分裂点在min_samples_leaf左分支和右分支中的每个分支上至少留下训练样本时，才考虑。这可能具有平滑模型的效果，尤其是在回归中。如果为int，则认为min_samples_leaf是最小值。如果为float，min_samples_leaf则为分数， 是每个节点的最小样本数。ceil(min_samples_leaf n_samples)
（8）min_weight_fraction_leaf, float，默认值= 0.0,在所有叶节点处（所有输入样本）的权重总和中的最小加权分数。如果未提供sample_weight，则样本的权重相等。
（9）max_depth, int，默认= 3,各个回归估计量的最大深度。最大深度限制了树中节点的数量。调整此参数以获得最佳性能；最佳值取决于输入变量的相互作用。也就是那个树有多少层（一般越多越容易过拟合）
（10）min_impurity_decrease， 浮动，默认值= 0.0，如果节点分裂会导致杂质的减少大于或等于该值，则该节点将被分裂
（11）min_impurity_split ，float，默认=无提前停止树木生长的阈值。如果节点的杂质高于阈值，则该节点将分裂，否则为叶
（12）init:计量或“零”，默认=无,一个估计器对象，用于计算初始预测。 init必须提供fit和predict_proba。如果为“零”，则初始原始预测设置为零。默认情况下，使用 DummyEstimator预测类优先级
（13）max_features:节点分裂时参与判断的最大特征数

XGBoost和GBDT

区别

xgboost是梯度提升树的一种高效系统实现，是对GBDT进一步的改进，包括对代价函数进行了二阶泰勒展开，在代价函数里加入了正则项，借鉴了随机森林的列采样方法，支持并行计算等
1.传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。 —可以通过booster [default=gbtree]设置参数:gbtree: tree-based models/gblinear: linear models
2.传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。 —对损失函数做了改进（泰勒展开，一阶信息g和二阶信息h）
3.xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性
4.shrinkage and column subsampling —还是为了防止过拟合，论文2.3节有介绍，这里答主已概括的非常到位
（1）shrinkage缩减类似于学习速率，在每一步tree boosting之后增加了一个参数n（权重），通过这种方式来减小每棵树的影响力，给后面的树提供空间去优化模型。
（2）column subsampling列(特征)抽样，说是从随机森林那边学习来的，防止过拟合的效果比传统的行抽样还好（行抽样功能也有），并且有利于后面提到的并行化处理算法。
5.split finding algorithms(划分点查找算法)：—理解的还不够透彻，需要进一步学习
（1）exact greedy algorithm—贪心算法获取最优切分点
（2）approximate algorithm— 近似算法，提出了候选分割点概念，先通过直方图算法获得候选分割点的分布情况，然后根据候选分割点将连续的特征信息映射到不同的buckets中，并统计汇总信息。详细见论文3.3节
（3）Weighted Quantile Sketch—分布式加权直方图算法，论文3.4节
这里的算法（2）、（3）是为了解决数据无法一次载入内存或者在分布式情况下算法（1）效率低的问题，以下引用的还是wepon大神的总结：
可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
6.对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。 —稀疏感知算法，论文3.4节，Algorithm 3: Sparsity-aware Split Finding
10.并行化处理 —系统设计模块,块结构设计等
xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
此外xgboost还设计了高速缓存压缩感知算法，这是系统设计模块的效率提升。
当梯度统计不适合于处理器高速缓存和高速缓存丢失时，会大大减慢切分点查找算法的速度。
（1）针对 exact greedy algorithm采用缓存感知预取算法
（2）针对 approximate algorithms选择合适的块大小
原文链接：https://blog.csdn.net/sb19931201/article/details/52557382

是否需要剪枝

不需要后剪枝操作：
正则化项γ起到了一定的预剪枝的效果
观察分裂后的收益，我们会发现节点划分不一定会使得结果变好，因为我们有一个引入新叶子的惩罚项，也就是说引入的分割带来的增益如果小于一个阀值的时候，我们可以剪掉这个分割。

如何处理缺失值问题

传统GBDT没有专门针对缺失值进行处理；XGB能够自动学习出缺失值的处理策略.
缺失值：XGBoost没有假设缺失值一定进入左子树还是右子树，则是尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优(分到那个子节点带来的增益大)来决定一个处理缺失值默认的方向，这样处理起来更加的灵活和合理。

二阶导数为何更优

使用泰勒展开到二阶的原因：
1. 统一损失函数求导的形式以支持自定义损失函数
2. 二阶信息本身就能让梯度收敛更快更准确

LightGBM和XGBoost

主要区别

1、决策树算法
XGBoost使用的是pre-sorted算法，能够更精确的找到数据分隔点；LightGBM使用的是histogram算法，占用的内存更低，数据分隔的复杂度更低。
2、决策树生长策略
XGBoost采用的是level（depth）-wise生长策略，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。

效率和内存上的提升

直方图算法，LightGBM提供一种数据类型的封装相对Numpy,Pandas,Array等数据对象而言节省了内存的使用，原因在于他只需要保存离散的直方图，LightGBM里默认的训练决策树时使用直方图算法，XGBoost里现在也提供了这一选项，不过默认的方法是对特征预排序，直方图算法是一种牺牲了一定的切分准确性而换取训练速度以及节省内存空间消耗的算法

  • 在训练决策树计算切分点的增益时，预排序需要对每个样本的切分位置计算，所以时间复杂度是O(#data)而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可，时间复杂度为O(#bins),时间效率上大大提高了(初始构造直方图是需要一次O(#data)的时间复杂度，不过这里只涉及到加和操作) ： histogram算法简单来说，就是先对特征值进行装箱处理，形成一个一个的bins。对于连续特征来说，装箱处理就是特征工程中的离散化：如[0,0.3)—>0，[0.3,0.7)—->1等。在Lightgbm中默认的#bins为256（1个字节的能表示的长度，可以设置）。对于分类特征来说，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。在节点分裂的时候，这时候就不需要按照预排序算法那样，对于每个特征都计算#data遍了，而是只需要计算#bins遍，这样就大大加快了训练速度。 直方图优化算法需要在训练前预先把特征值转化为bin value，也就是对每个特征的取值做个分段函数，将所有样本在该特征上的取值划分到某一段（bin）中。最终把特征取值从连续值转化成了离散值。需要注意得是：feature value对应的bin value在整个训练过程中是不会改变的。 直方图做差进一步提高效率，计算某一节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到，所以每次分裂只需计算分裂后样本数较少的子节点的直方图然后通过做差的方式获得另一个子节点的直方图，进一步提高效率
  • 带有深度限制的按叶子生长 (leaf-wise) 算法代替了传统的(level-wise) 决策树生长策略，提升精度，同时避免过拟合危险。
  • 节省内存
    • 将连续数据离散化为直方图的形式，对于数据量较小的情形可以使用小型的数据类型来保存训练数据
    • 不必像预排序一样保留额外的对特征值进行预排序的信息
  • 减少了并行训练的通信代价

对比xgboost的优势

  • 1. Histogram算法：Pre-sorted 算法需要的内存约是训练数据的两倍(2 #data #features 4Bytes)，它需要用32位浮点(4Bytes)来保存 feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位(4Bytes)的存储空间。因此是(2 #data #features 4Bytes)。而对于 histogram 算法，则只需要(#data #features 1Bytes)的内存消耗，仅为 pre-sorted算法的1/8。因为 histogram 算法仅需要存储 feature bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而 bin value 用 1Bytes(256 bins) 的大小一般也就足够了。
  • 计算上的优势则是大幅减少了计算分割点增益的次数。对于每一个特征，pre-sorted 需要对每一个不同特征值都计算一次分割增益，代价是O(#feature#distinct_values_of_the_feature)；而 histogram 只需要计算#bins次，代价是(#feature#bins)。
  • LightGBM和XGBoost直方图：实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢？xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图。比如local策略下，根节点有data个样本，对n个特征创建n个直方图，直方图的划分是根据样本的2阶梯度作为权重得到的，每次分裂后，样本的2阶梯度就会发生变化，就需要重新计算更新直方图。有点疑问：XGB应该也是针对每个特征都分别构建一个直方图，分桶的依据是样本的二级梯度；完成一次分裂后，样本的二阶梯度发生变化，就需要重新计算，重新构建每个特征的直方图。 lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。(1)根节点包含所有样本data，对n个特征，构建n个直方图，(2)根节点分裂为左右两个子节点，可以先对右节点创建n个直方图,右节点的样本数量为data/2，再用根节点的对应的n个直方图减去右节点的n个直方图，就得到左节点的n个直方图，(3)如果一棵树有m层深，则就需要构建m次直方图，对应的样本量分别为data,data/2,data/4…. 原文链接：https://blog.csdn.net/qfikh/article/details/105157438
  • 还有一个很重要的点是cache-miss。事实上，cache-miss对速度的影响是特别大的。预排序中有2个操作频繁的地方会造成cache miss，一是对梯度的访问，在计算gain的时候需要利用梯度，不同特征访问梯度的顺序都是不一样的，且是随机的，因此这部分会造成严重的cache-miss。二是对于索引表的访问，预排序使用了一个行号到叶子节点号的索引表（row_idx_to_tree_node_idx ），来防止数据切分时对所有的数据进行切分，即只对该叶子节点上的样本切分。在与level-wise进行结合的时候， 每一个叶子节点都要切分数据，这也是随机的访问。这样会带来严重的系统性能下降。而直方图算法则是天然的cache friendly。在直方图算法的第3个for循环的时候，就已经统计好了每个bin的梯度，因此，在计算gain的时候，只需要对bin进行访问，造成的cache-miss问题会小很多。
  • 最后，在数据并行的时候，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大。LightGBM 与 XGboost 的并行策略不同：特征并行 ：LightGBM特征并行的前提是每个worker留有一份完整的数据集，但是每个worker仅在特征子集上进行最佳切分点的寻找；worker之间需要相互通信，通过比对损失来确定最佳切分点；然后将这个最佳切分点的位置进行全局广播，每个worker进行切分即可。XGB的特征并行与LGB的最大不同在于XGB每个worker节点中仅有部分的列数据，也就是垂直切分，每个worker寻找局部最佳切分点，worker之间相互通信，然后在具有最佳切分点的worker上进行节点分裂，再由这个节点广播一下被切分到左右节点的样本索引号，其他worker才能开始分裂。二者的区别就导致了LGB中worker间通信成本明显降低，只需通信一个特征分裂点即可，而XGB中要广播样本索引。 数据并行 ：传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。这种数据划分有一个很大的缺点：通讯开销过大。LightGBM在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算; 在节点分裂时利用直方图做差，进一步减少了一半的通信量。：https://blog.csdn.net/qfikh/article/details/105157438
  • 2 直方图做差加速:在histogram算法上一个trick是histogram 做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。利用这个方法，Lightgbm 可以在构造一个叶子（含有较少数据）的直方图后，可以用非常微小的代价得到它兄弟叶子（含有较多数据）的直方图。 因为构建兄弟叶子的直方图是做差得到的，时间复杂度仅为O（#bins），几乎可以忽略，因此，比起不做差得到的兄弟节点的直方图，在速度上可以提升一倍。
  • 3.带深度限制的Leaf-wise的叶子生长策略 ：在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝。LightGBM进行进一步的优化，采用的Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合
  • （数据并行的优化是Lightgbm的令一个亮点，这里不是特别理解，需要再深入研究）

    劣势

    histogram 算法不能找到很精确的分割点，训练误差没有 pre-sorted 好。但从实验结果来看， histogram 算法在测试集的误差和 pre-sorted 算法差异并不是很大，甚至有时候效果更好。实际上可能决策树对于分割点的精确程度并不太敏感，而且较“粗”的分割点也自带正则化的效果，再加上boosting算法本身就是弱分类器的集成。
    原文链接：https://blog.csdn.net/anshuai_aw1/article/details/83040541

    XGBoost、LightGBM更多

    https://zhuanlan.zhihu.com/p/87885678