机器学习面试005—决策树

1. 请问（决策树、随机森林，Boosting、Adaboot）GBDT和XGBoost的区别是什么？

Ans：①首先，随机森林是一个包含多个决策树的分类器；AdaBoost——即Adaptive Boosting(自适应增强)，经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务，对异常点outlier比较敏感；GBDT指梯度上升决策树算法，相当于融合决策树和梯度上升的Boosting算法。
②xgboost类似gbdt的优化版，在精度和效率上都有了提升，具体优点包括：1.损失函数是用泰勒展开式二项逼近，而非gbdt的一阶导数；2.对树的结构进行了正则化约束，防止模型过度复杂，降低过拟合的可能性；3.节点分裂的方式不同，gbdt用的gini系数，xgboost是经过优化推导后的。

2. 为什么梯度提升方法倾向选择决策树 (通常是CART树) 作为基学习器？

Ans：这与决策树自身的优点有关系：①决策树可以认为是if-then规则集合，易于理解，可解释性强，预测速度快。②相对于其他算法更少的特征工程，如可以不用做特征标准化，可处理缺失值，不用关心特征之间是否相互依赖。③决策树能自动组合多个特征，轻松处理特征之间的交互关系，并且是非参数化的，不必担心异常值或是否线性可分。

3. 在GBDT中，如何抑制单棵决策树的过拟合问题？

Ans：剪枝、限制树的最大深度，限制叶子节点的最少样本数量、限制几点分裂时的最少样本数量，吸收bagging思想对训练样本采样、在学习单棵决策树时只使用一部分样本、借鉴随机森林的思路在学习时只采样一部分特征、在目标函数中添加正则项。

4. 为什么xgboost要用泰勒展开，优势在哪里？

Ans：xgboost使用了一阶和二阶偏导，二阶导数有利于梯度下降的更快更准，使用泰勒展开取得二阶导数形式，可以再不选定损失函数具体形式的情况下，用于算法优化分析。本质上把损失函数的选取和模型算法优化/参数选择分开了，这种去耦合增加了xgboost的适用性。

5. Xgboost如何寻找最优特征？是有放回的，还是无放回的？

Ans：xgboost在训练的过程中，给出各个特征的评分，以表明每个特征对模型训练的重要性。xgboost利用梯度优化模型算法，样本是不放回的。但xgboost支持子采样——即每轮计算可以不使用全部样本。

6. ID3和C4.5有什么区别？

Ans：①ID3采用信息熵的增益作为切分依据，倾向于选取特征值较多的属性进行划分；C4.5采用信息熵的增益比作为切分依据，对较少特征数目的属性有所偏好。

7.请谈一谈决策树剪枝有哪些方法？

Ans：剪枝的作用是为了防止决策树过拟合，有两种思路：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)
①预剪枝——指在构造决策树的同时进行剪枝。在创建分支的过程中，为了避免过拟合，可以设定一个阈值，熵减少小于阈值时，则停止继续创建分支。实际效果并不好
②后剪枝——指在决策树构建完成之后回溯，进行剪枝。对拥有相同父节点的一组节点进行检查，判断如果将其合并，熵增加量是否小于某一阈值？是，则合并为一个节点，其中包含了所有可能的结果。后剪枝是删除一些子树，然后用叶子节点代替。此叶子节点的类别通过多数原则确定——用子树中大多数训练样本所属的类别来标识。算法包括Reduced-Error Pruning、Pessimistic Error Pruning(悲观剪枝)
③预剪枝可能产生欠拟合的风险，后剪枝由于需要先生成完整的树，再自底向上进行剪枝，因此花费的时间要久的多。

8. 决策树怎么处理连续值和缺失值？

Ans：①连续值处理——采用连续属性离散化技术，最简答的方法是采用二分法进行处理(C4.5采用的机制)。对特征值进行升序排序，取两个特征值之间的中点作为可能的分裂点，以此离散化。
②缺失值处理——包含两个待解决的问题：1. 如何在属性值缺失的情况下，进行划分属性的选择？显然，仅课根据在各属性上没有缺失值的样本来选择。2.给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？若样本x在属性A上的取值已知，则将x划入与其取值对应的子节点，且样本权重在子节点中保持为Wx；若样本x在属性A上取值未知，则将x划入所有子节点，且样本权重与属性值Av对应的子节点中，调整为Rv*Wx。直观上，就是让同一个样本以不同的概率划入到不同的子节点去。

9. Adaboost的集成效果为什么会比单个学习器效果好？怎么最大化其优势？

Ans：①首先介绍一下boost的理论依据。假设单个学习器的错误率为：

image

假设错误率相互独立，由Hoeffding不等式可以得到整体学习器的错误率：