第八章机器学习决策树ID3算法的实例解析课件_第1页
第八章机器学习决策树ID3算法的实例解析课件_第2页
第八章机器学习决策树ID3算法的实例解析课件_第3页
第八章机器学习决策树ID3算法的实例解析课件_第4页
第八章机器学习决策树ID3算法的实例解析课件_第5页
已阅读5页,还剩101页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

决策树模型决策树模型1排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg共有145人参加了ICDM2006Panel(会议的专题讨论),并对18种候选算法进行投票,选出了数据挖掘10大算法ICDM2006会议的算法投票结果排名挖掘主题算法得票数发表时间作者陈述人1分类C4.56112信息的定量描述衡量信息多少的物理量称为信息量。若概率很大,受信者事先已有所估计,则该消息信息量就很小;若概率很小,受信者感觉很突然,该消息所含信息量就很大。信息的定量描述衡量信息多少的物理量称为信息量。3信息量的定义根据客观事实和人们的习惯概念,函数f(p)应满足以下条件:f(p)应是概率p的严格单调递减函数,即当p1>p2,f(p1)<f(p2);当p=1时,f(p)=0;当p=0时,f(p)=∞;两个独立事件的联合信息量应等于它们分别的信息量之和。信息量的定义根据客观事实和人们的习惯概念,函数f(p)应满足4对信息量的

认识理解

信息量的定义若一个消息x出现的概率为p,则这一消息所含的信息量为其中,对数的底大于1信息量单位以2为底时,单位为bit(binaryunit,比特)以e为底时,单位为nat(naturalunit,奈特)以10为底时,单位为hart(Hartley,哈特)对信息量的

认识理解

