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

第七章,机器学习,7,.1,机器学习的基本概念,7.2,归纳学习,7,.2.2,基于描述空间的归纳学习,消除候选者算法,应用示例,7.2.3,基于决策树的归纳学习方法,1,、,决策树及决策树构造算法,CLS,CLS,算法描述,CLS,算法应用示例,2,、,ID3,算法,ID3,算法相关定义,ID3,算法应用示例,7.3,基于解释的学习,7.3.1,基于解释的学习框架,基于解释的学习框架示例,7.3.2,基于解释的学习过程,基于解释的学习过程示例,7.4,遗传算法,7.5,人工神经网络,作业,消除候选者算法应用示例,例,7.2,对例,7.1,给出的概念空间，应用消除候选者学习算法，说明学习得到,一般概念“圆”的学习步骤,和学习结果。,消除候选者算法应用示例,已知概念空间：,应用,消除候选者,学习算法，说明“,圆,”概念的学习过程。,(x y),(small square),(small circle),(large square),(large circle),(small y),(large y),(x square),(x circle),消除候选者算法应用示例,解：,“,圆,”的一般概念可表示为,(x circle),，,其学习过程如下：,1,）初始化描述空间,H = ,其中：,G=,（,x y,）,S= (small square), (small circle),(large square), (large circle) ,消除候选者算法应用示例,2,）若首先提供一个,正例：,(small circle),删去,G,中与提供的正例不相容的元素：由于,G= (x y) ,，其,中,(x y),是最一般概念，与提供的正例,(small circle),相容，故仍有：,G= (x y) ,对,S,中的元素尽可能小地一般化，使其与提供的正例相容，删去,S,中一般化后仍然与提供的正例不相容的元素,(large square),，,得：,S= (small y), (small circle), (x circle) ,消除候选者算法应用示例,3,）此时有,G,S,，,若再提供一个反例：,(large square),直接删去,S,中,所有与该例,相容,的概念：由于,S,中的元素都与提供的反例不相容，,故,S,不变，仍有：,S= (small y), (small circle), (x circle),对,G,中的元素,(x y),尽可能小地特殊化，可由,(x y),得出与提供的反例,(large square),不相容的,2,个概念,(small y),和,(x circle),，,故有：,G = (small y), (x circle) ,消除候选者算法应用示例,4,）此时有,G,S,，,若再提供一个正例,(large circle),直接删去,G,中与提供的正例,(large circle),不相容的元素,(small y),，,故有,：,G=(x circle),对,S,中的元素尽可能小地一般化，使其与提供的正例相容，删去,S,中无法最小一般化的元素,(small y),（超过上界，即比,G,中概念还要大）,，故有：,S = (x circle) (x circle) ,消除候选者算法应用示例,5,）,此时有,G = S = (x circle) ,，,算法中止。,经过学习后获得的“,圆,”概念为：,(x circle),CLS,算法应用示例,假设需要根据人员的,外貌特征,对人员进行分类，用于人员分类的外貌特征有,3,个，它们组成人员分类属性表为：,AttrList,= height, hair, eyes ,各属性的值域分别为：,ValueType(height,) = short, tall ,ValueType(hair,) = blond, red, dark ,ValueType(eyes,) = blue, brown ,对人员进行分类的结果有两种，分别用“,+,”,和“,”,表示，组成分类结果表为：,Class = +,提供学习的训练实例集为：,T=, , , , ,应用,CLS,构造算法构造决策树，说明构造过程，画出构造的决策树,。,解,:,1,）若选取属性表,AttrList,= height, hair, eyes,中属性,height,作为第,1,个检测属性，则将,T,分为,2,个子集,T,1,和,T,2,，,T,1,是属性,height,取值为,short,的训练实例子集，,T,2,是属性,height,取值,为,tall,的训练实例子集。,T,1,=, ,T,2,=, , , ,从属性表中删去检测属性,height,，,故新的属性表为：,AttrList,=hair, eyes,至此，生成的决策树如图所示：,height,T,1,T,2,short,tall,2,）由于,T,1,和,T,2,中的实例的分类结果仍有两种，故需按新的属性表递归构造,T,1,和,T,2,的子树。,若选取新属性表中的属性,hair,作为,第,2,个,检测属性，由于,hair,的值域,ValueType(hair,) = blond, red, dark,，,有,3,个取值,，,故将,T,1,分为,3,个子集,：,T,11,、,T,12,和,T,13,，将,T,2,也分为,3,个子集,T,21,、,T,22,和,T,23,：,T,11,=, ,T,12,= ,T,13,=,T,21,=, ,T,22,=,T,23,=, ,从属性表中删去检测属性,hair,，,故新的属性表为：,AttrList,=eyes,至此，生成的决策树如图所示：,height,hair,hair,T,12,T,11,T,13,T,21,T,23,short,red,tall,blond,dark,blond,dark,T,22,red,3,）由于,T,13,、,T,22,和,T,23,中的实例的,分类结果均只有一种,，故,无需继续划分,子集，,用,T,13,的实例分类结果“,”,，作为叶节点代替上图中节点,T,13,，用,T,22,的实例分类结果“,+,”,作为叶节点代替,T,22,，用,T,23,的的实例分类结果“,”,作为叶节点代替,T,23,，,T,12,是一个,空集,，故从决策树中,删去,节点,T,12,：,height,hair,hair,T,11,T,21,short,tall,blond,dark,blond,dark,+,red,由于,T,11,和,T,21,中的实例的,分类结果仍有两种,，故还需按新的属性表,递归构造,T,11,和,T,21,的子树。,以新属性表中的属性,eyes,作为,第,3,个,检测属性,，,eyes,的值域为：,ValueType(eyes,) = blue, brown ,有,2,个取值,，故将,T,11,分为,2,个子集,T,111,和,T,112,，,将,T,21,也分为,2,个子集,T,211,和,T,212,，,它们分别为：,T,111,=,T,112,=,T,211,=,T,212,=,从属性表中删去检测属性,eyes,，,故新的属性表已成为一个空表。至此，生成的决策树如图所示：,blue,height,hair,hair,short,tall,blond,dark,blond,dark,+,red,eyes,eyes,T,111,T,112,T,211,T,212,brown,blue,brown,4,）由于,T,111,、,T,112,、,T,211,和,T,212,中的实例的分类结果都只有一种，则用它们的实例分类结果作为叶节点来分别代替它们，得到最后的完整的决策树如图所示,。,height,hair,hair,short,tall,blond,dark,blond,dark,+,red,eyes,eyes,+,+,brown,blue,brown,blue,2. ID3,算法,CLS,决策树构造算法每次从属性表属性,AttrList,中,任选,一个属性,A,i,作为检测属性来扩展生成决策树，按照属性,A,i,的取值来反复划分训练实例集,T,，,因此,，,CLS,算法的,效率较低,。,ID3,算法应用示例,假设需要根据人员的,外貌特征,对人员进行分类，用于人员分类的外貌特征有,3,个，它们组成人员分类属性表为：,AttrList,=height, hair, eyes,各属性的值域分别为：,ValueType(height,)=short, tall,ValueType(hair,)=blond, red, dark,ValueType(eyes,)=blue, brown,对人员进行分类的结果有两种，分别用“,+,”,和“,”,表示，组成分类结果表为,：,Class=+,提供学习的训练实例集为：,T=, , , , ,应用,ID3,算法构造决策树，说明构造过程，画出构造的决策树,。,解：,1,）在实例,集,T,中，分类结果为“,+,”,的实例数为,3,，分类结果为“,”,的实例数为,5,，故（,划分前,）,T,的,实例平均信息量,为：,I(T)=,( 5log,2,5/8 + 3log,2,3/8 ) / 8 = 0.954 (bit),若选,第,1,个属性,height,为检测属性，,其值域,ValueType(height,) = short, tall,则将,T,分为,2,个子集：,=, ,=, , ,中分类结果为“,+,”,的实例数为,1,，分类结果为“,”,的实例数为,2,，可得：,的实例平均信息量为：,- ( log,2,1/3 + 2log,2,2/3 ) / 3 = 0.918 (bit),中分类结果为“,+,”,的实例数为,2,，分类结果为“,”,的实例数为,3,，可得：,的实例平均信息量为：,- ( 2log,2,2/5 + 3log,2,3/5 ) / 5 = 0.971 (bit),故而，,若以属性,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),同理可得：,GI(T, hair)=0.5 (bit),GI(T, eyes)=0.347 (bit),由于,GI(T, hair),最大,，故选取,第,2,个属性,hair,作为检测属性。,划分后，从属性表中删去属性,hair,，,更新属性表为：,AttrList,= height, eyes ,至此，生成的决策树如下图所示：,=, , ,=,=, ,hair,blond,dark,red,2,）由于 中的实例分类结果仍有两种，故还需划分,在 中，分类结果为“,+,”,的实例数为,2,，分类结果为“,”,的实例数也为,2,，可得,划分前,的实例平均信息量为：,I( ) = -(2log,2,2/4+2log,2,2/4)/4=1 (bit),若选,新属性表,的第,1,个属性,height,为检测属性，其值域,ValueType(height,)=short, tall,将 划分为,2,个子集：,= ,=, ,计算实例平均信息量：,I( )=-(log,2,1/2+log,2,1/2)/2=1 (bit),I( )=-(log,2,1/2+log,2,1/2)/2=1 (bit),I( , height),= (2I( ) + 2I( ) / 4,=1 (bit),GI( , height),= I( ),I( , height),=0,显然属性,eyes,对实例集 的信息量,GI( , eyes) = 1,，因此选择属性,eyes,作为检测属性。,最后生成的决策树如下图所示：,hair,blond,dark,red,+,eyes,brown,blue,+,作业,P. 294,7.3,7.4,7.5,（,2,） 第一次划分过程,