《2022年机器学习算法总结-决策树.docx》由会员分享，可在线阅读，更多相关《2022年机器学习算法总结-决策树.docx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品学习资源第三章 决策树决策树 DecisionTree是在已知各种情形发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评判项目风险， 判定其可行性的决策分析方法， 是直观运用概率分析的一种图解法； 由于这种决策分支画成图形很像一棵树的枝干，故称决策树；在机器学习中，决策树是一个猜测模型，他代 表的是对象属性与对象值之间的一种映射关系；Entropy = 系统的凌乱程度，使用算法 ID3, C4.5和 C5.0 生成树算法使用熵；这一度量是基于信息学理论中熵的概念；2.1 决策树模型与学习2.1.1 决策树模型定义 2.1 决策树分类决策树模型是一种描述对实例进行分类的
2、树形结构；决策树由结点 node和有向边 directed edge组成；决策点， 是对几种可能方案的挑选， 即最终挑选的最正确方案； 假如断策属于多级决策， 就决策树的中间可以有多个决策点， 以决策树根部的决策点为最终决策方案为最终决策方案；状态节点，代表备选方案的经济成效期望值，通过各状态节点的经济成效的比照， 依据肯定的决策标准就可以选出最正确方案； 由状态节点引出的分支称为概率枝， 概率枝的数目表示可能显现的自然状态数目每个分枝上要注明该状态显现的概率；结果节点， 将每个方案在各种自然状态下取得的损益值标注于结果节点的右端；欢迎下载精品学习资源2.1.2 决策树学习决策树是以实例为基础
3、的归纳学习算法；它从一组无次序、 无规章的元组中推理出决策树表示形式的分类规章；它采纳自顶向下的递归方式， 在决策树的内部结点进行属性值的比较， 并依据不同的属性值从该结点向下分支， 叶结点是要学习划分的类； 从根到叶结点的一条路径就对应着一条合取规章，整个决策树就对应着一组析取表达式规章；1986 年Quinlan 提出了闻名的 ID3 算法；在 ID3 算法的基础上， 1993 年 Quinlan 又提出了 C4.5 算法；为了适应处理大规模数据集的需要，后来又提出了假设干改良的算 法， 其 中 SLIQsuper-visedlearninginquest 和 SPRINT scalabl
4、eparallelizableinduction of decision trees是比较有代表性的两个算法；2.1.3 决策树分析法决策树分析法是常用的风险分析决策方法； 该方法是一种用树形图来描述各方案在将来收益的运算； 比较以及挑选的方法， 其决策是以期望值为标准的； 它利用了概率论的原理，并且利用一种树形图作为分析工具；它利用了概率论的原理， 并且利用一种树形图作为分析工具； 其基本原理是用决策点代表决策问题， 用方案分枝代表可供挑选的方案， 用概率分枝代表方案可能显现的各种结果， 经过对各种方案在各种结果条件下损益值的运算比较，为决策者供应决策依据；欢迎下载精品学习资源决策树分析法是
5、常用的风险分析决策方法； 该方法是一种用树形图来描述各方案在将来收益的运算； 比较以及挑选的方法， 其决策是以期望值为标准的； 人们对将来可能会遇到好几种不同的情形； 每种情形均有显现的可能， 人们目前无法确知，但是可以依据以前的资料来推断各种自然状态显现的概率；在这样的条件下，人们运算的各种方案在将来的经济成效只能是考虑到各种自然状态显现的概率的期望值，与将来的实际收益不会完全相等；假如一个决策树只在树的根部有一决策点， 就称为单级决策； 假设一个决策不仅在树的根部有决策点，而且在树的中间也有决策点，就称为多级决策；科学的决策是现代治理者的一项重要职责； 我们在企业治理实践中， 常遇到的情形
6、是：假设干个可行性方案制订出来了，分析一下企业内、外部环境，大部 分条件是己知的， 但仍存在肯定的不确定因素； 每个方案的执行都可能显现几种结果，各种结果的显现有肯定的概率， 企业决策存在着肯定的胜算， 也存在着肯定的风险；这时，决策的标准只能是期望值；即，各种状态下的加权平均值；针对上述问题，用决策树法来解决不失为一种好的挑选；决策树法作为一种决策技术， 已被广泛地应用于企业的投资决策之中， 它是随机决策模型中最常见、 最普及的一种规策模式和方法此方法，有效地掌握了决策带来的风险；所谓决策树法，就是运用树状图表示各决策的期望值， 通过运算， 最终优选出效益最大、 成本最小的决策方法； 决策树
7、法属于风险型决策方法， 不同于确定型决策方法， 二者适用的条件也不同； 应用决策树决策方法必需具备以下条件：1 有决策者期望到达的明确目标；2 存在决策者可以挑选的两个以上的可行备选方案；3 存在着决策者无法掌握的两种以上的自然状态 如气候变化、市场行情、经济进展动向等 ；4 不同行动方案在不同自然状态下的收益值或缺失值 简称损益值 可以运算出来；5 决策者能估量出不同的自然状态发生概率；欢迎下载精品学习资源2.2 特点挑选2.2.1 特点挑选问题1、为什么要做特点挑选在有限的样本数目下， 用大量的特点来设计分类器运算开销太大而且分类性能差；2、特点挑选的确切含义将高维空间的样本通过映射或者是
8、变换的方式转换到低维空间，到达降维的目的，然后通过特点选取删选掉冗余和不相关的特点来进一步降维；3、特点选取的原就猎取尽可能小的特点子集， 不显著降低分类精度、 不影响类分布以及特点子集应具有稳固适应性强等特点4、特点挑选需要考虑的问题a、确定挑选算法，在答应的时间内以最小的代价找出最小的、最能描述类别的特点组合， b、确定评判标准，衡量特点组合是否是最优，得到特点猎取操作的停止条件；5、特点猎取方法a、依据特点子集的形成方式可以分为三种，穷举法exhaustion 、启示法heuristic和随机法random；穷举法需要遍历特点空间中全部的特点组合， 所以方法复杂度最大，有用性不强；启示法
9、通过采纳期望的人工机器调度规章， 重复迭代产生递增的特点子集， 复杂度略低于穷举法， 但是只能猎取近似最优解； 立刻方法分为完全随机方法和概率随机方法两种，对参数设置的依靠性较强；b、依据特点评判标准来分，依据评判函数与分类器的关怀，可以分为挑选器 和封装器两种， 挑选器的评判函数与分类器无关， 封装器采纳分类器的错误概率作为评判函数； 挑选器的评判函数可以细分为距离测度、 信息测度、 相关性测度和一样性测度； 距离测度用距离来衡量样本之间的相像度， 信息测度用利用最小不确定性特点来分类；6、特点猎取方法的选取原就a、处理的数据类型欢迎下载精品学习资源b、处理的问题规模c、问题需要分类的数量d
10、、对噪声的容忍才能e、无噪声环境下，产生稳固性好、最优特点子集的才能；特点挑选的一般过程可用图 1 表示；第一从特点全集中产生出一个特点子集， 然后用评判函数对该特点子集进行评判， 评判的结果与停止准就进行比较， 假设评判结果比停止准就好就停止， 否就就连续产生下一组特点子集， 连续进行特点挑选；选出来的特点子集一般仍要验证其有效性；综上所述，特点挑选过程一般包括产生过程，评判函数，停止准就，验证过 程，这 4 个部分； 1产生过程 Generation Procedure 产生过程是搜寻特点子集的过程， 负责为评判函数供应特点子集； 搜寻特点子集的过程有多种， 将在 2.2 小节绽开介绍；
11、2评判函数 EvaluationFunction 评判函数是评判一个特点子集好坏程度的一个准就； 3停止准就 StoppingCriterion 停止准就是与评判函数相关的， 一般是一个阈值， 当评判函数值到达这个阈值后就可停止搜寻； 4验证过程 ValidationProcedure 在验证数据集上验证选出来的特点子集的有效性；2.2.2 信息增益信息增益Kullback Leiblerdivergence 又称 informationdivergence ，information gain，relative entropy或者 KLIC；在概率论和信息论中，信息增益是非对称的，用以度量两种
12、概率分布P和 Q 的差异；信息增益描述了当使用 Q进行编码时， 再使用 P 进行编码的差异； 通常P代表样本或观看值的分布， 也有可能是精确运算的理论分布； Q代表一种理论， 模型，描述或者对 P 的近似；尽管信息增益通常被直观地作为是一种度量或距离，但事实上信息增益并不是；就比方信息增益不是对称的， 从 P到 Q的信息增益通常不等于从 Q到 P的信息增益；信息增益是 f 增益 f-divergences的一种特别情形；在 1951 年由Solomon Kullback和 Richard Leibler第一提出作为两个分布的直接增益欢迎下载精品学习资源directed divergence；它
13、与微积分中的增益不同，但可以从Bregman 增益Bregman divergence 推导得到；在信息增益中， 重要性的衡量标准就是看特点能够为分类系统带来多少信息， 带来的信息越多，该特点越重要；因此先回忆一下信息论中有关信息量就是“熵” 的定义；说有这么一个变量 X，它可能的取值有 n 多种，分别是 X 1,X 2, Xn ，每一种取到的概率分欢迎下载精品学习资源别是 P1,P2, Pn，那么 X的熵就定义为：H X nPilog 2 Pii 121欢迎下载精品学习资源意思就是一个变量可能的变化越多反而跟变量详细的取值没有任何关系， 只和值的种类多少以及发生概率有关 ，它携带的信息量就越
14、大因此我始终觉得我们的政策法规信息量特别大，由于它变化许多，基本朝令夕改，笑；对分类系统来说，类别 C是变量，它可能的取值是 C1,C 2, Cn ，而每一个类别显现的概率是 PC1, PC 2, PCn ，因此 n 就是类别的总数；此时分欢迎下载精品学习资源类系统的熵就可以表示为：H CnPCi . log 2 PCi 22i 1欢迎下载精品学习资源信息增益是针对一个一个的特点而言的，就是看一个特点 t ，系统有它和没它的时候信息量各是多少， 两者的差值就是这个特点给系统带来的信息量， 即增益；系统含有特点 t 的时候信息量很好运算， 就是刚刚的式子， 它表示的是包含全部特点时系统的信息量；
15、问题是当系统不包含 t 时，信息量如何运算？我们换个角度想问题， 把系统要做的事情想象成这样： 说教室里有许多座位， 同学们每次上课进来的时候可以任凭坐，因而变化是很大的许多种可能的座次情形；但是现在有一个座位， 看黑板很清晰， 听老师讲也很清晰， 于是校长的小舅子的姐姐的女儿托关系 真辗转啊，把这个座位定下来了，每次只能给她坐，别人不行，此时情形怎样？对于座次的可能情形来说， 我们很简洁看出以下两种情形是等价的： 1教室里没有这个座位；2教室里虽然有这个座位，但其他人不能坐由于反正它也不 能参加到变化中来，它是不变的 ；欢迎下载精品学习资源对应到我们的系统中，就是下面的等价： 1系统不包含特
16、点 t ；2系统虽然包含特点 t ，但是 t 已经固定了，不能变化；我们运算分类系统不包含特点 t 的时候，就使用情形 2来代替，就是运算当一个特点 t 不能变化时， 系统的信息量是多少； 这个信息量其实也有特地的名称，就叫做“条件熵” ，条件嘛，自然就是指“ t 已经固定“这个条件；但是问题接踵而至， 例如一个特点 X，它可能的取值有 n 多种 x1,x2, xn ，当运算条件熵而需要把它固定的时候， 要把它固定在哪一个值上呢？答案是每一种可能都要固定一下， 运算 n 个值， 然后取均值才是条件熵； 而取均值也不是简洁的加一加然后除以 n，而是要用每个值显现的概率来算平均简洁懂得，就是一个值
17、显现的可能性比较大， 固定在它上面时算出来的信息量占的比重就要多一些；欢迎下载精品学习资源因此有这样两个条件熵的表达式：H C| Xxi 23欢迎下载精品学习资源欢迎下载精品学习资源这是指特点 X 被固定为值 xi 时的条件熵，H C| X 24欢迎下载精品学习资源这是指特点 X 被固定时的条件熵， 留意与上式在意义上的区分； 从刚刚运算均值的争论可以看出来，其次个式子与第一个式子的关系就是：欢迎下载精品学习资源H C | X P1HC |Xx1P2 H C | Xx2 .Pn H C |Xxn nPi Hi 1C |Xxi 25欢迎下载精品学习资源2.2.3 熵在信息论中， 要对符号进行编码
18、， 一个符号的熵就是要表示这个符号所需要的最少二进制数位数；这是一个极限；这也是信息压缩的基础；条件熵，当两个 符号之间存在某种关系，或者两个随机变量不相互独立的时候，对于A，B 两个随机大事，非独立，知道 A 的情形， B的不确定性削减；举例来说，假设 S 是一个关于布尔概念的有 14 个样例的集合，它包括 9 个正例和 5 个反例我们采纳记号 9+ ，5- 来概括这样的数据样例 ，那么 S 相对于这个布尔样例的熵为：欢迎下载精品学习资源Entropy 9 ,59 /14 log 29 /145 /14log 25 /140.940 留意，假如S欢迎下载精品学习资源的全部成员属于同一类，En
19、tropyS0 ，例如，假如全部的成员是正的 p1，欢迎下载精品学习资源欢迎下载精品学习资源那么 p- 就是 0，于是EntropyS1*log2 10log2 00 ； 另外 S 的正反样欢迎下载精品学习资源例数量相等， EntropyS1 ； S的正反样例数量不等，熵介于 0，1 之间，如下列图所示：/ 依据详细属性和值来运算熵double ComputeEntropyvectorvector remain_state, stringattribute,string value,bool ifparentvector count 2,0; unsigned int i,j;bool don
20、e_flag = false;/ 哨兵值forj = 1; j MAXLEN; j+ifdone_flag break;if.attribute_rowjpareattributefori=1;i;i+if.ifparent&.remain_stateijparevalue | ifparent/ifparen记录是否算父节点if.remain_stateiMAXLEN- 1pareyescount0+; else count1+;done_flag = true;ifcount0 = 0 | count1 = 0 return 0;/全部是正实例或者负实例/详细运算熵依据 +count0,
21、-count1,log2为底通过换底公式换成自然数底数double sum = count0 + count1;欢迎下载精品学习资源doubleentropy= - count0/sum*logcount0/sum/log2.0- count1/sum*logcount1/sum/log2.0;return entropy;举个例子： A 大事是： 季节 春，夏，秋，冬 ，B 大事是： 天气 下雨，下雪，晴天，多云 ；那就可以画出一个二维表格， 最直观的是 夏天&下雪的概率 冬天&下雪的概率；当我知道天气是下雪的时候， 我就有很大的概率认为季节是冬天； 这说明：我知道了 B 大事的情形， 对
22、A 的不确定性削减了； 假如 A，B 是独立的， 比方， A 大事是季节 春，夏，秋，冬 ， B 大事是交通的情形 堵，不堵 ，我知道 B 的情形， 对 A的不确定性并没影响； 上面说的是概念性的懂得， 假如用数学公式对应起来懂得，为什么会显现这样的情形？P A | B 已知 B 的情形，A的概率有没有变化？当 A，B 独立， PA | BP A说明 没有变化， 当 AB不独立的时候， 即两者存在某种相关性质， 换句话说就是B确定的前提下， A 的概率分布与在总体上看不一样；信息论中有熵，用来表示时间的不确定性，这个跟这个大事的可能值数目， 仍有取每个值的概率，比方有A 大事1,2,3,4每个
23、取值等概，那么熵为 2；假如 A1,2 每个取值等概率，熵为1 ；当取值数目一样的时候A1,2,3,4，欢迎下载精品学习资源P A1P A2P A31/ 6 ， P A41/ 2 ，那么这个熵小于 2；这是欢迎下载精品学习资源为什么？由于在数据压缩方面， 对于小概率大事就要用长的编码， 大致率大事用短编码，这样最终平均每个大事的编码就比较小！ 而对于等概率大事， 这种策略就没法使用，就没法实现数据的压缩；熵说的就是这种下界；反过来，当我们说一个大事熵很大，就意味着1 这个大事的取值范畴许多2或者这个大事中每个取值的概率比较匀称以上两者都代表着这个大事的不确定性很大， 所以我们又说熵是一种不确定
24、性的度量欢迎下载精品学习资源那么什么是条件熵呢，为什么H A | B 小于等于H A 呢？欢迎下载精品学习资源上面说了，知道了 B，1：第一 A 的取值范畴会缩小，为什么？拿上面一个例子来说，我知道了天气是下雪， 那么几乎可以说 A 的取值只能从 春天， 冬天 里选欢迎下载精品学习资源择；2：A 中每个取值的概率分布会发生变化P A | Bb 与P A 的概率分布不同；欢迎下载精品学习资源欢迎下载精品学习资源数学证明H A | BH ABH BH A ；即已知 B 的结果， A 的不确定性减欢迎下载精品学习资源少；要表述 A 这个大事的编码数更少；在决策树中，我们关怀的是H结果 | 属性的关系
25、，即已知某属性，结果的不确定性仍有多少； 我们需要知道，哪个属性能使得结果的不确定性削减最多；2.3 决策树的生成2.3.1 ID3算法假如学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示， 就可以采纳例如学习方法的一个变种 决策树学习，其代表性的算法是昆兰，1986提出的 ID3；ID3 算法是由 Quinlan 第一提出的；该算法是以信息论为基础，以信息熵和信息增益度为衡量标准， 从而实现对数据的归纳分类； 以下是一些信息论的基本概念：定义：假设存在 n 个相同概率的消息，就每个消息的概率p 是 1/n ，一个消息传递的信息量为 Log2 n欢
26、迎下载精品学习资源定义 2.3 ：假设有 n 个消息，其给定概率分布为P p1, p2pn ，就由该欢迎下载精品学习资源欢迎下载精品学习资源分布传递的信息量称为P 的熵，记为I pnpi Log 2 pi ；i 1欢迎下载精品学习资源定义：假设一个记录集合 T 依据类别属性的值被分成相互独立的类C1C2.Ck， 就识别 T 的一个元素所属哪个类所需要的信息量为InfoT=Ip，其中 P 为欢迎下载精品学习资源C1C2Ck 的概率分布，即 P| C1| / | T|,| Ck | / | T|26 ；欢迎下载精品学习资源定义：假设我们先依据非类别属性X的值将 T 分成集合 T1,T2Tn，就确定
27、T 中一个元素类的信息量可通过确定Ti 的加权平均值来得到，即 InfoTi的加欢迎下载精品学习资源权平均值为：nInfo X ,T | Ti | / | T| Info Ti 27欢迎下载精品学习资源i 1定义：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量， 另一个信息量是在已得到的属性X 的值后需确定的 T 一个欢迎下载精品学习资源元素的信息量，信息增益度公式为：Gain X,TInfoTInfo X ,T 28 ID3欢迎下载精品学习资源算法运算每个属性的信息增益， 并选取具有最高增益的属性作为给定集合的测试属性；对被选取的测试属性创建一个节点， 并以该节
28、点的属性标记， 对该属性的每个值创建一个分支据此划分样本；ID3 的输入是描述各种已知类别实例的列表； 例子由预先定义的属性值对来表示；归纳推理产生的结果不是以往争论的那种合取表达式， 而是一棵决策树也称判别树，并可转而表示为决策规章的一个集合 ，用它可正确地区分全部给定例子的类属；树中的每一非叶节点对应一个需测试的属性， 每个分叉就是该属性可能的取值；树的叶节点就指示一个例子事物的类别；ID3 的显著优点是归纳学习花费的时间和所给任务的困难度 取决于例子个数， 用来描述对象的属性数， 所学习概念的复杂度即决策树的节点数等仅成线性增长关系；当然，ID3 只能处理用属性- 值对表示的例子；在 I
29、D3 中,每一个例子用相同的一组属性来表示， 每一个属性又有自身的属性值集，如 颜色 属性可取值是 红、绿、兰 等；构造决策树的目的是为了对事物作出正确的分类；决策树形式的分类规章适用于任何的对象集； 如是空的， 那么它无需分类， 对应的决策树也为空； 如中的对象是同一类的， 那么决策树就一个叶节点， 即该类名； 假如集中的对象属于二个不同的类别， 那未我们可以选取一个对象的属性，随后按其可能值把划分成一些不相交的子集C1， C2， Cn，其中 Ci 是含有所选属性的第个值的那些对象集；对每一个这样的子集又可以用同样的策略处理，最终的结果是一棵树；ID3 Examples,Target-att
30、rlbute,Attrlbutes 创建树的 root 节点欢迎下载精品学习资源假如 Examples 都为正，返回 label=+ 的单节点输 root假如 Examples 都为反，返回 label= -的单节点输 root如 果 Attrlbutes为 空 ， 那 么 返 回 单 节 点 输 root ， label=Examples中 最 普 遍 的Target-attributes 值AAttributes 中分类 examples 才能最好的属性Root 的决策属性A对于 A 的每个可能值 vi在 root 下加一个新的分支对应测试A=vi令 Examples 为 Examples
31、 中满意 A 属性值为 vi 的子集假如 Examples 为空在这个新分支下加一个叶子结点，节点的label=Examples中最普遍的Target-attributes 值否就在新分支下加一个子树ID3Examples Target-attribute ，Attributes -A 终止返回 root下面给出一个关于人分类的例子 对象集，并预先定义了指定的一组属性及其可取值：高度 高，矮 ，发色. 黑色,红色，金色 和眼睛 兰色，棕色 ；这里，将人分为两类，分别以、来指示；否就开头高度发色眼睛类别矮黑色兰色高黑色兰色矮金色兰色高金色棕色高黑色棕色矮金色棕色高金色兰色欢迎下载精品学习资源高红
32、色兰色如我们第一选取 发色 为树的根节点，即可获得图 6.11 所示的决策树；相应于 黑色 ， 红色 和 金色 三值都有一个对象子集；随后我们再测试金色 这一分支，又按属性 眼睛 把其所含的对象集划分成兰色和棕色二类；至此，全部叶结点相应的对象子集只含同一类的对象，我们就可以用相应的类别名本例中的 + 和 - 来取代各子集，得到一决策树；一个对象所属类的判别从决策树的根开头， 第一依据根节点指示的属性 发色，挑选与该对象属性值相应的分支；然后，以同样的方式进行下去,始终到达叶节点； 有时判别一个对象的类别， 由于从根到叶节点的路径较短， 只要测试少量的属性； 如上例中， 假设 发色 的值是 黑
33、色 或 红色 ，就对象就可以直接归属相应的类别， 而不必再去判定其它属性的取值； 假设为 金色 ，就再测试一次 眼睛 的值而不必考虑 高度 就可以进行判别；假设不存在这样的二个对象 :. 它们在每个属性上都具有相同的值， 却属于不同的类别， 那么这种生成决策树的过程是可行的；产生这种归纳学习方法的关键 在于如何挑选一系列有用的属性来测试一个对象集，以使生成的决策树是最小的；ID3 采纳了香农 Shannon信息论中的方法以使分类时期望平均的测试次数最小；一个决策树可看成一个信息源， 即给定一个对象， 可从决策树产生一个该对象所属类别的消息 比方类别 + 或-；决策树的复杂程度与借助这个消息所传
34、递的信息量亲密相关；假设决策树传递的不同类别消息的概率用P+ 对应于+ 类 和 P-表示 对应于- 类 ，那么这个消息的期望信息量为 :Plog 2 PPlog 2 p对给定的物体集 C，我们可以把这概率近似地表示为相对频率,此时 P+和 P-分别等于 C中类别为 + 和- 的对象所占的比例；从 C集对应的决策树中得到消息的期望信息量记为MC，并定义 M=0 ；对于上述例子， C集有八个例子，三个为 + ，五为- ，就欢迎下载精品学习资源M C 3/ 8log2 3/ 85/ 8log25/ 80.954bits欢迎下载精品学习资源这是一个局部决策树， A为构造决策树时下一个可能选取的属性，
35、Ai 为属性A的值且是互斥的； 属性 A将集合 C划分为假设干个子集合 C1，C2，.，Cn；欢迎下载精品学习资源设 MCi 是值为 Ai 的子集 Ci 所对应决策树的期望信息量， 就确定以属性 A 作为树根的决策树的期望信息量 BC, A 可通过权值平均而得到 :BC, A A 值为 Ai 的概率 * MCi同样我们把 Ai 的概率用相比照样来代替， 即在全部对象中具有 Ai 值所占的相比照样；我们期望待选的测试属性能使决策树获得最大的信息增益即MC-BC, A 为最大值；由于 MC为判别一个对象的类属所要求的总的期望信息量，BC,A 为按属性 A 构造局部决策树后仍需要的期望信息量； 二者
36、的差越大， 说明测试这个属性所能传递的信息量越大 , 就判别的速度也就越快；例如，我们选取的属性为 高度 ，对高度值为 高 的分支的所需期望信息量为：2 / 5log 2 2 / 53/ 5log 2 3/ 50.971bits同样对值为 矮 的分支为 :1/ 3log 21/ 32 / 3log 2 2 / 30.918bits就以属性 高度 作划分后进一步判别所需的期望信息量为：就测试这属性传递的信息为 : bits；假如我们不是挑选 高度 而选用属性 头发, 就有:bits就测试属性 头发 猎取的信息为 MC-BC, 头发= 0.945 - 0.5 = 0.45 bits ；bits ；
37、依据最大信息量原理 ,ID3 就选取 头发 为决策树的根节点属性；ID3 通过不断的循环处理，逐步求精决策树，直到形成一棵完整的决策树， 即树的叶节点所对应的对象例子均属于同一类；2C4.5 算法继承了 ID3 算法的优点，并在以下几方面对 ID3 算法进行了改良：1) 用信息增益率来挑选属性，克服了用信息增益挑选属性时偏向挑选取值多的属性的不足；欢迎下载精品学习资源2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理；C4.5 算法与其它分类算法如统计方法、神经网络等比较起来有如下优点： 产生的分类规章易于懂得，精确率较高；其缺点是：在构造树的过
38、程中，需要对 数据集进行多次的次序扫描和排序，因而导致算法的低效；此外，C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行； C4.5 算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类；1 用信息增益率来挑选属性克服了用信息增益来挑选属性时偏向挑选值多的属性的不足；信息增益率欢迎下载精品学习资源定义为：GainRatioS, AGain S, A29欢迎下载精品学习资源SplitInfo S, A其中GainS,A 与 ID3 算法中的信息增益相同， 而分裂信息 SplitInfoS,A代表了依据属性 A 分裂样本集 S 的广度和匀
39、称性；欢迎下载精品学习资源SplitInfo S, Ae | Si| Si |Log 2210欢迎下载精品学习资源i 1 | S | S |其中， S1到 Sc是 c 个不同值的属性 A分割 S而形成的 c 个样本子集；如依据属性 A 把 S 集含 30 个用例分成了 10 个用例和 20 个用例两个集合2就SplitInfoS, A1/ 3log 2 1/ 32 / 3log 2 / 3 2 可以处理连续数值型属性C4.5 既可以处理离散型描述属性，也可以处理连续性描述属性；在挑选某节点上的分枝属性时，对于离散型描述属性， C4.5 的处理方法与 ID3 相同，依据该属性本身的取值个数进行运
40、算；对于某个连续性描述属性 Ac，假设在某个结点上的数据集的样本数量为 total ，C4.5 将作以下处理；(1) 将该结点上的全部数据样本依据连续型描述属性的详细数值， 由小到大进行排序，得到属性值的取值序列 A1c，A2c， Atotalc ；欢迎下载精品学习资源(2) 在取值序列中生成 total-1个分割点；第 i 0itotal个分割点的取值设置为 Vi=Aic+Ai+1 c/2, 它可以将该节点上的数据集划分为两个子集；(3) 从 total-1个分割点中挑选最正确分割点； 对于每一个分割点划分数据集的方式， C4.5 运算它的信息增益比，并且从中挑选信息增益比最大的分割点来划分
41、数据集；3 采纳了一种后剪枝方法防止树的高度无节制的增长，防止过度拟合数据，该方法使用训练样本集本身来估量剪枝前后的误差，从而打算是否真正剪欢迎下载精品学习资源枝；方法中使用的公式如下：Prfqzc211欢迎下载精品学习资源q 1q / N其中 N是实例的数量， f=E/N 为观看到的误差率其中 E 为 N个实例中分类错误的个数，q 为真实的误差率， c 为置信度，z 为对应于置信度 c 的标准差，其值可依据 c 的设定值通过查正态分布表得到； 通过该公式即可运算出真实误差率 q 的一个置信度上限，用此上限为该节点误差率e 做一个悲观的估量：z2ff 2z2fZ2欢迎下载精品学习资源e2NNN
42、4Nz2212欢迎下载精品学习资源1N通过判定剪枝前后 e 的大小，从而打算是否需要剪枝；4 对于缺失值的处理在某些情形下，可供使用的数据可能缺少某些属性的值；假设x，cx 是样本集 S 中的一个训练实例，但是其属性A 的值 Ax 未知；处理缺少属性值的一种策略是赋给它结点 n 所对应的训练实例中该属性的最常见值； 另外一种更复杂的策略是为 A 的每个可能值给予一个概率；例如，给定一个布尔属性A，假如结点 n 包含 6 个已知 A=1和 4 个 A=0的实例，那么 Ax=1 的概率是 0.6 ，而Ax=0 的概率是 0.4 ；于是，实例 x 的 60%被安排到 A=1的分支， 40%被安排到另一个分支；这些片断样例 fractional examples的目的是运算信息增益， 另外，假如有其次个缺少值的属性必需被测试， 这些样例可以在后继的树分支中被进一步细分； C4.5 就是使用这种方法处理缺少的属性值；