2022年机器学习算法总结-决策树 .docx

《2022年机器学习算法总结-决策树 .docx》由会员分享，可在线阅读，更多相关《2022年机器学习算法总结-决策树 .docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 第三章 决策树决策树 Decision Tree是在已知各种情形发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评判项目风险, 判定其可行性的决策分析方法, 是直观运用概率分析的一种图解法；由于这种决策分支画成图形很像一棵树的枝干,故称决策树；在机器学习中,决策树是一个猜测模型,他代表的是对象属性与对象值之间的一种映射关系；Entropy = 系统的凌乱程度,使用算法 ID3, C4.5 和 C5.0 生成树算法使用熵；这一度量是基于信息学理论中熵的概念；2.1 决策树模型与学习2.1.1 决策树模型定义 2.1 决策树分

2、类决策树模型是一种描述对实例进行分类的树形结构；决策树由结点 node和有向边 directed edge组成； 决策点, 是对几种可能方案的挑选, 即最终挑选的最正确方案； 假如断策属于多级决策, 就决策树的中间可以有多个决策点,为最终决策方案为最终决策方案； 状态节点,代表备选方案的经济成效期望值以决策树根部的决策点,通过各状态节点的经济成效的比照, 依据肯定的决策标准就可以选出最正确方案；由状态节点引出 的分支称为概率枝, 概率枝的数目表示可能显现的自然状态数目每个分枝上要注 明该状态显现的概率； 结果节点, 将每个方案在各种自然状态下取得的损益值标注于结果节点的右端；名师归纳总结 -

3、- - - - - -第 1 页,共 20 页精选学习资料 - - - - - - - - - 2.1.2 决策树学习决策树是以实例为基础的归纳学习算法；它从一组无次序、 无规章的元组中推理出决策树表示形式的分类规章；它采 用自顶向下的递归方式, 在决策树的内部结点进行属性值的比较,并依据不同的 属性值从该结点向下分支, 叶结点是要学习划分的类； 从根到叶结点的一条路径 就对应着一条合取规章,整个决策树就对应着一组析取表达式规章；1986 年 Quinlan 提出了闻名的 ID3 算法；在 ID3 算法的基础上, 1993 年 Quinlan 又提出 了 C4.5 算法；为了适应处理大规模数据

4、集的需要,后来又提出了假设干改良的算 法 , 其 中SLIQsuper-vised learning in quest 和 SPRINT scalable parallelizableinduction of decision trees 2.1.3 决策树分析法 决策树分析法是常用的风险分析决策方法；是比较有代表性的两个算法；该方法是一种用树形图来描述各方案在将来收益的运算； 比较以及挑选的方法, 其决策是以期望值为标准的；它利用了概率论的原理,并且利用一种树形图作为分析工具；它利用了概率论的原理, 并且利用一种树形图作为分析工具；其基本原理是用决策点代表决策问题, 用方案分枝代表可供挑选的

5、方案,用概率分枝代表方案可能显现的各种结果, 经过对各种方案在各种结果条件下损益值的运算比较,为决策者供应决策依据；名师归纳总结 - - - - - - -第 2 页,共 20 页精选学习资料 - - - - - - - - - 决策树分析法是常用的风险分析决策方法；该方法是一种用树形图来描述各方案在将来收益的运算； 比较以及挑选的方法, 其决策是以期望值为标准的；人们对将来可能会遇到好几种不同的情形；每种情形均有显现的可能, 人们目前无法确知,但是可以依据以前的资料来推断各种自然状态显现的概率；在这样的条 件下,人们运算的各种方案在将来的经济成效只能是考虑到各种自然状态显现的 概率的期望值,

6、与将来的实际收益不会完全相等；假如一个决策树只在树的根部有一决策点,就称为单级决策； 假设一个决策不仅在树的根部有决策点,而且在树的中间也有决策点,就称为多级决策；科学的决策是现代治理者的一项重要职责；我们在企业治理实践中, 常遇到的情形是：假设干个可行性方案制订出来了,分析一下企业内、外部环境,大部 分条件是己知的, 但仍存在肯定的不确定因素； 每个方案的执行都可能显现几种结果,各种结果的显现有肯定的概率,企业决策存在着肯定的胜算,也存在着一定的风险；这时,决策的标准只能是期望值；即,各种状态下的加权平均值；针对上述问题,用决策树法来解决不失为一种好的挑选；决策树法作为一种决策技术, 已被广

