深入浅出决策树分类(精彩故事引入)课件.pptVIP

决策树分类唐国明国防科技大学原信息系统与管理学院

授课内容§决策树的基本概念§如何构建一棵决策树§ID3算法2

小故事：女博士相亲序号年龄长相1226中等是否否是…决策树!!372928…中等3帅√X4丑高…………3

决策树的基本概念§决策树(DecisionTree):是一种树形归纳分算法,通过对训练集数据的学习,挖掘出一定的规则,用于对测试集数据进行预测.§相亲的例子：§分类类别：见or不见§训练集：已相亲人(的年龄、长相、收入等属性)§测试集：待相亲人(的年龄、长相、收入等属性)4

决策树的基本概念§决策树的结构根节点?每个内部结点代表对某个属性的一次测试，每条分支代表一个测试结果，叶结点代表某个类.内部节点分支?决策树提供了一种展示在什么条件下会得到什么类别这种规则的方法.叶节点5

决策树的构建§已知：训练数据集D中有m个不同的类{C,C,C,…,C}，123设C是数据集D中C类的样本的集合,|D|和mi,D|C|分别是D和C中的样本个数ii,Di,D§问题：如何构建一棵决策树对测试数据集进行分类？6

决策树的构建§ID3§最具影响和最为典型的算法§使用信息增益度选择测试属性§C4.5§CART7

根据以下训练集，使用ID3算法为电脑推销员构建一棵决策树年龄30收入高学生否否否否是是是否是是是否是否信用一般好买电脑?否30高否30-4040高一般一般一般好是中等低是40是40低否30-4030低好是中一般一般一般好否30低是40中是30中是30-4030-4040中好是高一般好是中否8

决策树的构建(ID3)1.决定分类属性集合;2.对目前的数据表，建立一个节点N;3.如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类;4.如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别;5.否则，根据信息增益（GAIN值）选出一个最佳属性作为节点N的测试属性;6.节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏;7.如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树.9

信息熵(Entropy)§如何衡量信息量的多少？比如一本50多万字的《史记》或一套莎士比亚全集§1948年，香农(ClaudeShannon)在他著名的论文“通信的数学原理”中提出了信息熵的概念，证明熵与信息内容的不确定程度有等价关系§若一个系统中存在多个事件E1,E2,…En，每个事件出现的概率是p1,p2,…pn，则这个系统的熵(平均信息量)是10

数据集的信息熵§设数据集D中有m个不同的类C,C,C,...,C，C是mi,D123数据集D中C类的样本的集合,|D|和|C|分别是D和iC中的样本个数i,Di,D§数据集D的信息熵:其中p是数据集D中任意样本属于类C的概率，用ii估计11

计算对下列数据集分类所需的信息熵年龄30收入高学生否否否否是是是否是是是否是否信用一般好买电脑?否|D|=1430高否|C|=51,D|C|=930-4040高一般一般一般好是2,D中等低是40是40低否30-4030低好是中一般一般一般好否30低是40中是30中是30-4030-4040中好是高一般好是中否12

信息增益选择具有最高信息增益Gain(A)的属性A作为分裂属性按照能做“最佳分类”的属性A划分，使完成样本分类需要的信息量最小13

确定第一次分裂的属性：按年龄划分年龄30收入高学生否否否否是是是否是是是否是否信用一般好买电脑?否年龄30的有5个,其中3个为“否”年龄30-40的有4个,其中0个为“否”30高否30-4040高一般一般一般好是年龄40的有5个,其中2个为“否”Info(D)年龄中等低是40是40低否30-4030低好是中一般一般一般好否30低是40中是30中是30-4030-4040中好是高一般好是Gain(年龄)中否=Info(D)-Info(D)年龄=0.940-0.694=0.24614

确定第一次分裂的属性：按收入划分年龄30收入高学生否否否否是是是否是是是否是否信用一般好买电脑?否收入=高的有4个,其中2个为“否”收入=中的有6个,其中2个为“否”收入=低的有4个,其中1个为“否”30高否30-4040高一般一般一般好是中等低是Info(D)收入40是40低否30-4030低好是中一般一般一般好否30低是40中是30中是30-4030-4040中好是Gain(收入)高一般好是=Info(D)-Info(D)收入=0.940-0.91