美文网首页深度学习
吃瓜学习笔记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吃瓜教程

相关文章

  • 决策树基本要点及方法对比

    决策树的生产,基本方法有ID3、C4.5、CART。基于基础决策树学习器,可进一步构建提升树。 ID3 ID3算法...

  • 从cart决策树到XGBoost

    一. cart决策树简述 我们知道决策树算法有ID3、C4.5和cart三种,ID3和C4.5是基于信息增益和信息...

  • 经典决策树对比

    关于经典决策树算法ID3、C4.5及CART树的部分细节梳理。 决策树 决策树可以从两个视角理解。 If-Then...

  • 05 决策树 - 生成算法 ID3、C4.5、CART

    ID3 提出了初步的决策树算法;C4.5 提出了完整的决策树算法;CART (Classification And...

  • 决策树

    1. 引言   决策树的学习通常包括三个步骤:特征选择,决策树的生成和决策树的修剪,本文梳理一下ID3,C4.5和...

  • 决策树和随机森林

    随机森林和GBDT算法的基础是决策树 而建立决策树的算法由很多,ID3,C4.5,CART等, ID3:ID3算法...

  • 决策树简记

    具有不同划分准则的算法决策树原理剖析及实现(ID3)理解决策树算法(实例详解)-ID3算法与C4.5算法 ID3(...

  • ID3/C4.5/CART决策树算法推导

    目录 一、ID3决策树 二、C4.5决策树 三、CART决策树 四、总结 信息熵——度量样本集合纯度最常用一种指标...

  • 机器学习:决策树(ID3)

    ID3 决策树构建树的依据是简单的比较样本集分类前后的信息增益 此外还有 CART 决策树,C4.5 决策树等 优...

  • day10-决策树

    今天学了决策树的基本知识。 基于信息论的决策树算法有:ID3, CART, C4.5等算法。 ID3 算法是根...

网友评论

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

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