决策树(理论知识3)

devtools/2024/12/27 5:56:50/

目录

  • 评选算法
    • 信息增益( ID3 算法选用的评估标准)
    • 信息增益率( C4.5 算法选用的评估标准)
    • 基尼系数( CART 算法选用的评估标准)
    • 基尼增益
    • 基尼增益率

评选算法

决策树学习的关键在于:如何选择最优划分属性。一般而言,随着划分过程的不断进行,我们自然希望决策树各分支结点所包含的样本尽可能属于同一类别,即结点的 “纯度” (purity) 越来越高。下面介绍几类较为主流的评选算法

信息增益( ID3 算法选用的评估标准)

信息增益 𝑔(𝐷, 𝑋) :表示某特征 𝑋 使得数据集 𝐷 的不确定性减少程度,定义为集合 𝐷 的熵与在给定特征 𝑋 的条件下 𝐷 的条件熵 𝐻(𝐷 | 𝑋) 之差,即
g ( D , X ) = H ( D ) − H ( D ∣ X ) g(D,X)=H(D)−H(D|X) g(D,X)=H(D)H(DX)

从该式可以看出,信息增益表达了样本数据在被分类后的专一性。因此,它可以作为选择当前最优特征的一个指标。

根据前面的计算结果,可知集合 𝐷 的熵 𝐻(𝐷) = 0.6931 ,特征 “天气”、“温度”、“风速”、“湿度” 的条件熵分别为 𝐻(D | X天气) = 0.3961 、𝐻(D | X温度) = 0.6931、𝐻(D | X风速) = 0.5983、𝐻(D | X湿度) = 0.6315。根据这些数据,可以算出全部特征在被用于分类时,各自的信息增益:

g ( D ∣ X 天气 ) = H ( D ) − H ( D ∣ X 天气 ) = 0.6931 − 0.3961 = 0.2970 g ( D ∣ X 温度 ) = H ( D ) − H ( D ∣ X 温度 ) = 0.6931 − 0.6931 = 0.0000 g ( D ∣ X 风速 ) = H ( D ) − H ( D ∣ X 风速 ) = 0.6931 − 0.5983 = 0.0948 g ( D ∣ X 湿度 ) = H ( D ) − H ( D ∣ X 湿度 ) = 0.6931 − 0.6315 = 0.0616 g(D|X天气)=H(D)−H(D∣X天气)=0.6931−0.3961=0.2970 \\ g(D|X温度)=H(D)−H(D∣X温度)=0.6931−0.6931=0.0000\\ g(D|X风速)=H(D)−H(D∣X风速)=0.6931−0.5983=0.0948\\ g(D|X湿度)=H(D)−H(D∣X湿度)=0.6931−0.6315=0.0616 g(DX天气)=H(D)H(DX天气)=0.69310.3961=0.2970g(DX温度)=H(D)H(DX温度)=0.69310.6931=0.0000g(DX风速)=H(D)H(DX风速)=0.69310.5983=0.0948g(DX湿度)=H(D)H(DX湿度)=0.69310.6315=0.0616

上面各特征求得的信息增益中,“天气” 特征对应的是最大的。也就是说,如果将 “天气” 作为决策树的第一个划分特征,系统整体的熵值将降低 0.297,是所有备选特征中效果最好的。因此,根据 “学校举办运动会的历史数据” 构建决策树时,根节点最好取 “天气” 特征。

接下来,在 “晴天” 中的数据将按上面的流程继续执行,直到构建好一棵完整的决策树(或达到指定条件)。不过此时,备选特征只剩下 “温度”、“风速” 和 “湿度” 3 项(往后,每当决策树的深度加 1 时,都会减少一个)。

信息增益率( C4.5 算法选用的评估标准)

以信息增益作为划分数据集的特征时,其偏向于选择取值较多的特征。比如,当在学校举办运动会的历史数据中加入一个新特征 “编号” 时,该特征将成为最优特征。因为给定 “编号” 就一定知道那天是否举行过运动会,因此 “编号” 的信息增益很高。
但实际我们知道,“编号” 对于类别的划分并没有实际意义。故此,引入信息增益率。

在这里插入图片描述
信息增益率 𝑔𝑅(𝐷, 𝑋) 定义为其信息增益 𝑔(𝐷, 𝑋) 与数据集 𝐷 在特征 𝑋 上值的熵 𝐻𝑋(𝐷) 之比,即:
g R ( D , X ) = g ( D , X ) H X ( D ) g_R(D,X)=\frac{g(D,X)}{H_X(D)} gR(D,X)=HX(D)g(D,X)

