GBDT、RF、SVM、XGBoost面试要点整理

小咪咪 2022-05-16 06:10 238阅读 0赞

对于经典机器学习算法，是所有从事相关工作者必须了解的，同时也是面试官经常提及的问题。下面我将与大家分享GBDT（Gradient Boosting Decision Tree）、RF（Random Forest）、SVM（Support Vector Machine）、XGBoost四种机器学习算法的面试考核点。若有错误，欢迎大家批评指正！！！

### 一、GBDT算法 ###

**1、算法简介**

GBDT，梯度上升决策树属于集成学习 （目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性）。GBDT是通过采用加法模型，其目的是通过不断减少训练过程中产生的残差来达到将数据进行分类或回归的算法。

**2、GBDT训练过程**

GBDT是通过多次迭代，每一次计算都是为了减小上一次的残差，为了消除残差，我们在残差减小的梯度方向上建立模型，即，在Gradient Boosting中，每个新建立的模型是为了使得之前的模型的残差往梯度负方向下降的方法，而在多次迭代过程中，每次迭代产生一个弱分类器，每个分类器基于上一轮分类器的残差进行训练。该弱分类器一般是比较简单，且要求是低方差高偏差。这是因为在训练过程中，该算法是在训练过程中通过降低偏差来不断提高最终分类器的精确度。

弱分类器的选择是CART TREE，即分类回归树，由于弱分类器是低方差高偏差，每个分类回归树的深度不会很深。最终的总分类器是将每轮训练过程产生的弱分类器加权求和得到的（即上述加法模型）。

注：GBDT算法中，所产生的树是分类树还是回归树？

解：GBDT的树会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后可以用于分类但不代表GBDT的树是分类树）。

其实，GBDT算法的关键点在于如何使得损失函数尽可能快的减小。其核心是GB（Gradient Boosting） ，即使损失函数沿着梯度负方向下降。（为什么梯度负方向是下降最快的呢？请看博客[“为什么梯度负方向是函数下降最快的？”][Link 1]）在GB算法中，利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。在GBDT每次迭代的过程，都去拟合一棵回归树。每轮训练都会使得损失函数尽可能快的减小，尽快的收敛达到局部最优解或全局最优解。

**3、GBDT如何生成回归树（如何选择特征）？**

在训练过程中，需要生成CART回归树，提醒一下，GBDT的弱分类器默认的是CART回归树，其实也可以选择其他的弱分类器，但前提是改弱分类器是低方差高偏差，且框架服从Boosting框架即可。接下来介绍一下回归树（一种二叉树）的生成过程。

其实，CART回归树的生成就是特征选择的过程。假设总共有N个特征。首先从中选择一个特征 i，作为二叉树的第一个分节点；然后对特征 i 的值选择一个切分点 n。如果一个样本的特征 i 的值小于 n，则分为一类，如果大于 n，则分为另一类。至此，就构建成功了一个回归树的一个节点，其他节点的生成一样。那么，如何选择特征 i 和特征 i 的切分点 n？

最后总结一下GBDT算法的优缺点：

（1）GBDT算法的优点有：

*  可以灵活处理各种类型的数据，包括连续值和离散值。
 *  使用一些比较strong的损失函数，比如Huber损失函数和Quantile损失函数，对异常值的鲁棒性非常强。
 *  相对于SVM来说，在相对较少的调参时间下，预测的准确度较高。

（2）GBDT算法的缺点：

*  由于弱学习器之间存在依赖关系，难以并行训练数据。

### 二、Random Forest算法 ###

Random Forest的基本单元是决策树，属于集成学习 （Ensemble Learning）方法（目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性）。随机森林是Bagging的扩展变体，它在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机特征选择，因此，随机森林包括四部分：(1)随机有放回的选取样本；(2)随机选择样本；(3)构建决策树；(4)随机森林投票（简单平均）。

**1、随机森林的生成**

通俗易懂的解释：随机森林中存在许多决策树，每棵决策树就是一个分类器。假如森林中有一棵新的树长成，森林要开大会讨论该植物属于哪一类，每棵树都要根据待分类树的特征发言并给出结论进行投票（每棵植物的看法都是独立的，互不影响），判断该树是松树还是杉树，根据每棵树的投票情况，获得票数最多的类别就是森林的分类结果。由于森林中每棵树都是独立的，那么森林大会中所有投票的结果必定会包括所有的情况。部分优秀的树（强分类器）给出的投票结果会更加准确，大部分树的投票结果可能会产生更大的偏差，但是将若干个投票树（弱分类器）组合在一起就形成一个强分类器，即集中所有的分类器投票的结果，将投票次数最多的类别指定为最终的输出，这就是简单的随机森林Bagging的思想。