信息量的定义5抛一枚均匀硬币,出现正面与反面的信息量是多少?解:出现正面与反面的概率均为0.5,它们的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b抛一枚均匀硬币,出现正面与反面的信息量是多少?6抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出现正面与反面时的信息量是多少?解:出现正面与反面的概率分别是1/4,3/4,它们的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出7信源含有的信息量是信源发出的所有可能消息的平均不确定性,香农把信源所含有的信息量称为信息熵,是指每个符号所含信息量的统计平均值。m种符号的平均信息量为信源含有的信息量是信源发出的所有可能消息的平均不确定性,香农8抛一枚均匀硬币的信息熵是多少?解:出现正面与反面的概率均为0.5,信息熵是抛一枚均匀硬币的信息熵是多少?9抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出现正面与反面时的信息量是多少?解:出现正面与反面的概率分别是1/4,3/4,信息熵是抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出10例:气象预报例:气象预报1112条件自信息量在事件yj出现的条件下,随机事件xi发生的条件概率为p(xi|yj),则它的条件自信息量定义为条件概率对数的负值:12条件自信息量在事件yj出现的条件下,随机事件xi发生的条13条件熵在给定yj条件下,xi的条件自信息量为I(xi|yj),X集合的条件熵H(X|yj)为在给定Y(即各个yj

)条件下,X集合的条件熵H(X|Y)条件熵H(X|Y)表示已知Y后,X的不确定度13条件熵在给定yj条件下,xi的条件自信息量为I(xi|是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎14活动天气是否进行垒球活动进行取消晴阴雨晴阴雨活动进行取消活动天气是否进行垒球活动进行取消晴阴雨晴阴雨活动进行15活动的熵活动有2个属性值,进行,取消。其熵为:H(活动)=-(9/14)*log

(9/14)-(5/14)*log

(5/14)=0.94活动进行取消活动的熵活动有2个属性值,进行,取消。其熵为:活动进行取消16已知户外的天气情况下活动的条件熵户外有三个属性值,晴,阴和雨。其熵分别为:H(活动|户外=晴)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971H(活动|户外=阴)=-(4/4)*log2(4/4)=0H(活动|户外=雨)=-(3/5)*log2(3/5)-(2/5)*log2(2/5)=0.971活动天气进行取消晴阴雨已知户外的天气情况下活动的条件熵户外有三个属性值,晴,阴和雨17已知户外时活动的条件熵H(活动|户外)=5/14*H(活动|户外=晴)+4/14*H(活动|户外=阴)+5/14*H(活动|户外=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693晴阴雨已知户外时活动的条件熵H(活动|户外)=5/14*H(活动|18平均互信息I(活动;户外)=H(活动)-H(活动|户外)=0.94-0.693=0.246平均互信息I(活动;户外)=H(活动)-H(活动|户19是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎20活动的熵H(活动)=-(9/14)*lb

(9/14)-(5/14)*lb

(5/14)=0.94天气

温度

湿度

风速

活动

炎热

进行

适中

进行

寒冷

正常

进行

寒冷

正常

进行

寒冷

正常

进行

适中

正常

进行

适中

正常

进行

适中

进行

炎热

正常

进行

炎热

取消

炎热

取消

寒冷

正常

取消

适中

取消

适中

取消

活动的熵H(活动)=-(9/14)*lb(9/14)21已知天气时活动的条件熵H(活动|天气)=5/14*H(活动|天气=晴)+4/14*H(活动|天气=阴)+5/14*H(活动|天气=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693温度

湿度

风速

天气

活动

寒冷

正常

进行

适中

正常

进行

炎热

取消

炎热

取消

适中

取消

炎热

进行

寒冷

正常

进行

适中

进行

炎热

正常

进行

适中

进行

寒冷

正常

进行

适中

正常

进行

寒冷

正常

取消

适中

取消

已知天气时活动的条件熵H(活动|天气)=5/14*H(活动|22天气

湿度

风速

温度

活动

炎热

进行

正常

炎热

进行

炎热

取消

炎热

取消

适中

进行

正常

适中

进行

正常

适中

进行

适中

进行

适中

取消

适中

取消

正常

寒冷

进行

正常

寒冷

进行

正常

寒冷

进行

正常

寒冷

取消

已知温度时活动的条件熵H(活动|温度)=0.911天气湿度风速温度活动阴高弱炎热进行阴正23天气

温度

风速

湿度

活动

炎热

进行

适中

进行

适中

进行

炎热

取消

炎热

取消

适中

取消

适中

取消

寒冷

正常

进行

寒冷

正常

进行

寒冷

正常

进行

适中

正常

进行

适中

正常

进行

炎热

正常

进行

寒冷

正常

取消

H(活动|湿度)

=0.789已知湿度时活动的条件熵天气温度风速湿度活动阴炎热弱高进行雨适24天气

温度

湿度

风速

活动

寒冷

正常

进行

适中

正常

进行

适中

进行

炎热

取消

寒冷

正常

取消

适中

取消

炎热

进行

适中

进行

寒冷

正常

进行

寒冷

正常

进行

适中

正常

进行

炎热

正常

进行

炎热

取消

适中

取消

H(活动|风速)=0.892已知风速时活动的条件熵天气温度湿度风速活动阴寒冷正常强进行晴25各互信息量I(活动;天气)=H(活动)-H(活动|天气)=0.94-0.693=0.246I(活动;温度)=

H(活动)-H(活动|温度)=0.94-0.911=0.029I(活动;湿度)=

H(活动)-H(活动|湿度)=0.94-0.789=0.151I(活动;风速)=

H(活动)-H(活动|风速)=0.94-0.892=0.048各互信息量I(活动;天气)=H(活动)-H(活动|天26天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消温度

湿度

风速

活动

寒冷

正常

进行

适中

正常

进行

炎热

取消

炎热

取消

适中

取消

温度

湿度

风速

活动

适中

进行

寒冷

正常

进行

适中

正常

进行

寒冷

正常

取消

适中

取消

温度湿度风速活动炎热高弱进行寒冷正常强进行适中高强进行炎热正常弱进行阴晴雨天气

温度

湿度

风速

活动

寒冷

正常

进行

适中

正常

进行

炎热

取消

炎热

取消

适中

取消

炎热

进行

寒冷

正常

进行

适中

进行

炎热

正常

进行

适中

进行

寒冷

正常

进行

适中

正常

进行

寒冷

正常

取消

适中

取消

天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进27ID3算法生成的决策树ID3算法生成的决策树28ID3算法ID3(A:条件属性集合,d:决策属性,U:训练集)返回一棵决策树{ifU为空,返回一个值为Failure的单结点;//一般不会出现这种情况,为了程序的健壮性ifU是由其值均为相同决策属性值的记录组成,返回一个带有该值的单结点;//此分支至此结束ifA为空,则返回一个单结点,其值为在U的记录中找出的频率最高的决策属性值;//这时对记录将出现误分类将A中属性之间具有最大I(d;a)的属性赋给a;将属性a的值赋给{aj|j=1,2,…,m};将分别由对应于a的值的aj的记录组成的U的子集赋值给{uj|j=1,2,…,m};返回一棵树,其根标记为a,树枝标记为a1,a2,…,am;再分别构造以下树:ID3(A-{a},d,u1),ID3(A-{a},d,u2),…,ID3(A-{a},d,um);//递归算法}ID3算法ID3(A:条件属性集合,d:决策属性,U:训练集292003.11.1830决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题,ID3被扩展成C4.52003.11.1830决策树学习的常见问题决策树学习的实际2003.11.1831避免过度拟合数据过度拟合对于一个假设,当存在其他的假设对训练样例的拟合比它差,但事实上在实例的整个分布上表现得却更好时,我们说这个假设过度拟合训练样例定义:给定一个假设空间H,一个假设hH,如果存在其他的假设h’H,使得在训练样例上h的错误率比h’小,但在整个实例分布上h’的错误率比h小,那么就说假设h过度拟合训练数据。2003.11.1831避免过度拟合数据过度拟合2003.11.1832避免过度拟合数据(2)导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声当训练数据没有噪声时,过度拟合也有可能发生,特别是当少量的样例被关联到叶子节点时,很可能出现巧合的规律性,使得一些属性恰巧可以很好地分割样例,但却与实际的目标函数并无关系。2003.11.1832避免过度拟合数据(2)导致过度拟合的33避免过度拟合数据(3)避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中,精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功33避免过度拟合数据(3)避免过度拟合的方法2003.11.1834避免过度拟合数据(4)避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例,来评估通过后修剪方法从树上修建节点的效用。使用所有可用数据进行训练,但进行统计测试来估计扩展(或修剪)一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度,当这个编码的长度最小时停止树增长。2003.11.1834避免过度拟合数据(4)避免过度拟合的2003.11.1835避免过度拟合数据(5)方法评述第一种方法是最普通的,常被称为训练和验证集法。可用数据分成两个样例集合:训练集合,形成学习到的假设验证集合,评估这个假设在后续数据上的精度方法的动机:即使学习器可能会被训练集合误导,但验证集合不大可能表现出同样的随机波动验证集合应该足够大,以便它本身可提供具有统计意义的实例样本。常见的做法是,样例的三分之二作训练集合,三分之一作验证集合。2003.11.1835避免过度拟合数据(5)方法评述2003.11.1836错误率降低修剪将树上的每一个节点作为修剪得候选对象修剪步骤删除以此节点为根的子树,使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点,每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点继续修剪,直到进一步的修剪是有害的为止数据分成3个子集训练样例,形成决策树验证样例,修剪决策树测试样例,精度的无偏估计如果有大量的数据可供使用,那么使用分离的数据集合来引导修剪2003.11.1836错误率降低修剪将树上的每一个节点作为2003.11.1837规则后修剪从训练集合推导出决策树,增长决策树直到尽可能好地拟合训练数据,允许过度拟合发生将决策树转化为等价的规则集合,方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序,并按这样的顺序应用这些规则来分类后来的实例2003.11.1837规则后修剪从训练集合推导出决策树,增2003.11.1838规则后修剪(2)例子if(outlook=sunny)(Humidity=High)thenPlayTennis=No考虑删除先行词(outlook=sunny)和(Humidity=High)选择使估计精度有最大提升的步骤考虑修剪第二个前件2003.11.1838规则后修剪(2)例子2003.11.1839规则后修剪(3)规则精度估计方法使用与训练集不相交的验证集基于训练集合本身被C4.5使用,使用一种保守估计来弥补训练数据有利于当前规则的估计偏置过程先计算规则在它应用的训练样例上的精度然后假定此估计精度为二项式分布,并计算它的标准差对于一个给定的置信区间,采用下界估计作为规则性能的度量评论对于大的数据集,保守预测非常接近观察精度,随着数据集合的减小,离观察精度越来越远不是统计有效,但是实践中发现有效2003.11.1839规则后修剪(3)规则精度估计方法2003.11.1840规则后修剪(4)把决策树转化成规则集的好处可以区分决策节点使用的不同上下文消除了根节点附近的属性测试和叶节点附近的属性测试的区别提高了可读性2003.11.1840规则后修剪(4)把决策树转化成规则集2003.11.1841合并连续值属性ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现,即先把连续值属性的值域分割为离散的区间集合2003.11.1841合并连续值属性ID3被限制为取离散值2003.11.1842合并连续值属性(2)例子,Temperature应该定义什么样的基于阈值的布尔属性选择产生最大信息增益的阈值按照连续属性排列样例,确定目标分类不同的相邻实例产生一组候选阈值,它们的值是相应的A值之间的中间值可以证明产生最大信息增益的c值位于这样的边界中(Fayyad1991)通过计算与每个候选阈值关联的信息增益评估这些候选值方法的扩展连续的属性分割成多个区间,而不是单一阈值的两个空间2003.11.1842合并连续值属性(2)例子,Tempe2003.11.1843小结和补充读物决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法ID3算法贪婪算法从根向下推断决策树搜索完整的假设空间归纳偏置,较小的树过度拟合问题ID3算法的扩展2003.11.1843小结和补充读物决策树学习为概念学习和2003.11.1844附录C4.5isasoftwareextensionofthebasicID3algorithmdesignedbyQuinlantoaddressthefollowingissuesnotdealtwithbyID3:AvoidingoverfittingthedataDetermininghowdeeplytogrowadecisiontree.Reducederrorpruning.Rulepost-pruning.Handlingcontinuousattributes.e.g.,temperatureChoosinganappropriateattributeselectionmeasure.Handlingtrainingdatawithmissingattributevalues.Handlingattributeswithdifferingcosts.Improvingcomputationalefficiency.2003.11.1844附录C4.5isasoftwa分类器评价标准预测准确度计算复杂度模型描述的简洁度:产生式规则分类器评价标准预测准确度45准确度分析一般采用召回率r(Recall)和精准率p(Precision)这两个指标衡量分类器的准确度。—个好的分类器应同时具有较高的召回率和精准率,当然这两个指标一般情况下是互斥的,有时要根据需要在这两个指标间作某种权衡和妥协。准确度分析一般采用召回率r(Recall)和精准率p(Pre46召回率r(Recall)和精准率p(Precision)为了定义这两个指标,引入分类中常用的两个基本概念,Relevant和Retrieved。Relevant:真正属于某类的集合Retrieved:判断属于某类的集合召回率反映了分类器正确分类的对象在真正归入该类的对象中所占的比率,而精准率反映了分类器正确分类的对象在系统归入该类的对象中所占的比率。RelevantRetrievedRelevant∩RetrievedRelevantRetrievedRelevant∩Retrieved召回率r(Recall)和精准率p(Precision)为了47F1召回率和精准率反映了分类质量的两个不同侧面,两者必须综合考虑,不可偏废,因此,可引入一种新的评价指标F1,该指标综合了这两种因素,其公式如下:F1召回率和精准率反映了分类质量的两个不同侧面,两者必须综合48构造分类器的主要步骤将现有的已知类别的数据划分为训练集和测试集两部分。构造分类算法对训练集进行学习,得到一个分类模型,它可以以分类规则、决策树或数学公式等形式给出。使用分类模型对测试集进行检测,如果符合测试要求(如分类精度),则进行④;否则,返回②。应用得到的分类模型对未知类别的数据进行分类。构造分类器的主要步骤将现有的已知类别的数据划分为训练集和测试49训练数据和测试数据的划分方法其中,对于步骤(1),目前主要有两种划分方法:保持(holdout)方法。保持方法将已知数据随机划分为训练数据和测试数据两部分,一般是三分之二作为训练数据,另外三分之一作为测试数据。使用训练数据导出分类模型,它在测试数据上的分类精度作为最终的分类精度。k折交叉验证(k-foldcrossvalidation)方法。k折交叉验证则将已知数据随机划分为k个大致相等的数据子集S1,S2,…,Sk,训练和测试重复进行k次。在第i次过程中,Si作为测试数据,其余的子集则作为训练数据。最终分类器的分类精度取k次测试分类精度的平均值。这种方法适用于原始数据量较小的情况,这时不适合直接应用保持方法。训练数据和测试数据的划分方法其中,对于步骤(1),目前主要有50作业给出决策树方法的模型、策略、算法;C4.5决策树方法中的信息增益比的特点?C4.5决策树方法生成的决策树的特点?作业给出决策树方法的模型、策略、算法;51谢谢!谢谢!52演讲完毕,谢谢观看!演讲完毕,谢谢观看!53决策树模型决策树模型54排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg共有145人参加了ICDM2006Panel(会议的专题讨论),并对18种候选算法进行投票,选出了数据挖掘10大算法ICDM2006会议的算法投票结果排名挖掘主题算法得票数发表时间作者陈述人1分类C4.561155信息的定量描述衡量信息多少的物理量称为信息量。若概率很大,受信者事先已有所估计,则该消息信息量就很小;若概率很小,受信者感觉很突然,该消息所含信息量就很大。信息的定量描述衡量信息多少的物理量称为信息量。56信息量的定义根据客观事实和人们的习惯概念,函数f(p)应满足以下条件:f(p)应是概率p的严格单调递减函数,即当p1>p2,f(p1)<f(p2);当p=1时,f(p)=0;当p=0时,f(p)=∞;两个独立事件的联合信息量应等于它们分别的信息量之和。信息量的定义根据客观事实和人们的习惯概念,函数f(p)应满足57对信息量的

认识理解

信息量的定义若一个消息x出现的概率为p,则这一消息所含的信息量为其中,对数的底大于1信息量单位以2为底时,单位为bit(binaryunit,比特)以e为底时,单位为nat(naturalunit,奈特)以10为底时,单位为hart(Hartley,哈特)对信息量的

认识理解

信息量的定义58抛一枚均匀硬币,出现正面与反面的信息量是多少?解:出现正面与反面的概率均为0.5,它们的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b抛一枚均匀硬币,出现正面与反面的信息量是多少?59抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出现正面与反面时的信息量是多少?解:出现正面与反面的概率分别是1/4,3/4,它们的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出60信源含有的信息量是信源发出的所有可能消息的平均不确定性,香农把信源所含有的信息量称为信息熵,是指每个符号所含信息量的统计平均值。m种符号的平均信息量为信源含有的信息量是信源发出的所有可能消息的平均不确定性,香农61抛一枚均匀硬币的信息熵是多少?解:出现正面与反面的概率均为0.5,信息熵是抛一枚均匀硬币的信息熵是多少?62抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出现正面与反面时的信息量是多少?解:出现正面与反面的概率分别是1/4,3/4,信息熵是抛一枚畸形硬币,出现正面与反面的概率分别是1/4,3/4,出63例:气象预报例:气象预报6465条件自信息量在事件yj出现的条件下,随机事件xi发生的条件概率为p(xi|yj),则它的条件自信息量定义为条件概率对数的负值:12条件自信息量在事件yj出现的条件下,随机事件xi发生的条66条件熵在给定yj条件下,xi的条件自信息量为I(xi|yj),X集合的条件熵H(X|yj)为在给定Y(即各个yj

)条件下,X集合的条件熵H(X|Y)条件熵H(X|Y)表示已知Y后,X的不确定度13条件熵在给定yj条件下,xi的条件自信息量为I(xi|是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎67活动天气是否进行垒球活动进行取消晴阴雨晴阴雨活动进行取消活动天气是否进行垒球活动进行取消晴阴雨晴阴雨活动进行68活动的熵活动有2个属性值,进行,取消。其熵为:H(活动)=-(9/14)*log

(9/14)-(5/14)*log

(5/14)=0.94活动进行取消活动的熵活动有2个属性值,进行,取消。其熵为:活动进行取消69已知户外的天气情况下活动的条件熵户外有三个属性值,晴,阴和雨。其熵分别为:H(活动|户外=晴)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971H(活动|户外=阴)=-(4/4)*log2(4/4)=0H(活动|户外=雨)=-(3/5)*log2(3/5)-(2/5)*log2(2/5)=0.971活动天气进行取消晴阴雨已知户外的天气情况下活动的条件熵户外有三个属性值,晴,阴和雨70已知户外时活动的条件熵H(活动|户外)=5/14*H(活动|户外=晴)+4/14*H(活动|户外=阴)+5/14*H(活动|户外=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693晴阴雨已知户外时活动的条件熵H(活动|户外)=5/14*H(活动|71平均互信息I(活动;户外)=H(活动)-H(活动|户外)=0.94-0.693=0.246平均互信息I(活动;户外)=H(活动)-H(活动|户72是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎73活动的熵H(活动)=-(9/14)*lb

(9/14)-(5/14)*lb

(5/14)=0.94天气

温度

湿度

风速

活动

炎热

进行

适中

进行

寒冷

正常

进行

寒冷

正常

进行

寒冷

正常

进行

适中

正常

进行

适中

正常

进行

适中

进行

炎热

正常

进行

炎热

取消

炎热

取消

寒冷

正常

取消

适中

取消

适中

取消

活动的熵H(活动)=-(9/14)*lb(9/14)74已知天气时活动的条件熵H(活动|天气)=5/14*H(活动|天气=晴)+4/14*H(活动|天气=阴)+5/14*H(活动|天气=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693温度

湿度

风速

天气

活动

寒冷

正常

进行

适中

正常

进行

炎热

取消

炎热

取消

适中

取消

炎热

进行

寒冷

正常

进行

适中

进行

炎热

正常

进行

适中

进行

寒冷

正常

进行

适中

正常

进行

寒冷

正常

取消

适中

取消

已知天气时活动的条件熵H(活动|天气)=5/14*H(活动|75天气

湿度

风速

温度

活动

炎热

进行

正常

炎热

进行

炎热

取消

炎热

取消

适中

进行

正常

适中

进行

正常

适中

进行

适中

进行

适中

取消

适中

取消

正常

寒冷

进行

正常

寒冷

进行

正常

寒冷

进行

正常

寒冷

取消

已知温度时活动的条件熵H(活动|温度)=0.911天气湿度风速温度活动阴高弱炎热进行阴正76天气

温度

风速

湿度

活动

炎热

进行

适中

进行

适中

进行

炎热

取消

炎热

取消

适中

取消

适中

取消

寒冷

正常

进行

寒冷

正常

进行

寒冷

正常

进行

适中

正常

进行

适中

正常

进行

炎热

正常

进行

寒冷

正常

取消

H(活动|湿度)

=0.789已知湿度时活动的条件熵天气温度风速湿度活动阴炎热弱高进行雨适77天气

温度

湿度

风速

活动

寒冷

正常

进行

适中

正常

进行

适中

进行

炎热

取消

寒冷

正常

取消

适中

取消

炎热

进行

适中

进行

寒冷

正常

进行

寒冷

正常

进行

适中

正常

进行

炎热

正常

进行

炎热

取消

适中

取消

H(活动|风速)=0.892已知风速时活动的条件熵天气温度湿度风速活动阴寒冷正常强进行晴78各互信息量I(活动;天气)=H(活动)-H(活动|天气)=0.94-0.693=0.246I(活动;温度)=

H(活动)-H(活动|温度)=0.94-0.911=0.029I(活动;湿度)=

H(活动)-H(活动|湿度)=0.94-0.789=0.151I(活动;风速)=

H(活动)-H(活动|风速)=0.94-0.892=0.048各互信息量I(活动;天气)=H(活动)-H(活动|天79天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消温度

湿度

风速

活动

寒冷

正常

进行

适中

正常

进行

炎热

取消

炎热

取消

适中

取消

温度

湿度

风速

活动

适中

进行

寒冷

正常

进行

适中

正常

进行

寒冷

正常

取消

适中

取消

温度湿度风速活动炎热高弱进行寒冷正常强进行适中高强进行炎热正常弱进行阴晴雨天气

温度

湿度

风速

活动

寒冷

正常

进行

适中

正常

进行

炎热

取消

炎热

取消

适中

取消

炎热

进行

寒冷

正常

进行

适中

进行

炎热

正常

进行

适中

进行

寒冷

正常

进行

适中

正常

进行

寒冷

正常

取消

适中

取消

天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进80ID3算法生成的决策树ID3算法生成的决策树81ID3算法ID3(A:条件属性集合,d:决策属性,U:训练集)返回一棵决策树{ifU为空,返回一个值为Failure的单结点;//一般不会出现这种情况,为了程序的健壮性ifU是由其值均为相同决策属性值的记录组成,返回一个带有该值的单结点;//此分支至此结束ifA为空,则返回一个单结点,其值为在U的记录中找出的频率最高的决策属性值;//这时对记录将出现误分类将A中属性之间具有最大I(d;a)的属性赋给a;将属性a的值赋给{aj|j=1,2,…,m};将分别由对应于a的值的aj的记录组成的U的子集赋值给{uj|j=1,2,…,m};返回一棵树,其根标记为a,树枝标记为a1,a2,…,am;再分别构造以下树:ID3(A-{a},d,u1),ID3(A-{a},d,u2),…,ID3(A-{a},d,um);//递归算法}ID3算法ID3(A:条件属性集合,d:决策属性,U:训练集822003.11.1883决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题,ID3被扩展成C4.52003.11.1830决策树学习的常见问题决策树学习的实际2003.11.1884避免过度拟合数据过度拟合对于一个假设,当存在其他的假设对训练样例的拟合比它差,但事实上在实例的整个分布上表现得却更好时,我们说这个假设过度拟合训练样例定义:给定一个假设空间H,一个假设hH,如果存在其他的假设h’H,使得在训练样例上h的错误率比h’小,但在整个实例分布上h’的错误率比h小,那么就说假设h过度拟合训练数据。2003.11.1831避免过度拟合数据过度拟合2003.11.1885避免过度拟合数据(2)导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声当训练数据没有噪声时,过度拟合也有可能发生,特别是当少量的样例被关联到叶子节点时,很可能出现巧合的规律性,使得一些属性恰巧可以很好地分割样例,但却与实际的目标函数并无关系。2003.11.1832避免过度拟合数据(2)导致过度拟合的86避免过度拟合数据(3)避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中,精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功33避免过度拟合数据(3)避免过度拟合的方法2003.11.1887避免过度拟合数据(4)避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例,来评估通过后修剪方法从树上修建节点的效用。使用所有可用数据进行训练,但进行统计测试来估计扩展(或修剪)一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度,当这个编码的长度最小时停止树增长。2003.11.1834避免过度拟合数据(4)避免过度拟合的2003.11.1888避免过度拟合数据(5)方法评述第一种方法是最普通的,常被称为训练和验证集法。可用数据分成两个样例集合:训练集合,形成学习到的假设验证集合,评估这个假设在后续数据上的精度方法的动机:即使学习器可能会被训练集合误导,但验证集合不大可能表现出同样的随机波动验证集合应该足够大,以便它本身可提供具有统计意义的实例样本。常见的做法是,样例的三分之二作训练集合,三分之一作验证集合。2003.11.1835避免过度拟合数据(5)方法评述2003.11.1889错误率降低修剪将树上的每一个节点作为修剪得候选对象修剪步骤删除以此节点为根的子树,使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点,每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点继续修剪,直到进一步的修剪是有害的为止数据分成3个子集训练样例,形成决策树验证样例,修剪决策树测试样例,精度的无偏估计如果有大量的数据可供使用,那么使用分离的数据集合来引导修剪2003.11.1836错误率降低修剪将树上的每一个节点作为2003.11.1890规则后修剪从训练集合推导出决策树,增长决策树直到尽可能好地拟合训练数据,允许过度拟合发生将决策树转化为等价的规则集合,方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序,并按这样的顺序应用这些规则来分类后来的实例2003.11.1837规则后修剪从训练集合推导出决策树,增2003.11.1891规则后修剪(2)例子if(outlook=sunny)(Humidity=High)thenPlayTennis=No考虑删除先行词(outlook=sunny)和(Humidity=High)选择使估计精度有最大提升的步骤考虑修剪第二个前件2003.11.1838规则后修剪(2)例子2003.11.1892规则后修剪(3)规则精度估计方法使用与训练集不相交的验证集基于训练集合本身被C4.5使用,使用一种保守估计来弥补训练数据有利于当前规则的估计偏置过程先计算规则在它应用的训练样例上的精度然后假定此估计精度为二项式分布,并计算它的标准差对于一个给定的置信区间,采用下界估计作为规则性能的度量评论对于大的数据集,保守预测非常接近观察精度,随着数据集合的减小,离观察精度越来越远不是统计有效,但是实践中发现有效2003.11.1839规则后修剪(3)规则精度估计方法2003.11.1893规则后修剪(4)把决策树转化成规则集的好处可以区分决策节点使用的不同上下文消除了根节点附近的属性测试和叶节点附近的属性测试的区别提高了可读性2003.11.1840规则后修剪(4)把决策树转化成规则集2003.11.1894合并连续值属性ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论