其中 H x ( D ) = − ∑ i = 1 k ∣ D i ∣ ∣ D ∣ log ∣ D i ∣ ∣ D ∣ Hx(D)=-\sum_{i=1}^k{\frac{|D_i|}{|D|}\text{log}\frac{|D_i|}{|D|}} Hx(D)=i=1kDDilogDDi,k是特征 X 的取值类别个数。
从上式可以看出,信息增益率考虑了特征本身的熵(此时,当某特征取值类别较多时, g R ( D , X ) g_R(D, X) gR(D,X)式中的分母也会增大),从而降低了 “偏向取值较多的特征” 这一影响。根据该式,可得到基于各特征划分的信息增益率如下:

按天气划分:
在这里插入图片描述

按温度划分:
在这里插入图片描述
按风速划分:
在这里插入图片描述
按湿度划分:

在这里插入图片描述
从上面的结果可以看出,信息增益率能明显降低取值较多的特征偏好现象,从而更合理地评估各特征在划分数据集时取得的效果。因此,信息增益率是现阶段用得较多的一种算法

基尼系数( CART 算法选用的评估标准)

从前面的讨论不难看出,无论是 ID3 还是 C4.5 ,都是基于信息论的熵模型出发而得,均涉及了大量对数运算。能不能简化模型同时又不至于完全丢失熵模型的优点呢?分类回归树(Classification and Regression Tree,CART)便是答案,它通过使用基尼系数来代替信息增益率,从而避免复杂的对数运算。基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。注:这一点和信息增益(率)恰好相反。

在分类问题中,假设有 k 个类别,且第 k 个类别的概率为 p k p_k pk,则基尼系数为:

G i n i ( p ) = ∑ i = 1 k p i ( 1 − p i ) = 1 − ∑ i = 1 k p i 2 Gini(p) =\sum_{i=1}^k{p_i(1-p_i)}=1-\sum_{i=1}^k{p_i^2} Gini(p)=i=1kpi(1pi)=1i=1kpi2

对于给定数据集D,假设有k个类别,且第k个类别的数量为 C k C_k Ck,则该数据集的基尼系数为:

G i n i ( D ) = ∑ i = 1 k ∣ C i ∣ ∣ D ∣ ( 1 − ∣ C i ∣ ∣ D ∣ ) = 1 − ∑ i = 1 k ( ∣ C i ∣ ∣ D ∣ ) 2 Gini(D)=\sum_{i=1}^k{\frac{|C_i|}{|D|}(1-\frac{|C_i|}{|D|})} =1-\sum_{i=1}^k{(\frac{|C_i|}{|D|})^2} Gini(D)=i=1kDCi(1DCi)=1i=1k(DCi)2

从上式可以看出,基尼系数表征了样本集合里一个随机样本分类错误的平均概率。例如:

在这里插入图片描述

如果数据集D根据特征X的取值将其划分为 D 1 , D 2 , … , D m {D_1 , D_2 , … , D_m} D1,D2,,Dm ,则在特征D的条件下,划分后的集合D的基尼系数为:
G i n i ( D , X ) = ∑ i = 1 k ∣ C i ∣ ∣ D ∣ G i n i ( D i ) Gini(D,X)=\sum_{i=1}^k{\frac{|C_i|}{|D|}}Gini(D_i) Gini(D,X)=i=1kDCiGini(Di)

由于基尼系数Gini(D)表示集合D的不确定性,则基尼系数Gini(D,X)表示 “基于指定特征X进行划分后,集合D的不确定性”。
该值越大,就表示数据集D的不确定性越大,也就说明以该特征进行划分越容易分乱。基于前面各特征对数据集的划分,可得到其对应的基尼系数为:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

基尼增益

同信息增益一样,如果将数据集D的基尼系数减去数据集D根据特征X进行划分后得到的基尼系数就得到基尼增益(系数):
G ( D , X ) = G i n i ( D ) − G i n i ( D , X ) G(D,X) =Gini(D) -Gini(D,X) G(D,X)=Gini(D)Gini(D,X)

显然,采用越好的特征进行划分,得到的基尼增益也越大。基于前面各特征对数据集的划分,可得到其对应的基尼增益。

步骤一:先算出初始数据集合D的基尼系数。

