演示文稿(四次课).pptVIP

* 第三章 规则学习算法 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为公式。 一个例子e=V1, …Vn满足选择子[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表示规则（概念描述）。 F←true; PE’ ←PE, NE’ ←NE, CPX←true; 按上述(a) (b)两规则选出一个属性值V 0 , 设V 0 为第j0个属性的取值，建立选择子[Xj0=V0]并加入公式中，CPX←CPX∧ [Xj0=V0] 如果[Xj0=V0]覆盖NE’中的反例，转(5); 否则 F←F∨CPX, 转(6); (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算法： 普化(generalize) : 特化(specialize) : 一致 完备 肺炎 Normal fasts flack mediu low 5 Dry-peep Fast Spot slight absent 4 Normal Normal Strip slight low 3 核 Dry-peep Fast Hole heavy high 2 肺结 Normal Normal Strip slight absent 1 Bubblelike Normal Flack slight mediu 5 Bubblelike Normal Flack mediu high 4 Dry-peep Normal Spot slight low 3 Bubblelike Normal Flack heavy mediu 2 肺炎 Bubblelike Normal Flack heavy high 1 Ausculat. ESR X-ray Cough Fever no 表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中的元素