决策树——(二)决策树的生成与剪枝ID3,C4.5

2024-03-30 00:18
文章标签 生成 c4.5 决策树 剪枝 id3

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

1.基本概念

在正式介绍决策树的生成算法前,我们先将之前的几个概念梳理一下:

1.1 信息熵

X X X是一个取有限个值的离散型随机变量,其分布概率为
P ( X = x i ) = p i , i = 1 , 2 , . . . , n P(X=x_i)=p_i,i=1,2,...,n P(X=xi)=pi,i=1,2,...,n

则随机变量 X X X的熵定义为
H ( X ) = − ∑ i = 1 n p i log ⁡ p i (1.1) H(X)=-\sum_{i=1}^np_i\log{p_i}\tag{1.1} H(X)=i=1npilogpi(1.1)

其中,若 p i = 0 p_i=0 pi=0,则定义 0 log ⁡ 0 = 0 0\log0=0 0log0=0;且通常 log ⁡ \log log取2为底和 e e e为底时,其熵的单位分别称为比特(bit)或纳特(nat).如无特殊说明,默认2为底。

1.2 条件熵

设有随机变量 ( X , Y ) (X,Y) (X,Y),其联合概率分布分
P ( X = x i , Y = y i ) = p i j , i = 1 , 2 , . . . , n ;    j = 1 , 2 , . . . , m P(X=x_i,Y=y_i)=p_{ij},i=1,2,...,n;\;j=1,2,...,m P(X=xi,Y=yi)=pij,i=1,2,...,n;j=1,2,...,m

条件熵 H ( Y ∣ X ) H(Y|X) H(YX)表示在已知随机变量 X X X的条件下,随机变量 Y Y Y的不确定性。其定义为
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) (1.2) H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)\tag{1.2} H(YX)=i=1npiH(YX=xi)(1.2)

其中, p i = P ( X = x i ) , i = 1 , 2 , . . . , n p_i=P(X=x_i),i=1,2,...,n pi=P(X=xi),i=1,2,...,n
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称之为经验熵(empirical entropy)和经验条件熵(empirical coditional entropy)。事实上我们在实际处理的时候确实时用的经验熵和经验条件熵,这一点同朴素贝叶斯中的处理一样。

1.3 信息增益

特征 A A A对训练数据集 D D D的信息增益 d ( D , A ) d(D,A) d(D,A),定义为集合 D D D的经验熵 H ( D ) H(D) H(D)与特征 A A A给定条件下 D D D的经验条件熵 H ( D ∣ A ) H(D|A) H(DA)之差,即
g ( D , A ) = H ( D ) − H ( D ∣ A ) (1.3) g(D,A)=H(D)-H(D|A)\tag{1.3} g(D,A)=H(D)H(DA)(1.3)

设训练集为 D D D ∣ D ∣ |D| D表示其样本容量,即样本个数。设有 K K K个类 C k , k = 1 , 2 , . . . , K ;    ∣ C k ∣ C_k,k=1,2,...,K;\;|C_k| Ck,k=1,2,...,K;Ck为属于类 C k C_k Ck的样本的个数,即 ∑ k = 1 K ∣ C k ∣ = ∣ D ∣ \sum_{k=1}^K|C_k|=|D| k=1KCk=D.设特征 A A A n n n个不同的取值 a 1 , a 2 , . . . , a n {a_1,a_2,...,a_n} a1,a2,...,an,根据特征 A A A的取值将 D D D划分为 n n n个子集 D 1 , D 2 , . . . , D n D_1,D_2,...,D_n D1,D2,...,Dn, ∣ D i ∣ |D_i| Di D i D_i Di的样本个数,即 ∑ i = 1 n ∣ D i ∣ = ∣ D ∣ \sum_{i=1}^n|D_i|=|D| i=1nDi=D.记子集 D i D_i Di中,属于类 C k C_k Ck的样本集合为 D i k D_{ik} Dik,即 D i k = D i ⋂ C k D_{ik}=D_i\bigcap C_k Dik=DiCk ∣ D i k ∣ |D_{ik}| Dik D i k D_{ik} Dik的样本个数. 则有:
(1)数据集 D D D的经验熵 H ( D ) H(D) H(D)
H ( D ) = − ∑ k = 1 K ∣ C k ∣ ∣ D ∣ log ⁡ 2 ∣ C k ∣ ∣ D ∣ (1.4) H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}\tag{1.4} H(D)=k=1KDCklog2DCk(1.4)

(2)特征值A对数据集 D D D的经验条件熵 H ( D ∣ A ) 为 H(D|A)为 H(DA)
H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ∑ k = 1 K ∣ D i k ∣ ∣ D i ∣ log ⁡ 2 D i k D i (1.5) H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log_2{\frac{D_{ik}}{D_i}}\tag{1.5} H(DA)=i=1nDDiH(Di)=i=1nDDik=1KDiDiklog2DiDik(1.5)

