欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-02 10:24:55
...

基础知识点

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

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

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

条件熵

条件熵H(YX)H(Y | X) 就是在已知XX的条件下Y的不确定度,定义:
H(YX)=i=1nP(X=xi)H(YX=xi),i=1,2,,nH(Y | X)=\sum_{i=1}^{n} P\left(X=x_{i}\right) H\left(Y | X=x_{i}\right), i=1,2, \ldots, n

联合熵

联合概率分布P(X,Y)P(X, Y)的经验熵
H(X,Y)=i,jP(X=xi,Y=yj)log(P(X=xi,Y=yj))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)

交叉熵

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

信息增益

特征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(DA)g(D, A)=H(D)-H(D | A)

信息增益率

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

Gini指数

Gini(p)=k=1Kpk(1pk)=1k=1Kpk2\operatorname{Gini}(\mathrm{p})=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}

什么是决策树

通俗的解释就是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(DA)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指数越小表示集合中被选中的样本被分错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。

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

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

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

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

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

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

决策树的生成

最小二乘回归树

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

#分类树的生成
分类树用基尼指数做特征选择,同时决定该特征的最优二值切分点
对于特征A的条件下,集合D的基尼指数定义为
Gini(D,A)=D1DGini(D1)+D2DGini(D2)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)

对于训练集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。也就是被预测出错的人数越多,错的越离谱,均方差就越大,通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限),若最终叶子节点上人的年龄不唯一,则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

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

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

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

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

  1. 决策树对缺失值如何处理?

决策树相关知识点以及面试题
10. 如何避免决策树的过拟合?
剪枝、减少特征、增加样本

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

参考

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

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

相关标签: 决策树