决策树主要原理

这篇具有很好参考价值的文章主要介绍了决策树主要原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

决策树

决策树的概念

1、决策树是一种分类器,是一个有向、无环树

2、树中根节点没有父节点,一个节点可以有1-2个或者没有子节点

3、每个叶节点都对应一个类别标识C的值;每个内部节点都对应一个用于分割数据集的属性Xi,称为分割属性;每个内部节点都有一个分割判断规则qj

4、节点n的分割属性和分割判断规则组成了节点n的分割标准。
决策树主要原理

决策树原理

1、决策树原理:归纳推理

2、归纳:是从特殊到一般的过程

3、归纳推理:从若干个事实表现出的特征、特性或属性中,通过比较、总结、概括而得出一个规律性的结论。

4、归纳推理的基本假定:任一假设如果能在足够大的训练样本集中很好地逼近目标函数,则它也能在未见样本中很好地逼近目标函数。

ID3算法

Quinlan设计的ID3方法是国际上最有影响和最为典型的决策树学习方法。在ID3方法中, Quinlan使用信息增益度量选择测试属性

举例说明测试属性选择的重要性:假设卫生部门调查学生的膳食结构和缺钙之间的关系,得调查数据如下表所示,其中1表示主要膳食包含事务,0表示主要膳食不包含该食物。

决策树主要原理

对于不同的测试属性及其先后顺序将会产生不同的决策树,下面是产生的两个不同的决策树。

决策树主要原理

决策树主要原理

从中可以看出两个决策树差别巨大,因此测试属性的选择十分重要。ID3中使用信息增益选择测试属性。

信息的度量

信息量的大小取决于信息内容消除的人们认识的不确定程度,消除的不确定程度大,则发出的信息量就大;消除的不确定程度小,则发出的信息量就越小。

信息消除的人们认识上“不确定程度”的大小,就是该信息所包含信息量的大小。

例如,现在某甲到1000人的学校去找某乙,这时,在某甲的头脑中,某乙所处的可能性空间是该学校的1000人。当传达室告诉他:“这个人就在管理系”,而管理系就100人,那么他获得的信息为100/1000=1/10,也就是说可能性空间缩小到原来的1/10。通常,我们不直接用1/10表示信息量,而用1/10的负对数来表示,即-log1/10=log10

如果管理系的人告诉他,某乙就在管理系的教研室,那么他获得了第二个信息。假定管理系教研室有10个教师,则第二个信息的确定性又缩小到原来的100/1000*10/100=10/1000。显然:-log100/1000+(-log10/100)=-log10/1000

只要可能性范围缩小了,获得的信息量总是正的;如果可能性范围没有变化。-log1=0,获得的信息量就是零;如果可能性范围扩大了,信息量变为负值,人们对这件事的认识变得更模糊了。

信息量的计算方式

我们利用概率来度量信息。信息量的单位为比特(bit)。信息量的公式为:

决策树主要原理

一比特信息量指含有两个独立均等概率状态的事件所具有的不确定性能被全部消除所需要的信息。这里的Xi代表第i个状态,P(Xi)代表出现第i个状态的概率,H(X)就是用以消除这个系统不确定性所需的信息量。

例如,硬币下落可能有正反两种状态,出现这两种状态的概率都是1/2,即:P(Xi)=0.5,这时,H(x)=-[P(X1)log2P(X1)+P(X2)log2P(X2)]=-(-0.5-0.5)=1比特

同理可得,投掷均匀正六面体骰子的H(X)=2.58比特。

注:计算信息量这一公式恰好与热力学第二定律中熵的公式相一致,熵是系统无序状态的度量,即系统不确定性的度量。但是,信息量和熵所反应的系统运动过程和方向相反。系统的信息量增加总是表明不确定性减少,有序化程度增大。因此,信息在系统的运动过程中可以看作是负熵。信息量越大,则负熵越大。熵值越小,反映了该系统无序程度越小,有序化越高。信息度量表述了系统的有序化过程。

ID3算法的一些定义

定义4-2:若某属性存在n个相同的概率的状态,则每个状态的概率p是1/n,一个消息可以消除状态出现的不确定性,该消息传递的信息量为-log2(p)=log2(n)

定义4-3:若给定的某属性概率分布P=(p1,p2,…,pm),一个消息可以消除该属性状态出现的不确定性,则该消息传递的信息量称为P的熵,即:

