1. 什么是决策树/简要介绍决策树
- 首先决策树是一种树结构，
- 其次是它满足if-then规则（找对象）
- 此外它是定义在特征空间与类空间上的条件概率分布，决策树实际上是将特征空间划分成了互不相交的单元，每个从根到叶的路径对应着一个单元。
- 决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。
- 实际中，哪个类别有较高的条件概率，就把该单元中的实例强行划分为该类别。
2. 和其他模型比，它的优点？
优点：
- 可解释性高
- 能处理非线性的数据
- 不需要数据归一化
- 可以用于特征工程，特征选择
- 对数据分布没有偏好
缺点：
- 启发式生成，不是最优解
- 容易过拟合
- 微小的数据改变会改变整个树的形状
- 对类别不平衡的数据不友好
3. 如何学习一个决策树
决策树的学习本质上就是从训练数据集中归纳出一组分类规则，使它与训练数据矛盾较小的同时具有较强的泛化能力。从另一个角度看，学习也是基于训练数据集估计条件概率模型（至此，回答完了模型部分，下面接着说策略和算法）。
决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化（说完了策略，该说算法了）。
由于这个最小化问题是一个NP完全问题，现实中，我们通常采用启发式算法（这里，面试官可能会问什么是启发式算法，要有准备，SMO算法就是启发式算法）来近似求解这一最优化问题，得到的决策树是次最优的。
-
该启发式算法可分为三步：
- 特征选择
- 模型生成
- 决策树的剪枝
3.1 什么是启发式算法
有两种不同的定义：
- 一种定义为，是一种基于直观或经验构造的算法，在可接受的计算成本（计算时间、占用空间等）内，给出一个近似最优解，该近似解与最优解的偏离程度一般不能被事先预计；
- 另一种是，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解是最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。
我比较赞同第二种定义，因为启发式算法现在还没有完备的理论体系，只能视作一种技术。
4. 能具体谈谈这三个步骤吗？
从总体上看，这三个步骤就是一个递归地选择最优特征，并根据这个最优特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，这个过程就是划分特征空间，构建决策树的过程。
4.1 如何选择最优特征呢？
根据特征的分类能力去选择最优特征，特征分类能力的衡量通常采用信息增益或信息增益比。
4.2 谈谈你对信息增益和信息增益比的理解
-
要理解信息增益，首先要理解熵这个概念。从概率统计的角度看，熵是对随机变量不确定性的度量，而不确定性是一个事件出现不同结果的可能性
-
举例子
信息熵 -
熵越大，随机变量的不确定性越大。对同一个随机变量，当它的概率分布为均匀分布时，不确定性最大，熵也最大。对有相同概率分布的不同的随机变量，取值越多的随机变量熵越大。（这是精华）。熵的公式如下：
熵的定义
举例
-
-
其次，要理解条件熵的概念。条件熵是指，有相关性的两个随机变量X和Y，在已知随机变量Y的条件下随机变量X的不确定性。定义为Y给定条件下X的条件概率分布的熵对Y的数学期望。公式如下：
条件熵
如果熵和条件熵中的概率由数据估计（特别是极大似然估计）得到，所对应的熵与条件熵分别为经验熵与经验条件熵
信息增益， 就是指集合X的经验熵H(X)与特征Y给定条件下X的经验条件熵H(X|Y)之差，简单讲就是熵与条件熵的差，公式如下：
4.3 递归的终止条件是什么呢？
有两个终止条件，
- 一是所有训练数据子集被正确分类。
- 二是没有合适的特征可选，即可用特征为0，或者可用特征的信息增益或信息增益比都很小了。
4.4 什么是决策树剪枝，怎么剪枝？
由于根据训练数据生成的决策树往往过于复杂，导致泛化能力比较弱(容易过拟合)，所以，实际的决策树学习中，会将已生成的决策树进行简化，以提高其泛化能力，这一过程叫做剪枝。
具体说就是在已生成的决策树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点。
具体剪枝时，有一般的剪枝算法和CART剪枝算法两种
4.4.1 一般剪枝算法
-
剪枝算法都基于同一个思想，就是减小决策树模型的整体损失函数，这个整体损失函数是正则化的极大似然函数，其形式如下：
整体损失函数 表示决策树T对训练数据集的预测误差，
表示决策树的叶节点个数，即模型复杂度。
是权衡因子。
基尼指数也是一种衡量随机变量不确定性的指标
基尼指数
- 给定α后，通过不断剪枝来减小决策树模型的整体损失。
具体步骤是：
- 假设一组叶节点回缩到其父节点之前与之后的整体树分别为
与
，对应的损失函数值分别是
与
，如果
-
，则进行剪枝，将父节点变为新的叶节点。
递归地进行以上步骤，直到不能继续为止，得到损失函数最小的子树。
-
具体实现这个算法时可采用动态规划（说出动态规划，应当是加分项）。
4.4.2 CART剪枝算法
相比一般剪枝算法，CART剪枝算法的优势在于，不用提前确定α值，而是在剪枝的同时找到最优的α值。
对决策树的每一个内部节点
，计算
代表以内部节点t为根节点的子树。 这样计算出的值表示剪枝后整体损失函数减少的程度。
- 选择g(t)
T_g(t)$。
- 然后，对这棵新树继续上面的剪枝过程，又得到一棵新树。
一直到单节点树，可以得到一系列的树，它们互相嵌套。用交叉验证法从中选出最优的子树，它对应的
为
。
5. 对比分析ID3,C4.5,CART三种决策树的区别
参考这个吧，写的真好：
面试之常见决策树异同
6. 决策树如何处理缺失值？
在xgboost里，
- 在每个结点上都会将对应变量是缺失值的数据往左右分支各导流一次，
- 然后计算两种导流方案对目标函数的影响，
- 最后认为对目标函数降低更明显的方向（左或者右）就是缺失数据应该流向的方向，在预测时在这个结点上将同样变量有缺失值的数据都导向训练出来的方向。
例如，某个结点上的判断条件是 A>0 ，有些数据是A<=0，有些是A>0，有些数据的A是缺失值。那么算法首先忽略带缺失值的数据，像正常情况下一样将前两种数据分别计算并导流到左子树与右子树，然后
- 将带缺失值的数据导向左子树，计算出这时候模型的Objective_L；
- 接着将带缺失值的数据导向右子树，计算出这时候模型的Objective_R；
- 最后比较Objective_L和Objective_R。
假设Objective_L更小，那么在预测时所有变量A是缺失值的数据在这个结点上都会被导向左边，当作A<=0处理。
随机森林
关于随机森林的东西太多了，前人也给出了一些非常好的总结，面试时参考以下三个吧，总结的很好,重点是前两个吧
RF、GBDT、XGBoost面试级整理
随机森林和GBDT的几个核心问题
RF、GBDT、XGBoost常见面试题整理
参考：
https://blog.csdn.net/Heitao5200/article/details/84994505
https://www.jianshu.com/p/fb97b21aeb1d
https://blog.csdn.net/u013713010/article/details/44905133
https://www.huxiu.com/article/175046.html
决策树是如何处理不完整数据的？ - TomHall的回答 - 知乎
https://www.zhihu.com/question/34867991/answer/224122110
https://blog.csdn.net/u012328159/article/details/79413610
