1、第三章規(guī)則學(xué)習(xí)算法1. 基本概念：定義1 （例子）. 設(shè)E=D1D2 Dn 是n維有窮向量空間， 其中 Dj是有窮離散符號(hào)集。E中的元素e=(V1,V2, ,Vn)簡(jiǎn)記為叫做例子。其中VjDj。例如：對(duì)表2.1D1=高，矮；D2=淡黃，紅，黑；D3=蘭，褐E=D1 D2 D3例子 e=(矮，淡黃，蘭）定義2。選擇子是形為xj=Aj的關(guān)系語句，其中xj為第j個(gè)屬性，Aj Dj; 公式（或項(xiàng)）是選擇子的合取式，即ljJxj=Aj,其中 J 1, ,n; 規(guī)則是公式的析取式，即公式。i =1Li，其中Li為一個(gè)例子e=滿足選擇子xj=Aj當(dāng)且僅當(dāng)Vj是Aj的元素，即Vj Aj; e滿足一個(gè)公式當(dāng)且僅

2、當(dāng)它滿足該公式的每一個(gè)選擇子；e滿足一條規(guī)則當(dāng)且僅當(dāng)e滿足該規(guī)則的至少一個(gè)公式。例子滿足選擇子（公式、規(guī)則）也稱做選擇子（公式、規(guī)則）覆蓋該例子。例如： 例子e= 滿足選擇子頭發(fā)=淡黃紅色和 眼睛=藍(lán)色；滿足公式頭發(fā)=淡黃紅色 眼睛= 藍(lán)色 。定義3：普化(generalize) :減少規(guī)則的約束，使其覆蓋更多的訓(xùn)練例子叫普化。定義4：特化(specialize) : 增加規(guī)則的約束，使其覆蓋訓(xùn)練例子較少叫特化。定義5：一致：只覆蓋正例不覆蓋反例的規(guī)則被稱為是一致的。定義6：完備：覆蓋所有正例的規(guī)則被稱為是完備的。2. GS算法： GS算法輸入： 例子集； 輸出： 規(guī)則；原則： （a) 從所有

3、屬性中選出覆蓋正例最多的屬性；(b) 在覆蓋正例數(shù)相同的情況下，優(yōu)先選擇只覆蓋正例不覆蓋反例的屬性值；設(shè)PE,NE是正例，反例的集合。 PE,NE是臨時(shí)正，反例集。CPX表示公式，F(xiàn)表示規(guī)則（概念描述）。(1) Ftrue;(2) PE PE, NE NE, CPXtrue;(3) 按上述(a) (b)兩規(guī)則選出一個(gè)屬性值V 0 , 設(shè)V 0 為第j0個(gè)屬性的取值，建立選擇子Xj0=V0并加入公式中， CPXCPX Xj0=V0(4) 如果Xj0=V0覆蓋NE中的反例，轉(zhuǎn)(5);否則 FFCPX, 轉(zhuǎn)(6);f(5) 重新構(gòu)造PE和NE, PE含有原來PE中被Xj0=V0覆蓋的例子NE含有原來

4、NE中被Xj0=V0覆蓋的例子，轉(zhuǎn)（3）；(6) PEPEPE,如果PE=,停止，否則轉(zhuǎn)(2);GS算法舉例：例子集見表2.3 學(xué)習(xí)結(jié)果：ESR=normalAusculation=bublelike X-ray=spotESR=normal3. AQ算法：1) 普化(generalize) :2) 特化(specialize) :3) 一致4) 完備肺炎表2.3 肺炎與肺結(jié)核兩組病歷noFeverCoughX-rayESRAusculat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike3lowslightSp

5、otNormalDry-peep4highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike1absentslightStripNormalNormal肺結(jié)2highheavyHoleFastDry-peep核3lowslightStripNormalNormal4absentslightSpotFastDry-peep5lowmediuflackfastsNormalAQ算法：輸入：例子集、參數(shù)#SOL、#CONS、Star的容量m、優(yōu)化標(biāo)準(zhǔn)；輸出：規(guī)則；1）Pos和NEG分別代表某概念的正例和反例的 集合 從Pos中隨機(jī)地

