深入浅出决策树分类精彩故事引入省名师优质课获奖课件市赛课一等奖课件.ppt

,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,Click to edit Master title style,Edit Master text styles,Second level,Third level,Fourth level,Fifth level,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,决议树分类,唐国明,国防科技大学原信息系统与管理学院,第1页,讲课内容,决议树基本概念,怎样构建一棵决议树,ID3,算法,第2页,2,小故事：女博士相亲,序号,年纪,长相,收入,是否公务员,中意？,1,26,中等,中等,是,2,37,中等,高,否,X,3,29,帅,高,否,4,28,丑,高,是,X,决议树,!,第3页,3,决议树基本概念,决议树,(Decision Tree):,是一个,树形,归纳,分类,算法,经过对,训练集,数据,学习,挖掘出,一定,规则,用于对,测试,集,数据,进行预测.,相亲例子：,分类类别：,见,or,不见,训练集：,已相亲,人,(,年纪、长相、收入等,属性,),测试集：,待相亲,人,(,年纪、长相、收入等,属性,),第4页,4,决议树基本概念,决议树结构,根节点,叶节点,分支,内部,节点,每个,内部结点,代表对某个属性一次,测试,，每条,分支,代表一个,测试结果,，,叶结点,代表某个,类,.,决议树提供了一个展示在,什么条件下,会得到,什么类别,这种规则方法,.,第5页,5,决议树构建,已知：,训练数据集,D,中有,m,个不一样类,C,1,C,2,C,3,C,m,，设,C,i,D,是数据集,D,中,C,i,类样本集合,|D|,和,|C,i,D,|,分别是,D,和,C,i,D,中样本个数,问题：,怎样,构建一棵决议树对测试数据集进行分类？,第6页,6,决议树构建,ID3,最具影响,和,最为经典,算法,使用,信息增益度,选择测试属性,C4.5,CART,第7页,7,年纪,收入,学生,信用,买电脑,?,30,高,否,普通,否,40,中等,否,普通,是,40,低,是,普通,是,40,低,是,好,否,30-40,低,是,好,是,30,中,否,普通,否,40,中,是,普通,是,40,中,否,好,否,依据以下训练集，使用,ID3,算法,为电脑推销员构建一棵决议树,第8页,8,决议树构建,(ID3),1.,决定分类属性集合,;,2.,对当前数据表，建立一个节点,N;,3.,假如数据库中数据都属于同一个类，,N,就是树叶，在树叶上标出所属类,;,4.,假如数据表中没有其它属性能够考虑，则,N,也是树叶，按照少数服从多数标准在树叶上标出所属类别,;,5.,不然，依据,信息增益（,GAIN,值）,选出一个最正确属性作为节点,N,测试属性,;,6.,节点属性选定后，对于该属性中每个值：从,N,生成一个分支，并将数据表中与该分支相关数据搜集形成份支节点数据表，在表中删除节点属性那一栏,;,7.,假如分支数据表属性非空，则转,1,，利用以上算法从该节点建立子树,.,第9页,9,信息熵(Entropy),怎样衡量信息量多少？比如一本50多万字史记或一套莎士比亚全集,1948年，,香农,(Claude Shannon)在他著名论文“通信数学原理”中提出了,信息熵,概念，证实熵与,信息内容不确定程度,有等价关系,若一个系统中存在多个事件,E1,E2,En,，每个事件出现概率是,p1,p2,pn,，则这个系统熵,(,平均信息量,),是,第10页,10,数据集信息熵,设数据集,D,中有,m,个不一样类,C,1,C,2,C,3,.,C,m,，,C,i,D,是数据集,D,中,C,i,类样本集合,|D|,和,|C,i,D,|,分别是,D,和,C,i,D,中样本个数,数据集D信息熵:,其中p,i,是,数据集,D中任意样本属于类C,i,概率，用 预计,第11页,11,计算对以下数据集分类所需信息熵,年纪,收入,学生,信用,买电脑,?,30,高,否,普通,否,40,中等,否,普通,是,40,低,是,普通,是,40,低,是,好,否,30-40,低,是,好,是,30,中,否,普通,否,40,中,是,普通,是,40,中,否,好,否,|D|,=14,|C,1,D,|,=5,|C,2,D,|,=9,第12页,12,信息增益,选择含有最高信息增益Gain(A),属性A作为分裂属性,按照能做“最正确分类”属性A划分，,使完成样本分类需要信息量最小,第13页,13,确定第一次分裂属性：按,年纪,划分,年纪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,中,否,好,否,第14页,14,确定第一次分裂属性：按,收入,划分,收入=高有4个,其中2个为“否”,收入=中有6个,其中2个为“否”,收入=低有4个,其中1个为“否”,Info,收入,(D),Gain(收入),=Info(D)-Info,收入,(D),=0.940-0.911=0.029,年纪,收入,学生,信用,买电脑,?,30,高,否,普通,否,40,中等,否,普通,是,40,低,是,普通,是,40,低,是,好,否,30-40,低,是,好,是,30,中,否,普通,否,40,中,是,普通,是,40,中,否,好,否,第15页,15,确定第一次分裂属性：按,学生,划分,是学生有7个,其中1个为“否”,不是学生有7个,其中4个为“否”,Info,学生,(D),Gain(学生),=Info(D)-Info,学生,(D),=0.940-0.788=0.152,年纪,收入,学生,信用,买电脑,?,30,高,否,普通,否,40,中等,否,普通,是,40,低,是,普通,是,40,低,是,好,否,30-40,低,是,好,是,30,中,否,普通,否,40,中,是,普通,是,40,中,否,好,否,第16页,16,确定第一次分裂属性：按,信用,划分,信用好有6个,其中3个为“否”,信用普通有8个,其中2个为“否”,Info,信用,(D),Gain(信用),=Info(D)-Info,信用,(D),=0.940-0.892=0.048,年纪,收入,学生,信用,买电脑,?,30,高,否,普通,否,40,中等,否,普通,是,40,低,是,普通,是,40,低,是,好,否,30-40,低,是,好,是,30,中,否,普通,否,40,中,是,普通,是,40,中,否,好,否,第17页,17,确定第一次分裂属性,收入,学生,信用,买电脑,?,中,否,普通,是,低,是,普通,是,低,是,好,否,中,是,普通,是,中,否,好,否,年纪,40,“年纪”属性详细最高,信息增益，成为分裂属性,收入,学生,信用,买电脑,?,高,否,普通,是,低,是,好,是,中,否,好,是,高,是,普通,是,收入,学生,信用,买电脑,?,高,否,普通,否,高,否,好,否,中,否,普通,否,低,是,普通,是,中,是,好,是,第18页,18,确定第二次分裂属性,收入,学生,信用,买电脑,?,高,否,普通,否,高,否,好,否,中,否,普通,否,低,是,普通,是,中,是,好,是,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/5*(-1/2*log1/2-1/2*log1/2),=0.951,“学生”属性含有最高,信息增益，成为分裂属性,第19页,19,决议树构建,年纪,40,学生,不买,买,不是学生,是学生,买,第20页,20,本堂小结,决议树分类,概念，结构,决议树构建,ID3,算法，信息熵，信息增益,下节预告,ID3,算法不足,C4.5,算法对,ID3,改进,第21页,21,谢谢大家！,唐国明,国防科技大学原信息系统与管理学院,第22页,