7、泛地应用于企业的投资决策之中,它是 随机决策模型中最常见、 最普及的一种规策模式和方法此方法,有效地掌握了决 策带来的风险；所谓决策树法,就是运用树状图表示各决策的期望值, 通过运算,不 最终优选出效益最大、 成本最小的决策方法； 决策树法属于风险型决策方法,同于确定型决策方法, 二者适用的条件也不同； 应用决策树决策方法必需具备以 下条件：1 有决策者期望到达的明确目标；2 存在决策者可以挑选的两个以上的可行备选方案；3 存在着决策者无法掌握的两种以上的自然状态 济进展动向等 ； 如气候变化、市场行情、经4 不同行动方案在不同自然状态下的收益值或缺失值 简称损益值 可以运算出来；5 决策者能

8、估量出不同的自然状态发生概率；名师归纳总结 - - - - - - -第 3 页,共 20 页精选学习资料 - - - - - - - - - 2.2 特点挑选2.2.1 特点挑选问题1、为什么要做特点挑选 在有限的样本数目下, 用大量的特点来设计分类器运算开销太大而且分类性能 差；2、特点挑选的确切含义 将高维空间的样本通过映射或者是变换的方式转换到低维空间,到达降维的目 的,然后通过特点选取删选掉冗余和不相关的特点来进一步降维；3、特点选取的原就 猎取尽可能小的特点子集, 不显著降低分类精度、 不影响类分布以及特点子集 应具有稳固适应性强等特点 4、特点挑选需要考虑的问题 a、确定挑选算法

9、,在答应的时间内以最小的代价找出最小的、最能描述类别 的特点组合, b、确定评判标准,衡量特点组合是否是最优,得到特点猎取操作 的停止条件；5、特点猎取方法a、依据特点子集的形成方式可以分为三种,穷举法exhaustion 、启示法heuristic和随机法random；穷举法需要遍历特点空间中全部的特点组合,所以方法复杂度最大,有用性不强；启示法通过采纳期望的人工机器调度规章,重复迭代产生递增的特点子集, 复杂度略低于穷举法, 但是只能猎取近似最优解；立刻方法分为完全随机方法和概率随机方法两种,对参数设置的依靠性较强；b、依据特点评判标准来分,依据评判函数与分类器的关怀,可以分为挑选器和封装

10、器两种, 挑选器的评判函数与分类器无关,封装器采纳分类器的错误概率作为评判函数； 挑选器的评判函数可以细分为距离测度、信息测度、 相关性测度和一样性测度； 距离测度用距离来衡量样本之间的相像度,不确定性特点来分类；6、特点猎取方法的选取原就 a、处理的数据类型信息测度用利用最小名师归纳总结 - - - - - - -第 4 页,共 20 页精选学习资料 - - - - - - - - - b、处理的问题规模 c、问题需要分类的数量 d、对噪声的容忍才能 e、无噪声环境下,产生稳固性好、最优特点子集的才能；特点挑选的一般过程可用图1 表示；第一从特点全集中产生出一个特点子集,然后用评判函数对该特

11、点子集进行评判,评判的结果与停止准就进行比较,假设评判结果比停止准就好就停止, 否就就连续产生下一组特点子集,连续进行特点挑选；选出来的特点子集一般仍要验证其有效性；综上所述,特点挑选过程一般包括产生过程,评判函数,停止准就,验证过程,这 4 个部分； 1 产生过程 Generation Procedure 产生过程是搜寻特征子集的过程, 负责为评判函数供应特点子集；搜寻特点子集的过程有多种,将在 2.2 小节绽开介绍； 2 评判函数 Evaluation Function 评判函数是评判一个特点子集好坏程度的一个准就；3 停止准就 Stopping Criterion 停止准就是与评判函数相

