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

《第07章机器学习人工智能ppt课件.ppt》由会员分享，可在线阅读，更多相关《第07章机器学习人工智能ppt课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第七章第七章第七章第七章机器学习机器学习机器学习机器学习7.1机器学习的基本概念机器学习的基本概念7.2归纳学习归纳学习7.2.2基于描述空间的归纳学习基于描述空间的归纳学习消除候选者算法消除候选者算法应用示例应用示例7.2.3基于决策树的归纳学习方法基于决策树的归纳学习方法1、决策树及决策树构造算法决策树及决策树构造算法CLSCLS算法描述算法描述CLS算法应用示例算法应用示例2、ID3算法算法ID3算法相关定义算法相关定义ID3算法应用示例算法应用示例7.3基于解释的学习基于解释

2、的学习7.3.1基于解释的学习框架基于解释的学习框架基于解释的学习框架示例基于解释的学习框架示例7.3.2基于解释的学习过程基于解释的学习过程基于解释的学习过程示例基于解释的学习过程示例7.4遗传算法遗传算法7.5人工神经网络人工神经网络作业作业严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例l例例7.2对对例例7.1给给出出的的概概念念空空间间，应应用用消消除除候候选选者者学学习习算算法法，说说明明学学习习得得到到一一般般概概念念“圆圆”的学

3、习步骤和学习结果。的学习步骤和学习结果。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例l已知概念空间：已知概念空间：l应用应用消除候选者消除候选者学习算法，说明学习算法，说明“圆圆”概念的学习过程。概念的学习过程。(x y)(small square)(small circle)(large square)(large circle)(small y)(large y)(x square)(x circle)严格执行突发事件上报制度、校外活动

4、报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例解：解：l“圆圆”的的一一般般概概念念可可表表示示为为(xcircle)，其其学学习习过过程程如下：如下：1）初始化描述空间）初始化描述空间H=其中：其中：G=（xy）S=(smallsquare),(smallcircle),(largesquare),(largecircle)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用

5、示例消除候选者算法应用示例消除候选者算法应用示例2）若首先提供一个）若首先提供一个正例：正例：(smallcircle)l删删去去G中中与与提提供供的的正正例例不不相相容容的的元元素素：由由于于G=(xy)，其其中中(xy)是是最最一一般般概概念念，与与提提供供的的正正例例(smallcircle)相相容容，故仍有：故仍有：G=(xy)l对对S中中的的元元素素尽尽可可能能小小地地一一般般化化，使使其其与与提提供供的的正正例例相相容容，删删去去S中中一一般般化化后后仍仍然然与与提提供供的的正正例例不不相相容容的的元元素素(largesquare)，得：，得：S=(smally),(smallci

6、rcle),(xcircle)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例3）此时有）此时有GS，若再提供一个反例：，若再提供一个反例：(largesquare)l直直接接删删去去S中中所所有有与与该该例例相相容容的的概概念念：由由于于S中中的的元元素素都都与与提提供供的的反反例例不不相相容容，故故S不不变变，仍仍有有：S=(smally),(smallcircle),(xcircle)l对对G中中的的元元素素(xy)尽尽可可能能小小地地特

7、特殊殊化化，可可由由(xy)得得出出与与提提供供的的反反例例(large square)不不相相容容的的2个个概概念念(smally)和和(xcircle)，故有：，故有：G=(smally),(xcircle)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例4）此时有）此时有GS，若再提供一个正例，若再提供一个正例(largecircle)l直直接接删删去去G中中与与提提供供的的正正例例(largecircle)不不相相容容的的元素元素(sm

8、ally)，故有：，故有：G=(xcircle)l对对S中中的的元元素素尽尽可可能能小小地地一一般般化化，使使其其与与提提供供的的正正例例相相容容，删删去去S中中无无法法最最小小一一般般化化的的元元素素(smally)（超过上界，即比（超过上界，即比G中概念还要大）中概念还要大），故有：，故有：S=(xcircle)(xcircle)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例消除候选者算法应用示例5）此时有）此时有G=S=(xcircle)，算法中止。，算法中

9、止。l经过学习后获得的经过学习后获得的“圆圆”概念为：概念为：(xcircle)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。CLSCLS算法应用示例算法应用示例算法应用示例算法应用示例l假设需要根据人员的假设需要根据人员的外貌特征外貌特征对人员进行分类，用对人员进行分类，用于人员分类的外貌特征有于人员分类的外貌特征有3个，它们组成人员分类属个，它们组成人员分类属性表为：性表为：AttrList=height,hair,eyesl各属性的值域分别为：各属性的值域分别为：ValueType(height)=short,tallVa

