决策树面试题
1. 简单介绍决策树算法
决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
决策树将算法组织成一颗树的形式。其实这就是将平时所说的if-then语句构建成了树的形式。决策树主要包括三个部分:内部节点、叶节点、边。内部节点是划分的特征,边代表划分的条件,叶节点表示类别。
构建决策树 就是一个递归的选择内部节点,计算划分条件的边,最后到达叶子节点的过程。 决策树在本质上是一组嵌套的if-else判定规则,从数学上看是分段常数函数,对应于用平行于坐标轴的平面对空间的划分。判定规则是人类处理很多问题时的常用方法,这些规则是我们通过经验总结出来的,而决策树的这些规则是通过训练样本自动学习得到的。
训练时,通过最大化Gini或者其他指标来寻找最佳分裂。决策树可以输特征向量每个分量的重要性。
决策树是一种判别模型,既支持分类问题,也支持回归问题,是一种非线性模型(分段线性函数不是线性的)。它天然的支持多分类问题。
2. 决策树和条件概率分布的关系?
决策树可以表示成给定条件下类的条件概率分布。
决策树中的每一条路径对应的都是划分的一个条件概率分布. 每一个叶子节点都是通过多个条件之后的划分空间,在叶子节点中计算每个类的条件概率,必然会倾向于某一个类,即这个类的概率最大。
3. 信息增益比相对信息增益有什么好处?
- 使用信息增益时:模型偏向于选择取值较多的特征
- 使用信息增益比时:对取值多的特征加上的惩罚,对这个问题进行了校正。
4. ID3算法>C4.5算法> CART算法
算法没有考虑连续特征,比如长度,密度都是连续值,无法在ID3运用。这大大限制了ID3的用途。 算法采用信息增益大的特征优先建立决策树的节点,偏向于取值比较多的特征 算法对于缺失值的情况没有做考虑 算法没有考虑过拟合的问题
在 算法上面的改进 - 连续的特征离散化
- 使用信息增益比
- 通过剪枝算法解决过拟合
的不足: 生成的是多叉树 只能用于分类,如果能将决策树用于回归的话可以扩大它的使用范围。 由于使用了熵模型,里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算
算法 - 可以做回归,也可以做分类,
- 使用基尼系数来代替信息增益比
分类树离散值的处理问题,采用的思路是不停的二分离散特征。
5. 决策树的缺失值是怎么处理的
主要需要解决的是两个问题,一是在样本某些特征缺失的情况下选择划分的属性,二是选定了划分属性,对于在该属性上缺失特征的样本的处理。
如何在特征值缺失的情况下进行划分特征的选择?
每个样本设置一个权重(初始可以都为1)
划分数据,一部分是有特征值
的数据,另一部分是没有特征值 的数据,记为 , 对没有缺失特征值
的数据集 ,来和对应的特征 的各个特征值一起计算加权重后的信息增益比,最后乘上一个系数 。
假设特征$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$的样本所占无缺失值样本的比例
新的信息增益公式:
给定划分特征,若样本在该特征上的值是缺失的,那么该如何对这个样本进行划分?
(即到底把这个样本划分到哪个结点里?)
- 让包含缺失值的样本以不同的概率划分到不同的子节点中去。
比如缺失特征A的样本a之前权重为1,特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1,A2,A3。对应权重调节为2/9,3/9, 4/9。
6. 决策树的目标函数是什么?
其中
7. 决策树怎么处理连续性特征?
因为连续特征的可取值数目不再有限,因此不能像前面处理离散特征枚举离散特征取值来对结点进行划分。因此需要连续特征离散化,常用的离散化策略是二分法,这个技术也是
训练集D,连续特征
,其中A有n个取值 对
的取值进行从小到大排序得到: 寻找划分点
, 将D分为子集 与 :特征 上取值不大于 的样本 :特征 上取值大于 的样本
对相邻的特征取值
与 ,t再区间 中取值所产生的划分结果相同,因此对于连续特征 ,包含有 个元素的后选划分点集合
把区间
的中位点 作为候选划分点 按照处理离散值那样来选择最优的划分点,使用公式:
其中
是样本集 基于划分点 二分之后的信息增益。划分点时候选择使用 最大的划分点。
8. 决策树对离散值的处理
思想和
CART采用的是不停的二分。会考虑把特征
9. 决策树怎么防止过拟合?
对于决策树进行约束:根据情况来选择或组合
设置每个叶子节点的最小样本数,可以避免某个特征类别只适用于极少数的样本。
设置每个节点的最小样本数,从根节点开始避免过度拟合。
设置树的最大深度,避免无限往下划分。
设置叶子节点的最大数量,避免出现无限多次划分类别。
设置评估分割数据是的最大特征数量,避免每次都考虑所有特征为求最佳,而采取随机选择的方式避免过度拟合。
预剪枝(提前停止):控制深度、当前的节点数、分裂对测试集的准确度提升大小
- 限制树的高度,可以利用交叉验证选择
- 利用分类指标,如果下一次切分没有降低误差,则停止切分
- 限制树的节点个数,比如某个节点小于100个样本,停止对该节点切分
后剪枝(自底而上):生成决策树、交叉验证剪枝:子树删除,节点代替子树、测试集准确率判断决定剪枝
- 在决策树构建完成之后,根据加上正则项的结构风险最小化自下向上进行的剪枝操作. 剪枝的目的就是防止过拟合,是模型在测试数据上变现良好,更加鲁棒。
10. 如果特征很多,决策树中最后没有用到的特征一定是无用吗?
不是无用的,从两个角度考虑:
特征替代性,如果可以已经使用的特征
和特征 可以提点特征 ,特征 可能就没有被使用,但是如果把特征 单独拿出来进行训练,依然有效 决策树的每一条路径就是计算条件概率的条件,前面的条件如果包含了后面的条件,只是这个条件在这棵树中是无用的,如果把这个条件拿出来也是可以帮助分析数据.
11.决策树的优缺点?
优点:
- 简单直观,生成的决策树很直观。
- 基本不需要预处理,不需要提前归一化,处理缺失值。
- 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
- 可以处理多维度输出的分类问题。
- 相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释
- 可以交叉验证的剪枝来选择模型,从而提高泛化能力。
- 对于异常点的容错能力好,健壮性高。
- 用白盒模型,可清洗观察每个步骤,对大数据量的处理性能较好,更贴近人类思维。
缺点:
- 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
- 决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
- 寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。
- 有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
- 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
12. 树形结构为什么不需要归一化?
计算信息增益前,按照特征值进行排序,排序的顺序不变,那么所属的分支以及分裂点就不会有不同。
数值缩放不影响分裂点位置,对树模型的结构不造成影响。
13. 如果特征很多,决策树中最后没有用到的特征一定是无用吗?
不是无用的,从两个角度考虑:
特征替代性,如果可以已经使用的特征
和特征 可以提点特征 ,特征 可能就没有被使用,但是如果把特征 单独拿出来进行训练,依然有效. 决策树的每一条路径就是计算条件概率的条件,前面的条件如果包含了后面的条件,只是这个条件在这棵树中是无用的,如果把这个条件拿出来也是可以帮助分析数据。