




已阅读5页,还剩74页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第4章(1)分类:决策树,4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,分类的是利用一个分类函数(分类模型、分类器),该模型能把数据库中的数据映射到给定类别中的一个。,训练样本、学习测试、分类属性分类界限or分类规则,思路:人如何学习、分类类比计算机如何学习、分类?,分类,基本概念,训练集:数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,.,vn;c);其中vi表示属性值,c表示类别。测试集(检验集):用于评估分类模型的准确率,数据分类一个两步过程(1),第一步,建立一个模型,描述预定数据类集和概念集假定每个元组属于一个预定义的类,由一个类标号属性确定学习模型可以用分类规则、决策树或数学公式的形式提供,数据分类一个两步过程(2),第二步,使用模型,对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本,将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集,否则会出现“过分适应数据”的情况如果准确性能被接受,则分类规则就可用来对新数据进行分类,有监督的学习VS.无监督的学习,有监督的学习(用于分类)模型的学习在被告知每个训练样本属于哪个类的“监督”下进行新数据使用训练数据集中得到的规则进行分类无监督的学习(用于聚类)每个训练样本的类编号是未知的,要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类,分类模型的构造方法,1.机器学习方法:决策树法规则归纳2.统计方法:知识表示是判别函数和原型事例贝叶斯法非参数法(近邻学习或基于事例的学习)3.神经网络方法:BP算法,模型表示是前向反馈神经网络模型4.粗糙集(roughset)知识表示是产生式规则,4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,一个决策树的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,SplittingAttributes,训练数据,模型:决策树,决策树的另一个例子,categorical,categorical,continuous,class,MarSt,Refund,TaxInc,YES,NO,NO,Yes,No,Married,Single,Divorced,80K,用决策树归纳分类,什么是决策树?类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个树叶节点代表类或类分布决策树的生成由两个阶段组成决策树构建开始时,所有的训练样本都在根节点递归的通过选定的属性,来划分样本(必须是离散值)树剪枝许多分枝反映的是训练数据中的噪声和孤立点,树剪枝试图检测和剪去这种分枝决策树的使用:对未知样本进行分类通过将样本的属性值与决策树相比较,为了对未知数据对象进行分类识别,可以根据决策树的结构对数据集中的属性进行测试,从决策树的根节点到叶节点的一条路径就形成了相应对象的类别测试。决策树可以很容易转换为分类规则,决策树分类任务,DecisionTree,一个决策树的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,SplittingAttributes,训练数据,模型:决策树,应用决策树进行分类,测试数据,Startfromtherootoftree.,应用决策树进行分类,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,AssignCheatto“No”,决策树分类,DecisionTree,4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,决策树,有许多决策树算法:Hunt算法信息增益Informationgain(ID3)增益比率Gainration(C4.5)基尼指数Giniindex(SLIQ,SPRINT),Hunt算法,设Dt是与结点t相关联的训练记录集算法步骤:如果Dt中所有记录都属于同一个类yt,则t是叶结点,用yt标记如果Dt中包含属于多个类的记录,则选择一个属性测试条件,将记录划分成较小的子集。对于测试条件的每个输出,创建一个子结点,并根据测试结果将Dt中的记录分布到子结点中。然后,对于每个子结点,递归地调用该算法,Dt,?,Hunt算法,DontCheat,决策树构建,Hunt算法采用贪心策略构建决策树.在选择划分数据的属性时,采取一系列局部最优决策来构造决策树.决策树归纳的设计问题如何分裂训练记录如何停止分裂过程,怎样选择最佳划分?,选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低,类分布就越倾斜结点不纯性的度量:,不纯性大,不纯性小,怎样找到最佳划分?,B?,Yes,No,NodeN3,NodeN4,A?,Yes,No,NodeN1,NodeN2,划分前:,Gain=M0M12vsM0M34,结点不纯性的测量,GiniEntropyclassificationerror,停止分裂过程,当所有的记录属于同一类时,停止分裂当所有的记录都有相同的属性时,停止分裂提前终止树的生长,三种著名的决策树,Cart:基本的决策树算法Id3:利用增益比不纯性,树采用二叉树,停止准则为当所有的记录属于同一类时,停止分裂,或当所有的记录都有相同的属性时,停止分裂C4.5:id3的改进版本,也是最流行的分类数算法。采用多重分支和剪枝技术。,决策树,特点:决策树是一种构建分类模型的非参数方法不需要昂贵的的计算代价决策树相对容易解释决策树是学习离散值函数的典型代表决策数对于噪声的干扰具有相当好的鲁棒性冗余属性不会对决策树的准确率造成不利影响数据碎片问题。随着数的生长,可能导致叶结点记录数太少,对于叶结点代表的类,不能做出具有统计意义的判决子树可能在决策树中重复多次。使决策树过于复杂,4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,ID3算法详解,ID3使用信息增益作为属性选择度量。该度童基于香农(ClaudeShannon)在研究消息的值或信息内容的信息论方面的先驱工作。设结点N代表或存放分区D的元组。选择具有最高信息增益的属性作为结点N的分裂属性。该属性使结果分区中对元组分类所需要的信息量最小,并反映这些分区中的最小随机性或不纯性。这种方法使得对一个对象分类所需要的期望测试数目最小,并确保找到一棵简单的(但不必是最简单的)树。,ID3算法,对D中的元组分类所需要的期望信息由下式给出:其中,Pi是D中任意元组属于类Ci的非零概率,并用估计。Info(D)是识别D中无组的类标号所需要的平均信息量。注意,此时我们所有的信息只是每个类的元组所占的百分比。Info(D)又称为D的熵(entropy)非负性:Info(D)大于等于0连续性:Info(D)对任意q连续极值性:当q都等于1K时Info(D)达到最大值logK,ID3算法期望信息,熵(entropy),ID3算法计算Entropy的例子,P(C1)=0/6=0P(C2)=6/6=1Info(D)=1log1=0=0,P(C1)=1/6P(C2)=5/6Info(D)=(1/6)log2(1/6)(5/6)log2(1/6)=0.65,P(C1)=2/6P(C2)=4/6Info(D)=(2/6)log2(2/6)(4/6)log2(4/6)=0.92,P(C1)=3/6P(C2)=3/6Info(D)=(1/2)log2(1/2)(1/2)log2(1/2)=1,现在,假设我们要按某属性A划分D中的元组,其中属性A根据训练数据的观测具有v个不同值如果A是离散值的,则这些值直接对应A上测试的v个输出。可以用属性A将D划分为v个分区或子集其中,Dj包含D中的元组,它们的A值为aj。这些分区对应于从结点N生长出来的分枝。理想情况下,我们希望该划分产生元组的准确分类。即我们希望每个分区都是纯的。然而,这些分区多半是不纯的(例如,分区可能包含来自不同类而不是来自单个类的元组)。(在此划分之后)为了得到准确的分类,我们还需要多少信息?这个量由划分A的期望信息度量,ID3算法期望信息,熵(entropy),划分的期望信息项充当第j个分区的权重。InfoA(D)是基于按A划分对D的元组分类所需要的期望信息。需要的期望信息越小,分区的纯度越高。信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对A划分后1)之间的差。即,ID3算法信息增益,信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对A划分后1)之间的差。即换言之,Gain(A)告诉我们通过A上的划分我们得到了多少。它是知道A的值而导致的信息需求的期望减少。选择具有最高信息增益Gain(A)的属性A作为结点N的分裂属性。这等价于在“能做最佳分类”的属性A上划分,使得完成元组分类还需要的信息最小(即最小化Gain(A)。,ID3算法信息增益,Trainingdataset:Buys_computerThedatasetfollowsanexampleofQuinlansID3(PlayingTennis)Resultingtree:,ID3算法例子,一个标记类的元组的训练集D,随机地从AlIElectronics顾客数据库中选取。在这个例子中,每个属性都是离散值的,连续值属性已经被离散化。类标号属性buys_compter有两个不同值(即yes,no),因此有两个不同的类(即m=2)。设类C1对应于yes,而类C2对应于no。类yes有9个元组,类no有5个元组。为D中的元组创建(根)结点N。为了找出这些元组的分裂准则,必须计算每个属性的信息增益。,ID3算法例子,下一步,需要计算每个属性的期望信息需求。从属性age开始。需要对age的每个类考察yes和no元组的分布。,ID3算法例子,ClassP:buys_computer=“yes”ClassN:buys_computer=“no”,由于age在属性中具有最高的信息增益,所以它被选作分裂属性。结点N用age标记,并且每个属性值生长出一个分枝。然后元组据此划分,如图所示。,ID3算法例子,注意,落在分区age=“3040的元组都属于相同的类。由于它们都属于类yes,所以要在该分枝的端点创建一个树叶,并用yes标记。,ID3算法例子,信息增益度量偏向具有许多输出的测试。换句话说,它倾向于选择具有大量值的属性。例如,考虑充当唯一标识符的属性,如product_ID。在product_ID的划分将导致大量分区(与值一样多),每个只包含一个元组。由于每个分区都是纯的,所以基于该划分对数据集D分类所需要的信息Infoproduct_ID(D)=0。因此,通过对该属性的划分得到的信息增益最大。显然,这种划分对分类没有用。1D3的后继C4.5使用一种称为增益率(gainratio)的信息增益扩充,试图克服这种偏倚。它用分裂信息(splitinfonnation)值将信息增益规范化。,C4.5算法增益率,分裂信息(splitinfonnation)定义如下:该值代表由训练数据集D划分成对应于属性A测试的v个输出的v个分区共生的信息。注意,对于每个输出,它相对于D中元组的总数考虑具有该输出的元组数。增益率(gainratio)定义如下:GainRatio(A)=Gain(A)/SplitInfo(A)属性income的测试将数据划分成3个分区,即low、medium和high,分别包含4、6和4个元组。gain_ratio(income)=0.029/1.557=0.019,C4.5算法增益率,4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,怎样为不同类型的属性指定测试条件?,依赖于属性的类型二元标称序数连续依赖于划分的路数2路划分多路划分,基于标称属性的分裂,多路划分:划分数(输出数)取决于该属性不同属性值的个数.二元划分:划分数为2,这种划分要考虑创建k个属性值的二元划分的所有2k-1-1种方法.,OR,多路划分:划分数(输出数)取决于该属性不同属性值的个数.二元划分:划分数为2,需要保持序数属性值的有序性.,基于序数属性的划分,OR,基于连续属性的划分,多路划分:viAvi+1(i=1,k)二元划分:(Asplit_point的元组集合。,基于连续属性的划分(ID3算法),4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,怎样选择最佳划分?,选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低,类分布就越倾斜结点不纯性的度量:,不纯性大,不纯性小,结点不纯性的测量,GiniEntropyclassificationerror,不纯性的测量:GINI,给定结点t的Gini值计算:(p(j|t)是在结点t中,类j发生的概率).当类分布均衡时,Gini值达到最大值(1-1/nc)相反当只有一个类时,Gini值达到最小值0,计算GINI的例子,P(C1)=0/6=0P(C2)=6/6=1Gini=1P(C1)2P(C2)2=101=0,P(C1)=1/6P(C2)=5/6Gini=1(1/6)2(5/6)2=0.278,P(C1)=2/6P(C2)=4/6Gini=1(2/6)2(4/6)2=0.444,基于GINI的划分,当一个结点p分割成k个部分(孩子),划分的质量可由下面公式计算ni=孩子结点i的记录数,n=父结点p的记录数.,基于ClassificationError的划分,给定结点t的ClassificationError值计算:当类分布均衡时,error值达到最大值(1-1/nc)相反当只有一个类时,error值达到最小值0,例子,P(C1)=0/6=0P(C2)=6/6=1Error=1max(0,1)=11=0,P(C1)=1/6P(C2)=5/6Error=1max(1/6,5/6)=15/6=1/6,P(C1)=2/6P(C2)=4/6Error=1max(2/6,4/6)=14/6=1/3,不纯性度量之间的比较,二元分类问题:,4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.3.1决策树的工作原理4.3.2如何建立决策树补充:ID3决策树详解(后继C4.5)4.3.3表示属性测试条件的方法4.3.4选择最佳划分的度量4.4模型的过分拟合,模型过分拟合和拟合不足,分类模型的误差大致分为两种:训练误差:是在训练记录上误分类样本比例泛化误差:是模型在未知记录上的期望误差一个好的分类模型不仅要能够很好的拟合训练数据,而且对未知样本也要能准确分类。换句话说,一个好的分类模型必须具有低训练误差和低泛化误差。当训练数据拟合太好的模型,其泛化误差可能比具有较高训练误差的模型高,这种情况成为模型过分拟合,模型过分拟合和拟合不足,当决策树很小时,训练和检验误差都很大,这种情况称为模型拟合不足。出现拟合不足的原因是模型尚未学习到数据的真实结构。随着决策树中结点数的增加,模型的训练误差和检验误差都会随之下降。当树的规模变得太大时,即使训练误差还在继续降低,但是检验误差开始增大,导致模型过分拟合,模型模型过分拟合和拟合不足,过分拟合,导致过分拟合的原因(1、噪声),导致过分拟合的原因(1、噪声),噪声导致的过分拟合例子:哺乳动物的分类问题十个训练记录中有两个被错误标记:蝙蝠和鲸如果完全拟合训练数据,决策树1的训练误差为0,但它在检验数据上的误差达30%.人和海豚,针鼹误分为非哺乳动物相反,一个更简单的决策树2,具有较低的检验误差(10%),尽管它的训练误差较高,为20%决策树1过分拟合了训练数据
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 25431.1-2025橡胶塑料挤出机和挤出生产线第1部分:挤出机的安全要求
- 中国双氰胺项目投资计划书
- 中国枳实提取物项目商业计划书
- 中国吐酒石项目投资计划书
- 中国网格导电袋项目商业计划书
- 中国红矾钠项目投资计划书
- 2025妇幼保健院宫内治疗技术专项考核
- 中国搅拌站项目投资计划书
- 朔州市人民医院物体表面监测考核
- 秦皇岛市人民医院神经电生理室主任技术管理考核
- (正式版)DB32∕T 5184-2025 《海域使用权立体分层设权技术规范》
- 医院培训课件:《医疗事故的防范与处理》
- 2025鄂尔多斯伊金霍洛旗九泰热力招聘专业技术人员考试模拟试题及答案解析
- 积小善成大德课件
- 【MOOC】人工智能原理-北京大学 中国大学慕课MOOC答案
- 公共艺术设计-课件
- 保安员知识培训课件
- 人工智能技术介绍完整版人工智能概述、围棋课件
- 人教版八年级下册英语全册教案完整版教学设计含教学反思
- 组织知识清单
- 《中华人民共和国职业分类大典》电子版
评论
0/150
提交评论