决策树相关知识点以及面试题

基础知识点

熵

熵是一个物理概念，代表一个系统的混乱程度，在信息论里用于表示一个随机变量不确定性的度量，熵越大，不确定性越高。假设$ X $ 是一个离散分布的随机变量，取值有限，那么的熵可以表示为
$H(p)=-\sum_{i=1}^{N} p_{i} \log \left(p_{i}\right)$H(p)=−∑i=1N​pi​log(pi​)
从定义可知$0 \leq H(p) \leq \log (n)$0≤H(p)≤log(n) ，右边等号成立当且仅当$p_{1}=p_{2}=\ldots=p_{N}=1 / N$p1​=p2​=…=pN​=1/N

通俗的说约平均就约混乱。
举例
有5张牌， 其中4张是J，1张是K ， 那么随机抽一张，得到J的几率就是4/5,也就是它的不确定度小，熵很小

如果5张牌，3张是J，2张是K，那么随机抽一张得到J的概率是3/5,它的不确定度变大了，熵增加了

条件熵

条件熵$H(Y | X)$H(Y∣X) 就是在已知$X$X的条件下Y的不确定度，定义：
$H(Y | X)=\sum_{i=1}^{n} P\left(X=x_{i}\right) H\left(Y | X=x_{i}\right), i=1,2, \ldots, n$H(Y∣X)=∑i=1n​P(X=xi​)H(Y∣X=xi​),i=1,2,…,n

联合熵

联合概率分布$P(X, Y)$P(X,Y)的经验熵
$H(X, Y)=-\sum_{i, j} P\left(X=x_{i}, Y=y_{j}\right) \log \left(P\left(X=x_{i}, Y=y_{j}\right)\right)$H(X,Y)=−∑i,j​P(X=xi​,Y=yj​)log(P(X=xi​,Y=yj​))

交叉熵

关于样本集有两个分布p和q，p是真实分布，q 是非真实分布，如果用非真实分布 q来编码真实分布 p :
$H(p, q)=-\sum_{i} p_{i} \log \left(q_{i}\right)$H(p,q)=−∑i​pi​log(qi​)

信息增益

特征A对训练集D的信息增益$g(D,A)$g(D,A),定义为集合D的经验熵$H(D)$H(D)与特征A在给定条件下D的经验条件熵$H(D/A)$H(D/A)之差：

$g(D, A)=H(D)-H(D | A)$g(D,A)=H(D)−H(D∣A)

信息增益率

信息增益除以特征A的值的熵$H_A(D)$HA​(D)之比
$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$gR​(D,A)=HA​(D)g(D,A)​
其中
$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}$HA​(D)=−∑i=1n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​

Gini指数

$\operatorname{Gini}(\mathrm{p})=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$Gini(p)=∑k=1K​pk​(1−pk​)=1−∑k=1K​pk2​

什么是决策树

通俗的解释就是if else的层层嵌套。
也就是在给定的训练数据集中，根据特征的选则，递归的选择最优的划分，使得各子数据有最好的分类结果

举例