10、lueType(hair)=blond,red,darkValueType(eyes)=blue,brown严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l对对人人员员进进行行分分类类的的结结果果有有两两种种，分分别别用用“+”和和“”表表示示，组成分类结果表为：组成分类结果表为：Class=+,l提供学习的训练实例集为：提供学习的训练实例集为：T=,l应应用用CLS构构造造算算法法构构造造决决策策树树，说说明明构构造造过过程程，画画出出构构造造的的决策树。决策树。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及

11、时发现、制止、汇报并处理各类违纪行为或突发事件。解解:1）若若选选取取属属性性表表AttrList=height,hair,eyes中中属属性性height作作为第为第1个检测属性，则将个检测属性，则将T分为分为2个子集个子集T1和和T2，lT1是属性是属性height取值为取值为short的训练实例子集，的训练实例子集，lT2是属性是属性height取值为取值为tall的训练实例子集。的训练实例子集。T1=,T2=,严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l从属性表中删去检测属性从属性表中删去检测属性height，故新的

12、属性表为：，故新的属性表为：AttrList=hair,eyesl至此，生成的决策树如图所示：至此，生成的决策树如图所示：heightT1T2shorttall严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2）由由于于T1和和T2中中的的实实例例的的分分类类结结果果仍仍有有两两种种，故故需需按按新新的的属属性性表表递递归归构构造造T1和和T2的子树。的子树。l若若选选取取新新属属性性表表中中的的属属性性hair作作为为第第2个个检检测测属属性性，由由于于hair的的值值域域ValueType(hair)=blond,red,da

13、rk，有有3个个取取值值，故故将将T1分分为为3个个子子集集：T11、T12和和T13，将，将T2也分为也分为3个子集个子集T21、T22和和T23：T11=,T12=T13=T21=,T22=T23=,严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l从属性表中删去检测属性从属性表中删去检测属性hair，故新的属性表为：，故新的属性表为：AttrList=eyesl至此，生成的决策树如图所示：至此，生成的决策树如图所示：heighthairhairT12T11T13T21T23shortredtallblonddarkblond

14、darkT22red严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。3）由由于于T13、T22和和T23中中的的实实例例的的分分类类结结果果均均只只有有一一种种，故故无无需需继继续续划划分分子子集集，用用T13的的实实例例分分类类结结果果“”，作作为为叶叶节节点点代代替替上上图图中中节节点点T13，用用T22的的实实例例分分类类结结果果“+”作作为为叶叶节节点点代代替替T22，用用T23的的的的实实例例分分类类结结果果“”作作为为叶叶节节点点代代替替T23，T12是是一一个个空空集集，故故从从决决策树中策树中删去删去节点节点T12

15、：heighthairhairT11T21shorttallblonddarkblonddark+red严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l由由于于T11和和T21中中的的实实例例的的分分类类结结果果仍仍有有两两种种，故故还还需需按按新新的的属性表属性表递归构造递归构造T11和和T21的子树。的子树。l以新属性表中的属性以新属性表中的属性eyes作为作为第第3个个检测属性，检测属性，eyes的值域为：的值域为：ValueType(eyes)=blue,brown有有2个取值个取值，故将，故将T11分为分为2个子集个子

16、集T111和和T112，将将T21也分为也分为2个子集个子集T211和和T212，它们分别为：，它们分别为：T111=T112=T211=T212=严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l从从属属性性表表中中删删去去检检测测属属性性eyes，故故新新的的属属性性表表已已成成为为一一个个空空表。至此，生成的决策树如图所示：表。至此，生成的决策树如图所示：blueheighthairhairshorttallblonddarkblonddark+redeyeseyesT111T112T211T212brownbluebrow

17、n严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。4）由由于于T111、T112、T211和和T212中中的的实实例例的的分分类类结结果果都都只只有有一一种种，则则用用它它们们的的实实例例分分类类结结果果作作为为叶叶节节点点来来分分别别代代替替它它们们，得得到到最最后后的的完完整整的的决决策策树树如图所示。如图所示。heighthairhairshorttallblonddarkblonddark+redeyeseyes+brownbluebrownblue严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制

