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

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