[外链图片转存失败(img-EejKxQkD-1567916904408)(https://i.loli.net/2019/09/08/xGyaUer2hNO4BTo.png)]

用决策树建立起来后，能得到这样的模型：
[外链图片转存失败(img-XDIxn9cJ-1567916904409)(https://i.loli.net/2019/09/08/xGyaUer2hNO4BTo.png)]

决策树怎么生成的

决策树的生成有3个步骤

• 特征选择: 信息增益（ID3），信息增益率（C4.5），基尼指数
• 决策树的生成 ：回归树和分类树
• 决策树的剪枝： 预剪枝和后剪枝

ID3算法

$g(D, A)=H(D)-H(D | A)$g(D,A)=H(D)−H(D∣A)

简单的理解就是 ，没有属性A的信息量 - 有A的时候的信息量

举例

可以看出，在此数据中，总数据量14个，买电脑的人9个，不买电脑的人5个，因此，H（D）计算方式如下：

然后，我们想计算下age属性的信息量，<30的5人，<30并买电脑的2人，不买的3人，其余31-40，>40方法同理，因此计算方式如下：

因此Gain(age) = 0.940-0.694 = 0.246
再对比下其余属性Gain(Income)=0.029,Gain(Student)=0.151,Gain(Credit_rating)=0.048，因此可以看出，age属性信息量最大，因此选择age属性作为根节点。计算节点方法同理。

C4.5算法

ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。
[外链图片转存失败(img-T3x4RyJw-1567916904422)(https://i.loli.net/2019/09/08/hoy3PlRJrQUmAZw.png)]
其中各符号意义与ID3算法相同，然后，增益率被定义为：
[外链图片转存失败(img-7vYWyhKc-1567916904424)(https://i.loli.net/2019/09/08/mOHtrPlxI6czunR.png)]

和其他模型相比决策树的优点

C4.5选择具有最大增益率的属性，ID3选择最大信息获取量的属性

基尼指数（CART算法）

定义：基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。

    注意： Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
$\operatorname{Gini}(\mathrm{p})=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$Gini(p)=∑k=1K​pk​(1−pk​)=1−∑k=1K​pk2​
说明:

1. pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)

2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和

3. 当为二分类是，Gini§ = 2p(1-p)

需要说明的是CART是个二叉树，也就是当使用某个特征划分样本集合只有两个集合：1. 等于给定的特征值 的样本集合D1 ， 2 不等于给定的特征值 的样本集合D2

实际上是对拥有多个取值的特征的二值处理。

决策树的生成

最小二乘回归树

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域，并决定每个子区域上的输出值，构建二叉决策树

#分类树的生成
分类树用基尼指数做特征选择，同时决定该特征的最优二值切分点
对于特征A的条件下，集合D的基尼指数定义为
$G i n i(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)

对于训练集D的特征A， 分别计算A的每个取值的基尼系数，选择最小的基尼指数的的特征最为切分点，生成2个子节点。 然后再继续递归

注意：

• CART既可以做分类也可以做回归
• 不同于ID3、C4.5可以是多叉树，CART只能是二叉树
• ID3和C4.5的特征是不能在不同层级之间复用的，而CART可以
• C4.5通过剪枝来平衡模型的准确性和泛化能力，而CART直接利用全部数据发现所有可能的树进行对比

剪枝

决策树生成算法递归地生成决策树，直到满足停止条件，这种情况下，对于训练集的数据会有较好的预测，但是对于测试集往往效果不理想，容易产生过拟合，因此要对决策树进行剪枝，简化树状结构，提高泛化能力。

剪枝分为预剪枝和后剪枝。
预剪枝：在树的构建生长阶段进行剪枝，如果结点满足信息Gini指数小于阈值或者该结点的样本树量少于多少，则不对该结点继续细分。
后剪枝：在树完全生长后再从叶子结点逐个往上剪枝，利用测试集数据验证剪枝前后，树的损失函数是否有变化。如果剪枝后损失函数减小，那说明剪枝是提高了模型泛化能力，否则不能剪枝。

通俗的说 ，在训练集上用这个特征进行划分人，得到的准确率有60%， 但是在测试集上这个特征准确率下降到50% ，那么就说明这个特征不需要再分类了，也就是把这个特征划分点给减掉

一些问题

1. 信息增益率有什么优缺点
   是对信息增益的一种改进，对属性值多的样本做一下惩罚，避免分类的时候偏向于优先划分属性值多的特征；
   另外如果样本中某一个特征下的值没有重复的，ID3中使用信息增益更偏向于将每个样本各自分为一类，这样的方式是不合理的，用信息增益率可以避免这个问题。

2. 如何对决策树进行剪枝
   预剪枝和后剪枝

3. 为什么决策树需要进行剪枝?
   防止过拟合

4. C4.5对ID3做了哪些改进？
   将信息增益改成了信息增益率；可以处理连续型特征

5. C4.5决策树算法如何处理连续数值型属性？
   通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性特征转为布尔型，从而将连续型变量转换多个取之区间的离散型变量

6. C4.5与CART的区别
   C4.5只能做分类，CART既可以做分类也可以做回归，分类的时候用Gini指数，回归的时候用平方差。
   C4.5可以是多叉树，而CART只能是二叉树
   C4.5的特征在每个层级之间不会复用，CART的每个特征可以复用。
   C4.5通过剪枝来平衡模型的准确性和泛化能力，而CART直接利用全部数据发现所有可能的树进行对比

7. 简述一下分类树和回归树
   分类树
   以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1)，按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

回归树
回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即(每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

总结：分类树使用信息增益或增益比率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。回归树使用最大均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。

8. CART树对离散特征取值数目>=3的特征如何处理？
   因为CART树是二叉树，所以对于样本的有N>=3个取值的离散特征的处理时也只能有两个分支，这就要通过组合人为的创建二取值序列并取GiniGain最小者作为树分叉决策点。如某特征值具有[‘young’,’middle’,’old’]三个取值,那么二分序列会有如下3种可能性(空集和满集在CART分类中没有意义):

[((‘young’,), (‘middle’, ‘old’)), ((‘middle’,), (‘young’, ‘old’)), ((‘old’,), (‘young’, ‘middle’))]

采用CART算法，就需要分别计算按照上述List中的二分序列做分叉时的Gini指数，然后选取产生最小的GINIGain的二分序列做该特征的分叉二值序列参与树构建的递归。

9. 决策树对缺失值如何处理？

10. 如何避免决策树的过拟合？
剪枝、减少特征、增加样本

11. 决策树需要进行归一化处理吗？
    不需要，因为决策树是一种概率模型，它们不关心变量的值，而是关心变量的分布和变量之间的条件概率。数值缩放不会影响决策树的分裂点位置。

参考

决策树 (Decision Tree) 原理简述及相关算法(ID3,C4.5)

决策树从原理简述到面试详细总结