目录

1 简单描述一下Adaboost的算法原理和流程。

2 Adaboost的优点和缺点？

3 简单说一下GBDT的原理。

4 为什么对于高维稀疏特征不太适合用GBDT？

5  GBDT和随机森林的异同点？

6  GBDT的优缺点？

7 简单介绍一下XGBOOST。

8 XGBOOST和GBDT的区别在哪里？

9 为什么XGBOOST要用泰勒展开，优势在哪里？

10  XGBOOST是如何寻找最优特征的？

11  XGBOOST是如何处理缺失值的？

12  XGBOOST的并行化是如何实现的？

13  XGBOOST采样时有放回的还是无放回的？

14  XGBOOST的调参步骤是怎样的？

15  XGBOOST特征重要性的输出原理？

16  LightGBM相比XGBOOST在原理和性能上的差异？

1 简单描述一下Adaboost的算法原理和流程。

Adaboost基于分类器的错误率分配不同的权重系数，最后得到累加加权的的预测结果。

算法流程：

给数据中每一个样本一个权重，若有N个样本，则每个样本的权重为1/N.

训练数据的每一个样本，得到第一个分类器。

计算该分类器的错误率，根据错误率计算给分类器分配的权重。

将第一个分类器分错的样本权重增加，分对的样本权重减少，然后再用新的样本权重训练数据，得到新的分类器。

迭代这个训练步骤直到分类器错误为0或达到迭代次数。

将所有的弱分类器加权求和，得到分类结果(分类器权重)，错误率低的分类器获得更高的决定系数，从而在数据进行预测起关键作用。

2 Adaboost的优点和缺点？

优点：

分类精度高，构造简单，结果可理解。

可以使用各种回归分类模型来构建弱学习器，非常灵活。

不容易过拟合。

缺点：

训练时会过于偏向分类困难的数据，导致Adaboost容易受噪声数据干扰。

依赖于弱分类器，训练时间可能比较长。

3 简单说一下GBDT的原理。

GBDT是boosting的一种方法，主要思想是每一次建立单个分类器时，是在之前建立的模型的损失函数的梯度下降方向。损失函数越大，说明模型越容易出错，如果我们的模型能让损失函数持续的下降，则说明我们的模型在持续不断的改进，而最好的方式就是让损失函数在其梯度的方向上下降。

GBDT的核心在于每一棵树学的是之前所有树结论和的残差，残差就是真实值与预测值的差值，所以为了得到残差，GBDT中的树全部是回归树，之所以不用分类树，是因为分类的结果相减是没有意义的。

Shrinkage(缩减)是 GBDT 的一个重要演进分支，Shrinkage的思想在于每次走一小步来逼近真实的结果，要比直接迈一大步的方式更好，这样做可以有效减少过拟合的风险。它认为每棵树只学到了一小部分，累加的时候只累加这一小部分，通过多学习几棵树来弥补不足。这累加的一小部分(步长*残差)来逐步逼近目标，所以各个树的残差是渐变的而不是陡变的。

GBDT可以用于回归问题(线性和非线性)，也可用于分类问题。

4 为什么对于高维稀疏特征不太适合用GBDT？

GBDT在每一次分割时需要比较大量的特征，特征太多，模型训练很耗费时间。

树的分割往往只考虑了少部分特征，大部分的特征都用不到，所有的高维稀疏的特征会造成大量的特征浪费。

5  GBDT和随机森林的异同点？

相同点：

都是由多棵树构成，最终的结果也是由多棵树决定。

不同点：

随机森林可以由分类树和回归树组成，GBDT只能由回归树组成。

随机森林的树可以并行生成，而GBDT只能串行生成，所以随机森林的训练速度相对较快。

随机森林关注减小模型的方差，GBDT关注减小模型的偏差。

随机森林对异常值不敏感，GBDT对异常值非常敏感。

随机森林最终的结果是多数投票或简单平均，而GBDT是加权累计起来。

6  GBDT的优缺点？

优点：

GBDT每一次的残差计算都增大了分错样本的权重，而分对的权重都趋近于0，因此泛化性能比较好。

可以灵活的处理各种类型的数据。

缺点：

对异常值比较敏感。

由于分类器之间存在依赖关系，所以很难进行并行计算。

7 简单介绍一下XGBOOST。

XGBOOST是一种梯度提升的算法，用来解决分类和回归问题。它的基学习器可以是CART树，也可以是线性分类器。当用CART树做基学习器时，训练的时候采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。XGBoost对GBDT进行了一系列优化，比如损失函数进行了二阶泰勒展开、目标函数加入正则项、特征粒度上支持并行计算和默认缺失值处理等，在可扩展性和训练速度上有了巨大的提升。

8 XGBOOST和GBDT的区别在哪里？

传统的GBDT是以CART树作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)，线性分类器的速度是比较快的，这时候xgboost的速度优势就体现了出来。

传统的GBDT在优化时只使用一阶导数，而xgboost对损失函数做了二阶泰勒展开，同时用到了一阶和二阶导数，并且xgboost支持使用自定义损失函数，只要损失函数可一阶，二阶求导。