6、選擇一 生成e相對(duì)于反例集NEG的一個(gè)約束Star(reduced star), G(e|NEG,m) , 其中元素不多于m個(gè)。 在得到的star中，根據(jù)設(shè)定的優(yōu)化標(biāo)準(zhǔn)LEF找出一個(gè)最優(yōu)的描述D。 若描述D完全覆蓋集合Pos,則轉(zhuǎn) 否則，減少Pos的元素使其只包含不被D覆蓋的。從步驟開始重復(fù)整個(gè)過程。 生成所有描述D的析取，它是一個(gè)完備且一致的概念描述。2) Star生成: Induce方法je的各個(gè)選擇符被放入PS(partial star)中,將ps中的元素按照各種標(biāo)準(zhǔn)排序.k在ps中保留最優(yōu)的m個(gè)選擇符.l對(duì)ps中的選擇符進(jìn)行完備性和一致性檢查,從ps中取出完備一致的描述放入SOLUTI

7、ON表中,若SOLUTION表的大小大于參數(shù)#SOL,則算法停止.一致但不完備的描述從ps中取出放入表CONSISTENT中,若CONSISTENT表的大小大于參數(shù)#COS,則轉(zhuǎn)n;m對(duì)每個(gè)表達(dá)式進(jìn)行特殊化處理,所有得到的表達(dá)式根據(jù)優(yōu)化標(biāo)準(zhǔn)排列,僅保留m個(gè)最優(yōu)的.重復(fù)步驟l, m直到CONSISTENT表中包含#CONS個(gè)表達(dá)式或該過程分配的時(shí)間用完為止.n得到的一般化描述按優(yōu)先標(biāo)準(zhǔn)排序,保留m個(gè)最優(yōu)的表達(dá)式構(gòu)成約束Star(e|NEG,m).舉例:例子集: 表2.3 #SOL=2#CONS=2 M=2優(yōu)化標(biāo)準(zhǔn): 正例數(shù)/反例數(shù)1種子e+:Fever=highCough=heavyX-ray=

8、flackESR=normalAusculation=bubblelike第一輪:（進(jìn)入Induce算法）Ps:n Fever=highmCough=heavykX-ray=flacklESR=normaljAusculation=bubblelike保留m個(gè)表達(dá)式Ausculation=bubblelike一致的表達(dá)式,放入CONSISTENT中X-ray=flack特化;x-ray=flackESR=normalX-ray=flackx-ray=flackCough=heavyx-ray=flackFever=high上面3個(gè)表達(dá)式均為一致的,放入CONSISTENT中,按優(yōu)先標(biāo)準(zhǔn)排序,并

9、保留m(2)個(gè)表達(dá)式.Ausculation=bubblelikex-ray=flackESR=normal（出Induce算法）選出一個(gè)最優(yōu)的作為DD: Ausculation=bubblelikee+ , e+ , e+ , e+將D覆蓋的正例去掉. 去掉1245第一輪結(jié)束.第二輪:e+種子3: Fever=lowCough=slightx-ray=spotESR=normalAusculation=dry-peepPs:mfever=lownCough=slightjx-ray=spotkESR=normallAusculation=dry-peep保留m(2)個(gè)表達(dá)式: ESR=nor

10、malx-ray=spot特殊化:ESR=normal fever=lowESR=normalESR=normal Cough=slightESR=normal Ausculation=dry-peepx-ray=spot ESR=normalx-ray=spot Ausculation=dry-peep x-ray=spotx-ray=spot fever=low x-ray=spot Cough=slight上面有3個(gè)表達(dá)式是一致的,放入CONSISTENT表中,按優(yōu)先標(biāo)準(zhǔn)排序,并保留m(2)個(gè)表達(dá)式x-ray=spot ESR=normal x-ray=spot fever=low 選出

11、一個(gè)最優(yōu)的作為DD: x-ray=spot ESR=normale將D覆蓋的正例從pos中去掉,去掉+3,pos空.生成規(guī)則:Ausculation=bubblelike x-ray=spot ESR=normal肺炎算法結(jié)束.參考文獻(xiàn):1. Machine learning: An Artificial Intelligence Approach Edited byR.S. MichalskiP39-135.2. 歸納學(xué)習(xí)-算法,理論,應(yīng)用.洪家榮著 P4-11, P30-333. 機(jī)器學(xué)習(xí):實(shí)現(xiàn)人工智能的途徑. 科學(xué). P.23-77. FCV算法PENE序號(hào)X1X2X3X4序號(hào)X1X2X3X43100012000411112221052001700106121080100901111