12、关的, 一般是一个阈值, 当评判函数值到达这个阈值后就可停止搜寻； 4 验证过程 Validation 的特点子集的有效性；2.2.2 信息增益Procedure 在验证数据集上验证选出来信息增益Kullback Leibler divergence 又称 information divergence ,information gain,relative entropy 或者 KLIC；在概率论和信息论中,信息增益是非对称的,用以度量两种概率分布 P和 Q的差异；信息增益描述了当使用Q进行编码时, 再使用 P 进行编码的差异； 通常P代表样本或观看值的分布, 也有可能是精确运算的理论分布； Q

13、代表一种理论,模型,描述或者对 P 的近似；尽管信息增益通常被直观地作为是一种度量或距离,但事实上信息增益并不名师归纳总结 是；就比方信息增益不是对称的, 从 P到 Q的信息增益通常不等于从Q到 P的信第 5 页,共 20 页息增益；信息增益是f 增益 f-divergences的一种特别情形；在1951 年由Solomon Kullback 和 Richard Leibler第一提出作为两个分布的直接增益- - - - - - -精选学习资料 - - - - - - - - - directed divergence；它与微积分中的增益不同,但可以从Bregman 增益Bregman div

14、ergence 推导得到；在信息增益中,重要性的衡量标准就是看特点能够为分类系统带来多少信息,带来的信息越多,该特点越重要；因此先回忆一下信息论中有关信息量就是“ 熵”的定义；说有这么一个变量 X,它可能的取值有n 多种,分别是X1,X2,X,Xn ,每一种取到的概率分别是P P 1, 2,Pn,那么 X的熵就定义为：HnPlog2P21i1意思就是一个变量可能的变化越多反而跟变量详细的取值没有任何关系,只和值的种类多少以及发生概率有关 ,它携带的信息量就越大因此我始终觉得我们的政策法规信息量特别大,由于它变化许多,基本朝令夕改,笑；对分类系统来说,类别 C是变量,它可能的取值是 C C 1,

15、 2, , Cn,而每一个类别显现的概率是 P C 1, P C 2, , P Cn ,因此 n 就是类别的总数；此时分n类系统的熵就可以表示为：H C P C i . log 2 P C i 2 2i 1信息增益是针对一个一个的特点而言的,就是看一个特点 t ,系统有它和没它的时候信息量各是多少, 两者的差值就是这个特点给系统带来的信息量,即增益；系统含有特点 t 的时候信息量很好运算, 就是刚刚的式子, 它表示的是包含全部特点时系统的信息量；问题是当系统不包含t 时,信息量如何运算？我们换个角度想问题,把系统要做的事情想象成这样： 说教室里有许多座位, 同学们每次上课进来的时候可以任凭坐,

16、因而变化是很大的许多种可能的座次情形；但是现在有一个座位,看黑板很清晰, 听老师讲也很清晰, 于是校长的小舅子的姐姐的女儿托关系真辗转啊,把这个座位定下来了,每次只能给她坐,别人不行,此时情形怎样？对于座次的可能情形来说, 我们很简洁看出以下两种情形是等价的： 1教室里没有这个座位；2教室里虽然有这个座位,但其他人不能坐由于反正它也不能参加到变化中来,它是不变的 ；名师归纳总结 - - - - - - -第 6 页,共 20 页精选学习资料 - - - - - - - - - 对应到我们的系统中,就是下面的等价： 1系统不包含特点 t ；2系统虽然包含特点 t ,但是 t 已经固定了,不能变化

17、；我们运算分类系统不包含特点t 的时候,就使用情形2来代替,就是计算当一个特点 t 不能变化时, 系统的信息量是多少； 这个信息量其实也有特地的名称,就叫做“ 条件熵”,条件嘛,自然就是指“t 已经固定“ 这个条件；,xn ,但是问题接踵而至,例如一个特点 X,它可能的取值有 n 多种 1, 2,当运算条件熵而需要把它固定的时候,要把它固定在哪一个值上呢？答案是每一种可能都要固定一下, 运算 n 个值,然后取均值才是条件熵； 而取均值也不是简 单的加一加然后除以 n,而是要用每个值显现的概率来算平均简洁懂得,就是 一个值显现的可能性比较大, 固定在它上面时算出来的信息量占的比重就要多一 些；因

