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

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