(3)信息增益
g ( D , A ) = H ( D ) − H ( D ∣ A ) (1.6) g(D,A)=H(D)-H(D|A)\tag{1.6} g(D,A)=H(D)H(DA)(1.6)

仅看上面的公式肯定会很模糊,还是举个例子来说明一下(将公式同下面的计算式子对比着看会更容易理解).下表是一个由15个样本组成的贷款申请训练数据集。数据包括4个特征,最后一列表示是否通过申请。
I D 年龄 有工作 有自己的房子 贷款情况 类别 1 青年 否 否 一般 否 2 青年 否 否 好 否 3 青年 是 否 好 是 4 青年 是 是 一般 是 5 青年 否 否 一般 否 6 中年 否 否 一般 否 7 中年 否 否 好 否 8 中年 是 是 好 是 9 中年 否 是 非常好 是 10 中年 否 是 非常好 是 11 老年 否 是 非常好 是 12 老年 否 是 好 是 13 老年 是 否 好 是 14 老年 是 否 非常好 是 15 老年 否 否 一般 否 \begin{array}{c|cc} \hline ID&\text{年龄}&\text{有工作}&\text{有自己的房子}&\text{贷款情况}&\text{类别}\\ \hline 1&\text{青年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ 2&\text{青年}&\text{否}&\text{否}&\text{好}&\text{否}\\ 3&\text{青年}&\text{是}&\text{否}&\text{好}&\text{是}\\ 4&\text{青年}&\text{是}&\text{是}&\text{一般}&\text{是}\\ 5&\text{青年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ \hline 6&\text{中年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ 7&\text{中年}&\text{否}&\text{否}&\text{好}&\text{否}\\ 8&\text{中年}&\text{是}&\text{是}&\text{好}&\text{是}\\ 9&\text{中年}&\text{否}&\text{是}&\text{非常好}&\text{是}\\ 10&\text{中年}&\text{否}&\text{是}&\text{非常好}&\text{是}\\ \hline 11&\text{老年}&\text{否}&\text{是}&\text{非常好}&\text{是}\\ 12&\text{老年}&\text{否}&\text{是}&\text{好}&\text{是}\\ 13&\text{老年}&\text{是}&\text{否}&\text{好}&\text{是}\\ 14&\text{老年}&\text{是}&\text{否}&\text{非常好}&\text{是}\\ 15&\text{老年}&\text{否}&\text{否}&\text{一般}&\text{否}\\ \hline \end{array} ID123456789101112131415年龄青年青年青年青年青年中年中年中年中年中年老年老年老年老年老年有工作有自己的房子贷款情况一般一般一般一般非常好非常好非常好非常好一般类别

这篇关于决策树——(二)决策树的生成与剪枝ID3,C4.5的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中,我们经常需要从 W

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压:从3秒到0.5秒的质变1.2 批量操作的优雅

Python使用python-pptx自动化操作和生成PPT

《Python使用python-pptx自动化操作和生成PPT》这篇文章主要为大家详细介绍了如何使用python-pptx库实现PPT自动化,并提供实用的代码示例和应用场景,感兴趣的小伙伴可以跟随小编... 目录使用python-pptx操作PPT文档安装python-pptx基础概念创建新的PPT文档查看

在ASP.NET项目中如何使用C#生成二维码

《在ASP.NET项目中如何使用C#生成二维码》二维码(QRCode)已广泛应用于网址分享,支付链接等场景,本文将以ASP.NET为示例,演示如何实现输入文本/URL,生成二维码,在线显示与下载的完整... 目录创建前端页面(Index.cshtml)后端二维码生成逻辑(Index.cshtml.cs)总结

Python实现数据可视化图表生成(适合新手入门)

《Python实现数据可视化图表生成(适合新手入门)》在数据科学和数据分析的新时代,高效、直观的数据可视化工具显得尤为重要,下面:本文主要介绍Python实现数据可视化图表生成的相关资料,文中通过... 目录前言为什么需要数据可视化准备工作基本图表绘制折线图柱状图散点图使用Seaborn创建高级图表箱线图热

SQLServer中生成雪花ID(Snowflake ID)的实现方法

《SQLServer中生成雪花ID(SnowflakeID)的实现方法》:本文主要介绍在SQLServer中生成雪花ID(SnowflakeID)的实现方法,文中通过示例代码介绍的非常详细,... 目录前言认识雪花ID雪花ID的核心特点雪花ID的结构(64位)雪花ID的优势雪花ID的局限性雪花ID的应用场景

Django HTTPResponse响应体中返回openpyxl生成的文件过程

《DjangoHTTPResponse响应体中返回openpyxl生成的文件过程》Django返回文件流时需通过Content-Disposition头指定编码后的文件名,使用openpyxl的sa... 目录Django返回文件流时使用指定文件名Django HTTPResponse响应体中返回openp

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2