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