【机器学习】决策树(三)——生成算法(ID3、C4.5与CRAT)

2023-10-20 17:50

本文主要是介绍【机器学习】决策树(三)——生成算法(ID3、C4.5与CRAT),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

回顾

简单理解决策树
通过例子理解决策树构建过程

前面我们介绍了决策树的特征选择,以及根据信息增益构建决策树。

那么决策树的生成又有哪些经典算法呢?本篇将主要介绍ID3的生成算法,然后介绍C4.5中的生成算法。最后简单介绍CRAT算法。

ID3算法

前面我们提到,一般而言,信息增益越大,则意味着使用该属性来进行划分所获得的“纯度”提升就越大。因此,我们可以用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来划属性的。

ID3算法流程
输入:训练数据集 D D D,特征集 A A A,阀值 E \mathcal{E} E
输出:决策树 T T T
(1)若 D D D中所属实例属于同一类 C k C_k Ck,则T为单结点树,并将类 C k C_k Ck作为该结点的类标记,返回 T T T
(2)若 A = ϕ A = \phi A=ϕ,则 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回 T T T
(3)否则,按照计算 A A A中每个特征对 D D D信息增益,选择信息增益最大的特征 A m A_m Am
(4)如果 A m A_m Am的信息增益小于阀值 E \mathcal{E} E,则置 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回 T T T
(5)否则,对 A m A_m Am的每一种可能值 a i a_i ai,依 A m = a i A_m=a_i Am=ai D D D分割为若干非空子集 D i D_i Di,将 D i D_i Di中实例数最大的类作为标记,构建子结点,由结点及其子结点构成树 T T T,返回 T T T
(6)对第 i i i个子结点,以 D i D_i Di为训练集,以 A − A m A-A_m AAm为特征集,递归调用步骤(1)~(5),得到子树 T i T_i Ti,返回 T i T_i Ti

ID3算法的优缺点

  • 优点:

决策树构建速度快,容易构建

  • 缺点:

计算依赖于特征数目较多的特征,而属性值最多的属性并不一定最优
ID3算法不是递增算法
ID3算法是单变量决策树,对特征属性之间的关系不会考虑
抗噪性差
只适合小规模数据集,需要将数据放到内存中
容易产生过拟合

C4.5算法

C4.5算法与ID3算法相似,C4.5算法对ID3算法进行了改进。C4.5在生成的过程中,用信息增益比来选特征。

信息增益比

以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题,使用信息增益比可以对这一问题进行校正。这是特征选择的另一准则。

定义:特征 A A A对训练数据集 D D D的信息增益比 g R ( D , A ) g_R(D,A) gR(D,A)定义为其信息增益 g ( D , A ) g(D,A) g(D,A)与训练数据集 D D D关于特征 A A A的值的熵 H A ( D ) H_A(D) HA(D)之比,即:
g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D,A) = \frac{g(D,A)}{H_A(D)} gR(D,A)=HA(D)g(D,A)
其中: H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ ∣ D ∣ H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|} HA(D)=i=1nDDilog2DDi n n n是特征 A A A取值的个数。

C4.5算法流程
输入:训练数据集 D D D,特征集 A A A,阀值 E \mathcal{E} E
输出:决策树 T T T
(1)若 D D D中所属实例属于同一类 C k C_k Ck,则T为单结点树,并将类 C k C_k Ck作为该结点的类标记,返回 T T T
(2)若 A = ϕ A = \phi A=ϕ,则 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回 T T T
(3)否则,按照计算 A A A中每个特征对 D D D信息增益比,选择信息增益比最大的特征 A m A_m Am
(4)如果 A m A_m Am的信息增益比小于阀值 E \mathcal{E} E,则置 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回 T T T
(5)否则,对 A m A_m Am的每一种可能值 a i a_i ai,依 A m = a i A_m=a_i Am=ai D D D分割为若干非空子集 D i D_i Di,将 D i D_i Di中实例数最大的类作为标记,构建子结点,由结点及其子结点构成树 T T T,返回 T T T
(6)对第 i i i个子结点,以 D i D_i Di为训练集,以 A − A m A-A_m AAm为特征集,递归调用步骤(1)~(5),得到子树 T i T_i Ti,返回 T i T_i Ti

C4.5算法的优缺点

  • 优点:

产生的规则易于理解
准确率较高
实现简单

  • 缺点:

对数据需要进行多次扫描和排序,所以效率低
只适合小规模数据集,需要将数据放到内存中

CART算法