那么森林中的每棵树是如何生成的？下面介绍每棵树的生成规则。

(1)假如总共有 M 个样本，对于每棵树而言，随机且有放回地从样本集中抽取 N （M<N）个训练样本，作为该树的训练集；

注：值得注意的是，在选取训练集时，每棵树的训练集都是不同的，而且每个训练集之间都有重复的训练样本。

为什么随机选取训练集？

如果不随机抽样，那么每棵树的训练集都是一样的，则最终训练出来的树分类结果也是完全一样的，这样就违背了Bagging思想；

为什么有放回地抽样？

随机森林最后的分类结果取决于若干个弱分类器的投票结果，投票次数最多的类别，就是该待分类树的所属类别，在这个过程中是求同，而有放回地抽样就会产生相同的训练样本。如果不是有放回地抽样，那么每棵树的训练样本都是相同，没有交集，也就是说，每棵树训练出来的结果会存在很大的偏差。因此使用完全不一样的训练集来训练每棵树这样的做法对最终的分类结果没有任何的帮助。总之，对于每棵树的训练集而言，我们需要有放回地抽样。

(2)假设每个训练样本的特征维度是 W，随机地从 W 个特征集中选取 x （x<W）个特征子集，每次树进行分裂时，从这 x 个特征中选择最优特征作为分裂点；

(3)每棵树尽最大程度生长，不剪枝。

影响随机森林分类结果的因素：

1.  森林中任意两棵树的相关性：相关性越大，错误率越大；
2.  森林中每棵树的分类能力：每棵树的分类器能力越强，整个森林的错误率越低。

减小特征数 x ，树的相关性和分类能力都会降低；增大 x ，两者也会随之增大。所以，随机森林的关键问题在于特征子集 x （x 的个数或 x 的范围选择）的最优选择，这也是随机森林唯一的一个可调参数。

最后总结一下随机森林的优缺点：

1、随机森林的优点：

*  随机森林仅需要指定两个参数，学习和使用更简单，预测精度高、训练速度快；
 *  随机森林引入两个随机性，使得随机森林具有良好的抗噪声能力，不容易出现过拟合；
 *  随机森林可以在分类中对各个变量的重要性进行估计，可以在创建过程中给出对泛化误差的无偏估计；
 *  随机森林可以处理很高维的数据，对数据集的适应能力强；
 *  随机森林的预测效果和性能稳定性要优于许多单预测器和集成预测方法，分类精度可与Boosting方法（如AdaBoost）相媲美，并且运行速度更快。

2、随机森林的缺点：

*  随机森林在训练数据较少时会可能导致过拟合。

### 三、XGBoost算法 ###

**1、XGBoost算法基本原理**

XGBoost是很多CART回归树集成，其性能在GBDT算法上进一步提升。

**树的复杂度定义：**

![70][]

把树拆分为结构部分 q 和叶子权重部分 w。

则树的复杂度函数和样例：

![70 1][]

定义树的结构和复杂度的原因很简单，这样就可以衡量模型的复杂度了啊，从而可以有效控制过拟合。

**xgboost中的boosting tree模型：**

![70 2][]

和传统的boosting tree模型一样，xgboost的提升模型也是采用的残差（或梯度负方向），不同的是分裂结点选取的时候不一定是最小平方损失。

![\\pounds (t)=\\sum \_i L(\\widehat\{y\_i\},y\_i)+ \\sum \_k \\Omega (f\_k) \\\\][pounds _t_sum _i L_widehat_y_i_y_i_ _sum _k _Omega _f_k_]

where ![\\Omega (f)=\\gamma T+ \\frac\{1\}\{2\} \\lambda \\left \\| w \\right \\|^2][Omega _f_gamma T_ _frac_1_2_ _lambda _left _ w _right _2]

**对目标函数的改写：**

![70 3][]

最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。这么写的原因很明显，由于之前的目标函数求最优解的过程中只对平方损失函数时候方便求，对于其他的损失函数变得很复杂，通过二阶泰勒展开式的变换，这样求解其他损失函数变得可行了。

当定义了分裂候选集合的时候，![I\_j=\\\{ i|q(x\_i)=j \\\}][I_j_ i_q_x_i_j]可以进一步改目标函数。分裂结点的候选响集是很关键的一步，这是xgboost速度快的保证，怎么选出来这个集合，后面会介绍。

