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

决议树分类唐国明国防科技大学原信息系统与管理学院第1页讲课内容决议树基本概念怎样构建一棵决议树ID3算法第2页2小故事：女博士相亲序号年纪长相收入是否公务员中意？126中等中等是√237中等高否X329帅高否√428丑高是X………………决议树!!第3页3决议树基本概念决议树(DecisionTree):是一个树形归纳分类算法,经过对训练集数据学习,挖掘出一定规则,用于对测试集数据进行预测.相亲例子：分类类别：见

or不见训练集：已相亲人(年纪、长相、收入等属性)测试集：待相亲人(年纪、长相、收入等属性)第4页4决议树基本概念决议树结构根节点叶节点分支内部节点每个内部结点代表对某个属性一次测试，每条分支代表一个测试结果，叶结点代表某个类.决议树提供了一个展示在什么条件下会得到什么类别这种规则方法.第5页5决议树构建已知：训练数据集D中有m个不一样类{C1,C2,C3,…,Cm}，设Ci,D是数据集D中Ci类样本集合,|D|和|Ci,D|分别是D和Ci,D中样本个数问题：怎样构建一棵决议树对测试数据集进行分类？第6页6决议树构建ID3最具影响和最为经典算法使用信息增益度选择测试属性C4.5CART第7页7年纪收入学生信用买电脑?<30高否普通否<30高否好否30-40高否普通是>40中等否普通是>40低是普通是>40低是好否30-40低是好是<30中否普通否<30低是普通是>40中是普通是<30中是好是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年，香农(ClaudeShannon)在他著名论文“通信数学原理”中提出了信息熵概念，证实熵与信息内容不确定程度有等价关系若一个系统中存在多个事件E1,E2,…En，每个事件出现概率是p1,p2,…pn，则这个系统熵(平均信息量)是第10页10数据集信息熵设数据集D中有m个不一样类C1,C2,C3,...,Cm，Ci,D是数据集D中Ci类样本集合,|D|和|Ci,D|分别是D和Ci,D中样本个数数据集D信息熵:其中pi是数据集D中任意样本属于类Ci概率，用预计第11页11计算对以下数据集分类所需信息熵年纪收入学生信用买电脑?<30高否普通否<30高否好否30-40高否普通是>40中等否普通是>40低是普通是>40低是好否30-40低是好是<30中否普通否<30低是普通是>40中是普通是<30中是好是30-40中否好是30-40高是普通是>40中否好否|D|=14|C1,D|=5|C2,D|=9第12页12信息增益选择含有最高信息增益Gain(A)属性A作为分裂属性按照能做“最正确分类”属性A划分，使完成样本分类需要信息量最小第13页13确定第一次分裂属性：按年纪划分年纪<30有5个,其中3个为“否”年纪30-40有4个,其中0个为“否”年纪>40有5个,其中2个为“否”Info年纪(D)Gain(年纪)=Info(D)-Info年纪(D)=0.940-0.694=0.246年纪收入学生信用买电脑?<30高否普通否<30高否好否30-40高否普通是>40中等否普通是>40低是普通是>40低是好否30-40低是好是<30中否普通否<30低是普通是>40中是普通是<30中是好是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高否普通否<30高否好否30-40高否普通是>40中等否普通是>40低是普通是>40低是好否30-40低是好是<30中否普通否<30低是普通是>40中是普通是<30中是好是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高否普通否<30高否好否30-40高否普通是>40中等否普通是>40低是普通是>40低是好否30-40低是好是<30中否普通否<30低是普通是>40中是普通是<30中是好是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高否普通否<30高否好否30-40高否普通是>40中等否普通是>40低是普通是>40低是好否30-40低是好是<30中否普通否<30低是普通是>40中是普通是<30中是好是30-40中否好是30-40高是普通是>40中否好否第17页17确定第一次分裂属性收入学生信用买电脑?中否普通是低是普通是低是好否中是普通是中否好否年纪<3030-40>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.400Info学生(D)=3/5*(-3/3*log3/3-0/3*log0/3)+2/5*(-2/2*log2/2-0/2*log0/2)=0Info信用(D)=3/5*(-2/3*log2/3-1/3*log1/3)+2/5*(-1/2*log1/2-1/2*lo