【18】机器学习算法面试八股_人工智能面试八股文

331决策树的划分标准是什么

有三种：最大信息增益、最大信息增益率、基尼系数。而这三种不同的划分标准就对应了三种典型决策树：ID3（最大信息增益）、C4.5（最大信息增益率）、CART（基尼系数）。
信息增益：指的是使用某一个属性a进行划分后，所带来的纯度（信息熵用来度量样本集合的纯度）提高的大小。一般而言，信息增益越大，意味着使用属性a来进行划分所获得的“纯度提升”越大。但信息增益对可取值较多的属性有所偏好。
而信息增益率则解决了特征偏好的问题。
但是不论是信息增益还是信息增益率，存在的问题是涉及对数运算，计算量大，为了解决这个问题。可以采用基尼系数作为节点划分的标准。

332ID3和C4.5的区别

最大的区别是划分标准的不同：ID3采用信息增益，而C4.5采用的是信息增益率。
C4.5继承了ID3的优点，并在以下几个方面对ID3算法进行了改进：

1. 用信息增益率来选择属性，克服了用信息增益选择属性是偏向选择去之多的属性的不足
2. 在树的构造过程中进行剪枝
3. 能够对连续的属性进行离散化处理
4. 能够对不完整的数据进行处理

333树模型对离散特征怎么处理的

树模型是要寻找最佳分裂点，对于离散特征，树模型会评估每个离散值的信息增益，将信息增益最大的数值作为分裂点，因此，树模型不需要对离散特征进行事先one-hot处理，否则会使特征维度增大且稀疏，不仅会增加模型的计算量，而且会损失数据的信息量造成模型的效果不佳，以及过拟合的风险。也不需要进行归一化处理。

334决策树出现过拟合的原因及解决办法

原因

1. 在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）；
2. 样本中有一些噪声数据，没有对噪声数据进行有效的剔除；
   解决办法
3. 选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，我们一般采用后剪枝的方法；
4. 利用K-folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用K-1份作为训练样本数据集，另外一份作为测试集；
5. 减少特征，计算每一个特征和响应变量的相关性，常见得为皮尔逊相关系数，将相关性较小的变量剔除；

335如何对决策树进行剪枝？

剪枝是防止决策树过拟合的方法。一棵完全生长的决策树很可能失去泛化能力，因此需要剪枝。
剪枝的策略
剪枝分为预剪枝和后剪枝两种，预剪枝是在构建决策树时抑制它的生长，后剪枝是决策树生长完全后再对叶子节点进行修剪。
预剪枝

1. 设置一个树的最大高度/深度或者为树设置一个最大节点数，达到这个值即停止生长（限制深度）

2. 对每个叶子节点的样本数设置最小值，生长时叶子节点样本数不能小于这个值（限制宽度）

3. 判断每次生长对系统性能是否有增益
   后剪枝

4. 错误率降低剪枝（Reduced-Error Pruning）
   后剪枝错误率降低剪枝的方法比较直观，从下至上遍历所有非叶子节点的子树，每次把子树剪枝（所有数据归到该节点，将数据中最多的类设为结果），与之前的树在验证集上的准确率进行比较，如果有提高，则剪枝，否则不剪，直到所有非叶子节点被遍历完。

5. 悲观剪枝（Pessimistic Error Pruning）

6. 代价复杂度剪枝（Cost-Complexity Pruning）
   预剪枝和后剪枝的优缺点比较

7. 时间成本方面，预剪枝在训练过程中即进行剪枝，后剪枝要在决策树完全生长后自底向上逐一考察。显然，后剪枝训练时间更长。预剪枝更适合解决大规模问题。

8. 剪枝的效果上，预剪枝的常用方法本质上是基于贪心的思想，但贪心法却可能导致欠拟合，后剪枝的欠拟合风险很小，泛化性能更高。

9. 另外，预剪枝的有些方法使用了阈值，如何设置一个合理的阈值也是一项挑战。

336决策树需要进行归一化处理吗

不需要归一化，因为他们不关心变量的值，而是关心变量的分布和变量之间的条件概率。决策树是一种概率模型，数值缩放，不影响分裂点位置。所以一般不对其进行归一化处理。

337决策树与逻辑回归的区别

1. 对于拥有缺失值的数据，决策树可以应对，而逻辑回归不可以，需要挖掘人员预先对缺失数据进行处理；
2. 逻辑回归对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于逻辑回归；
3. 逻辑回归擅长分析线性关系，而决策树对线性关系的把握较差。线性关系在实践中有很多优点：简洁，易理解，可以在一定程度上防止对数据的过度拟合。
4. 逻辑回归对极值比较敏感，容易受极端值的影响，而决策树在这方面表现较好。
5. 执行速度上：当数据量很大的时候，逻辑回归的执行速度非常慢，而决策树的运行速度明显快于逻辑回归。

338说下决策树的损失函数

339集成学习

链接
XGB
lgb

340LightGBM和xgBoost、GBDT的区别

xgboost与LightGBM的区别

