决策树面试整理

发表于 | 分类于 | 阅读次数:

口述决策树

决策树一种基本的分类与回归方法。它可以看作是 if-then 规则的集合，也可以看作是定义在特征空间与类空间上的条件概率分布。决策树是一种树形结构，由节点和有向边组成，结果有内部节点和叶子结点，内部节点表示的是一个特征，叶子节点表示的是一个类别。决策树学习的本质就是从训练数据中训练归纳出一组规则。决策树的损失函数是正则化的极大似然分布，学习的策略就是最小化损失函数。但是从所有可能的决策树中选出最优的决策树是 NP 难的问题，所以现实中我们学习决策树通常是采用启发式算法，也就是分成三步来进行：特征选择、决策树生成、决策树剪枝。

其中特征选择，是说我们依据什么来选择每个内部节点对应的属性，也就是选择利用哪个特征来对数据进行切分。我们要选择分类特征比较强的特征（如果一个特征没有分类能力，就是说利用这个特征进行分类，和随机分类的结果差不多）。如何判断一个特征的分类能力，通常有三种准则：信息增益、信息增益率、基尼系数，这三种特征选择的准则也分别对应了三种不同的决策树算法：ID3、C4.5、CART

信息增益是指知道了这个特征，使得整个数据集不确定性减少的程度。

信息增益比的出现，是因为信息增益会比较倾向于选择那些取值比较多的特征，但是那些特征不一定是分类能力最强的特征，所以提出了信息增益比，是对信息增益除上了一个基数，除上的是 $H_A(D) = \sum_{i=1}^n\frac {|D_i|}{|D|}\log _2 \frac{|D_i|}{|D|}|$ ，D 是数据集， $D_i$ 是数据集 D 依据特征 A（有 n 个取值），分成了 n 个子集，其中的第 i 个。也就是表示的是特征 A 的熵。

基尼系数，反应的是从数据集中随机抽取两个样本，它们的类别不一致的概率，也是反映了随机变量的不确定性，基尼系数越大，说明随机抽的两个样本不属于同样的类别的概率最大，随机变量越不稳定。$Gini(p) = \sum _{k=1} ^k p_k (1-p_k) = 1 - \sum_{k=1}^k p_k^2$ .

1. 什么是决策树

决策树一种分类和回归模型，可以从三个角度来理解：

  1. 一棵树
  2. if-then规则的集合，该集合是决策树上的所有所根节点到叶子结点的路径的集合
  3. 定义在特征空间与类空间的条件概率分布，决策树实际上是将特征空间划分成了互不相交的单元，每个从根节点到叶子结点的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中，哪个类别有较高的概率，就把该单元中的实例强行划分为该类别

2. 如何学习一棵树

决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化。由于最小化这个损失函数是一个NP难（不能在多项式时间内解决）的问题，现实中，通常采用启发式算法（在解决问题的时候采取的是一种根据经验规则进行发现的方法。其特点是，在解决问题时，利用过去的经验，选择已经行之有效的方法，而不是系统的、以确定的步骤去寻求答案）来近似求解这一最优化问题，得到的决策树是次优的。

决策树采用的是启发式的学习方法。

分为三步：特征选择、模型生成、剪枝

3. 决策树的优缺点

优点

主要有两个优点：

  1. 模型具有可解释性
  2. 分类速度快

其他的优点：

  1. 不用对数据进行过多的预处理，其他技术往往需要进行归一化等
  2. 能够同时处理数据型和常规型属性，其他技术往往需要数据型属性
  3. 对缺失值不敏感

缺点

  1. 对连续型的字段比较难预测

  2. 类别太多的时候，模型会很复杂

4. 构造决策树时的停止条件是什么

  1. 节点中样本个数小于阈值
  2. 样本集的基尼系数小于阈值
  3. 没有更多的特征了

5. 如何处理连续值特征

  1. 对于连续值 a，假设 a 在数据集 D 中共出现了n个不同的取值；

    对 n 个不同的取值从小到大排序：$(a_1, a_2, … , a_n)$

    由于划分点在 $[a_i, a_{i+1})$ 上任意取值，对划分结果不变，所以可以考虑 n-1 取值的划分点候选集。划分点 t 是二分点（将特征 a 不大于 t 的划分在一起，大于 t 的划分在一起）。

    然后怎么在候选集中进行选择最优的划分点？

    根据信息增益，选择最大的 g(D, a, t)：表示数据集 D 将特征 a 基于 t 划分之后，带来的信息增益。

    (上面这个说的是 C4.5 中的二分法连续值处理)

  2. 如果是CART的话，对于连续值的处理，可以参照CART回归树，遍历所有的输入变量 j 和切分点 s，根据最小化平方误差准则来选取

img

6. 如何处理缺失值

缺失值主要有这三种情况：

  1. 在选择分裂属性的时候，训练样本存在缺失值（也就是在计算各个属性带来的信息增益的时候），如何处理？

    计算数据集 D 在属性 a 上不缺失的部分 D’ 中，a 的信息增益，然后将得到的结果乘以不缺失的占比：|D’|/|D|

  2. 分类属性已经确定，但样本在该属性上的值缺失，如何处理？

    假设分类属性为 a，并且 a 有 3 个可能的取值，则将缺失 a 值的样本 x 分配到三个字节点，并且带有权重，权重为每个子节点的个数占三个字节点总数的占比。其他的节点的权重为1

  3. 训练完成之后，给测试样本分类，存在缺失值，如何处理？

    根据投票来确定，或者填充缺失值

Reference

https://applenob.github.io/decision_tree.html （整体介绍）

https://blog.csdn.net/u012328159/article/details/79396893 （连续值处理）

https://blog.csdn.net/u012328159/article/details/79413610 （缺失值处理详解）

https://www.zhihu.com/question/34867991/answer/151775210 （缺失值处理）