《深入浅出决策树分类(精彩故事引入)》由会员分享，可在线阅读，更多相关《深入浅出决策树分类(精彩故事引入)（22页珍藏版）》请在金锄头文库上搜索。
1、决策树分类,唐国明 国防科技大学原信息系统与管理学院,授课内容,决策树的基本概念 如何构建一棵决策树 ID3算法,2,小故事：女博士相亲,3,决策树!,决策树的基本概念,决策树(Decision Tree):是一种树形归纳分类算法,通过对训练集数据的学习,挖掘出一定的规则,用于对测试集数据进行预测. 相亲的例子： 分类类别：见 or 不见 训练集：已相亲人(的年龄、长相、收入等属性) 测试集：待相亲人(的年龄、长相、收入等属性),4,决策树的基本概念,决策树的结构,5,根节点,叶节点,分支,内部节点,每个内部结点代表对某个属性的一次测试，每条分支代表一个测试结果，叶结点代表某个类.,决策树提供
2、了一种展示在什么条件下会得到什么类别这种规则的方法.,决策树的构建,已知： 训练数据集D中有m个不同的类C1,C2,C3,Cm，设Ci,D是数据集D中Ci类的样本的集合,|D|和|Ci,D|分别是D和Ci,D中的样本个数 问题： 如何构建一棵决策树对测试数据集进行分类？,6,决策树的构建,ID3 最具影响和最为典型的算法 使用信息增益度选择测试属性 C4.5 CART,7,8,根据以下训练集，使用ID3算法为电脑推销员构建一棵决策树,决策树的构建(ID3),1.决定分类属性集合; 2.对目前的数据表，建立一个节点N; 3.如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类; 4
3、.如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别; 5.否则，根据信息增益（GAIN值）选出一个最佳属性作为节点N的测试属性; 6.节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏; 7.如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树.,9,信息熵 (Entropy),如何衡量信息量的多少？比如一本50多万字的史记或一套莎士比亚全集 1948年，香农(Claude Shannon)在他著名的论文“通信的数学原理”中提出了信息熵的概念，证明熵与信息内容
4、的不确定程度有等价关系 若一个系统中存在多个事件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的概率，用 估计,11,计算对下列数据集分类所需的信息熵,12,|D|=14 |C1,D|=5 |C2,D|=9,信息增益,13,选择具有最高信息增益Gain(A) 的属性A作为分裂属性,按照能做“最佳分类”的属性A划分， 使
5、完成样本分类需要的信息量最小,确定第一次分裂的属性：按年龄划分,年龄40的有5个, 其中2个为“否”,Info年龄(D),Gain(年龄) = Info(D) - Info年龄(D) = 0.940 - 0.694 = 0.246,14,确定第一次分裂的属性：按收入划分,收入=高的有4个, 其中2个为“否” 收入=中的有6个, 其中2个为“否” 收入=低的有4个, 其中1个为“否”,Info收入(D),Gain(收入) = Info(D) - Info收入(D) = 0.940 - 0.911 = 0.029,15,确定第一次分裂的属性：按学生划分,是学生的有7个, 其中1个为“否” 不是学生
6、的有7个, 其中4个为“否”,Info学生(D),Gain(学生) = Info(D) - Info学生(D) = 0.940 - 0.788 = 0.152,16,确定第一次分裂的属性：按信用划分,信用好的有6个, 其中3个为“否” 信用一般的有8个, 其中2个为“否”,Info信用(D),Gain(信用) = Info(D) - Info信用(D) = 0.940 - 0.892 = 0.048,17,确定第一次分裂的属性,年龄,30,30-40,40,“年龄”属性具体最高 信息增益，成为分裂属性,18,确定第二次分裂的属性,Info收入(D) = 2/5 * (-2/2 * log2/2
7、 - 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,决策树的构建,年龄,30,30-40,40,学生,不买,买,不是学生,是学生,买,20,本堂小结,决策树分类 概念，结构 决策树构建 ID3算法，信息熵，信息增益 下节预告 ID3算法的不足 C4.5算法对ID3的改进,21,谢谢大家！,唐国明 国防科技大学原信息系统与管理学院,