![70 4][]

**树结构的打分函数：**

Obj代表了当指定一个树的结构的时候，在目标上面最多减少多少。(structure score)

![70 5][]

对于每一次尝试去对已有的叶子加入一个分割 ：

![70 6][]

这样就可以在建树的过程中动态的选择是否要添加一个结点。

![70 7][]

假设要枚举所有x < a 这样的条件，对于某个特定的分割a，要计算a左边和右边的导数和。对于所有的a，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和![G\_L][G_L]、![G\_R][G_R]。然后用上面的公式计算每个分割方案的分数就可以了。

**寻找分裂结点的候选集**

1、暴力枚举

2、近似方法 ，近似方法通过特征的分布，按照百分比确定一组候选分裂点，通过遍历所有的候选分裂点来找到最佳分裂点。

两种策略：全局策略和局部策略。在全局策略中，对每一个特征确定一个全局的候选分裂点集合，就不再改变；而在局部策略中，每一次分裂 都要重选一次分裂点。前者需要较大的分裂集合，后者可以小一点。对比补充候选集策略与分裂点数目对模型的影响。 全局策略需要更细的分裂点才能和局部策略差不多。

3、Weighted Quantile Sketch

![70 8][]

**xgboost的改进点总结：**

*  目标函数通过二阶泰勒展开式做近似 ；
 *  定义了树的复杂度，并应用到目标函数中 ；
 *  分裂结点处通过结构打分和分割损失动态生长；
 *  分裂结点的候选集合通过一种分布式Quantile Sketch得到 ；
 *  可以处理稀疏、缺失数据 ；
 *  可以通过特征的列采样防止过拟合。

## **可调参数：** ##

xgboost 有很多可调参数，具有极大的自定义灵活性。比如说：

*  objective \[ default=reg:linear \] 定义学习任务及相应的学习目标，可选的目标函数如下：

“reg:linear” –线性回归。

“reg:logistic” –逻辑回归。

“binary:logistic” –二分类的逻辑回归问题，输出为概率。

“multi:softmax” –处理多分类问题，同时需要设置参数num\_class（类别个数）

*  ’eval\_metric’ The choices are listed below，评估指标:

“rmse”: root mean square error

“logloss”: negative log-likelihood

*  max\_depth \[default=6\] 数的最大深度。缺省值为6 ，取值范围为：\[1,∞\]

### 四、SVM算法 ###

**1、SVM基本原理**

SVM是一种有监督的统计学习方法，能够最小化经验误差和最大化几何边缘，被称为最大间隔分类器，可用于分类和回归分析。

SVM理论提供了一种避开高维空间的复杂性，直接使用此空间上的内积函数（核函数），再利用在线性可分的情况下的求解方法直接求解对应的高维空间的决策问题。当核函数已知时，可以简化高维空间问题的求解难度。

SVM是个机器学习过程，在高维空间中寻找一个分类超平面，将不同类别的数据样本点分开，使不同类别的点之间的间隔最大，该分类超平面即为最大间隔超平面，对应分类器称为最大间隔分类器。针对二分类问题，下图可以直观地描述SVM的空间特征。

![70 9][]

**SVM的训练数据样本及空间特征**

假设数据样本为 ![x\_1,x\_2, \\cdots, x\_n][x_1_x_2_ _cdots_ x_n]，分类超平面可以表达为：

![w^Tx-b=0][w_Tx-b_0]

其中，x 为分类超平面上的点；w 为垂直于分类超平面的向量；b 为位移量，用于改善分类超平面的灵活性，超平面不用必须通过原点。

两个分类超平面之间具有最大间隔，需要知道训练样本中的支持向量、距离支持向量最近的平行超平面，这些平行超平面可以表示为：

