規(guī)則學習算法

規(guī)則學習算法第一頁，共十五頁，編輯于2023年，星期五一個例子e=<V1,…Vn>滿足選擇子[xj=Aj]當且僅當Vj是Aj的元素，即VjAj;e滿足一個公式當且僅當它滿足該公式的每一個選擇子；e滿足一條規(guī)則當且僅當e滿足該規(guī)則的至少一個公式。例子滿足選擇子（公式、規(guī)則）也稱做選擇子（公式、規(guī)則）覆蓋該例子。例如：例子e=<矮，淡黃，蘭>滿足選擇子[頭發(fā)=淡黃∨紅色]和[眼睛=藍色]；滿足公式[頭發(fā)=淡黃∨紅色][眼睛=藍色]。定義3：普化(generalize):減少規(guī)則的約束，使其覆蓋更多的訓練例子叫普化。第二頁，共十五頁，編輯于2023年，星期五定義4：特化(specialize):增加規(guī)則的約束，使其覆蓋訓練例子較少叫特化。定義5：一致：只覆蓋正例不覆蓋反例的規(guī)則被稱為是一致的。定義6：完備：覆蓋所有正例的規(guī)則被稱為是完備的。第三頁，共十五頁，編輯于2023年，星期五2.GS算法：GS算法輸入：例子集；輸出：規(guī)則；原則：（a)從所有屬性中選出覆蓋正例最多的屬性；

(b)在覆蓋正例數(shù)相同的情況下，優(yōu)先選擇只覆蓋正例不覆蓋反例的屬性值；設PE,NE是正例，反例的集合。PE’,NE’是臨時正，反例集。CPX表示公式，F(xiàn)表示規(guī)則（概念描述）。F←true;PE’←PE,NE’←NE,CPX←true;按上述(a)(b)兩規(guī)則選出一個屬性值V0,設V0

為第j0個屬性的取值，建立選擇子[Xj0=V0]并加入公式中，CPX←CPX∧[Xj0=V0]如果[Xj0=V0]覆蓋NE’中的反例，轉(5);

否則F←F∨CPX,轉(6);第四頁，共十五頁，編輯于2023年，星期五(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):一致完備肺炎第五頁，共十五頁，編輯于2023年，星期五noFeverCoughX-rayESRAusculat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike3lowslightSpotNormalDry-peep4highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike1absentslightStripNormalNormal肺結2highheavyHoleFastDry-peep核3lowslightStripNormalNormal4absentslightSpotFastDry-peep5lowmediuflackfastsNormal表2..3肺炎與肺結核兩組病歷第六頁，共十五頁，編輯于2023年，星期五AQ算法：輸入：例子集、參數(shù)#SOL、#CONS、Star的容量m、優(yōu)化標準；輸出：規(guī)則；1）Pos和NEG分別代表某概念的正例和反例的事件集合①從Pos中隨機地選擇一事件②生成事件e相對于反例集NEG的一個約束Star(reducedstar),G(e|NEG,m),其中元素不多于m個。③在得到的star中，根據(jù)設定的優(yōu)化標準LEF找出一個最優(yōu)的描述D。④若描述D完全覆蓋集合Pos,則轉⑥⑤否則，減少Pos的元素使其只包含不被D覆蓋的事件。從步驟①開始重復整個過程。⑥生成所有描述D的析取，它是一個完備且一致的概念描述。第七頁，共十五頁，編輯于2023年，星期五2)Star生成:Induce方法事件e的各個選擇符被放入PS(partialstar)中,將ps中的元素按照各種標準排序.在ps中保留最優(yōu)的m個選擇符.對ps中的選擇符進行完備性和一致性檢查,從ps中取出完備一致的描述放入SOLUTION表中,若SOLUTION表的大小大于參數(shù)#SOL,則算法停止.一致但不完備的描述從ps中取出放入表CONSISTENT中,若CONSISTENT表的大小大于參數(shù)#COS,則轉;對每個表達式進行特殊化處理,所有得到的表達式根據(jù)優(yōu)化標準排列,僅保留m個最優(yōu)的.重復步驟,直到CONSISTENT表中包含#CONS個表達式或該過程分配的時間用完為止.得到的一般化描述按優(yōu)先標準排序,保留m個最優(yōu)的表達式構成約束Star(e|NEG,m).舉例:例子集:表2.3#SOL=2第八頁，共十五頁，編輯于2023年，星期五#CONS=2M=2優(yōu)化標準:正例數(shù)/反例數(shù)種子:[Fever=high][Cough=heavy][X-ray=flack][ESR=normal][Ausculation=bubblelike]第一輪:（進入Induce算法）Ps:[Fever=high]<2,1>[Cough=heavy]<2,1>[X-ray=flack]<4,1>[ESR=normal]<5,2>[Ausculation=bubblelike]<4,0>保留m個表達式[Ausculation=bubblelike]一致的表達式,放入CONSISTENT中[X-ray=flack]第九頁，共十五頁，編輯于2023年，星期五特化;[x-ray=flack][ESR=normal]<4,0>[X-ray=flack][x-ray=flack][Cough=heavy]<2,0>[x-ray=flack][Fever=high]<2,0>上面3個表達式均為一致的,放入CONSISTENT中,按優(yōu)先標準排序,并保留m(2)個表達式.[Ausculation=bubblelike][x-ray=flack][ESR=normal]（出Induce算法）選出一個最優(yōu)的作為DD:[Ausculation=bubblelike]將D覆蓋的正例去掉.去掉第一輪結束.第二輪:種子:[Fever=low][Cough=slight][x-ray=spot][ESR=normal][Ausculation=dry-peep]第十頁，共十五頁，編輯于2023年，星期五Ps:[fever=low]<1,2>[Cough=slight]<1,3>[x-ray=spot]<1,1>[ESR=normal]<1,2>[Ausculation=dry-peep]<1,2>保留m(2)個表達式:[ESR=normal][x-ray=spot]特殊化:[ESR=normal][fever=low]<1,1>[ESR=normal][ESR=normal][Cough=slight]<1,2>[ESR=normal][Ausculation=dry-peep]<1,0>

[x-ray=spot][ESR=normal]<1,0>[x-ray=spot][Ausculation=dry-peep]<1,1>[x-ray=spot][x-ray=spot][fever=low]<1,0>[x-ray=spot][Cough=slight]<1,1>第十一頁，共十五頁，編輯于2023年，星期五上面有3個表達式是一致的,放入CONSISTENT表中,按優(yōu)先標準排序,并保留m(2)個表達式[x-ray=spot][ESR=normal][x-ray=spot][fever=low]選出一個最優(yōu)的作為DD:[x-ray=spot][ESR=normal]將D覆蓋的正例從pos中去掉,去掉,pos空.生成規(guī)則:[Ausculation=bubblelike][x-ray=spot][ESR=normal]肺炎算法結束.參考文獻:Machinelearning:AnArtificialIntelligenceApproachEditedbyR.S.MichalskiP39-135.歸納學習-算法,理論,應用.洪家榮著P4-11,P30-33第十二頁，共十五頁，編輯于2023年，星期五3.機器學習:實現(xiàn)人工智能的途徑.科學出版社.P.23-77.3.機器學習:實現(xiàn)人工智能的途徑.科學出版社.P.23-77.FCV算法表2.4正例集PE和反例集NEPENE序號X1X2X3X4序號X1X2X3X4310001200041111222105200170010612108010090111130001101111140211112211122001第十三頁，共十五頁，編輯于2023年，星期五表2.5PE和NE的頻率矩陣F