决策树常见面试题

谈谈你对决策树的理解？

决策树算法，无论是哪种，其目的都是为了让模型的不确定性降低的越快越好，基于其评价指标的不同，主要是ID3算法，C4.5算法和CART算法，其中ID3算法的评价指标是信息增益，C4.5算法的评价指标是信息增益率，CART算法的评价指标是基尼系数。

决策树的优缺点？

优点：①计算简单、速度快 ②可解释性强③比较适合处理有缺失属性的样本。（逻辑回归需要对缺失值做预处理）
缺点：①容易过拟合 ②忽略了数据之间的关联性
③对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征（只要是使用了信息增益，都有这个缺点，如RF）。对应的案例如下：有这么一个场景，在一个样本集中，其中有100个样本属于A，9900个样本属于B，用决策树算法实现对AB样本进行区分的时候，会发生欠拟合的现象。因为在这个样本集中，AB样本属于严重失衡状态，在建立决策树算法的过程中，模型会更多的偏倚到B样本的性质，对A样本的性质训练较差，不能很好的反映样本集的特征。

谈谈你对信息增益和信息增益比的理解？

首先要理解熵：熵是对不确定性的度量，熵越大，随机变量的不确定性就越大。对同一个随机变量，当他的概率分布为均匀分布时，不确定性最大，熵也最大。对有相同概率分布的不同的随机变量，取值越多的随机变量熵越大。
熵的计算公式： $H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$
条件熵的计算公式： $H(X|Y) = -\sum\limits_{x_i \in X}\sum\limits_{y_i \in Y}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)$
什么是信息增益？熵H(X)度量了X的不确定性，条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性，那么H(X)-H(X|Y)度量了X在知道Y以后不确定性减少程度，在信息论中称为互信息，记为I(X,Y)，在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。
ID3的不足 ①ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
②ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
③ ID3算法对于缺失值的情况没有做考虑
④没有考虑过拟合的问题
什么是信息增益比？ 信息增益比计算公式： $I_R(D,A) = \frac{I(A,D)}{H_A(D)}$ ，这里 $H_A(D)$ 是特征熵，特征越多对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。
$H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$
ID3和C4.5的缺点： ①容易过拟合 ②生成多叉树，不利于计算机计算 ③大量对数运算以及排序算法，对cpu不友好。

采用信息增益率的算法C4.5为什么可以解决ID3算法中存在的问题？

引入了条件熵，平衡了信息增益容易偏向于取值较多特征的问题。
对于连续特征，将特征离散化

为什么CART树要用基尼系数？什么是基尼系数？

基尼系数 $Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$ ，基尼系数越小，代表不纯度越高，我们要尽可能选基尼系数小的特征，这里与信息增益、信息增益比是相反的（他俩选择最大的）。
基尼系数的优点：在保证准确率的情况下大大减小了计算量。
其次，CART树既可以做分类，也可以做回归，在做分类时用基尼系数做参照，在做回归时用平方误差做参照。

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

决策树在最极端的情况下，会根据每一个样本生成单独的叶子节点，这就导致了很严重的过拟合，因此需要剪枝。
决策树主要有两种剪枝方法：预剪枝和后剪枝。

简单解释一下预剪枝和后剪枝，以及剪枝过程中可以参考的参数有哪些？

CART树采用后剪枝算法： ①先生成决策树 ②生成各种剪枝效果的决策树 ③交叉验证检验效果
预剪枝：在分支前先利用验证集验证剪枝前后的准确率，如果变低了就不减了。
优缺点：后剪枝考虑了所有的可能性，因此有较高的计算开销，但模型效果最好；预剪枝一定成都上降低了过拟合风险，但由于基于贪心策略，不能保证全局最优。

决策树是如何处理缺失值的？

①抛弃缺失值
②补充缺失值
③概率化缺失值，对缺失值的样本赋予该属性所有属性值的概率分布。
④缺失值单独分支

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

逻辑回归通常用于分类问题，决策树可回归、可分类。
逻辑回归是线性函数，决策树是非线性函数（没有方程式可以表达自变量和因变量之间的关系）。
逻辑回归的核心是sigmoid函数，具有无限可导的优点，常作为神经网络的激活函数。
逻辑回归较为简单，不容易产生过拟合

决策树有哪些参数？

splitter特征选择标准：基尼系数or信息增益比
max_depth，决策树最大深度
min_impurity_decrease节点划分最小不纯度（低于这个值，则决策树不再进行生长）
min_samples_split内部节点再划分所需最小样本数
min_samples_leaf叶子节点最少样本数
max_leaf_nodes最大叶子节点数
class_weight类别权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。

分类树与回归树？

CART树既可以做分类，也可以做回归。
回归时采用最小均方差法：对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。

决策树的优点

简单直观，生成的决策树很直观。
基本不需要预处理，不需要提前归一化，处理缺失值。
使用决策树预测的代价是 $O(log_2m)$ ，m为样本数。
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
可以处理多维度输出的分类问题。
相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
可以交叉验证的剪枝来选择模型，从而提高泛化能力。
对于异常点的容错能力好，健壮性高。

决策树的缺点

决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。