美文网首页深度学习
吃瓜学习笔记3-第四章决策树(ID3决策树、C4.5决策树、CA

吃瓜学习笔记3-第四章决策树(ID3决策树、C4.5决策树、CA

作者: 曼曼668 | 来源:发表于2021-07-22 18:25 被阅读0次

    决策树就是一个判别的过程,比如说我想知道这是一个好瓜还是坏瓜,怎么做呢?你可以从瓜的属性进行划分,可能纹理模糊的是坏瓜,纹理清晰的是好瓜。决策树就是通过一系列的属性不断去划分,最终得到这个是好瓜还是坏瓜。

    西瓜数据集2.0上基于信息增益生成的决策树


    决策树学习基本算法

    ID3决策树

    我们划分的目的是希望分支结点所包含的样本尽可能属于同一类别,也就是结点的纯度越来越高。一说到纯度,我们都可以用信息熵来计算。

    "信息熵" (information entropy)是度量样本集合纯度最常用的一种指标.假定当前样本集合D 中第k 类样本所占的比例为Pk (k = 1, 2,. . . , IγI) ,则D的信息熵定义为

    公式4.1

    Ent(D) 的值越小,则D 的纯度越高.

    举个例子,如果好瓜是1/2,坏瓜1/2,则Ent(D)值是最大的,但如果好瓜是1,坏瓜是0,Ent(D)值是最小的,为0.因为都是好瓜,纯度肯定是最高的,没有其他杂质。

    解释了纯度,接下来是如何找到最优的属性划分。像上图,它是认为纹理是最优属性,就划分。

    ID3决策树是用信息增益为准则来选择划分属性的。

            假定离散属性a有V 个可能的取值{a^1,a^2,...a^V },若使用a来对样本集D 进行划分,则会产生V 个分支结点,其中第v个分支结点包含了D 中所有在属性a 上取值为a^v的样本, 记为D^v. 我们可根据式(4.1) 计算出D^v 的信息熵,再考虑到不同的分支结点所包含的样本数不同,给分支结点赋予权重D^v/|D|,即样本数越多的分支结点的影响越大,于是可计算出用属性a 对样本集D 进行划分所获得的"信息增益" (information gain)

    信息增益

    一般而言,信息增益越大,则意味着使周属性a 来进行划分所获得的"纯度提升"越大.最优属性就是信息增益最大的那个属性。

    西瓜书上P75-P77有个完整的例子说明。

    C4.5决策树

    实际上,信息增益准则对可取值数目较多的属性有所偏好(比如“编号”这个属性可取值很多,且样本数太少,容易过拟合),为减少这种偏好可能带来的不利影响,我们采用"增益率" (gain ratio) 来选择最优划分属性.

    增益率定义为:

    4.3

    其中

    4.4

    IV(a)称为属性a 的"固有值".增益率的公式可以了解到,IV(a)越大,则增益率越小。IV(a)的公式实际上就是信息熵的公式,如果属性a*的取值太多,不确定性就很高。

    C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式:先从候选划分属性中找出信息增益高于信息增益平均水平的属性,再从中选择增益率最高的。

    CART决策树

    CART 决策树使用"基尼指数" 来选择划分属性,数据集D 的纯度可用基尼值来度量:

    Gini(D) 越小,则数据集D 的纯度越高.因为Gini(D)主要反映在数据集D中随机抽取的两个样本是异类的概率。

    属性a的基尼指数定义为

    我们在候选属性集合A 中,选择那个使得划分后基尼指数最小的属性作为最优划分属性.

    但是,一般CART决策树是二叉树,这个公式并不适合,为此这个属性a的基尼指数应该写成:

    就是a=V和a≠V这两种情况来算。把全部情况都算出来,然后把最小的基尼指数属性作为划分点。南瓜书有最详细的例子。

    总结

    决策树最主要的步骤就是找到最优属性。

    ID3决策树是取信息增益最大的属性作为最优属性。

    C4.5决策树最优属性:先从候选划分属性中找出信息增益高于信息增益平均水平的属性,再从中选择增益率最高的。

    CART决策树是最小的基尼指数属性作为最优属性。

    感谢datawhale提供的学习交流平台和资源,学习视频可以参照:Datawhale吃瓜教程

    相关文章

      网友评论

        本文标题:吃瓜学习笔记3-第四章决策树(ID3决策树、C4.5决策树、CA

        本文链接:https://www.haomeiwen.com/subject/oucymltx.html