18、此有这样两个条件熵的表达式：H C|Xx i23这是指特点 X 被固定为值 xi 时的条件熵,H C X24这是指特点 X 被固定时的条件熵, 留意与上式在意义上的区分； 从刚刚运算均值 的争论可以看出来,其次个式子与第一个式子的关系就是：nH C|XPH C|Xx 1P H C|Xx 2.P H C|Xxni1PH C|Xx i252.2.3 熵在信息论中, 要对符号进行编码, 一个符号的熵就是要表示这个符号所需要 的最少二进制数位数；这是一个极限；这也是信息压缩的基础；条件熵,当两个符号之间存在某种关系,或者两个随机变量不相互独立的时候,对于 A,B 两个随机大事,非独立,知道A 的情形,

19、 B的不确定性削减；举例来说,假设 S 是一个关于布尔概念的有14 个样例的集合,它包括9 个正例和 5 个反例我们采纳记号 9+ ,5- 来概括这样的数据样例 ,那么 S 相对于这个布尔样例的熵为：名师归纳总结 - - - - - - -第 7 页,共 20 页精选学习资料 - - - - - - - - - Entropy 9 ,59 /14 log 9 /14 25 /14log 5 /14 20.940留意,假如S的全部成员属于同一类,Entropy S 0,例如,假如全部的成员是正的 p 1,那么 p- 就是 0,于是 Entropy S 1*log 2 1 0log 2 0 0；

20、另外 S 的正反样例数量相等,Entropy S 1；S的正反样例数量不等,熵介于 0,1 之间,如下列图所示：/ 依据详细属性和值来运算熵double ComputeEntropyvector vector remain_state, string attribute, string value,bool ifparent vector count 2,0; unsigned int i,j; bool done_flag = false;/ 哨兵值forj = 1; j MAXLEN; j+ ifdone_flag break; if.attribute_rowj pareattribut

21、efori=1;i;i+if.ifparent&.remain_stateij parevalue | ifparent/ifparen 记录是否算父节点if.remain_stateiMAXLEN - 1 pareyes count0+; else count1+; done_flag = true; ifcount0 = 0 | count1 = 0 return 0;/全部是正实例或者负实例/详细运算熵 依据 +count0, -count1,log2 为底通过换底公式换成自然数底数double sum = count0 + count1; 名师归纳总结 - - - - - - -第 8

22、 页,共 20 页精选学习资料 - - - - - - - - - doubleentropy=-count0/sum*logcount0/sum/log2.0 -count1/sum*logcount1/sum/log2.0; return entropy; 举个例子：A 大事是：季节 春,夏,秋,冬 ,B 大事是：天气 下雨,下雪,晴天,多云 ；那就可以画出一个二维表格,最直观的是夏天&下雪的概率 冬天&下雪的概率；当我知道天气是下雪的时候, 我就有很大的概率认为季节是冬天；这说明：我知道了 B 大事的情形, 对 A 的不确定性削减了； 假如 A,B 是独立的,比方, A 大事是季节 春,

23、夏,秋,冬 ,B 大事是交通的情形 堵,不堵 ,我知道 B 的情形,对 A的不确定性并没影响； 上面说的是概念性的懂得, 假如用数学公式对应起来懂得,为什么会显现这样的情形？P A B 已知 B 的情形,A的概率有没有变化？当A,B 独立,P A BP A 说明 没有变化, 当 AB不独立的时候, 即两者存在某种相关性质, 换句话说就是B确定的前提下, A 的概率分布与在总体上看不一样；信息论中有熵,用来表示时间的不确定性,这个跟这个大事的可能值数目,仍有取每个值的概率,比方有 A 大事 1,2,3,4 每个取值等概,那么熵为 2；如果 A1,2 每个取值等概率,熵为 1；当取值数目一样的时候