I(P)=-(p1*log2(p1)+…+pm*log2(pm))(就是信息的定义公式)

定义4-4:若一个记录的集合T根据类别属性的值分成相互独立的类c1,...,ck,则识别T的一个元素(元组)所属哪个类所需要的信息量是info(T)=I§,其中P是(c1,c2…ck)的概率分布,即P=(|c1|/|T|,……,|ck|/|T|)

定义4-5:若我们先根据非类别属性X的值将T分成集合T1,T2…Tn,则确定T中的一个元素所属类的信息量可通过确定Ti的加权平均值来得到,即Info(Ti)的加权平均为:

决策树主要原理

定义4-6:将增益Gain(X,T)定义为:Gain(X,T)=Info(T)-Info(X,T),即增益的定义是两个信息量之间的差值。

理解:不知任何信息时确定一个元素属于那类所需全部信息量为Info(T),知道一个属性信息后,确定一个元素属于那类所需全部信息量为Info(X,T), Info(X,T) 越小说明属性X对于分类越重要(即很小的信息量就分出该元素属于那类了,注意:事情的不确定性越大,要搞清楚这件事就需要越大的信息量。),所以Gain(X,T)值越大说明Info(X,T)越小。

ID3算法计算每个属性的信息增益。具有最高信息增益的属性选作给定的集合T的测试属性。创建一个节点,并以该属性标记,对属性的每个值创建分支,并据此划分样本。

例题

下表给出了取自AllElectronics顾客数据库元组训练集。类标号属性buys_computer有两个不同的值(yes,no)。设类C1对应yes,而类C2对应no。类yes有9个样本,类no有5个样本。给定样本分类所需要的期望信息为

RID age income student credit_rating Class: buys_computer
1 <=30 high no fair no
2 <=30 high no excellent no
3 31…40 high no fair yes
4 >40 medium no fair yes
5 >40 low yes fair yes
6 >40 low yes excellent no
7 31…40 low yes excellent yes
8 <=30 medium no fair no
9 <=30 low yes fair yes
10 >40 medium yes fair yes
11 <=30 medium yes excellent yes
12 31…40 medium no excellent yes
13 31…40 high yes fair yes
14 >40 medium no excellent no

C1 = 9/14, C2 = 5/14

info(T) = I(P) = I(C1, C2) = -9/14log2(9/14)-5/14log2(5/14)=0.940

下一步,需要计算每个属性的熵。从age开始。需要观察每个样本值的yes和no分布。

我们对每个分布计算期望信息

针对age属性,按照<30、31…40、>40三个区间划分,将整个数据集T划分成了T1、T2、T3三个集合(注意,不是三个独立的类别),所以这里面需要用到定义5。

age < 30(T1集合): info(T1)=I(C1, C2) = -2/5log2 (2/5)-3/5log2 (3/5)=0.971

age=31…40(T2集合): info(T2)=I(C1, C2) = 0 ,因为全部都是C1类,相当于是不需要信息。

age>40(T3集合): info(T3)=I(C1, C2) = 0.971(与T1相同,都是3个C1和2个C2)

所以根据样本age划分,对一个给定的样本分类所需的期望信息为:

info(age, T) = 5/14*0.971 + 4/14*0 + 5/14*0.971 = 0.694

Gain(age, T) = info(T) - info(age, T) = 0.246

类似可以计算出

Gain(income)=0.029,Gain(student)=0.151,Gain(credit_rating)=0.048

由于age在属性中具有最高信息增益,它被选作测试属性
决策树主要原理

最终的决策树如下:

决策树主要原理

剪枝

  1. 剪枝的原因:过度匹配(将异常数据也进行分类了)、树太深。

  2. 剪枝的目的:删除由于噪声数据而引起的分支,从而避免决策树的过匹配;使树更易理解。

  3. 剪枝方法分类:

    预剪枝:在生成决策树时,按给定阈值停止生成分枝,停止处的节点为叶子节点,该叶子节点只包含子集中最多的一类元素;

    后剪枝:在生成完整决策树后,按分枝分类的错误率进行剪枝,剪去分支用叶子节点代替,树叶用被代替的子树中最频繁的类来标记。

  4. 剪枝方法

    预剪枝方法:预先设定树的深度,以便生成树一边判断是否超过深度,超过就不再生成。 后剪枝方法:决策树生成完后,根据规则(判断预测的准确性)再剪枝。文章来源地址https://www.toymoban.com/news/detail-493640.html

