决策树算法(ID3,CART,C4.5)

news/2024/12/23 20:46:13/

一 基本流程

1. 决策树思想

在生活中,我们如何判别一个学生是否优秀?我们可能先会判断其成绩如何、再判断其能力如何、再判断其形象如何,判断等等属性,最后得出结论他优秀或不优秀。而且判别流程因人而异,不唯一。

决策树思想也是如此: 根据当前结点的数据集和属性集,选择一个最佳的属性将数据集划分出几个子集作为当前结点的孩子结点,孩子结点数据集和属性集是父结点的子集且再重复上述过程,直到产生叶节点,此时叶结点的数据尽可能地属于同一类。如下图是一个决策树的例子:
在这里插入图片描述
可以观察到,判断一个学生是否优秀有多条路径,这与我们生活中做判别是同样的。决策树的增长是不断选取不同的属性值进行数据划分的过程,而这个过程中子集的纯度(集合中同类所占的比例)越来越高,从而达到分类的效果,从根到叶子结点的一条路径就是一条判别序列。 决策树算法就是要从已知分类的数据集中学得一颗判别树,属于监督学习算法。

2. 基本算法

在这里插入图片描述

这是决策树最基本的算法,是个递归模型。该算法中最重要的一步就是13:选择最佳的划分属性,根据选择规则的不同决策树算法有ID3、CART和C4.5。另外,注意递归结束的条件:

(2行) D中样本属于同一类,这时已经找到一个判别类型了,无须再划分子集了。

(8行) A为空集,这时表明已经使用了所有属性来划分子集依然不能将类别完全分开,那么采用投票法,即样本数最多的分类为判别结果,不再继续划分;D中样本在A上的取值相同,这表明再按A中的属性来划分结果依然是D或空集,没有必要再划分下去了,此时D中存在多个类别,那么采用投票法。

(16行) D v D_v Dv为空,这表明D没有属性 a ∗ a_* a值为 a ∗ v a_*^v av的数据,那么判别到这儿如何分类呢?生成子节点,子节点的分类标记为父节点数据集D的投票结果。

二 划分属性选择

1.ID3的选择

ID3是最基本的决策树算法,其采用信息增益准则来选择最佳的划分属性。

信息熵(Information Entroyp):是度量样本集合纯度的一种量化标准。有Y是样本集D上的随机变量,令 P k P_k Pk为随机变量Y=k(k=1,2,…,|Y|) 时的概率,样本集D的信息熵为:
E n t ( D ) = − ∑ k = 1 ∣ Y ∣ P k log ⁡ 2 P k \begin{aligned} Ent(D) = - \sum_{k=1}^{|Y|} P_k \log_2 P_k \end{aligned} Ent(D)=k=1YPklog2Pk
举个例子来理解信息熵,假设随机变量Y={ 0 , 1 0,1 0,1},假设有如下三种情况:

若两类在集合D上分布均匀,即 P 0 = P 1 = 1 2 P_0=P_1=\frac{1}{2} P0=P1=21,则信息熵为: − ( P 0 log ⁡ 2 P 0 + P 1 log ⁡ 2 P 1 ) = − log ⁡ 2 1 2 = 1 -(P_0\log_2P_0+P_1\log_2P_1)=-\log_2\frac{1}{2}=1 (P0log2P0+P1log2P1)=log221=1

若有一类所占比例比较高,即 P 0 = 3 4 、 P 1 = 1 4 P_0=\frac{3}{4}、P_1=\frac{1}{4} P0=43P1=41,则信息熵为: − ( 3 4 log ⁡ 2 3 4 + 1 4 log ⁡ 2 1 4 ) = 0.81 -(\frac{3}{4}\log_2\frac{3}{4}+\frac{1}{4}\log_2\frac{1}{4})=0.81 (43log243+41log241)=0.81

若完全只有一类,即 P 0 = 1 , P 2 = 0 P_0=1,P_2=0 P0=1P2=0,则信息熵为: − ( log ⁡ 2 1 + 0 ) = 0 -(\log_2 1+0)=0 (log21+0)=0

可以看出:随机变量分布越均匀(纯度越低),信息熵越大;分布越不均匀(纯度越高),信息熵越小。

条件熵: D v D^v Dv D D D在属性 a a a上取值为 a v a^v av的样本集,那么在条件 a = a v a=a^v a=av情况下D的条件熵为:
C o n ( D , a ) = ∑ v = 1 ∣ a ∣ ∣ D v ∣ ∣ D ∣ E n t ( D v ) \begin{aligned} Con(D,a) = \sum_{v=1}^{|a|} \cfrac{|D^v|}{|D|} Ent(D^v) \end{aligned} Con(D,a)=v=1aDDvEnt(Dv)
条件熵表示限制条件下的信息纯度。

信息增益:信息熵 − - 条件熵。即,
G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 ∣ a ∣ ∣ D v ∣ ∣ D ∣ E n t ( D v ) \begin{aligned} Gain(D,a) = Ent(D)-\sum_{v=1}^{|a|} \cfrac{|D^v|}{|D|} Ent(D^v) \end{aligned} Gain(D,a)=Ent(D)v=1aDDvEnt(Dv)
信息熵表示信息纯度,条件熵表示限制条件下的信息纯度。那么信息增益越大,说明选择属性a来划分可以使得纯度更高的提升,即选择最佳属性为有最大的信息增益的属性:
a ∗ = a r g m a x ( a ∈ A ) G a i n ( D , a ) \begin{aligned} a_*= arg max_{(a\in A)} Gain(D,a) \end{aligned} a=argmax(aA)Gain(D,a)
信息增益准则的缺点: 对可取值数目较多的属性有所偏好。