CART决策树使用“基尼指数”来选择特征划分,数据集 D D D的纯度可以用基尼值来度量:
G i n i ( D ) = ∑ k = 1 ∣ y ∣ ∑ k ′ ≠ k p k p k ′ = 1 − ∑ k = 1 ∣ y ∣ p k 2 Gini(D) = \sum_{k=1}^{|y|}\sum_{k^{'} \neq k}p_kp_{k^{'}} = 1 - \sum_{k=1}^{|y|}p_k^2 Gini(D)=k=1yk̸=kpkpk=1k=1ypk2
直观来说, G i n i ( D ) Gini(D) Gini(D)反映了从数据集 D D D中随机抽取两个样本,其类别标记不一致的概率。因此 G i n i ( D ) Gini(D) Gini(D)越小,则数据集 D D D的纯度越高。

如果样本集合 D D D根据特征 A A A是否取某一可能值 a a a被分割成 D 1 D_1 D1 D 2 D_2 D2两部分,即:
KaTeX parse error: Can't use function '$' in math mode at position 31: …in D|A(x) = a\}$̲,$D_2 = D - D_1
则在特征 A A A的条件下,集合 D D D的基尼指数定义为:
G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) Gini(D,A)=DD1Gini(D1)+DD2Gini(D2)
通式为:
G i n i ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini(D,a) = \sum_{v=1}^{V}\frac{|D_v|}{|D|}Gini(D_v) Gini(D,a)=v=1VDDvGini(Dv)
基尼指数 G i n i ( D ) Gini(D) Gini(D)表示集合 D D D的不确定性,基尼指数 G i n i ( D , A ) Gini(D,A) Gini(D,A)表示经 A = a A=a A=a分割后集合 D D D的不确定性。
我们在候选属性集合 A A A中,选择那个是的划分后基尼指数最小的属性作为最优划分属性。

注:基尼指数用来划分属性生成分类数的,对于回归树的生成我们用的是最小二乘回归树生成算法。

最小二乘回归树生成算法

输入:训练数据集 D D D
输出:回归树 f ( x ) f(x) f(x)

在训练数据集所在的输入空间中,递归的将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树。
(1)选择最优切分变量 j j j与切分点 s s s,求解:
min ⁡ j , s [ min ⁡ c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min_{j,s}[\min_{c_1}\sum_{x_i \in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i \in R_2(j,s)}(y_i-c_2)^2] j,smin[c1minxiR1(j,s)(yic1)2+c2minxiR2(j,s)(yic2)2]
遍历变量 j j j,对固定的切分变量 j j j扫描切分点 s s s,选择使上式达到最小值 的对 ( j , s ) (j,s) (j,s)
(2)用选定的对 ( j , s ) (j,s) (j,s)划分区域,并决定相应的输出值:
R 1 ( j , s ) = { x ∣ x ( j ) ⩽ s } , R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)}\leqslant s\},R_2(j,s)=\{x|x^{(j)} > s\} R1(j,s)={xx(j)s}R2(j,s)={xx(j)>s}
c m = 1 N m ∑ x i ∈ R m ( j , s ) y i , x ∈ R m , m = 1 , 2 c_m = \frac{1}{N_m}\sum_{x_i \in R_m(j,s)}y_i,x \in R_m,m = 1, 2 cm=Nm1xiRm(j,s)yixRmm=1,2
(3)继续对两个子区域调用步骤(1)(2),直到满足停止条件
(4)将输入空间划分为 M M M个区域 R 1 , R 2 , . . . , R M R_1,R_2,...,R_M R1,R2,...,RM,生成决策树:
f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x) = \sum_{m=1}^{M}c_mI(x \in R_m) f(x)=m=1McmI(xRm)
CART基于基尼指数的生成算法

输入:训练数据集 D D D,停止计算条件;
输出:CART决策树

根据训练数据集,从根结点开始,递归的将每个结点进行以下操作,构建二叉决策树。
(1)设结点的训练数据集为 D D D,计算现有特征对该数据集的基尼指数。此时,对每一个特征 A A A,对其可能取的每一个值 a a a,根据样本点对 A = a A=a A=a的测试为“是”或“否”将 D D D分割成 D 1 D_1 D1 D 2 D_2 D2两部分,计算 A = a A=a A=a时的基尼指数。
(2)在所有可能的特征 A A A以及它们所有可能的切分点 a a a中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点,生成两个子结点。
(3)对两个子结点递归调用(1),(2),直到满足停止条件;
(4)生成CART决策树。

总结

在这里插入图片描述

对于每种生成算法,只是使用了不同的方法来选择特征,流程基本类似。
ID3和C4.5算法均只适合小规模数据集上使用
ID3和C4.5算法都是单变量决策树
当属性取值比较多的时候,最好考虑C4.5算法,ID3算法得出的结果比较差
决策树分类一般只适合小数据量的情况
此外,我们还可以对决策树进行一些优化策略,比如:剪枝。决策树剪枝优化及可视化

参考资料:
李航《统计学习方法》
周志华《机器学习》西瓜书

这篇关于【机器学习】决策树(三)——生成算法(ID3、C4.5与CRAT)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/248706

相关文章

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-