xgboost在损失函数里加入了正则项，用来减小模型的方差，防止过拟合，正则项里包含了树的叶节点的个数， 每个叶子节点上输出的score的L2模的平方和。

xgboost里有一个参数叫学习速率(learning_rate)， xgboost在进行完一次迭代后，会将叶子节点的权重乘上学习速率，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把learing_rate设置得小一点，然后迭代次数(n_estimators)设置得大一点。

xgboost借鉴了随机森林的原理，支持行抽样(subsample)和列抽样(colsample_bytree,colsample_bylevel)， 行抽样指的是随机森林里对数据集进行有放回抽样，列抽样指的是对特征进行随机选择，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

9 为什么XGBOOST要用泰勒展开，优势在哪里？

xgboost使用了一阶和二阶偏导，二阶导数有利于梯度下降的更快更准，使用泰勒展开取得函数做自变量的二阶导数形式，可以在不选定损失函数具体形式的情况下，仅仅依靠输入数据的值就可以进行叶子分裂优化计算，本质上也就把损失函数的选取和模型算法的优化分开来了，这种去耦合增加了xgboost的适用性，使得它按需选取损失函数，既可以用于分类，也可以用于回归。

10  XGBOOST是如何寻找最优特征的？

xgboost在训练过程中给出各个特征的增益评分，最大增益的特征会被选出来作为分裂依据，从而记忆了每个特征在模型训练时的重要性，从根到叶子中间节点涉及某特征的次数作为该特征重要性排序。

11  XGBOOST是如何处理缺失值的？

xgboost为缺失值设定了默认的分裂方向，xgboost在树的构建过程中选择能够最小化训练误差的方向作为默认的分裂方向，即在训练时将缺失值划入左子树计算训练误差，再划入右子树计算训练误差，然后将缺失值划入误差小的方向。

12  XGBOOST的并行化是如何实现的？

xgboost的并行不是在tree粒度上的并行，xgboost也是一次迭代完才能进行下一次迭代(第t次迭代的损失函数包含了第t-1次迭代的预测值)，它的并行处理是在特征粒度上的，在决策树的学习中首先要对特征的值进行排序，然后找出最佳的分割点，xgboost在训练之前，就预先对数据做了排序， 然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

13  XGBOOST采样时有放回的还是无放回的？

xgboost属于boosting方法的一种，所以采样时样本是不放回的，因而每轮计算样本不重复，另外，xgboost支持子采样，每轮计算可以不使用全部的样本，以减少过拟合。另外一点是xgboost还支持列采样，每轮计算按百分比随机抽取一部分特征进行训练，既可以提高速度又能减少过拟合。

14  XGBOOST的调参步骤是怎样的？

PS：这里使用Gridsearch cv来穷举检索最佳的参数，如果时间允许，可以通过设置步数先粗调，再细调。

保持learning rate和其他booster相关的参数不变，调节和estimators的参数。learing_rate可设为0.1, max_depth设为4-6之间，min_child_weight设为1，subsample和colsample_bytree设为0.8 ，其他的参数都设为默认值即可。

调节max_depth 和 min_child_weight参数，首先，我们先大范围地粗调参数，然后再小范围地微调。

gamma参数调优

subsample和colsample_bytree 调优

正则化参数调优，选择L1正则化或者L2正则化

缩小learning rate，得到最佳的learning rate值

15  XGBOOST特征重要性的输出原理？

xgboost是用get_score方法输出特征重要性的，其中importance_type参数支持三种特征重要性的计算方法：

importance_type=weight(默认值)，使用特征在所有树中作为划分属性的次数。

importance_type=gain，使用特征在作为划分属性时loss平均的降低量。

importance_type=cover，使用特征在作为划分属性时对样本的覆盖度。

16  LightGBM相比XGBOOST在原理和性能上的差异？

1.速度和内存上的优化：

xgboost用的是预排序(pre-sorted)的方法， 空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果(例如排序后的索引，为了后续快速的计算分割点)，这里需要消耗训练数据两倍的内存。其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。

LightGBM用的是直方图(Histogram)的决策树算法，直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

2.准确率上的优化：

xgboost 通过level(depth)-wise策略生长树， Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

LightGBM通过leaf-wise(best-first)策略来生长树， Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

3.对类别型特征的处理：

xgboost不支持直接导入类别型变量，需要预先对类别型变量作亚编码等处理。如果类别型特征较多，会导致哑变量处理后衍生后的特征过多，学习树会生长的非常不平衡，并且需要非常深的深度才能来达到较好的准确率。

LightGBM可以支持直接导入类别型变量(导入前需要将字符型转为整数型，并且需要声明类别型特征的字段名)，它没有对类别型特征进行独热编码，因此速度比独热编码快得多。LightGBM使用了一个特殊的算法来确定属性特征的分割值。基本思想是对类别按照与目标标签的相关性进行重排序，具体一点是对于保存了类别特征的直方图根据其累计值(sum_gradient/sum_hessian)重排序,在排序好的直方图上选取最佳切分位置。