第七章机器学习7.1机器学习的基本概念7.2归纳学习7.2.2基于描述空间的归纳学习消除候选者算法应用示例7.2.3基于决策树的归纳学习方法1、决策树及决策树构造算法CLSCLS算法描述CLS算法应用示例2、ID3算法ID3算法相关定义ID3算法应用示例7.3基于解释的学习7.3.1基于解释的学习框架基于解释的学习框架示例7.3.2基于解释的学习过程基于解释的学习过程示例7.4遗传算法7.5人工神经网络作业消除候选者算法应用示例例7.2对例7.1给出的概念空间,应用消除候选者学习算法,说明学习得到一般概念“圆”的学习步骤和学习结果。消除候选者算法应用示例已知概念空间:应用消除候选者学习算法,说明“圆”概念的学习过程。(xy)(smallsquare)(smallcircle)(largesquare)(largecircle)(smally)(largey)(xsquare)(xcircle)消除候选者算法应用示例解:“圆”的一般概念可表示为(xcircle),其学习过程如下:1)初始化描述空间H=G,S其中:G={(xy)}S={(smallsquare),(smallcircle),(largesquare),(largecircle)}消除候选者算法应用示例2)若首先提供一个正例:(smallcircle)删去G中与提供的正例不相容的元素:由于G={(xy)},其中(xy)是最一般概念,与提供的正例(smallcircle)相容,故仍有:G={(xy)}对S中的元素尽可能小地一般化,使其与提供的正例相容,删去S中一般化后仍然与提供的正例不相容的元素(largesquare),得:S={(smally),(smallcircle),(xcircle)}消除候选者算法应用示例3)此时有G≠S,若再提供一个反例:(largesquare)直接删去S中所有与该例相容的概念:由于S中的元素都与提供的反例不相容,故S不变,仍有:S={(smally),(smallcircle),(xcircle)}对G中的元素(xy)尽可能小地特殊化,可由(xy)得出与提供的反例(largesquare)不相容的2个概念(smally)和(xcircle),故有:G={(smally),(xcircle)}消除候选者算法应用示例4)此时有G≠S,若再提供一个正例(largecircle)直接删去G中与提供的正例(largecircle)不相容的元素(smally),故有:G={(xcircle)}对S中的元素尽可能小地一般化,使其与提供的正例相容,删去S中无法最小一般化的元素(smally)(超过上界,即比G中概念还要大),故有:S={(xcircle)(xcircle)}消除候选者算法应用示例5)此时有G=S={(xcircle)},算法中止。经过学习后获得的“圆”概念为:(xcircle)CLS算法应用示例假设需要根据人员的外貌特征对人员进行分类,用于人员分类的外貌特征有3个,它们组成人员分类属性表为:AttrList={height,hair,eyes}各属性的值域分别为:ValueType(height)={short,tall}ValueType(hair)={blond,red,dark}ValueType(eyes)={blue,brown}对人员进行分类的结果有两种,分别用“+”和“—”表示,组成分类结果表为:Class={+,—}提供学习的训练实例集为:T={(short,blond,blue),+,(tall,blond,brown),—(tall,red,blue),+,(short,dark,blue),—,(tall,dark,blue),—,(tall,blond,blue),+,(tall,dark,brown),—,(short,blond,brown),—}应用CLS构造算法构造决策树,说明构造过程,画出构造的决策树。解:1)若选取属性表AttrList={height,hair,eyes}中属性height作为第1个检测属性,则将T分为2个子集T1和T2,T1是属性height取值为short的训练实例子集,T2是属性height取值为tall的训练实例子集。T1={(short,blond,blue),+,(short,dark,blue),—(short,blond,brown),—}T2={(tall,blond,brown),—,(tall,red,blue),+,,(tall,dark,blue),—,(tall,blond,blue),+,(tall,dark,brown),—}从属性表中删去检测属性height,故新的属性表为:AttrList={hair,eyes}至此,生成的决策树如图所示:heightT1T2shorttall2)由于T1和T2中的实例的分类结果仍有两种,故需按新的属性表递归构造T1和T2的子树。若选取新属性表中的属性hair作为第2个检测属性,由于hair的值域ValueType(hair)={blond,red,dark},有3个取值,故将T1分为3个子集:T11、T12和T13,将T2也分为3个子集T21、T22和T23:T11={(short,blond,blue),+,(short,blond,brown),—}T12={}T13={(short,dark,blue),—}T21={(tall,blond,brown),—,(tall,blond,blue),+}T22={(tall,red,blue),+}T23={(tall,dark,blue),—,(tall,dark,brown),—}从属性表中删去检测属性hair,故新的属性表为:AttrList={eyes}至此,生成的决策树如图所示:heighthairhairT12T11T13T21T23shortredtallblonddarkblonddarkT22red3)由于T13、T22和T23中的实例的分类结果均只有一种,故无需继续划分子集,用T13的实例分类结果“—”,作为叶节点代替上图中节点T13,用T22的实例分类结果“+”作为叶节点代替T22,用T23的的实例分类结果“—”作为叶节点代替T23,T12是一个空集,故从决策树中删去节点T12:heighthairhairT11—T21—shorttallblonddarkblonddark+red由于T11和T21中的实例的分类结果仍有两种,故还需按新的属性表递归构造T11和T21的子树。以新属性表中的属性eyes作为第3个检测属性,eyes的值域为:ValueType(eyes)={blue,brown}有2个取值,故将T11分为2个子集T111和T112,将T21也分为2个子集T211和T212,它们分别为:T111={(short,blond,blue),+}T112={(short,blond,brown),—}T211={(tall,blond,blue),+}T212={(tall,blond,brown),—}从属性表中删去检测属性eyes,故新的属性表已成为一个空表。至此,生成的决策树如图所示:blueheighthairhair——shorttallblonddarkblonddark+redeyeseyesT111T112T211T212brownbluebrown4)由于T111、T112、T211和T212中的实例的分类结果都只有一种,则用它们的实例分类结果作为叶节点来分别代替它们,得到最后的完整的决策树如图所示。heighthairhair——shorttallblonddarkblonddark+redeyeseyes+—+—brownbluebrownblue2.ID3算法CLS决策树构造算法每次从属性表属性AttrList中任选一个属性Ai作为检测属性来扩展生成决策树,按照属性Ai的取值来反复划分训练实例集T,因此,CLS算法的效率较低。ID3算法应用示例假设需要根据人员的外貌特征对人员进行分类,用于人员分类的外貌特征有3个,它们组成人员分类属性表为:AttrList={height,hair,eyes}各属性的值域分别为:ValueType(height)={short,tall}ValueType(hair)={blond,red,dark}ValueType(eyes)={blue,brown}对人员进行分类的结果有两种,分别用“+”和“—”表示,组成分类结果表为:Class={+,—}提供学习的训练实例集为:T={short,blond,blue,+,(tall,blond,brown),—(tall,red,blue),+,(short,dark,blue),—,(tall,dark,blue),—,(tall,blond,blue),+,(tall,dark,brown),—,(short,blond,brown),—}应用ID3算法构造决策树,说明构造过程,画出构造的决策树。解:1)在实例集T中,分类结果为“+”的实例数为3,分类结果为“—”的实例数为5,故(划分前)T的实例平均信息量为:I(T)=—(5log25/8+3log23/8)/8=0.954(bit)若选第1个属性height为检测属性,其值域ValueType(height)={short,tall}则将T分为2个子集:={(short,blond,blue),+,(short,dark,blue),—,(short,blond,brlwn),—}={(tall,blond,brlwn),—,(tall,red,blue),+,(tall,dark,blue),—,(tall,blond,blue),+,(tall,dark,brown),—})1(1T)1(2T中分类结果为“+”的实例数为1,分类结果为“—”的实例数为2,可得:的实例平均信息量为:-(log21/3+2log22/3)/3=0.918(bit)中分类结果为“+”的实例数为2,分类结果为“—”的实例数为3,可得:的实例平均信息量为:-(2log22/5+3log23/5)/5=0.971(bit))1(1T)1(2T)1(1T)()1(1TI)1(2T)()1(2TI故而,若以属性heigh为检测属性,(划分后)T的实例平均信息量为:I(T,height)=(3×I()+5×I())/8=(3×0.918+5×0.971)/8=0.951(bit)由此可得用属性height划分前后的信息量差为:GI(T,eight)=I(T)-I(T,height)=0.954-0.951=0.003(bit))1(1T)1(2T同理可得:GI(T,hair)=0.5(bit)GI(T,eyes)=0.347(bit)由于GI(T,hair)最大,故选取第2个属性hair作为检测属性。划分后,从属性表中删去属性hair,更新属性表为:AttrList={height,eyes}至此,生成的决策树如下图所示:={(short,blond,blue),+,(tall,blond,brown),—,(tall,blond,blue),+,(short,blond,brown),—}={(tall,red,blue),+}={(short,dark,blue),—,(tall,dark,blue),—(tall,dark,brown),—})2(1T)2(2T)2(3Thairblonddarkred)2(1T)2(2T)2(3T2)由于中的实例分类结果仍有两种,故还需划分在中,分类结果