24、 A1,2,3,4,P A 1 P A 2 P A 3 1/ 6,P A 4 1/ 2,那么这个熵小于 2；这是为什么？由于在数据压缩方面, 对于小概率大事就要用长的编码,大致率大事用短编码,这样最终平均每个大事的编码就比较小！而对于等概率大事, 这种策略就没法使用,就没法实现数据的压缩；熵说的就是这种下界；反过来,当我们说一个大事熵很大,就意味着 1 这个大事的取值范畴许多 2或者这个大事中每个取值的概率比较匀称以上两者都代表着这个大事的不确定性很大,性的度量所以我们又说熵是一种不确定名师归纳总结 那么什么是条件熵呢,为什么H A B 小于等于H A 呢？第 9 页,共 20 页- - -

25、- - - -精选学习资料 - - - - - - - - - 上面说了,知道了 B,1：第一 A 的取值范畴会缩小,为什么？拿上面一个例子来说,我知道了天气是下雪, 那么几乎可以说 A 的取值只能从 春天,冬天 里选择；2：A 中每个取值的概率分布会发生变化 P A B b 与 P A 的概率分布不同；数学证明 H A B H AB H B H A ；即已知 B 的结果, A 的不确定性减少；要表述 A 这个大事的编码数更少；在决策树中,我们关怀的是H结果 | 属性的关系,即已知某属性,结果的不确定性仍有多少； 我们需要知道,哪个属性能使得结果的不确定性削减最多；2.3 决策树的生成2.3.

26、1 ID3 算法假如学习的任务是对一个大的例子集作分类概念的归纳定义,而这些例子又都是用一些无结构的属性值对来表示,就可以采纳例如学习方法的一个变种 决策树学习,其代表性的算法是昆兰,1986提出的 ID3；ID3 算法是由 Quinlan 第一提出的；该算法是以信息论为基础,以信息熵和信息增益度为衡量标准, 从而实现对数据的归纳分类； 以下是一些信息论的基本概念：名师归纳总结 定义：假设存在 n 个相同概率的消息,就每个消息的概率p 是 1/n ,一个消第 10 页,共 20 页息传递的信息量为Log2 定义 2.3 ：假设有 n 个消息,其给定概率分布为P 1, 2pn ,就由该n分布传递

27、的信息量称为P 的熵,记为I p p Log2pi；i1定义：假设一个记录集合 T 依据类别属性的值被分成相互独立的类C1C2.Ck,就识别 T 的一个元素所属哪个类所需要的信息量为InfoT=Ip,其中P 为C1C2 Ck的概率分布,即P| 1| / |T|,|Ck| / |T|26；- - - - - - -精选学习资料 - - - - - - - - - 定义：假设我们先依据非类别属性X的值将 T 分成集合 T1,T2 Tn,就确定T 中一个元素类的信息量可通过确定Ti 的加权平均值来得到,即InfoTi的加Tn权平均值为：Info X T|Ti| / |T|Info Ti27i1定义：

28、信息增益度是两个信息量之间的差值,其中一个信息量是需确定的一个元素的信息量, 另一个信息量是在已得到的属性X 的值后需确定的 T 一个元素的信息量,信息增益度公式为：Gain X T , Info T Info X T , 28ID3算法运算每个属性的信息增益, 并选取具有最高增益的属性作为给定集合的测试属性；对被选取的测试属性创建一个节点,每个值创建一个分支据此划分样本；并以该节点的属性标记, 对该属性的ID3 的输入是描述各种已知类别实例的列表；例子由预先定义的属性值对来表示；归纳推理产生的结果不是以往争论的那种合取表达式,而是一棵决策树也称判别树,并可转而表示为决策规章的一个集合例子的类

29、属；树中的每一非叶节点对应一个需测试的属性,用它可正确地区分全部给定每个分叉就是该属性可能的取值；树的叶节点就指示一个例子事物的类别；ID3 的显著优点是归纳学习花费的时间和所给任务的困难度 取决于例子个数, 用来描述对象的属性数, 所学习概念的复杂度即决策树的节点数等仅成线性增长关系；当然,ID3 只能处理用属性- 值对表示的例子；在 ID3 中, 每一个例子用相同的一组属性来表示, 每一个属性又有自身的属性值集,如 颜色 属性可取值是 红、绿、兰 等；构造决策树的目的是为了对事物作出正确的分类；决策树形式的分类规章适用于任何的对象集；如是空的,那么它无需分类, 对应的决策树也为空； 如中的

