第 07 章 机器学习 人工智能课件

第七章机器学习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）由于中的实例分类结果仍有两种，故还需划分在中，分类结果