![\\left\\\{\\begin\{matrix\} w^Tx-b=1 & \\\\ w^Tx-b=-1& \\end\{matrix\}\\right.][left_begin_matrix_ w_Tx-b_1 _ _ w_Tx-b_-1_ _end_matrix_right.]

其中，w 为分类超平面的法向量，长度未定；1 和 -1 只是为了计算方便而取的常量，其他常量只要互为相反数即可。

如果给定的训练样本是线性可分的，那么就可以找到两个间距最大的平行超平面，并且这两个超平面之间没有任何训练样本，它们之间的距离为![\\frac\{2\}\{\\left \\| w \\right \\|^2\}][frac_2_left _ w _right _2]。所以最小化![\\left \\| w \\right \\|^2][left _ w _right _2]，就可以使这两个超平面之间的间隔最大化。

为了使所有训练样本点在上述两个平行超平面间隔区域之外，我们需要确保所有的训练数据样本点 ![x\_1,x\_2, \\cdots, x\_n][x_1_x_2_ _cdots_ x_n]，都满足以下条件之一，即

![\\left\\\{\\begin\{matrix\} w^Tx\_i-b\\geqslant 1 & \\\\ w^Tx\_i-b\\leqslant =-1& \\end\{matrix\}\\right.][left_begin_matrix_ w_Tx_i-b_geqslant 1 _ _ w_Tx_i-b_leqslant _-1_ _end_matrix_right.]

**最后总结一下SVM算法的优缺点：**

**1、SVM算法的优点**

*  可以解决小样本情况下的机器学习问题；
 *  可以提高泛化性能；
 *  可以处理高维空间数据；
 *  可以解决非线性问题。

**2、SVM算法的缺点**

*  对于线性问题没有通用的解决方案，必须谨慎选择核函数；
 *  在选择合适的核函数之后，在处理分类问题时，要求解函数的二次规划，而在这过程中，需要大量的存储空间。

[Link 1]: http://www.360doc.com/content/18/0205/18/5315_727939162.shtml
[70]: /images/20220516/9dbc3c8edd694435b05c3ed1e2512c0b.png
[70 1]: /images/20220516/2c700a9208ac4c21b3706d0b2d61a3dc.png
[70 2]: /images/20220516/0053172be31f4362b9f54bd211dfa309.png
[pounds _t_sum _i L_widehat_y_i_y_i_ _sum _k _Omega _f_k_]: https://private.codecogs.com/gif.latex?%5Cpounds%20%28t%29%3D%5Csum%20_i%20L%28%5Cwidehat%7By_i%7D%2Cy_i%29&plus;%20%5Csum%20_k%20%5COmega%20%28f_k%29%20%5C%5C
[Omega _f_gamma T_ _frac_1_2_ _lambda _left _ w _right _2]: https://private.codecogs.com/gif.latex?%5COmega%20%28f%29%3D%5Cgamma%20T&plus;%20%5Cfrac%7B1%7D%7B2%7D%20%5Clambda%20%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%5E2
[70 3]: /images/20220516/7679ac3ade2542518ef0730d828f3ff4.png
[I_j_ i_q_x_i_j]: https://private.codecogs.com/gif.latex?I_j%3D%5C%7B%20i%7Cq%28x_i%29%3Dj%20%5C%7D
[70 4]: /images/20220516/7c5f1c8f7ef74f5c8e96495e50057a66.png
[70 5]: /images/20220516/3fbdb4407d35406c89383bf291f21e9e.png
[70 6]: /images/20220516/26c7a473811d4c4e8e375ea10c52ab38.png
[70 7]: /images/20220516/06045990dca14da78e0da2573ff24ab7.png
[G_L]: https://private.codecogs.com/gif.latex?G_L
[G_R]: https://private.codecogs.com/gif.latex?G_R
[70 8]: /images/20220516/5743ddeb69604cef9dd7eacd1549b7ca.png
[70 9]: /images/20220516/ba21f1f0d5da4f5998dc84003cb997a1.png
[x_1_x_2_ _cdots_ x_n]: https://private.codecogs.com/gif.latex?x_1%2Cx_2%2C%20%5Ccdots%2C%20x_n
[w_Tx-b_0]: https://private.codecogs.com/gif.latex?w%5ETx-b%3D0
[left_begin_matrix_ w_Tx-b_1 _ _ w_Tx-b_-1_ _end_matrix_right.]: https://private.codecogs.com/gif.latex?%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20w%5ETx-b%3D1%20%26%20%5C%5C%20w%5ETx-b%3D-1%26%20%5Cend%7Bmatrix%7D%5Cright.
[frac_2_left _ w _right _2]: https://private.codecogs.com/gif.latex?%5Cfrac%7B2%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%5E2%7D
[left _ w _right _2]: https://private.codecogs.com/gif.latex?%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%5E2
[left_begin_matrix_ w_Tx_i-b_geqslant 1 _ _ w_Tx_i-b_leqslant _-1_ _end_matrix_right.]: https://private.codecogs.com/gif.latex?%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20w%5ETx_i-b%5Cgeqslant%201%20%26%20%5C%5C%20w%5ETx_i-b%5Cleqslant%20%3D-1%26%20%5Cend%7Bmatrix%7D%5Cright.