6.-决策树分类.ppt
《6.-决策树分类.ppt》由会员分享,可在线阅读,更多相关《6.-决策树分类.ppt(96页珍藏版)》请在咨信网上搜索。
1、决策树分类决策树分类王成(副教授)王成(副教授)计算机科学与技术学院计算机科学与技术学院主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法Decision Tree ModelingDecision Tree Modeling决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的预测预测预测预测方法方法方法方法决策树决策树图图3.1 3.1 常见的决策树形式常见的决策树形式决策树主要有二元分支(决策树主要有二元分支(binary splitbinary split)树和多分支()树和多分支(multiway spli
2、tmultiway split)树。)树。一般时候采用二元分裂,因为二元分裂在穷举搜索中更加灵活。一般时候采用二元分裂,因为二元分裂在穷举搜索中更加灵活。决策树形式决策树形式决策树决策树决策树决策树(Decision Tree)又称为判定树判定树,是运用于分类的一种树结构树结构。其中的每个内部结点内部结点(internal node)代表对某个属性的一次测试测试,每条边边代表一个测试结果测试结果,叶结点叶结点(leaf)代表某个类类(class)或者类的分布(类的分布(class distributionclass distribution),),最上面的结点是根结点根结点决策树决策树提供了一
3、种展示在什么条件下在什么条件下会得到什么类别什么类别这类规则规则的方法。下例是为了解决这个问题而建立的一棵决决策树策树,从中可以看到决策树的基本组成部分:决策结点决策结点、分支分支和叶结点叶结点决策树决策树下图给出了一个商业上使用的决策树商业上使用的决策树的例子。它表示了一个关心电子产品的用户是关心电子产品的用户是否会购买否会购买PC(buys_computer)的知识,用它可以预测某条记录(某个人)的购买意预测某条记录(某个人)的购买意向向决策树决策树这棵决策树对销售记录进行分类,指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点(方形框)代表对某个属性的
4、一次检测。每个叶结点(椭圆框)代表一个类:buys_computers=yes 或者 buys_computers=no在这个例子中,特征向量为:(age,student,credit_rating,buys_computers)被决策数据的格式为:(age,student,credit_rating)输入新的被决策的记录,可以预测该记录隶属于哪个类。使用决策树进行分类使用决策树进行分类第1步:利用训练集建立并精化一棵决策树,建立决策树模型。这个过程实际上是一个从数据中获取知识,进行机器学习的过程第2步:利用生成完毕的决策树对输入数据进行分类。对输入的记录,从根结点依次测试记录的属性值,直到到
5、达某个叶结点,从而找到该记录所在的类主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法如何从训练数据中学习决策树如何从训练数据中学习决策树?IDAgeHas-jobOwn_houseCredit_ratingClassClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYe
6、s9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrueFalseExcellentYes15OldFalseFalsefairno贷款申请数据集如何从训练数据中学习决策如何从训练数据中学习决策树树?Age?youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house?truefalseNo:0Yes:6No:6Yes:3(a)(b)两种可能的
7、根节点选取方式哪种更好?ID3ID3算法算法ID3算法主要针对属性选择问题使用信息增益度选择测试属性ID3ID3决策树建立算法决策树建立算法1 决定分类属性集合;决定分类属性集合;2 对目前的数据表,建立一个节点对目前的数据表,建立一个节点N3 如果数据库中的数据都属于同一个类,如果数据库中的数据都属于同一个类,N就是树叶,在树叶上就是树叶,在树叶上 标出所属的类标出所属的类(纯的类别纯的类别)4 如果数据表中没有其他属性可以考虑,则如果数据表中没有其他属性可以考虑,则N也是树叶,按照少也是树叶,按照少 数服从多数的原则在树叶上标出所属类别数服从多数的原则在树叶上标出所属类别(不纯的类别不纯的
8、类别)5 否则,否则,根据平均信息期望值根据平均信息期望值E或或GAIN值选出一个最佳属性作值选出一个最佳属性作 为节点为节点N的测试属性的测试属性6 节点属性选定后,对于该属性中的每个值:节点属性选定后,对于该属性中的每个值:从从N生成一个分支,并将数据表中与该分支有关的数据收集形生成一个分支,并将数据表中与该分支有关的数据收集形 成分支节点的数据表,在表中删除节点属性那一栏成分支节点的数据表,在表中删除节点属性那一栏 7如果分支数据表属性非空,则转如果分支数据表属性非空,则转1,运用以上算法从该节点建立子树,运用以上算法从该节点建立子树信息熵信息熵(Entropy)(Entropy)我们常
9、说信息很多,或信息很少,但却很难说清楚信息到底有多少比如一本50多万字的史记有多少信息量?或一套莎士比亚全集有多少信息量?这个问题几千年来都没有人给出很好的解答,直到1948年,香农(Claude Shannon)在他著名的论文“通信的数学原理”中提出了信息熵信息熵的概念,才解决了信息的度量信息的度量问题问题,并且量化出信息的作用量化出信息的作用信息熵信息熵(Entropy)(Entropy)一条信息的信息量和它的不确定性有着直接的关系比如,要搞清楚一件非常不确定的事,或是我们一无所知的事情,就需要了解大量信息。相反,如果我们对某件事已经有了较多了解,那么不需要太多信息就能把它搞清楚从这个角度
10、看,信息量就等于不确定性的多少如何量化信息的度量呢?信息熵信息熵(Entropy)(Entropy)假如我错过了一个有32支球队参加的足球赛,赛后我问一个知道比赛结果的观众“哪支球队是冠军”?他不愿意直接告诉我,而让我猜,每猜一次,他要收一元钱才肯告诉我是否猜对,那我需要付多少钱才能知道谁是冠军呢?我可以把球队编号,从1到32,然后问“冠军球队在1-16号中吗?”,假如他告诉我猜对了,我就接着问“冠军在1-8号中吗?”,假如他说猜错了,那我就知道冠军在9-16号中。这样只要5次,我就能知道哪支球队是冠军当然,香农不是用钱,而是用比特(bit)来度量信息量,在上例中,这条消息的信息量是5比特信息
11、量的比特数和所有可能情况的对数有关,例如本例中,信息量=log(球队数),即 5=log(32)信息熵信息熵(Entropy)(Entropy)实际上可能不需要5次就能猜出谁是冠军,因为一些强队得冠的可能性更高,因此第一次猜测时可以把少数几支强队分成一组,其它球队分成另一组,然后猜冠军球队是否在那几支强队中这样,也许三次或四次就能猜出结果。因此,当每支球队夺冠的可能性(概率)不等时,这条信息的信息量比5比特少香农指出,它的准确信息量应该是p1,p2,.,p32分别是这32支球队夺冠概率,香农把它称作信息熵,单位为比特信息熵,单位为比特;可以算出,当32支球队夺冠概率相同时,对应的信息熵为5比特
12、。信息熵信息熵(Entropy)(Entropy)对于任意一个随机变量X(比如夺冠球队),它的熵定义为变量的不确定性越大,熵也就越大,把它搞清楚所需要的信息量也就越大数据集的信息熵数据集的信息熵设数据集D中有m个不同的类C1,C2,C3,.,Cm设 Ci,D是数据集D中Ci类的样本的集合,|D|和|Ci,D|分别是D和 Ci,D中的样本个数其中pi是数据集D中任意样本属于类Ci的概率,用 估计数据集D的信息熵:例例:计算对下列数据集分类所需的信息计算对下列数据集分类所需的信息熵熵年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中等否一般是40低是一般是40低是好否30-40低
13、是好是30中否一般否40中是一般是40中否好否|D|=14|C1,D|=5|C2,D|=9使用熵衡量数据纯度使用熵衡量数据纯度假设有一个数据集合假设有一个数据集合D,其中只有两个类,一个是正例类,一个是负例类,其中只有两个类,一个是正例类,一个是负例类计算计算D中正例类和负例类在三种不同的组分下熵的变化情况。中正例类和负例类在三种不同的组分下熵的变化情况。(1)D中包含有中包含有50%的正例和的正例和50%的负例。的负例。H(D)=-0.5*log20.5-0.5*log20.5=1(2)D中包含有中包含有20%的正例和的正例和80%的负例。的负例。H(D)=-0.2*log20.2-0.8*
14、log20.8=0.722(3)D中包含有中包含有100%的正例和的正例和0%的负例。的负例。H(D)=-1*log21-0*log20=0可以看到一个趋势,可以看到一个趋势,当数据变得越来越当数据变得越来越“纯纯”时,熵的值变得越来越小时,熵的值变得越来越小。当当D中中正反例所占比例相同时,熵取最大值正反例所占比例相同时,熵取最大值。当当D 中中所有数据都只属于一个类时,熵得到最小值所有数据都只属于一个类时,熵得到最小值。因此因此熵可以作为数据纯净度或混乱度的衡量指标熵可以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中。这正是决策树学习中需要的。需要的。数据集的信息熵数据集的信息熵假设
15、按属性 A 划分 D 中的样本,且属性 A 根据训练数据的观测具有 v 个不同取值 a1,a2,.,aj,.,av。如果 A 是离散值离散值,可依属性 A 将 D 划分为 v 个子集 D1,D2,.,Dj,.,Dv 其中,Dj为D中的样本子集,它们在A上具有属性值aj 这些划分将对应于从该节点A出来的分支。按属性A对D划分后,数据集的信息熵:其中,充当第 j 个划分的权重。InfoA(D)越小,表示划分的纯度越高信息增益信息增益选择具有最高信息增益Gain(A)的属性A作为分裂属性按照能做“最佳分类”的属性A划分,使完成样本分类需要的信息量最小确定第一次分裂的属性:按确定第一次分裂的属性:按年
16、龄年龄划分划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否年龄40的有5个,其中2个为“否”Info年龄(D)Gain(年龄)=Info(D)-Info年龄(D)=0.940-0.694=0.246确定第一次分裂的属性:按收入划分确定第一次分裂的属性:按收入划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否收入=高的有4个,其中2个为“否”收入=中的有6个,其中2个
17、为“否”收入=低的有4个,其中1个为“否”Info收入(D)Gain(收入)=Info(D)-Info收入(D)=0.940-0.911=0.029确定第一次分裂的属性:按学生划分确定第一次分裂的属性:按学生划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否是学生的有7个,其中1个为“否”不是学生的有7个,其中4个为“否”Info学生(D)Gain(学生)=Info(D)-Info学生(D)=0.940-0.788=0.152确定第一次分裂的属性:按信用划分确定第一次分裂的属性:按
18、信用划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否信用好的有6个,其中3个为“否”信用一般的有8个,其中2个为“否”Info信用(D)Gain(信用)=Info(D)-Info信用(D)=0.940-0.892=0.048收入收入学生学生信用信用 买了电脑买了电脑高否一般 否高否好否中否一般 否低是一般 是中是好是收入收入学生学生信用信用买了电脑买了电脑高否一般是低是好是中否好是高是一般是确定第一次分裂的属性确定第一次分裂的属性收入收入学生学生信用信用买了电脑买了电脑中否一般是
19、低是一般是低是好否中是一般是中否好否年龄40“年龄”属性具体最高信息增益,成为分裂属性收入收入学生学生信用信用买了电脑买了电脑高否一般否高否好否中否一般否低是一般是中是好是 Info收入(D)=2/5*(-2/2*log2/2-0/2*log0/2)+2/5*(-1/2*log1/2-1/2*log1/2)+1/5*(-1/1*log1/1-0/1*log0/1)=0.400 Info学生(D)=3/5*(-3/3*log3/3-0/3*log0/3)+2/5*(-2/2*log2/2-0/2*log0/2)=0 Info信用(D)=3/5*(-2/3*log2/3-1/3*log1/3)+2
20、/5*(-1/2*log1/2-1/2*log1/2)=0.951“学生”属性具体最高信息增益,成为分裂属性确定第二次分裂的属性确定第二次分裂的属性年龄40学生不买买不是学生是学生.买ID3ID3决策树建立算法决策树建立算法1 决定分类属性;决定分类属性;2 对目前的数据表,建立一个节点对目前的数据表,建立一个节点N3 如果数据库中的数据都属于同一个类,如果数据库中的数据都属于同一个类,N就是树叶,在树叶上就是树叶,在树叶上 标出所属的类标出所属的类4 如果数据表中没有其他属性可以考虑,则如果数据表中没有其他属性可以考虑,则N也是树叶,按照少也是树叶,按照少 数服从多数的原则在树叶上标出所属类
21、别数服从多数的原则在树叶上标出所属类别5 否则,否则,根据平均信息期望值根据平均信息期望值E或或GAIN值选出一个最佳属性作值选出一个最佳属性作 为节点为节点N的测试属性的测试属性6 节点属性选定后,对于该属性中的每个值:节点属性选定后,对于该属性中的每个值:从从N生成一个分支,并将数据表中与该分支有关的数据收集形生成一个分支,并将数据表中与该分支有关的数据收集形 成分支节点的数据表,在表中删除节点属性那一栏成分支节点的数据表,在表中删除节点属性那一栏7如果分支数据表属性非空,则转如果分支数据表属性非空,则转1,运用以上算法从该节点建立子树,运用以上算法从该节点建立子树它首先对数据进行处理,利
22、用归纳法生成它首先对数据进行处理,利用归纳法生成可读的规则和决策树,然后使用决策对新可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树技列规则对数据进行分类的过程。决策树技术发现数据模式和规则的核心是采用术发现数据模式和规则的核心是采用递归递归分割的贪婪算法分割的贪婪算法。决策树的基本原理决策树的基本原理 分类决策树分类决策树A decision tree is so called because the predictive model can be represented in a tree-lik
23、e structure.the target is categorical,the model is a called a classification tree.分类树采用的标准:分类树采用的标准:分类错误率分类错误率:Gini 指数指数:信息熵信息熵:主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法C4.5C4.5算法对算法对ID3ID3的改进的改进改进1:用信息增益率信息增益率代替信息增益信息增益来选择属性属性改进2:能够完成对连续值属性连续值属性的离散化处离散化处理理改进3:能处理属性值缺失属性值缺失的情况改进4:在决策树构造完成之后进行剪枝剪枝十大数据挖掘算法十
24、大数据挖掘算法C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNave BayesCART改进改进1 1:信息增益的问题:信息增益的问题假设按属性 A 划分 D 中的样本,且属性 A 根据训练数据的观测具有 v 个不同取值 a1,a2,.,aj,.,av。如果 A 是离散值离散值,可依属性 A 将 D 划分为 v 个子集 D1,D2,.,Dj,.,Dv 其中,Dj为D中的样本子集,它们在A上具有属性值aj 这些划分将对应于从该节点A出来的分支。信息增益度量信息增益度量偏向于对取值较多取值较多的属性属性进行测试,即它倾向于选择v较大较大的属性属性A举个极端的例
25、子:考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分(与样本个数一样多),每个分类只包含一个样本,且每个划分都是纯的。对属性PID划分得到的信息增信息增益最大益最大,显然,这种划分对分划分对分类没有用处类没有用处。改进改进1 1:信息增益率:信息增益率C4.5使用分裂信息分裂信息(split information)将信息增益规范化信息增益规范化该值表示数据集D按属性A分裂的v个划分产生的信息选择具有最大信息增益率最大信息增益率的属性作为分裂属性分裂属性改进改进1 1:信息增益率:信息增益率年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 决策树 分类
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。