第三章规则学习算法 1.基本概念: 定义1(例子).设E=D1XD2×…×Dn是n维有穷向量空间, 其中D是有穷离散符号集。E中的元素e=(V1,V2…,Vn)简 记为<V>叫做例子。其中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>叫做例子。其中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=<V1 , …Vn>满足选择子[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) 完备 肺炎