第三章规则学习算法 1.基本概念: 定义1(例子).设E=D1XD2×…×Dn是n维有穷向量空间, 其中D是有穷离散符号集。E中的元素e=(V1,V2…,Vn)简 记为叫做例子。其中j∈D 例如:对表2.1 D1={高,矮};D2={淡黄,红,黑};D3={兰,褐} E=D1×D,×D 例子e=(矮,淡黄,兰) 定义2。选择子是形为x=A的关系语句,其中x为第j个属性, A≤D;公式(或项)是选择子的合取式,即⌒[x=Aj, 其中J∈{1,…,n};规则是公式的析取式,即L其中Li为 公式
第三章 规则学习算法 1. 基本概念： 定义1 （例子）. 设E=D1×D2 ×… ×Dn 是n维有穷向量空间， 其中 Dj是有穷离散符号集。E中的元素e=(V1 ,V2 , …,Vn)简 记为叫做例子。其中Vj∈Dj。 例如：对表2.1 D1={高，矮}；D2={淡黄，红，黑}；D3={兰，褐} E=D1 × D2 × D3 例子 e=(矮，淡黄，兰） 定义2。选择子是形为[xj=Aj ]的关系语句，其中xj为第j个属性， Aj Dj; 公式（或项）是选择子的合取式，即 [xj=Aj], 其中 J {1, …,n}; 规则是公式的析取式，即 ，其中Li为 公式。 jJ Li l i=1
个例子e=V1,…Vn>满足选择子=A当且仅当Ⅴ是Aj的 元素,即V∈Aj;e满足一个公式当且仅当它满足该公式的 每一个选择子;e满足一条规则当且仅当e满足该规则的至 少一个公式。 例子满足选择子(公式、规则)也称做选择子(公式、规 则)覆盖该例子。 例如:例子e矮,淡黄,兰>满足选择子[头发=淡黄∨红 色]和[眼睛=蓝色];满足公式[头发=淡黄∨红色][眼睛= 蓝色]。 定义3:普化( generalize):减少规则的约束,使其覆盖更多的 训练例子叫普化
一个例子e=满足选择子[xj=Aj]当且仅当Vj是Aj的 元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的 每一个选择子；e满足一条规则当且仅当e满足该规则的至 少一个公式。 例子满足选择子（公式、规则）也称做选择子（公式、规 则）覆盖该例子。 例如： 例子e= 满足选择子[头发=淡黄∨红 色]和 [眼睛=蓝色] ；满足公式[头发=淡黄∨红色] [眼睛= 蓝色] 。 定义3：普化(generalize) :减少规则的约束，使其覆盖更多的 训练例子叫普化
定义4:特化( (specialize):增加规则的约束,使其覆盖训练例 子较少叫特化。 定义5:一致:只覆盖正例不覆盖反例的规则被称为是一致 的 定义6:完备:覆盖所有正例的规则被称为是完备的
定义4：特化(specialize) : 增加规则的约束，使其覆盖训练例 子较少叫特化。 定义5：一致：只覆盖正例不覆盖反例的规则被称为是一致 的。 定义6：完备：覆盖所有正例的规则被称为是完备的
2.GS算法: GS算法 输入:例子集; 输出:规则; 原则:(a)从所有属性中选出覆盖正例最多的属性; (b)在覆盖正例数相同的情况下,优先选择只覆盖正 例不覆盖反例的属性值; 设PE,NE是正例,反例的集合。PENE是临时正,反例集。 CPX表示公式,F表示规则(概念描述) (1)F←true 2)PE←PE,NE←NE,CPX←true; 3)按上述(a)(b)两规则选出一个属性值V。,设V。为第j个属 性的取值,建立选择子[Xj=V]并加入公式中, CPX←CPX∧[Xj=V0 (4)如果X=V覆盖NE中的反例,转(5) 否则F← FVCPX,转(6)
2. GS算法： GS算法 输入： 例子集； 输出： 规则； 原则： （a) 从所有属性中选出覆盖正例最多的属性； (b) 在覆盖正例数相同的情况下，优先选择只覆盖正 例不覆盖反例的属性值； 设PE,NE是正例，反例的集合。 PE’,NE’是临时正，反例集。 CPX表示公式，F表示规则（概念描述）。 (1) F←true; (2) PE’ ←PE, NE’ ←NE, CPX←true; (3) 按上述(a) (b)两规则选出一个属性值V 0 , 设V 0 为第j0个属 性的取值，建立选择子[Xj0=V0 ]并加入公式中， CPX←CPX∧ [Xj0=V0 ] (4) 如果[Xj0=V0 ]覆盖NE’中的反例，转(5); 否则 F←F∨CPX, 转(6);
(5)重新构造PE和NE,PE含有原来PE中被Xj0V0]覆盖的例子, NE'含有原来NE中被Ⅹj0=V0覆盖的例子,转(3) (6) PE+PEPE,如果PE=,停止,否则转2 GS算法举例: 例子集见表23 学习结果: ESR-normallausculationbublelike] 肺炎 TX-ray=spotJESR=normal 3AQ算法: l)普化( generalize 2)特化( specialize 3)一致 4)完备
(5) 重新构造PE’和NE’, PE’含有原来PE’中被[Xj0=V0]覆盖的例子， NE’含有原来NE’中被[Xj0=V0]覆盖的例子，转（3）； (6) PE←PE\PE’,如果PE= ,停止，否则转(2); GS算法举例： 例子集见表2.3 学习结果： [ESR=normal][Ausculation=bublelike] [X-ray=spot][ESR=normal] 3.AQ算法： 1) 普化(generalize) : 2) 特化(specialize) : 3) 一致 4) 完备 肺炎
表2.3肺炎与肺结核两组病历 no Fever CoughX-ray ESR Ausculat high heavy Flack Normal Bubblelike 肺炎|2 mediu heavyFlack Normal Bubblelike 345 slight Spot Normal Dry-peep high mediu Flack NormalBubblelike mediu slight Flack Normal Bubblelike absent slight Strip Normal 肺结2hig gh heavy Hole Fast Dry-peep 核 345 slight Strip Normal Normal absent slight Spot Fast Dry-peep low mediu flack fasts Normal
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(eNEG,m),其中元素不多于m个。 ③在得到的star中,根据设定的优化标准LEF找出一个最优的 描述D。 ④若描述D完全覆盖集合Pos则转⑥ ⑤否则,减少Pos的元素使其只包含不被D覆盖的事件。从步 骤①开始重复整个过程。 ⑥生成所有描述D的析取,它是一个完备且一致的概念描述
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中的选择符进行完备性和一致性检查从p中取出完备 致的描述放入 SOLUTION表中,若 SOLUTION表的大小大于参数 #SOL,则算法停止一致但不完备的描述从ps中取出放入表 CONSISTENT中,若 CONSISTENT表的大小大于参数#COS,则转 ⑤ ④对每个表达式进行特殊化处理,所有得到的表达式根据优化标 准排列仅保留m个最优的重复步骤⑧,直到 CONSISTENT表 中包含#CONS个表达式或该过程分配的时间用完为止 ⑥得到的一般化描述按优先标准排序保留m个最优的表达式构 成约束Star( eNEG,m) 举例 例子集:表23 #Sol=2
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
#CONS=2 M=2 优化标准:正例数/反例数 Fifel: [Fever=high][Cough=heavy][X-ray=flackJESR=normal] AUsculation=bubblelike] 第一轮 (进入 Induce算法) PS 5 Fever=high o[Cough=heavy ② TX-ray=fack] ③ESR= normal] OLAusculation=bubblelike] 保留m个表达式 [ ausculation- bubblelike]一致的表达式放入 CONSISTENT中 LX-ray=flack
#CONS=2 M=2 优化标准: 正例数/反例数 种子 : [Fever=high][Cough=heavy][X-ray=flack][ESR=normal] [Ausculation=bubblelike] 第一轮: （进入Induce算法） Ps: [Fever=high] [Cough=heavy] [X-ray=flack] [ESR=normal] [Ausculation=bubblelike] 保留m个表达式 [Ausculation=bubblelike] 一致的表达式,放入CONSISTENT中 [X-ray=flack] + 1 e
特化 IX-ray-flackJESr=normal] IX-ray=flack][Fever=high 上面3个表达式均为一致的放入 CONSISTENT中按优先标准排 序并保留m(2)个表达式 AUsculation=bubblelike LX-ray==normal (出 iNduce算法) 选出一个最优的作为D D: AUsculation=bubblelike 将D覆盖的正例去掉.去掉1e2,e4,es第一轮结束. 第二轮 种子e3:[ Fever=low cOugh=Slight x-ray=spot]Esr-normal AUsculation=dry-peep]
特化; [x-ray=flack][ESR=normal] [X-ray=flack] [x-ray=flack][Cough=heavy] [x-ray=flack][Fever=high] 上面3个表达式均为一致的,放入CONSISTENT中,按优先标准排 序,并保留m(2)个表达式. [Ausculation=bubblelike] [x-ray=flack][ESR=normal] （出Induce算法） 选出一个最优的作为D D: [Ausculation=bubblelike] 将D覆盖的正例去掉. 去掉 第一轮结束. 第二轮: 种子 : [Fever=low][Cough=slight][x-ray=spot][ESR=normal] [Ausculation=dry-peep] + + + + 1 2 4 5 e ,e ,e ,e + 3 e