30、对象是同一类的, 那么决策树就一个叶节点, 即该类名； 假如集中的对象属于二个不同的类别,那未我们可以选取一个对象的属性,随后按其可能值把划分成一些不相交的子集 C1,C2, , Cn,其中 Ci 是含有所选属性的第个值的那些对象集；对每一个这样的子集又可以用同样的策略处理,最终的结果是一棵树；ID3 Examples,Target-attrlbute,Attrlbutes 创建树的 root 节点名师归纳总结 - - - - - - -第 11 页,共 20 页精选学习资料 - - - - - - - - - 假如 Examples 都为正,返回label=+ 的单节点输root假如 Exa

31、mples 都为反,返回label=-的单节点输root中 最 普 遍 的如 果Attrlbutes为 空 , 那 么 返 回 单 节 点 输root , label=ExamplesTarget-attributes 值否就开头A Attributes 中分类 examples 才能最好的属性Root 的决策属性 A对于 A 的每个可能值 vi在 root 下加一个新的分支对应测试 A=vi令 Examples 为 Examples 中满意 A 属性值为 vi 的子集假如 Examples 为空在这个新分支下加一个叶子结点,节点的 Target-attributes 值 否就在新分支下加一个

32、子树 ID3label=Examples 中最普遍的Examples Target-attribute ,Attributes -A 终止返回 root下面给出一个关于人分类的例子对象 集,并预先定义了指定的一组属性及其可取值：高度 高,矮 ,发色 . 黑色 , 红色,金色 和眼睛 兰色,棕色 ；这里,将人分为两类,分别以、来指示；高度发色眼睛类别名师归纳总结 矮黑色兰色第 12 页,共 20 页高黑色兰色矮金色兰色高金色棕色高黑色棕色矮金色棕色高金色兰色- - - - - - -精选学习资料 - - - - - - - - - 高红色兰色如我们第一选取 发色 为树的根节点,即可获得图6.11

33、 所示的决策树；相应于 黑色 , 红色 和 金色 三值都有一个对象子集；随后我们再测试 金色 这一分支,又按属性 眼睛 把其所含的对象集划分成兰色和棕色二类；至此,全部叶结点相应的对象子集只含同一类的对象,我们就可以用相应的类别名本例中的 + 和 - 来取代各子集,得到一决策树；一个对象所属类的判别从决策树的根开头,第一依据根节点指示的属性 发色,挑选与该对象属性值相应的分支；然后,以同样的方式进行下去 , 始终到达叶节点； 有时判别一个对象的类别, 由于从根到叶节点的路径较短,只要测试少量的属性； 如上例中, 假设 发色 的值是 黑色 或 红色 ,就对象就可以直接归属相应的类别, 而不必再去

34、判定其它属性的取值；假设为 金色 ,就再测试一次眼睛 的值而不必考虑 高度 就可以进行判别；假设不存在这样的二个对象:. 它们在每个属性上都具有相同的值, 却属于不同的类别, 那么这种生成决策树的过程是可行的；产生这种归纳学习方法的关键在于如何挑选一系列有用的属性来测试一个对象集,以使生成的决策树是最小的；ID3 采纳了香农 Shannon信息论中的方法以使分类时期望平均的测试次数最小；一个决策树可看成一个信息源, 即给定一个对象, 可从决策树产生一个该对象所属类别的消息 比方类别 + 或- ；决策树的复杂程度与借助这个消息所传递的信息量亲密相关；假设决策树传递的不同类别消息的概率用: P+

35、对应于 +类 和 P-表示 对应于 - 类 ,那么这个消息的期望信息量为, 此时 P+和 P-分Plog2PPlog2p对给定的物体集C,我们可以把这概率近似地表示为相对频率别等于 C中类别为 + 和- 的对象所占的比例；从 C集对应的决策树中得到消息的期望信息量记为MC,并定义 M=0 ；对于上述例子, C集有八个例子,三个为 + ,五为 - ,就M C 3/ 8log 2 3/ 8 5/ 8log 5/ 8 0.954 bits这是一个局部决策树, A为构造决策树时下一个可能选取的属性,Ai 为属性A的值且是互斥的； 属性 A将集合 C划分为假设干个子集合 C1,C2,. ,Cn；名师归纳