1. 切分算法（切分点的选取）：XGBoost通过对所有特征都按照特征的数值进行预排序选取最好的分割点；LightGBM通过直方图算法寻找最优的分割点
2. LightGBM占用的内存更低，只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8
3. LightGBM直接支持类别特征
4. 决策树生长策略不同
   XGBoost采用的是带深度限制的level-wise生长策略。level-wise过一次数据可以能够同时分裂同一层的叶子，容易进行多线程优化，不容易过拟合；但不加区分的对待同一层叶子，带来了很多没必要的开销（实际上很多叶子的分裂增益较低，没必要进行搜索和分裂）
   LightGBM采用leaf-wise生长策略，每次从当前所有叶子中找到分裂增益最大（数据量最大）的一个叶子，进行分裂，如此循环；但会生长出比较深的决策树，产生过拟合（因此LightGBM在leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合）
   xgBoost、GBDT的区别
5. 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
6. 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数，训练速度更快。
7. xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。防止过拟合
8. Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。
9. 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
10. 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向；传统的GBDT没有设计对缺失值进行处理
11. xgboost工具支持并行。GBDT属于串行。
12. GBDT是机器学习算法，XGBoost是该算法的工程实现。

341xgBoost的block结构

在树生成过程中，最耗时的一个步骤就是在每次寻找最佳分裂点时都需要对特征的值进行排序。而 XGBoost 在训练之前会根据特征对数据进行排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。
作者提出通过按特征进行分块并排序，在块里面保存排序后的特征值及对应样本的引用，以便于获取样本的一阶、二阶导数值。具体方式如图：
通过顺序访问排序后的块遍历样本特征的特征值，方便进行切分点的查找。此外分块存储后多个特征之间互不干涉，可以使用多线程同时对不同的特征进行切分点查找，即特征的并行化处理。在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 XGBoost 能够实现分布式或者多线程计算的原因。

342XGBoost的优缺点

1. 精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；
2. 灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；
3. 正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合，这也是XGBoost优于传统GBDT的一个特性。
4. Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。传统GBDT的实现也有学习速率；
5. 列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。这也是XGBoost异于传统GBDT的一个特性；
6. 缺失值处理：对于特征的值有缺失的样本，XGBoost 采用的稀疏感知算法可以自动学习出它的分裂方向；
7. XGBoost工具支持并行：XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
8. 可并行的近似算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以XGBoost还提出了一种可并行的近似算法，用于高效地生成候选的分割点。
   缺点
9. 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
10. 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

343集成学习 Bagging Boosting

Bagging 是 bootstrap aggregation的缩写。bagging对于数据集进行bootstrap取样，每个数据点有同等几率被采样，然后创建n个模型，每个模型进行m个数据采样，最后进行投票（voting）得出最后结果。Bagging 的典型应用是随机森林

boosting创建了一系列预测器，或者说是学习器。前面的学习器用简单的模型去适配数据，然后分析错误。然后会给予错误预测的数据更高权重，然后用后面的学习器去修复。boosting通过把一些弱学习器串起来，组成一个强学习器。boosting的典型应用是Adaboost。

344RF和GBDT的区别

（1）相同点

1. 都是由多棵树组成
2. 最终的结果都是由多棵树一起决定
   （2）不同点
3. 组成随机森林的树可以分类树也可以是回归树，而GBDT只由回归树组成
4. 组成随机森林的树可以并行生成，而GBDT是串行生成
5. 随机森林的结果是多数表决表决的，而GBDT则是多棵树累加之和
6. 随机森林对异常值不敏感，而GBDT对异常值比较敏感
7. 随机森林是通过减少模型的方差来提高性能，而GBDT是减少模型的偏差来提高性能的
8. 随机森林不需要进行数据预处理，即特征归一化。而GBDT则需要进行特征归一化（因为涉及到梯度计算）

345GBDT是否适合于处理大规模的ID特征

不适合处理
GBDT对于海量的id类特征，GBDT由于树的深度和树的数量限制（防止过拟合），不能有效存储；
另外海量特征也会存在性能瓶颈，当GBDT的one hot特征大于100k维时，需要做分布式训练才能保证不爆内存，
因此，GBDT通常配合少量的反馈CTR特征来表达，在带来一定范化能力的同时会有信息损失，对于头部资源无法有效表达。

346LightGBM的直方图 排序后会比xgboost的效果差吗，为什么

会

1. 基于树模型的boosting算法，很多算法比如xgboost都是用预排序（pre-sorting）算法进行特征的选择和分裂
2. LightGBM采用HistoGram算法，
   其思想是将连续的浮点特征离散成k个离散值，并构造宽度为k的Histogram。
   然后遍历训练数据，计算每个离散值在直方图中的累计统计量。
   在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
   所以如果LightGBM的直方图排序后，最优的分割点就变了，效果可能会比xgboost差。

347xgboost正则化项和什么有关

树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。

348随机森林哪两个随机

2个随机(bootstrap+特征m)

1. 应用 bootstrap 法有放回地随机抽取 k个新的自助样本集(boostrap)，并由此构建 k 棵分类树(ID3 、 C4.5 、 CART)样本扰动。
2. 先随机选择属性子集，个数为k，然后再从这个子集中选择一个最优属性用于划分。

349bootstrap怎么做的

Bootstrap是一种抽样方法，即随机抽取数据并将其放回。如一次抽取一个样本，然后放回样本集中，下次可能再抽取这个样本。

350xgboost缺失值处理方法

论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，

只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。
在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。

如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。