到了这里,关于决策树主要原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【决策树-鸢尾花分类】

    决策树是一种基于树状结构的分类与回归算法。它通过对数据集进行递归分割,将样本划分为多个类别或者回归值。决策树算法的核心思想是通过构建树来对数据进行划分,从而实现对未知样本的预测。 决策树的构建过程包括以下步骤: 选择特征 :从数据集中选择一个最优

    2024年02月15日
    浏览(40)
  • 机器学习:分类、回归、决策树

            如:去银行借钱,会有借或者不借的两种类别         如:去银行借钱,预测银行会借给我多少钱,如:1~100000之间的一个数值         为了要将表格转化为一棵树,决策树需要找出最佳节点和最佳的分枝方法,对分类树来说,衡量这个 “ 最佳 ” 的指标 叫

    2024年02月02日
    浏览(47)
  • 决策树--CART分类树

    CART(Classification and Regression Trees)分类树是一种基于决策树的机器学习算法,用于解 决分类问题。它通过构建树状的决策规则来对数据进行分类。 ① 选择一个特征和相应的切分点,将数据集分为两个子集。 ② 对每个子集递归地重复步骤1,直到满足停止条件。 ③ 当达到停

    2024年02月01日
    浏览(39)
  • 决策树的分类

    决策树是一种树形结构 树中每个内部节点表示一个特征上的判断,每个分支代表一个判断结果的输出,每个叶子节点代表一种分类结果 决策树的建立过程 1.特征选择:选取有较强分类能力的特征。 2.决策树生成:根据选择的特征生成决策树。 3. 决策树也易过拟合,采用剪枝

    2024年01月18日
    浏览(56)
  • 9_分类算法—决策树

    信息论的创始人,香农是密歇根大学学士,麻省理工学院博士。 1948年,香农发表了划时代的论文——通信的数学原理,奠定了现代信息论的基础。 信息的单位:比特 假设存在一组随机变量X,各个值出现的概率关系如图; 现在有一组由X变量组成的序列:BACADDCBAC…;如果现

    2024年02月07日
    浏览(31)
  • 决策树分类算法

    #CSDN AI写作助手创作测评  目录 ID3算法  1.算法原理 2.代码实现 3.ID3算法的优缺点分析 C4.5算法 1.原理  2.优缺点 心得感受 决策树表示方法是应用最广泛的逻辑方法之一,它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。在决策树的内部节点进行属性值的

    2024年02月07日
    浏览(19)
  • 分类算法系列⑤:决策树

    目录 1、认识决策树 2、决策树的概念 3、决策树分类原理 基本原理 数学公式 4、信息熵的作用 5、决策树的划分依据之一:信息增益 5.1、定义与公式 5.2、⭐手动计算案例 5.3、log值逼近 6、决策树的三种算法实现 7、API 8、⭐两个代码案例 8.1、决策树分类鸢尾花数据集 流程:

    2024年02月09日
    浏览(27)
  • 视觉惯性组合导航技术最新综述:应用优势、主要类别及一种视觉惯性组合导航无人系统开发验证平台分享

    导读: 随着无人机、无人车以及移动机器人的井喷式发展,导航技术成为了制约无人平台广泛应用的瓶颈技术之一。在应用需求的牵引下, 视觉惯性组合导航技术,特别是视觉与微惯性传感器的组合, 逐渐发展成为当前自主导航及机器人领域的研究热点。 Part1视觉惯性组合导

    2023年04月08日
    浏览(37)
  • 机器学习之分类决策树与回归决策树—基于python实现

          大家好,我是带我去滑雪!       本期为大家介绍决策树算法,它一种基学习器,广泛应用于集成学习,用于大幅度提高模型的预测准确率。决策树在分区域时,会考虑特征向量对响应变量的影响,且每次仅使用一个分裂变量,这使得决策树很容易应用于高维空间,且

    2024年02月03日
    浏览(43)
  • 决策树的多类别分类

    决策树是一种常用的机器学习算法,它通过构建一棵树来对数据进行分类和预测。在这篇文章中,我们将深入探讨决策树在多类别分类任务中的应用,以及其核心概念、算法原理和实现细节。 决策树算法的主要优点包括易于理解、可视化、无需特征预处理等。然而,决策树也

    2024年03月22日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包