AI_决策树学习_Chap6

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人,工,工智,能,能,第,第6,章,章,学习,智,智能,体,体-,决,决策,树,树学,习,习,巢文,涵,涵,chaowenhanG1001/G931,北航,计,计算,机,机学,院,院智,能,能信,息,息研,究,究所,10/27/2022,1,大纲,简介,决策树,学,学习算,法,法,应用实,例,例,2,决策树(DecisionTree),决策树,学,学习是,应,应用最,广,广的归,纳,纳推理,算,算法之,一,一,它是一,种,种逼近,离散,函数的,方,方法,学习到,的,的函数,以,以决策,树,树的形,式,式表示,主要用,于,于分类,对噪声,数,数据有,很,很好的,鲁,鲁棒性,能够学,习,习析取,表,表达,3,分类任,务,务基本,框,框架,4,分类应,用,用实例,垃圾邮,件,件过滤,信贷分,析,析,新闻分,类,类,人脸识,别,别、手,写,写体识,别,别等,5,决策树,的,的结构,图结构,内部节,点,点（非,树,树叶节,点,点，包,括,括根节,点,点）,在一个,属,属性上,的,的测试,分枝,一个测,试,试输出,树叶节,点,点,类标识,6,决策树,示,示例,分类型,分类型,连续型,类别,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试属,性,性,训练数,据,据,模型：,决,决策树,(Refund=YES),(Refund=NO,(Refund=NO,Married=NO),7,另一棵,决,决策树,MarSt,Refund,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,相同的数据,可,可产生多棵,决,决策树,分类型,分类型,连续型,类别,8,决策树分类,任,任务框架,决策树,9,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,从根节点开,始,始,10,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,11,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,12,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,13,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,14,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,指定欺诈为,：,： “No,”,”,15,决策树分类,任,任务框架,Decision Tree,16,大纲,简介,决策树学习,算,算法,应用实例,17,决策树算,法,法,Hunt,s Algorithm,CART,ID3,C4.5,SLIQ,SPRINT,18,基本的ID3算法,19,基本算法,Dont,Cheat,Refund,Dont,Cheat,Dont,Cheat,Yes,No,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,Taxable,Income,Dont,Cheat,= 80K,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,20,决策树归,纳,纳,贪婪策略,根据特定,的,的性能度,量,量选择最,好,好的划分,属,属性,要素,哪个属性,是,是最佳的,分,分类属性,？,？,如何确定,最,最佳划分,点,点,如何确定,停,停止条件,21,度量标准,熵,熵(Entropy),信息论中,广,广泛使用,的,的一个度,量,量标准,刻画任意,样,样例集的,纯,纯度（purity）,一般计算,公,公式为：,对于二元,分,分类：给,定,定包含关,于,于某个目,标,标概念的,正,正反样例,的,的样例集,S,，那么,S,相对这个,布,布尔型分,类,类的熵为,：,：,Entropy,(,S,),-,p,log,2,p,-,p,log2,p,其中,p,是在,S,中正例的,比,比例，,p,是在,S,中负例的,比,比例。在,有,有关熵的,所,所有计算,中,中我们定,义,义0log0为0,。,。,22,例子,Entropy= -(0/6)log(0/6)-(6/6)log(6/6)=0,Entropy= 1-(1/6)log(1/6)-(5/6)log(5/6)=0.650,Entropy= 1-(3/6)log(3/6)-(3/6)log(3/6)=1,23,度量标准,熵,24,度量标准,熵,信息论中,熵,熵的一种,解,解释,熵确定了,要,要编码集,合,合,S,中任意成,员,员（即以,均,均匀的概,率,率随机抽,出,出的一个,成,成员）的,分,分类所需,要,要的最少,二,二进制位,数,数,= 1,接收者知,道,道抽出的,样,样例必为,正,正，所以,不,不必发任,何,何消息，,熵,熵为0,= 0.5,必须用一,个,个二进制,位,位来说明,抽,抽出的样,例,例是正还,是,是负，熵,为,为1,= 0.8,那么对所,需,需的消息,编,编码方法,是,是赋给正,例,例集合较,短,短的编码,，,，可能性,较,较小的反,例,例集合较,长,长的编码,，,，平均每,条,条消息的,编,编码少于1个二进,制,制位,25,性能度量,信息,增,增益,属性的信,息,息增益,使用这个,属,属性分割,样,样例而导,致,致的期望,熵,熵降低的,数,数量,Values,(,A,)是属性,A,所有可能,值,值的集合,S,v,是,S,中属性,A,的值为,v,的子集,，,，即S,v,=,s,S|A(s)=v,当,对,对,S,的,一,一,个,个,任,任,意,意,成,成,员,员,的,的,目,目,标,标,值,值,编,编,码,码,时,时,，,，,Gain,(,S,A,),的,的,值,值,是,是,在,在,知,知,道,道,属,属,性,性,A,的,值,值,后,后,可,可,以,以,节,节,省,省,的,的,二,二,进,进,制,制,位,位,数,数,26,例,子,子,假,设,设S,是,是,有,有,关,关,天,天,气,气,的,的,训,训,练,练,样,样,例,例,集,集9+,5-,其,中,中,：,：,wind=weak,的,的,样,样,例,例,是,是6+,2-,wind=strong,的,的,样,样,例,例+3,-3,问,题,题:,计,计,算,算,属,属,性,性wind,的,的,信,信,息,息,增,增,益,益,S,的,的,熵,熵,：,：E(S)=-(9/14)log(9/14),(5/14)log(9/14)=0.940,27,选,择,择,最,最,好,好,的,的,分,分,类,类,属,属,性,性,28,大,纲,纲,简,介,介,决,策,策,树,树,学,学,习,习,算,算,法,法,应,用,用,实,实,例,例,29,应,用,用,实,实,例,例,问,题,题,及,及,数,数,据,据,集,集,根,据,据,其,其,他,他,属,属,性,性,，,，,判,判,断,断,周,周,六,六,是,是,否,否,玩,玩,网,网,球,球playTennis=Y/N?,30,Step1:,确,确,定,定,根,根,节,节,点,点,分,别,别,计,计,算,算4,个,个,属,属,性,性,的,的,信,信,息,息,增,增,益,益,Outlook:0.246,=Sunny2+,3-,=Overcast4+,0-,=Rain3+,2-,Wind:0.048,=weak,的,的,样,样,例,例,是,是6+,2-,=strong,的,的,样,样,例,例+3,-3,Humidity:0.151,Temperature:0.029,因,此,此,：,：,根,根,节,节,点,点,为,为Outlook,31,Step2:,分,分,枝,枝,选,择,择,哪,哪,个,个,属,属,性,性,进,进,行,行,划,划,分,分,？,？,32,Step3:,循,循,环,环,选择哪个属,性,性进行划分,？,？,33,小结,实例是由“,属,属性-值”,对,对（pair）表示的,目标函数具,有,有离散的输,出,出值,可能需要析,取,取的描述（disjunctive description）,训练数据可,以,以包含错误,训练数据可,以,以包含缺少,属,属性值的实,例,例,34,作业,6-1画出,表,表示下面布,尔,尔函数的决,策,策树,（a）,A,B,（b）,A,B,C,（c）,A,XOR,B,（d）,A,B,C,D,35,作业,6-2考虑,下,下面的训练,样,样例集合,手动给出决,策,策树的构造,过,过程,36,作业,6-3ID3仅寻,找,找一个一致,的,的假设，而,候,候选消除算,法,法寻找所有,一,一致的假设,。,。考虑这两,种,种学习算法,间,间的对应关,系,系,（a）假定,给,给定,EnjoySport,的四个训练,样,样例，画出ID3学习,的,的决策树,（b）学习,到,到的决策树,和,和从同样的,样,样例使用变,型,型空间算法,得,得到的变型,空,空间间有什,么,么关系？树,等,等价于变型,空,空间的一个,成,成员吗？,37,作业,6-4 实,现,现ID3算,法,法，并以PlayTennis实,例,例中的训练,集,集进行训练,，,，给出最终,的,的决策树,38,演讲完毕，,谢,谢谢观看！,