18、止、汇报并处理各类违纪行为或突发事件。2.ID32.ID3算法算法算法算法 CLS决策树构造算法每次从属性表属性决策树构造算法每次从属性表属性AttrList中中任选任选一个属性一个属性Ai作为检测属性来扩作为检测属性来扩展生成决策树，按照属性展生成决策树，按照属性Ai的取值来反复划的取值来反复划分训练实例集分训练实例集T，因此，因此，CLS算法的算法的效率较低效率较低。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。ID3ID3算法应用示例算法应用示例算法应用示例算法应用示例l假设需要根据人员的假设需要根据人员的外貌特征外貌特征

19、对人员进行分类，用对人员进行分类，用于人员分类的外貌特征有于人员分类的外貌特征有3个，它们组成人员分类属个，它们组成人员分类属性表为：性表为：AttrList=height,hair,eyesl各属性的值域分别为：各属性的值域分别为：ValueType(height)=short,tallValueType(hair)=blond,red,darkValueType(eyes)=blue,brown严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l对对人人员员进进行行分分类类的的结结果果有有两两种种，分分别别用用“+”和和“”表表

20、示示，组成分类结果表为：组成分类结果表为：Class=+,l提供学习的训练实例集为：提供学习的训练实例集为：T=,l应用应用ID3算法构造决策树，说明构造过程，画出构造的决策树。算法构造决策树，说明构造过程，画出构造的决策树。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。解：解：1）在在实实例例集集T中中，分分类类结结果果为为“+”的的实实例例数数为为3，分分类类结结果果为为“”的的实实例数为例数为5，故（，故（划分前划分前）T的的实例平均信息量实例平均信息量为：为：I(T)=(5log25/8+3log23/8)/8=0.95

21、4(bit)l若选若选第第1个属性个属性height为检测属性，为检测属性，其值域其值域ValueType(height)=short,talll则将则将T分为分为2个子集：个子集：=,=,严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l中中分分类类结结果果为为“+”的的实实例例数数为为1，分分类类结结果果为为“”的实例数为的实例数为2，可得：，可得：的实例平均信息量为：的实例平均信息量为：-(log21/3+2log22/3)/3=0.918(bit)l中中分分类类结结果果为为“+”的的实实例例数数为为2，分分类类结结果果为为

22、“”的的实例数为实例数为3，可得：，可得：的实例平均信息量为：的实例平均信息量为：-(2log22/5+3log23/5)/5=0.971(bit)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l故故而而，若若以以属属性性heigh为为检检测测属属性性，（划划分分后后）T的的实实例例平平均均信息量信息量为：为：I(T,height)=(3I()+5I()/8=(30.918+50.971)/8=0.951(bit)l由此可得用属性由此可得用属性height划分前后划分前后的的信息量差信息量差为：为：GI(T,eight)=I(T

23、)I(T,height)=0.9540.951=0.003(bit)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l同理可得：同理可得：GI(T,hair)=0.5(bit)GI(T,eyes)=0.347(bit)l由由于于GI(T,hair)最最大大，故故选选取取第第2个个属属性性hair作作为为检检测属性。测属性。l划分后，从属性表中删去属性划分后，从属性表中删去属性hair，更新属性表为：，更新属性表为：AttrList=height,eyesl至此，生成的决策树如下图所示：至此，生成的决策树如下图所示：严格执行突发事件

24、上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。=,=,hairblonddarkred严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2）由于）由于中的实例分类结果仍有两种，故还需划分中的实例分类结果仍有两种，故还需划分在在中中，分分类类结结果果为为“+”的的实实例例数数为为2，分分类类结结果果为为“”的实例数也为的实例数也为2，可得，可得划分前划分前的实例平均信息量为：的实例平均信息量为：I()=-(2log22/4+2log22/4)/4=1(bit)l若若选选新新属属性性表表

25、的的第第1个个属属性性height为为检检测测属属性性，其其值值域域ValueType(height)=short,talll将将划分为划分为2个子集：个子集：=,严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l计算实例平均信息量：计算实例平均信息量：I()=-(log21/2+log21/2)/2=1(bit)I()=-(log21/2+log21/2)/2=1(bit)I(,height)=(2I()+2I()/4=1(bit)GI(,height)=I()I(,height)=0严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l显显然然属属性性eyes对对实实例例集集的的信信息息量量GI(,eyes)=1，因此选择属性因此选择属性eyes作为检测属性。作为检测属性。l最后生成的决策树如下图所示：最后生成的决策树如下图所示：hairblonddarkred+eyesbrownblue+严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。作业作业P.2947.37.47.5（2）第一次划分过程第一次划分过程