决策树-QA

作者: 司马山哥 | 来源:发表于2019-03-16 16:40 被阅读0次

Q1：决策树是“二叉”树吗？

分类回归树（CART）是“二叉”分支的决策树，内部结点特征取值为“是”和“否”，左分支为“是”，右分支取值为“否”。而基于ID3（信息增益）、C4.5（信息增益比）算法选择特征的分类决策树不是“二叉”型的，某节点对应特征的离散取值个数为n时，对应的子节点便是n个。

Q2：决策树和朴素贝叶斯同属条件概率模型，有何异同？

决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。决策树只用学习到一个特征空间的划分后，便可以基于划分后的每个集合估计条件概率模型，最后呈现为某条路径（规则）后的条件概率模型；而朴素贝叶斯基于特征条件独立假设，分别估计各类下单特征条件概率，并通过贝叶斯公式得到后验概率。这两个模型的参数复杂度差别较大（？？？），决策树不依赖特征条件独立假设，最后参数的估计都是基于极大似然所得（？）。

Q3：如何理解决策树学习的损失函数为“正则化极大似然函数”？

Q4：如何递归的生成决策树？

从根节点开始，对节点计算所有可能的特征的信息增益（比），选择值最大的特征作为节点的特征（不复用），由该特征的不同取值建立子节点，再对子节点递归地调用以上方法，构建决策树；直到所有的特征的信息增益（比）很小或者没有特征可以选择为止。

Q5：决策树为什么容易过拟合？

决策树的生成过程中，通过不断的分支，将样本实例划分到合适的单元，当样本中存在噪音数据，即可能是特征值观测误差或者标签值观测误差，使得在分支归节点的时候产生“矛盾”，这时决策树选择继续生成新的分支，来产生更“完美”的叶子节点，这便是由于噪音数据带来的误生成的分支，使得训练变现优越，而泛化能力下降。

Q6：决策树的深浅和对应的条件概率模型有何关系？

每条路径后的叶子节点，对应着特征空间的一个划分区域，而在此区域内估计各类的概率，便是此路径下的条件概率，当决策树模型较浅时，对应的路径上的节点数也较少，从而概率路径上的特征也较少，这表示，通过较少的特征估计了所有特征组合里的众多可能的条件概率，因此，较浅的决策树对应着舍弃某些特征组合下的“泛”条件概率模型（参数复杂度底）。

Q7：如何理解“决策树生成阶段为局部选择，剪枝阶段为全局选择”？

决策树在生成的时候，每一次分支都是基于当前分类最好（子节点混乱程度最低）为标准，这是一种贪心策略——在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。补充：从整体上看，调换某两个节点的特征选择可能会产生更好的泛化效果。

Q8：熵为何能表示随机变量的不确定性？

随机变量对应一个概率分布，当随机变量的分布越集中的时候，也就是随机变量的取值具有倾向性，这时候的随机变量的“随机性”貌似下降了（因为我们发现去猜测那些集中的取值时，更有可能猜中随机变量的真实值），那么设计一个指标用来量化随机变量的概率分布的集中性便可以很好的说明随机变量猜测的难度（不确定性大小），熵的定义便是量化随机变量的集中性，对于概率均匀取值的随机变量的熵是最大的。

Q9：极大似然估计和距估计何时相同？

距估计理论根源是辛钦大数定律，样本之间是独立同分布，当数据样本量很大的时候，样本观测值的平均值和总体的数学期望是在一个极小的误差范围内。极大似然要求样本之间独立，而有些似然函数难以求得最优值。并不是所有的分布，用矩估计和极大似然估计得到的参数值都是一样的，一般对于单参数的指数分布族，泊松分布，指数分布，bernoulli分布，矩估计和极大似然是相等的，因为1阶矩就是充分完备的统计量。两参数的指数分布族就要复杂一点了，正态分布的话，均值的估计是一样的，方差的极大似然估计分母为n，矩估计一般指的是无偏化修正之后的S^2，分母为n-1。一般极大似然估计要优于矩估计。
与矩法估计比较，最大似然估计的精确度较高，信息损失较少，但计算量较大。

Q10：信息增益倾向于选择取值较多的特征，为何？

信息增益在计算的过程中，存在对某个特征的某取值时的数据集合内的各类概率估计，当该特征的取值较多时，分到每个值小面的样本数也会少一些，而这使得概率的估计的稳定性变差（或者说离大数定律的要求越远），使得估计出的概率容易出现非均匀的情况，从而造成条件熵下降，即信息增益变大的倾向，但不是所有情况下都是这样的，详情见知乎贴https://www.zhihu.com/question/22928442。

Q11：信息增益比如何消除信息增益的倾向性？

通过将信息增益值与特征的内部熵值比较，消除因为特征取值较多带来的概率估计偏差的影响。其本质是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。这带来一个新的问题是，倾向于选择特征取值少的。

Q12：当特征中有连续值时，如何计算该特征的信息增益（比）？

将连续值离散化，可通二分法计算不同的取值左右的条件熵。ID3只能处理离散变量，而C4.5和CART都可以处理连续变量。C4.5通过对连续属性排序后找到类别不同的分割线作为切分点，根据切分点吧连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散变量。CART每次都会对特征进行二值划分，因此可以很好的使用于连续变量。

Q13：分类决策树在剪枝时，其损失函数极小化为何等价于正则化的极大似然估计？

Q14：分类决策树剪枝算法可以由一种动态规划的算法实现，如何理解？

Q15：CART中的回归树中，特征空间划分后的某单元上的最优值是多少？

在某个单元内，目标为误差平方和最小，即 $min \sum_{i\in R_m}(y_i-c_m)^2$ 求导后的结果为 $c_m=\frac{\sum_{i\in R_m}y_i}{|R_m|}$

Q16：CART中的回归树在生成过程中，特征会重复出现吗？树生成的停止条件是啥？

特征会复用，停止的条件是基尼指数低于阈值，或者样本数太少没有分支的意义，再或者是没有特征可供选择。补充：ID3和C4.5的特征不会复用，且是多分叉的树。

Q17：基尼指数和熵、分类误差率之间的关系？

Q18：决策树的优缺点？

优点：
1）简单直观，生成的决策树很直观。
2）基本不需要预处理，不需要提前归一化，处理缺失值。
3）使用决策树预测的代价低。
4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
5）可以处理多维度输出的分类问题。
6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释。
7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。
8）对于异常点的容错能力好，健壮性高。
缺点:
1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

Q19：决策树常见的函数公式。

数据集D的经验熵
$H(D)=-\sum_{k=1}^K \frac{|C_k|}{|D|}\log_2 \frac{|C_k|}{|D|}$
特征A下的条件熵
$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$
$D_i$ 表示D中特征A取第i个值得样本子集。
信息增益
$g(D,A)=H(D)-H(D|A)$
信息增益比
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
CART--最小基尼指数Gini
$Gini(D)=1-\sum_{k=1}^n (\frac{|C_k|}{|D|})^2$

Q20：ID3为何对缺失值敏感，而C4.5和CART却不会？

Q21：决策树剪枝的方法？

两种：预剪枝和后剪枝。
预剪枝：在树中节点进行扩展前考虑是否继续生长。
（1）树深达到一定程度；
（2）当前节点的样本数低于阈值；
（3）每次分裂时对于测试集的准确度提升小于阈值。
优点：算法简单、效率高，适用解决大规模问题。
缺点：具有局限性，有欠拟合风险。
后剪枝：树生成之后基于泛华能力剪枝。
错误率降低剪枝、悲观剪枝、代价复杂度剪枝、最小误差剪枝、CVP、OPP。