面经，内容包括机器学习，CV，NLP，推荐，开发

本文集文档发布于灏天文库

决策树面试题

文档摘要

决策树面试题 简单介绍决策树算法 决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。 决策树将算法组织成一颗树的形式。其实这就是将平时所说的if-then语句构建成了树的形式。决策树主要包括三个部分：内部节点、叶节点、边。内部节点是划分的特征，边代表划分的条件，叶节点表示类别。 构建决策树 就是一个递归的选择内部节点，计算划分条件的边，最后到达叶子节点的过程。 决策树在本质上是一组嵌套的if-else判定规则，从数学上看是分段常数函数，对应于用平行于坐标轴的平面对空间的划分。

决策树面试题

1. 简单介绍决策树算法

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

决策树将算法组织成一颗树的形式。其实这就是将平时所说的if-then语句构建成了树的形式。决策树主要包括三个部分：内部节点、叶节点、边。内部节点是划分的特征，边代表划分的条件，叶节点表示类别。

构建决策树 就是一个递归的选择内部节点，计算划分条件的边，最后到达叶子节点的过程。 决策树在本质上是一组嵌套的if-else判定规则，从数学上看是分段常数函数，对应于用平行于坐标轴的平面对空间的划分。判定规则是人类处理很多问题时的常用方法，这些规则是我们通过经验总结出来的，而决策树的这些规则是通过训练样本自动学习得到的。

训练时，通过最大化Gini或者其他指标来寻找最佳分裂。决策树可以输特征向量每个分量的重要性。

决策树是一种判别模型，既支持分类问题，也支持回归问题，是一种非线性模型（分段线性函数不是线性的）。它天然的支持多分类问题。

2. 决策树和条件概率分布的关系？

决策树可以表示成给定条件下类的条件概率分布。

决策树中的每一条路径对应的都是划分的一个条件概率分布. 每一个叶子节点都是通过多个条件之后的划分空间，在叶子节点中计算每个类的条件概率，必然会倾向于某一个类，即这个类的概率最大。

3. 信息增益比相对信息增益有什么好处？

  • 使用信息增益时：模型偏向于选择取值较多的特征
  • 使用信息增益比时：对取值多的特征加上的惩罚，对这个问题进行了校正。

4. ID3算法—>C4.5算法—> CART算法

  • ID3

    • ID3算法没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
    • ID3算法采用信息增益大的特征优先建立决策树的节点，偏向于取值比较多的特征
    • ID3算法对于缺失值的情况没有做考虑
    • ID3算法没有考虑过拟合的问题

  • C4.5在ID3算法上面的改进

    • 连续的特征离散化
    • 使用信息增益比
    • 通过剪枝算法解决过拟合

  • C4.5的不足：

    • C4.5生成的是多叉树
    • C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
    • C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算

  • CART算法

    • 可以做回归，也可以做分类，
    • 使用基尼系数来代替信息增益比
    • CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。

5. 决策树的缺失值是怎么处理的

主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。

  • 如何在特征值缺失的情况下进行划分特征的选择？

    • 每个样本设置一个权重（初始可以都为1）

    • 划分数据，一部分是有特征值a的数据，另一部分是没有特征值a的数据,记为\tilde{D}，

    • 对没有缺失特征值a的数据集\tilde{D}，来和对应的特征A的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数\rho 。

\rho=\frac{\sum_{x \in \tilde{D}} w_{x}}{\sum_{x \in {D}} w_{x}}
\tilde{p}_{k}=\frac{\sum_{x \in \tilde{D}_{k}} w_{x}}{\sum_{x \in \tilde{D}} w_{x}} \quad(1 \leq \mathrm{k} \leq|y|)
\tilde{r}_{v}=\frac{\sum_{x \in \tilde D^{v}} w_{x}}{\sum_{x \in \tilde{D}} w_{x}} \quad(1 \leq v \leq V)

​ 假设特征A有v个取值\{a_1,a_2 \dots a_v\}

​ \tilde D：该特征上没有缺失值的样本

​ \tilde D_k：\tilde D中属于第k类的样本子集

​ \tilde D^v：\tilde D中在特征a上取值为a_v的样本子集

​ \rho：无特征A缺失的样本加权后所占加权总样本的比例。

​ \tilde{p}_{k}：无缺失值样本第k类所占无缺失值样本的比例

​ \tilde{r}_{v}：无缺失值样本在特征a上取值a^v的样本所占无缺失值样本的比例

​ 新的信息增益公式：

\begin{aligned} &\operatorname{Gain}(D, a)=\rho \times \operatorname{Gain}(\tilde{D}, a)=\rho \times\left(\operatorname{Ent}(\tilde{D})-\sum_{v=1}^{V} \tilde{r}_{v} \operatorname{Ent}\left(\tilde{D}^{v}\right)\right)\\ &\operatorname{Ent}(\tilde{D})=-\sum_{k=1}^{|y|} \tilde{p}_{k} \log _{2} \tilde{p}_{k} \end{aligned}

  • 给定划分特征，若样本在该特征上的值是缺失的，那么该如何对这个样本进行划分？

    （即到底把这个样本划分到哪个结点里？）
​
    • 让包含缺失值的样本以不同的概率划分到不同的子节点中去。
    比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