36、总结 - - - - - - -第 13 页,共 20 页精选学习资料 - - - - - - - - - 设 MCi 是值为 Ai 的子集 Ci 所对应决策树的期望信息量,就确定以属性 A 作为树根的决策树的期望信息量BC, A 可通过权值平均而得到 : BC, A A 值为 Ai 的概率 * MCi 同样我们把 Ai 的概率用相比照样来代替, 即在全部对象中具有 Ai 值所占的相比照样；我们期望待选的测试属性能使决策树获得最大的信息增益即 MC-BC, A为最大值；由于 MC为判别一个对象的类属所要求的总的期望信息量,BC,A为按属性 A 构造局部决策树后仍需要的期望信息量；二者的差越大,

37、 说明测试这个属性所能传递的信息量越大 , 就判别的速度也就越快；例如,我们选取的属性为 高度 ,对高度值为 高的分支的所需期望信息量为：2 / 5log 2 / 53/ 5log 3/ 50.971bits同样对值为 矮 的分支为 : 1/ 3log 1/ 32 / 3log 2 / 30.918bits就以属性 高度 作划分后进一步判别所需的期望信息量为：就测试这属性传递的信息为 : bits；假如我们不是挑选 高度 而选用属性 头发, 就有: bits就测试属性 头发 猎取的信息为 MC-BC, 头发 = 0.945 - 0.5 = 0.45 bits ；bits ；依据最大信息量原理

38、,ID3 就选取 头发 为决策树的根节点属性；ID3 通过不断的循环处理,逐步求精决策树,直到形成一棵完整的决策树,即树的叶节点所对应的对象例子均属于同一类；2 C4.5 算法继承了 ID3 算法的优点,并在以下几方面对ID3 算法进行了改良： 1 用信息增益率来挑选属性,克服了用信息增益挑选属性时偏向挑选取值多的属性的不足；名师归纳总结 - - - - - - -第 14 页,共 20 页精选学习资料 - - - - - - - - - 2 在树构造过程中进行剪枝； 3 能够完成对连续属性的离散化处理； 4 能够对不完整数据进行处理；C4.5 算法与其它分类算法如统计方法、神经网络等比较起来

39、有如下优点：产生的分类规章易于懂得,精确率较高；其缺点是：在构造树的过程中,需要对 数据集进行多次的次序扫描和排序,因而导致算法的低效；此外,C4.5 只适合 于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行；C4.5 算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对 数据的归纳分类；1 用信息增益率来挑选属性 克服了用信息增益来挑选属性时偏向挑选值多的属性的不足；信息增益率定义为：GainRatio S A Gain S A 29SplitInfo S A其中 GainS,A 与 ID3 算法中的信息增益相同, 而分裂信息 SplitInfoS,A 代表了依

40、据属性 A 分裂样本集 S 的广度和匀称性；SplitInfo S Aie|S| Log|2|S i|2101|S|S|其中, S1到 Sc是 c 个不同值的属性A分割 S而形成的 c 个样本子集；如依据属性 A 把 S 集含 30 个用例分成了 10 个用例和 20 个用例两个集 合就SplitInfo S A 1/ 3 log 1/ 32 / 3log 2 / 3 22 可以处理连续数值型属性 C4.5 既可以处理离散型描述属性,也可以处理连续性描述属性；在挑选某 节点上的分枝属性时,对于离散型描述属性,C4.5 的处理方法与 ID3 相同,按 照该属性本身的取值个数进行运算；对于某个连续性描述属性 Ac,假设在某个结点上的数据集的样本数量为total ,C4.5 将作以下处理；名师归纳总结 1 将该结点上的全部数据样本依据连续型描述属性的详细数值,由小到大第 15 页,共 20 页进行排序,得到属性值的取值序列A1c,A2c, Atotalc；- - - - - - -精选学习资料 - - - - - - - - - 2 在取值序列中生成total-1个分割点；第i 0itotal个分割