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

唐国明国防科技大学原信息系统与管理学院决策树的基本概念如何构建一棵决策树ID3算法23序号序号年龄年龄长相长相收入收入是否公务员是否公务员中意？中意？126中等中等是237中等高否X X329帅高否428丑高是X X决策树!决策树(Decision Tree):是一种树形归纳分类算法,通过对训练集数据的学习,挖掘出一定的规则,用于对测试集数据进行预测.相亲的例子：分类类别：见 or 不见训练集：已相亲人(的年龄、长相、收入等属性)测试集：待相亲人(的年龄、长相、收入等属性)4决策树的结构5根节点叶节点分支内部节点每个内部结点代表对某个属性的一次测试，每条分支代表一个测试结果，叶结点代表某个类.决策树提供了一种展示在什么条件下会得到什么类别这种规则的方法.已知：训练数据集D中有m个不同的类C1,C2,C3,Cm，设Ci,D是数据集D中Ci类的样本的集合,|D|和|Ci,D|分别是D和Ci,D中的样本个数问题：如何构建一棵决策树对测试数据集进行分类？6ID3最具影响和最为典型的算法使用信息增益度选择测试属性C4.5CART78年龄年龄收入收入学生学生信用信用买电脑买电脑?30高否一般否40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否根据以下训练集，使用ID3算法为电脑推销员构建一棵决策树1.决定分类属性集合;2.对目前的数据表，建立一个节点N;3.如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类;4.如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别;5.否则，根据信息增益（GAIN值）选出一个最佳属性作为节点N的测试属性;6.节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏;7.如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树.9如何衡量信息量的多少？比如一本50多万字的史记或一套莎士比亚全集1948年，香农(Claude Shannon)在他著名的论文“通信的数学原理”中提出了信息熵信息熵的概念，证明熵与信息内容的不确定程度有等价关系若一个系统中存在多个事件E1,E2,En，每个事件出现的概率是p1,p2,pn，则这个系统的熵(平均信息量)是10设数据集D中有m个不同的类C1,C2,C3,.,Cm，Ci,D是数据集D中Ci类的样本的集合,|D|和|Ci,D|分别是D和 Ci,D中的样本个数数据集D的信息熵:其中pi是数据集D中任意样本属于类Ci的概率，用 估计1112年龄年龄收入收入学生学生信用信用买电脑买电脑?30高否一般否40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否|D|=14|C1,D|=5|C2,D|=913选择具有最高信息增益Gain(A)的属性A作为分裂属性按照能做“最佳分类”的属性A划分，使完成样本分类需要的信息量最小年龄年龄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收入收入=高的有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学生是学生的有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信用信用好的有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收入收入学生学生信用信用买电脑买电脑?中否一般是低是一般是低是好否中是一般是中否好否年龄40“年龄”属性具体最高信息增益，成为分裂属性收入收入学生学生信用信用买电脑买电脑?高否一般是低是好是中否好是高是一般是收入收入学生学生信用信用买买电电脑脑?高否一般否高否好否中否一般否低是一般是中是好是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年龄40学生不买买不是学生是学生买20决策树分类概念，结构决策树构建ID3算法，信息熵，信息增益下节预告ID3算法的不足C4.5算法对ID3的改进21唐国明国防科技大学原信息系统与管理学院