2. C4.5的选择

信息增益率
G a i n R a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) I V ( a ) = − ∑ v = 1 ∣ V ∣ ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ \begin{aligned} GainRatio(D,a)&=\cfrac{Gain(D,a)}{IV(a)} \\ IV(a)&=-\sum_{v=1}^{|V|}\cfrac{|D^v|}{|D|}log_2\cfrac{|D^v|}{|D|} \end{aligned} GainRatio(D,a)IV(a)=IV(a)Gain(D,a)=v=1VDDvlog2DDv
属性可取值数目越大,即|V|越大, G a i n ( D , a ) Gain(D,a) Gain(D,a)会越大,而 I V ( a ) IV(a) IV(a)也会越大。但是前者的增幅较小,后者的增幅较大,所以信息增益率对可取值数目较小的属性有所偏好

C4.5算法是先计算信息增益,从高于平均信息增益的属性中,再选择信息增益率高的。

3.CART的选择

CART算法用基尼指数来选择划分属性。

数据集D的基尼值
G i n i ( D ) = 1 − ∑ k = 1 ∣ Y ∣ P k 2 \begin{aligned} Gini(D)=1-\sum_{k=1}^{|Y|}P_k^2 \end{aligned} Gini(D)=1k=1YPk2
从数学的角度来理解基尼值:从数据集中随机抽取两个样本,两个样本不是同类的概率。因此,基尼值越小,随机抽取两个样本属于同类的概率越高,数据集D的纯度越大。

属性a的基尼指数为:

G i n i I n d e x ( D , . a ) = ∑ v = 1 ∣ V ∣ ∣ D v ∣ ∣ D ∣ G i n i ( D v ) \begin{aligned} GiniIndex(D,.a)=\sum_{v=1}^{|V|}\cfrac{|D^v|}{|D|}Gini(D^v) \end{aligned} GiniIndex(D,.a)=v=1VDDvGini(Dv)
数据D按属性a划分子集后,每个子集的纯度越高则基尼值越低,那么基尼指数越小。故而,选取基尼指数最小的属性来划分,即:
a ∗ = a r g m i n ( a ∈ A ) G i n i I n d e x ( D , a ) \begin{aligned} a_*= argmin_{(a\in A)} GiniIndex(D,a) \end{aligned} a=argmin(aA)GiniIndex(D,a)


http://www.ppmy.cn/news/67210.html

相关文章

数据建模方法论及实施步骤

了解数据建模之前首先要知道的是什么是数据模型。数据模型(Data Model)是数据特征的抽象,它从抽象层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表示与操作提供一个抽象的框架。 一、概要:数据…

机器学习——损失函数(lossfunction)

问:非监督式机器学习算法使用样本集中的标签构建损失函数。 答:错误。非监督式机器学习算法不使用样本集中的标签构建损失函数。这是因为非监督式学习算法的目的是在没有标签的情况下发现数据集中的特定结构和模式,因此它们依赖于不同于监督式…

图像处理opencv

**第三周学习笔记 2.图像处理 2.1图像阈值 2.1.1概念 1.关于图像阈值在基础的OpenCV中主要使用的是cv2.threshold()这个是简单阈值 2.首先我们要了解什么是简单阈值,阈值能够干什么,简单阈值是我们设置的一个临界值,这个临界值的作用就是…

彻底解决 Lost connection to MySQL server at ‘reading initial communication packet’, system error: 0 解决方法

当我遇到这错误的时候,我去网上也找过对应解决方法,出现这个的原因有很多种情况 大多是解决Linux系统里的 我是windows系统里的MySQL服务出问题了,所有那些方法对我来说毫无意义. 好了,说一下我的解决办法,其实也很简单 只需要卸载mysql服务,注册表也要删干净,也要把环境变…

基于SpringBoot+微信小程序的失物招领小程序

基于SpringBoot微信小程序的失物招领小程序 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目…

Android App开发实战之实现微信记账本(附源码 超详细必看)

需要源码或图片集请点赞关注收藏后评论区留言~~~ 一、需求描述 好用的记账本必须具备两项基本功能。一项时记录新帐单,另一项时查看账单列表,其中账单的记录操作要求用户输入账单的明细要素,包括账单的发生时间,账单的收支类型&a…

nodejs安装和环境配置-Windows

0.安装过程中遇到的常见问题 访问:https://blog.csdn.net/weixin_52799373/article/details/125718587?spm1001.2014.3001.5502 1.下载node.js 下载地址: https://nodejs.org/en/ 2.安装 2.1 安装 其实就是无脑下一步,第三步的时候可以选择自定义目…

【Axure】Axure RP 9下载、安装、授权、汉化

目录 一、Axure RP 9 下载二、Axure RP 9 安装三、Axure RP 9 授权四、Axure RP 9 汉化 一、Axure RP 9 下载 1、Axure RP 9 下载地址:https://www.axure.com/release-history/rp9 2、其他版本下载地址 ①登录axure官网:https://www.axure.com/ ②拉到最下面找到相…