​

6. 决策树的目标函数是什么？

C_{\alpha}(T)=\sum_{t=1}^{|T|} N_{t} H_{t}(T)+a|T|
H_{t}(T)=-\sum_{k} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}}

其中|T|代表叶节点个数

N_t表示具体某个叶节点的样本数

H_t(T) 表示叶节点t上的经验熵

\alpha|T|为正则项，\alpha \geqslant 0 为参数

7. 决策树怎么处理连续性特征？

因为连续特征的可取值数目不再有限，因此不能像前面处理离散特征枚举离散特征取值来对结点进行划分。因此需要连续特征离散化，常用的离散化策略是二分法，这个技术也是C4.5中采用的策略。下面来具体介绍下，如何采用二分法对连续特征离散化：

  • 训练集D，连续特征A，其中A有n个取值

  • 对A的取值进行从小到大排序得到：\{a_1,a_2\dots a_n\}

  • 寻找划分点t，t将D分为子集D_{t}^{-}与D_{t}^{+}

    • D_{t}^{-}：特征A上取值不大于t的样本
    • D_{t}^{+}：特征A上取值大于t的样本

  • 对相邻的特征取值a_i与a_{i+1}，t再区间[a_i,a_{i+1})中取值所产生的划分结果相同，因此对于连续特征A,包含有n-1个元素的后选划分点集合

T_a = \{\frac{a_i + a_{i+1}}{2}|1\leq{i}\leq{n-1} \}

  • 把区间[a_i,a_{i+1})的中位点\frac{a_i + a_{i+1}}{2}作为候选划分点

  • 按照处理离散值那样来选择最优的划分点,使用公式：

    Gain(D,a) =\underbrace{max}_{t\in T_a}Gain(D,a,t) = \underbrace{max}_{t\in T_a}\ (Ent(D) - \sum_{\lambda \in \{-,+ \}}\frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda}))

    其中Gain(D,a,t)是样本集D基于划分点t二分之后的信息增益。划分点时候选择使用Gain(D,a,t)最大的划分点。

8. 决策树对离散值的处理

思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。

CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3}，然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开，后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同，在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。

9. 决策树怎么防止过拟合？

  • 对于决策树进行约束：根据情况来选择或组合

    • 设置每个叶子节点的最小样本数，可以避免某个特征类别只适用于极少数的样本。

    • 设置每个节点的最小样本数，从根节点开始避免过度拟合。

    • 设置树的最大深度，避免无限往下划分。

    • 设置叶子节点的最大数量，避免出现无限多次划分类别。

    • 设置评估分割数据是的最大特征数量，避免每次都考虑所有特征为求“最佳”，而采取随机选择的方式避免过度拟合。

  • 预剪枝(提前停止)：控制深度、当前的节点数、分裂对测试集的准确度提升大小

    • 限制树的高度，可以利用交叉验证选择
    • 利用分类指标，如果下一次切分没有降低误差，则停止切分
    • 限制树的节点个数，比如某个节点小于100个样本，停止对该节点切分

  • 后剪枝(自底而上)：生成决策树、交叉验证剪枝：子树删除，节点代替子树、测试集准确率判断决定剪枝

    • 在决策树构建完成之后，根据加上正则项的结构风险最小化自下向上进行的剪枝操作. 剪枝的目的就是防止过拟合，是模型在测试数据上变现良好，更加鲁棒。

10. 如果特征很多，决策树中最后没有用到的特征一定是无用吗？

不是无用的，从两个角度考虑：

  • 特征替代性，如果可以已经使用的特征A和特征B可以提点特征C，特征C可能就没有被使用，但是如果把特征C单独拿出来进行训练，依然有效

  • 决策树的每一条路径就是计算条件概率的条件，前面的条件如果包含了后面的条件，只是这个条件在这棵树中是无用的，如果把这个条件拿出来也是可以帮助分析数据.

11.决策树的优缺点？

  • 优点:

    • 简单直观，生成的决策树很直观。
    • 基本不需要预处理，不需要提前归一化，处理缺失值。
    • 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
    • 可以处理多维度输出的分类问题。
    • 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
    • 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
    • 对于异常点的容错能力好，健壮性高。
    • 用白盒模型，可清洗观察每个步骤，对大数据量的处理性能较好，更贴近人类思维。

  • 缺点:

    • 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
    • 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
    • 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
    • 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
    • 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

12. 树形结构为什么不需要归一化?

  • 计算信息增益前，按照特征值进行排序，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。

  • 数值缩放不影响分裂点位置，对树模型的结构不造成影响。

13. 如果特征很多，决策树中最后没有用到的特征一定是无用吗？

不是无用的,从两个角度考虑：

  • 特征替代性，如果可以已经使用的特征A和特征B可以提点特征C，特征C可能就没有被使用，但是如果把特征C单独拿出来进行训练，依然有效.

  • 决策树的每一条路径就是计算条件概率的条件，前面的条件如果包含了后面的条件，只是这个条件在这棵树中是无用的，如果把这个条件拿出来也是可以帮助分析数据。

参考资料

c4.5为什么使用信息增益比来选择特征？

发布者: 作者: 转发
评论区 (0)
U
0/500