单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 规则学习算法,1.基本概念：,定义1（例子）.设,E=D,1,D,2,Dn,是,n,维有穷向量空间，其中,Dj,是有穷离散符号集E,中的元素,e=(V,1,V,2,Vn,),Vj,叫做例子其中,Vj,Dj,例如：对表2.1,D,1,=,高，矮；,D,2,=,淡黄，红，黑；,D,3,=,兰，褐,E=D,1,D,2,D,3,例子,e=(,矮，淡黄，兰）,定义2选择子是形为,x,j,=,A,j,的关系语句，其中,x,j,为第,j,个属性，,Aj,Dj,;,公式（或项）是选择子的合取式，即 ,xj,=,Aj,其中,J,1,n;,规则是公式的析取式，即 ，其中,Li,为公式一个例子e=满足选择子xj=Aj当且仅当Vj是Aj的元素，即Vj,Aj;e满足一个公式当且仅当它满足该公式的每一个选择子；e满足一条规则当且仅当e满足该规则的至少一个公式例子满足选择子（公式、规则）也称做选择子（公式、规则）覆盖该例子例如：例子e=满足选择子头发=淡黄红色和 眼睛=蓝色 ；满足公式头发=淡黄红色 眼睛=蓝色定义3：普化(generalize):减少规则的约束，使其覆盖更多的训练例子叫普化。
定义4：特化(specialize):增加规则的约束，使其覆盖训练例子较少叫特化定义5：一致：只覆盖正例不覆盖反例的规则被称为是一致的定义6：完备：覆盖所有正例的规则被称为是完备的2.GS算法：,GS算法,输入：例子集；,输出：规则；,原则：（a)从所有属性中选出覆盖正例最多的属性；,(b)在覆盖正例数相同的情况下，优先选择只覆盖正例不覆盖反例的属性值；,设PE,NE是正例，反例的集合PE,NE是临时正，反例集CPX表示公式，F表示规则（概念描述）Ftrue;,PE PE,NE NE,CPXtrue;,按上述(,a)(b),两规则选出一个属性值,V,0,设,V,0,为第,j,0,个属性的取值，建立选择子,Xj,0,=V,0,并加入公式中，,CPXCPX Xj,0,=V,0,如果,Xj,0,=V,0,覆盖,NE,中的反例，转(5);,否则,FFCPX,转(6);,no,Fever,Cough,X-ray,ESR,Ausculat.,1,high,heavy,Flack,Normal,Bubblelike,肺炎,2,mediu,heavy,Flack,Normal,Bubblelike,3,low,slight,Spot,Normal,Dry-peep,4,high,mediu,Flack,Normal,Bubblelike,5,mediu,slight,Flack,Normal,Bubblelike,1,absent,slight,Strip,Normal,Normal,肺结,2,high,heavy,Hole,Fast,Dry-peep,核,3,low,slight,Strip,Normal,Normal,4,absent,slight,Spot,Fast,Dry-peep,5,low,mediu,flack,fasts,Normal,表2.3 肺炎与肺结核两组病历,AQ算法：,输入：例子集、参数#SOL、#CONS、Star的容量m、优化标准；,输出：规则；,1）Pos和NEG分别代表某概念的正例和反例的事件集合,从Pos中随机地选择一事件,生成事件e相对于反例集NEG的一个约束Star(reduced star),G(e|NEG,m),其中元素不多于m个。
在得到的star中，根据设定的优化标准LEF找出一个最优的描述D若描述D完全覆盖集合Pos,则转,否则，减少Pos的元素使其只包含不被D覆盖的事件从步骤开始重复整个过程生成所有描述D的析取，它是一个完备且一致的概念描述2)Star生成:Induce方法,事件e的各个选择符被放入PS(partial star)中,将ps中的元素按照各种标准排序.,在ps中保留最优的m个选择符.,对ps中的选择符进行完备性和一致性检查,从ps中取出完备一致的描述放入SOLUTION表中,若SOLUTION表的大小大于参数#SOL,则算法停止.一致但不完备的描述从ps中取出放入表CONSISTENT中,若CONSISTENT表的大小大于参数#COS,则转;,对每个表达式进行特殊化处理,所有得到的表达式根据优化标准排列,仅保留m个最优的.重复步骤,直到CONSISTENT表中包含#CONS个表达式或该过程分配的时间用完为止.,得到的一般化描述按优先标准排序,保留m个最优的表达式构成约束Star(e|NEG,m).,举例:,例子集:表2.3,#SOL=2,特化;,x-ray=flackESR=normal ,X-ray=flack x-ray=flackCough=heavy ,x-ray=flackFever=high ,上面3个表达式均为一致的,放入CONSISTENT中,按优先标准排序,并保留m(2)个表达式.,Ausculation=bubblelike,x-ray=flackESR=normal,（出Induce算法）,选出一个最优的作为D,D:Ausculation=bubblelike,将D覆盖的正例去掉.去掉 第一轮结束.,第二轮:,种子 :Fever=lowCough=slightx-ray=spotESR=normal,Ausculation=dry-peep,Ps:,fever=low ,Cough=slight ,x-ray=spot ,ESR=normal ,Ausculation=dry-peep ,保留m(2)个表达式:,ESR=normal,x-ray=spot,特殊化:,ESR=normal fever=low ,ESR=normal ESR=normal Cough=slight ,ESR=normal Ausculation=dry-peep ,x-ray=spot ESR=normal ,x-ray=spot Ausculation=dry-peep ,x-ray=spot x-ray=spot fever=low ,x-ray=spot Cough=slight ,3.机器学习:实现人工智能的途径.科学出版社.P.23-77.,3.机器学习:实现人工智能的途径.科学出版社.P.23-77.,FCV算法,表2.4正例集PE和反例集NE,PE,NE,序号,X,1,X,2,X,3,X,4,序号,X,1,X,2,X,3,X,4,3,1,0,0,0,1,2,0,0,0,4,1,1,1,1,2,2,2,1,0,5,2,0,0,1,7,0,0,1,0,6,1,2,1,0,8,0,1,0,0,9,0,1,1,1,13,0,0,0,1,10,1,1,1,1,14,0,2,1,1,11,2,2,1,1,12,2,0,0,1,序号,X1,。