G ( D ) = 1 − ∑ i = 1 2 ( ∣ C i ∣ ∣ D ∣ ) 2 = 1 − ( ( 7 14 ) 2 + ( 7 14 ) 2 ) = 0.5000 G(D) =1-\sum_{i=1}^2{(\frac{|C_i|}{|D|})^2}=1-((\frac{7}{14})^2 +(\frac{7}{14})^2)=0.5000 G(D)=1i=12(DCi)2=1((147)2+(147)2)=0.5000

步骤二:计算基尼增益

在这里插入图片描述
可见,基尼增益在处理诸如 “编号” 这一类特征时,仍然会认为其是最优特征(此时,可采取类似信息增益率的方式,选用基尼增益率 )。但对常规特征而言,基尼增益的合理性还是较优的。

基尼增益率

基尼增益率 G R ( D , X ) G_R(D,X) GR(D,X)定义为其尼基增益G(D,X)与数据集D在特征X上的取值个数之比,即:
G R ( D , X ) = G ( D , X ) ∣ D X ∣ G_R(D,X) =\frac{G(D,X)}{|D_X|} GR(D,X)=DXG(D,X)

容易看出,基尼增益率考虑了特征本身的基尼系数(此时,当某特征取值类别较多时, G R ( D , X ) G_R(D,X) GR(D,X)式中的分母也会增大),从而降低了 “偏向取值较多的特征” 这一影响。根据该式,可得到基于各特征划分的基尼增益率如下:

在这里插入图片描述
从上面的结果可以看出,基尼增益率能明显降低取值较多的特征偏好现象,从而更合理地评估各特征在划分数据集时取得的效果。


http://www.ppmy.cn/devtools/145732.html

相关文章

CCF-A类 USENIX ATC 2025截稿指南

一、会议资讯: USENIX Annual Technical Conference (USENIX ATC)2025,即2025年USENIX年度技术会议,是CCF推荐A类会议,Core Conference Ranking A类会议。会议汇集了领先的系统研究人员,展示尖端的系统研究&#xff0…

OpenAI 12天发布会:AI革命的里程碑@附35页PDF文件下载

在人工智能的浪潮中,OpenAI的12天发布会无疑是2024年科技界的一场盛宴。从12月5日开始,OpenAI连续12天每天发布一个新应用或功能,标志着AI技术的又一次飞跃。本文将梳理这些激动人心的发布,带你一探究竟。 OpenAI发布会概览 Ope…

并发编程 - 死锁的产生、排查与解决方案

在多线程编程中,死锁是一种非常常见的问题,稍不留神可能就会产生死锁,今天就和大家分享死锁产生的原因,如何排查,以及解决办法。 线程死锁通常是因为两个或两个以上线程在资源争夺中,形成循环等待&#xf…

Kafka、RocketMQ、RabbitMQ 对比

面试中对 Kafka 、 RocketMQ 、和 RabbitMQ 的对比是常见问题,可以从以下几个维度进行分析: 1️⃣ 基础概念 特性KafkaRocketMQRabbitMQ开发语言Java ScalaJavaErlang定位分布式流处理平台分布式消息中间件高效、可靠的消息队列消息模型Topic &#xf…

C05S14-MySQL高级语句

一、MySQL高级语句 MySQL的高级语句主要是高级查询语句,实现复杂条件下的数据查询。 1. 单表查询 1.1 ORDER BY排序查询 要对数据进行排序可以使用ORDER BY子句。MySQL的ORDER BY子句可以按照一个或多个列的值进行升序排序(ASC)或降序排序&…

Mimicking-Bench:首个通过模仿大规模人类动作数据学习通用人形机器人场景交互技能的综合基准(具有 11K 对象形状和 23K 人机交互动作)

2024-12-24,由清华大学、Galbot、上海启智研究所和上海人工智能实验室联合创建了Mimicking-Bench数据集,这个数据集首次为通过模仿人类动作学习通用人形机器人场景交互技能提供了大规模的参考,对于机器人学和现实世界应用具有重要意义。 一、…

HUB、交换机、路由器和串口服务器

HUB:HUB是集线器,支持半双工的工作模式,就像对讲机那样。工作在物理层,收到数据后,会向其他端口转发,只是起到“中转站的作用”;而且对带宽是共享的,像河流一样,分的支流…

关于uni-forms组件的bug【提交的字段[‘*‘]在数据库中并不存在】

问题:在使用 uni-forms校验的时候,出来的一个问题,这个字段都没有设置校验的规则,不知道什么原因就出现了下图的问题: 解决办法: 在uni-forms-item 添加key 值就解决了 原因不知道,有大佬发现…