基于規(guī)則分類

1、計(jì)算機(jī)應(yīng)用技術(shù)目錄基于規(guī)則的分類法是使用一組“IFTHEN”規(guī)則來(lái)對(duì)記錄進(jìn)行分類的技術(shù)。 一個(gè)IF-THEN規(guī)則是一個(gè)如下形式的表達(dá)式：IF 條件 THEN 結(jié)論。規(guī)則R1是一個(gè)例子 R1：IF age=youth AND student=yes THEN buys_computer=yes 規(guī)則的“IF”部分（或左部）稱為規(guī)則前件或前提?！癟HEN”部分（或右部）是規(guī)則的結(jié)論或后件。規(guī)則前件，它是屬性測(cè)試的合?。?IF 其中（Aj,Vj）是屬性-值對(duì)，op是比較運(yùn)算符，取自集合（例如，age=youth 和 student=yes）。規(guī)則的結(jié)論包含一個(gè)類預(yù)測(cè)（在這個(gè)例子中，預(yù)測(cè)顧客是否購(gòu)買(mǎi)計(jì)

2、算機(jī)）。R1也可以寫(xiě)作 基本概念1:()()(_)Rageyouthstudentyesbuys computeryes1 11 11 1iA op vA op vA op v( , , , , , ) 基本概念 對(duì)于給定的元組，如果規(guī)則前件中的條件（即所有屬性測(cè)試）都成立，則我們說(shuō)規(guī)則前件被滿足，并且規(guī)則覆蓋了該元組。 規(guī)則R可以用它的覆蓋率和準(zhǔn)確率來(lái)評(píng)估。給定類標(biāo)記的數(shù)據(jù)集D中的一個(gè)元組X，設(shè) ncovers 為規(guī)則R覆蓋的元組， ncorrect為R正確分類的元組，|D|是D中的元組數(shù)?？梢詫的覆蓋率和準(zhǔn)確率定義為也就是說(shuō)，規(guī)則的覆蓋率是規(guī)則覆蓋（即其屬性值使得規(guī)則的前件為真）的元組的

3、百分比。對(duì)于規(guī)則的準(zhǔn)確率，考察在它覆蓋的元組中，可以被規(guī)則正確分類的元組所占的百分比。( )correctcoversaccuracnny R ( )co|v|coversneRrageD規(guī)則覆蓋率和準(zhǔn)確率舉例序號(hào)序號(hào)名字名字體溫體溫表皮覆蓋表皮覆蓋胎生胎生水生動(dòng)物水生動(dòng)物飛行動(dòng)物飛行動(dòng)物有腿有腿冬眠冬眠類標(biāo)號(hào)類標(biāo)號(hào)1人類恒溫毛發(fā)是否否是否哺乳類2蟒蛇冷血鱗片否否否否是爬行類3鮭魚(yú)冷血鱗片否是否否否魚(yú)類4鯨恒溫毛發(fā)是是否否否哺乳類5青蛙冷血無(wú)否半否是是兩棲類6巨蜥冷血鱗片否否否是否爬行類7蝙蝠恒溫毛發(fā)是否是是是哺乳類8鴿子恒溫羽毛否否是是否鳥(niǎo)類9貓恒溫軟毛是否否是否哺乳類10虹鳉冷血鱗片是是否

4、否否魚(yú)類11美洲鱷冷血鱗片否半否是否爬行類12企鵝恒溫羽毛否半否是否鳥(niǎo)類13豪豬恒溫剛毛是否否是是哺乳類 14鰻鱺冷血鱗片否是否否否魚(yú)類15蠑螈冷血無(wú)否半否是是兩棲類規(guī)則覆蓋率和準(zhǔn)確率舉例（續(xù)）規(guī)則：（胎生=是）（體溫=恒溫）哺乳類 Coverage= ncovers /|D|=5/15*100%=33% Accuracy= ncorrect / ncovers =5/5*100%=100%基于規(guī)則的分類器的特征Mutually exclusive rules (Mutually exclusive rules (互斥規(guī)則互斥規(guī)則) ) Classifier contains mutually

5、 exclusive rules if the rules are independent of each other 如果規(guī)則彼此獨(dú)立，則分類器包含互斥規(guī)則 Every record is covered by at most one rule 每個(gè)紀(jì)錄都由最多一個(gè)規(guī)則所覆蓋Exhaustive rules（窮舉規(guī)則） Classifier has exhaustive coverage if it accounts for every possible combination of attribute values 如果分類器考慮到屬性值的每一個(gè)可能的組合，都將進(jìn)行詳盡的覆蓋 Each r

6、ecord is covered by at least one rule 每條記錄至少包含一條規(guī)則Some algorithms not always achieve these two propertiesSome algorithms not always achieve these two properties研究背景和意義研究背景 數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。數(shù)據(jù)挖掘廣泛應(yīng)用于各種領(lǐng)域，比如電力系統(tǒng)的電力負(fù)荷預(yù)測(cè)、證券分析、網(wǎng)絡(luò)入侵、網(wǎng)絡(luò)信息的搜索引擎、以及生物醫(yī)學(xué)等等。當(dāng)前主流

7、的數(shù)據(jù)挖掘方法主要包括關(guān)聯(lián)規(guī)則、分類、聚類。分類是根據(jù)已知類別信息尋找數(shù)據(jù)間的分類模式；分類作為數(shù)據(jù)挖掘的重要的任務(wù)之一，將在未來(lái)的智能系統(tǒng)中發(fā)揮重要作用。目前，常用的分類主要包括基于規(guī)則的分類技術(shù)（包括決策樹(shù)分類、FOIL分類算法、關(guān)聯(lián)分類）、貝葉斯分類、K-近鄰分類、基于軟計(jì)算的分類和粗糙集等。研究背景和意義研究意義 基于規(guī)則的分類方法主要包括傳統(tǒng)的基于規(guī)則分類方法（決策樹(shù)，F(xiàn)OIL 算法）等。決策樹(shù)分類是典型的遞歸構(gòu)造，它的分類模型簡(jiǎn)潔且易于理解，但當(dāng)數(shù)據(jù)集的實(shí)例個(gè)數(shù)較多時(shí)，產(chǎn)生的決策樹(shù)非常大，需要簡(jiǎn)化決策樹(shù)。而且數(shù)據(jù)集中屬性值的遺失情況和類分布均勻性對(duì)決策樹(shù)的分類效果產(chǎn)生較大的影響，此

8、外決策樹(shù)是采用貪婪的算法，很難獲得全局的信息，決策樹(shù)上每條訓(xùn)練實(shí)例僅被一條分類規(guī)則覆蓋，這也是決策樹(shù)準(zhǔn)確率不高的一個(gè)原因。FOIL算法只用最好的屬性值產(chǎn)生的規(guī)則來(lái)構(gòu)造分類器，且一條訓(xùn)練實(shí)例只被一條規(guī)則覆蓋，因此當(dāng)數(shù)據(jù)集特別小時(shí)，可能產(chǎn)生的規(guī)則特別少，對(duì)分類準(zhǔn)確率有一定的影響；關(guān)聯(lián)規(guī)則挖掘的分類技術(shù)是目前非常流行的而且也收到了廣泛的關(guān)注，從總體上來(lái)說(shuō)，關(guān)聯(lián)分類的分類準(zhǔn)確率要顯著的高于傳統(tǒng)的基于規(guī)則分類方法，比如 FOIL 算法，決策樹(shù)等，但同時(shí)，關(guān)聯(lián)分類也存在一些不足之處，例如，規(guī)則產(chǎn)生的過(guò)程中生成太多的冗余規(guī)則，導(dǎo)致效率不高，分類模型難以理解等問(wèn)題。國(guó)內(nèi)外研究現(xiàn)狀 FOIL 算法首次由 Qui

9、nlan 在1993年提出，該算法分為正例和負(fù)例提取規(guī)則，F(xiàn)OIL 算法采用信息增益來(lái)提取最好的一個(gè)屬性值來(lái)生成規(guī)則，而且一次只生成一條規(guī)則，再生成規(guī)則之后，將被規(guī)則覆蓋的訓(xùn)練集刪除，繼續(xù)從剩余的訓(xùn)練集中尋找最好的屬性值。 該方法有效的減少了冗余的規(guī)則，然而每條訓(xùn)練集僅被一條規(guī)則覆蓋，因此在分類的時(shí)候準(zhǔn)確率不是很高，特別是當(dāng)訓(xùn)練集較小的時(shí)候。 Yin等人針對(duì)該問(wèn)題提出了新的分類算法 CPAR，在規(guī)則生成階段，CPAR 避免了一次只選擇一個(gè)最好屬性值的方法，因?yàn)橥ǔＳ泻芏鄬傩灾档男畔⒃鲆娑己芙咏詈脤傩灾档男畔⒃鲆?，因?CPAR 將接近那些信息增益接近最好屬性值的信息增益的屬性值都用來(lái)生成規(guī)則

10、，這樣就同時(shí)生成好幾條規(guī)則。在刪除訓(xùn)練集時(shí)，CPAR 也采用了權(quán)重的方法，每條訓(xùn)練實(shí)例只要被規(guī)則覆蓋一次就賦給一個(gè)權(quán)重，當(dāng)訓(xùn)練實(shí)例的權(quán)重達(dá)到一定程度時(shí)才會(huì)被刪除，因此也保證了每條訓(xùn)練實(shí)例不只被覆蓋一次。通過(guò)這樣，CPAR 取得了比 FOIL 算法較高的準(zhǔn)確率。國(guó)內(nèi)外研究現(xiàn)狀（續(xù)） 經(jīng)典的分類方法之一就是決策樹(shù)算法。決策樹(shù)采用樹(shù)的結(jié)構(gòu)來(lái)構(gòu)建分類模型，類標(biāo)簽為樹(shù)的葉子節(jié)點(diǎn)，某個(gè)屬性的分割為中間節(jié)點(diǎn)，該節(jié)點(diǎn)的分枝對(duì)應(yīng)分割屬性的一個(gè)取值。決策樹(shù)提供了一種根據(jù)不同情況(Case)采取對(duì)應(yīng)決策的方法。因此，決策樹(shù)分類模型易于理解，而且決策樹(shù)能用于預(yù)測(cè)。Quinlan 提出了最早的決策樹(shù)方法即基于信息熵的

11、ID3 算法。后來(lái)，Ouinlan 對(duì) ID3 作進(jìn)一步擴(kuò)展，提出 c4.5算法，將分類問(wèn)題從類別屬性擴(kuò)展到數(shù)值型屬性。決策樹(shù)的不足之處是：對(duì)于某些數(shù)據(jù)集， 當(dāng)數(shù)據(jù)集的實(shí)例個(gè)數(shù)較多時(shí)，產(chǎn)生的決策樹(shù)非常大，分類模型較為復(fù)雜，因此需要對(duì)決策樹(shù)進(jìn)行簡(jiǎn)化；此外，數(shù)據(jù)集中屬性值的遺失情況和類分布均勻性對(duì)決策樹(shù)的分類效果產(chǎn)生較大的影響。構(gòu)造分類規(guī)則的主要算法及流程 主要算法直接方法：利用規(guī)則歸納技術(shù)直接生成規(guī)則 e.g. FOIL,AQ,CN2,RIPPER,etc間接方法：從其他分類模型中提取規(guī)則： 利用決策樹(shù)方法先生成決策樹(shù)，然后再把決策樹(shù)轉(zhuǎn)換為規(guī)則； 使用粗糙集方法生成規(guī)則； 使用遺傳算法中的分類器

12、技術(shù)生成規(guī)則等； e.g. decision trees, neural networks, etc構(gòu)造分類規(guī)則的主要算法及流程算法簡(jiǎn)介規(guī)則歸納有四種策略：減法、加法，先加后減、先減后加策略： 減法策略：以具體例子為出發(fā)點(diǎn)，對(duì)例子進(jìn)行推廣或泛化，推廣即減除條件（屬性值）或減除合取項(xiàng)（為了方便，我們不考慮增加析取項(xiàng)的推廣），使推廣后的例子或規(guī)則不覆蓋任何反例。 加法策略：起始假設(shè)規(guī)則的條件部分為空（永真規(guī)則），如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項(xiàng)，直到該規(guī)則不再覆蓋反例。 先加后減策略：由于屬性間存在相關(guān)性，因此可能某個(gè)條件的加入會(huì)導(dǎo)致前面加入的條件沒(méi)什么作用，因此需要減除前面的

13、條件。 先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。順序覆蓋算法流程基本順序覆蓋算法構(gòu)造分類規(guī)則的主要算法及流程構(gòu)造分類規(guī)則的主要算法及流程規(guī)則產(chǎn)生過(guò)程： 這里，一次為一個(gè)類學(xué)習(xí)規(guī)則。理想情況下，在為C類學(xué)習(xí)規(guī)則時(shí)，我們希望它覆蓋C類的所有（或許多）訓(xùn)練元組，并且沒(méi)有（或很少）覆蓋其他類的元組。這樣，學(xué)習(xí)的規(guī)則應(yīng)該具有高準(zhǔn)確率。規(guī)則不必是高覆蓋率的。這是因?yàn)槊總€(gè)類可以有多個(gè)規(guī)則，使得不同的規(guī)則可以覆蓋同一類中的不同元組。該過(guò)程繼續(xù)，直到滿足終止條件，如不再有訓(xùn)練元組，或返回規(guī)則的質(zhì)量低于用戶指定的閾值。給定當(dāng)前的訓(xùn)練元組集，Learn_One_Rule過(guò)程為當(dāng)前類找出“最好的”規(guī)

14、則。 也就是說(shuō)，開(kāi)始時(shí)R為空，接下來(lái)用函數(shù)Learn_One_Rule提取類C的覆蓋當(dāng)前訓(xùn)練集的最佳規(guī)則。在提取規(guī)則時(shí)，類C的所有訓(xùn)練記錄被看作是正元組，而其他類的訓(xùn)練記錄則被當(dāng)成負(fù)元組。如果一個(gè)規(guī)則覆蓋大多數(shù)正元組，沒(méi)有或僅覆蓋極少數(shù)負(fù)元組，那么該規(guī)則是可取的。一旦找到這樣的規(guī)則，就刪掉它覆蓋的訓(xùn)練記錄，并把新規(guī)則追加到R的尾部。重復(fù)這個(gè)過(guò)程，直到滿足終止條件。然后，算法繼續(xù)產(chǎn)生下一個(gè)類的規(guī)則。示例規(guī)則空間從一般到特殊的搜索構(gòu)造分類規(guī)則的主要算法及流程示例說(shuō)明 為了學(xué)習(xí)“accept”類的規(guī)則，從一般的規(guī)則開(kāi)始，即從規(guī)則前件條件為空的規(guī)則開(kāi)始，然后考慮每個(gè)可以添加到該規(guī)則中的可能屬性測(cè)試。

15、Learn_One_Rule采用一種貪心的深度優(yōu)先策略。每當(dāng)面臨添加一個(gè)新的屬性測(cè)試到當(dāng)前規(guī)則時(shí)，它根據(jù)訓(xùn)練樣本選擇最能提高規(guī)則質(zhì)量屬性的測(cè)試。 而什么樣的度量能被選擇為規(guī)則質(zhì)量？構(gòu)造分類規(guī)則的主要算法及流程Learn_One_Rule需要度量規(guī)則的質(zhì)量。每當(dāng)考慮一個(gè)屬性測(cè)試時(shí)，乍一看準(zhǔn)確率似乎是一個(gè)顯然的選擇，但我們先看一下下面的例子：首先給出兩個(gè)概念： 正元組（pos）：學(xué)習(xí)規(guī)則的類的元組 負(fù)元組（neg）：除去學(xué)習(xí)規(guī)則的類的元組，其余的元組。規(guī)則質(zhì)量度量雖然R2只覆蓋兩個(gè)元組，但是R2的準(zhǔn)確率為100%,大于R1，在順序覆蓋算法中，將會(huì)選擇R2而不是R1，這顯然是不合理的。為了解決這個(gè)問(wèn)

16、題，我們采用另一種度量-信息增益，這種度量在一階歸納學(xué)習(xí)器（First Order Inductive Learner，F(xiàn)OIL）中提出。用Foil_Gain作為規(guī)則質(zhì)量標(biāo)準(zhǔn)：其中 pos ，neg為新增規(guī)則R所覆蓋的正元組和負(fù)元組，pos，neg是R覆蓋之前的R所覆蓋的正元組和負(fù)元組FOIL_Gain越大越好。規(guī)則質(zhì)量度量22_ (loglog)posposFOILGainposposnegposneg 上面介紹的規(guī)則質(zhì)量評(píng)估使用原訓(xùn)練數(shù)據(jù)的原則，這種評(píng)估是樂(lè)觀的，因?yàn)橐?guī)則可能過(guò)分?jǐn)M合這些數(shù)據(jù)。也就是說(shuō)，規(guī)則可能在訓(xùn)練數(shù)據(jù)上性能很好，但是在以后的數(shù)據(jù)上就不那么好。為了補(bǔ)償這一點(diǎn)，可以對(duì)規(guī)則剪

17、枝。下面給出一個(gè)剪枝方法：給定規(guī)則RFOIL_Prune(R)=(pos-neg)/(pos+neg)其中，pos和neg分別為規(guī)則R覆蓋的正元組和負(fù)元組。這個(gè)值將隨著R在剪枝集上的準(zhǔn)確率的增加而增加。因此，如果R剪枝后版本的FOIL_Prune值較高，則對(duì)R剪枝規(guī)則剪枝FOIL算法舉例ageincomestudentcredit_ratingbuys_computerpos3140highnofairyes40mediumnofairyes40lowyesfairyes3140lowyesexcellentyes40mediumyesfairyesneg=30highnofairno40lo

18、wyesexcellentno=30mediumnofairno說(shuō)明：首先以buys_computer=yes為正例，其它為負(fù)例訓(xùn)練集（Training Dataset）FOIL算法舉例（續(xù)）帶入公式，求出每個(gè)屬性值的增益：age40gain-1.2631.4740.966incomehighmediumlowgain-0.8480.3040.966studentyesnogain1.660-1.170Credit-ratingfairexcellentgain1.257-0.848pos=6, neg=4;例如，我們算一下age0，所以還要進(jìn)行內(nèi)循環(huán)ageincomestudentcredi

19、t_ratingbuys_computerPos40lowyesfairyes3140lowyesexcellentyes40mediumyesfairyesNeg40lowyesexcellentnoFOIL算法舉例（續(xù)） 再次求最大FOIL增益，這時(shí) pos=4，neg=1。age40gain0.3220.322-0.526incomelowmediumgain-0.2790.322credit-ratingfairexcellentgain0.966-0.678所以當(dāng)p=credit-rating=fair時(shí)有最大的FOIL_Gain。執(zhí)行 append p to r 那么規(guī)則r = s

20、tudent= yesAND credit-rating=fair； 移除pos、neg中不滿足規(guī)則r的元組，這時(shí)，neg=0，內(nèi)循環(huán)停止FOIL算法舉例（續(xù)） 此時(shí)pos= 30,第二次執(zhí)行外循環(huán): P賦給P，N賦給N,規(guī)則r 清空,neg=40, 執(zhí)行內(nèi)循環(huán):ageincomestudentcredit_ratingbuys_computerPos3140highnofairyes40mediumnofairyes3140lowyesexcellentyesNeg=30highnofairno40lowyesexcellentno40mediumnofairyesneg=30highnof

21、airno40lowyesexcellentno40mediumnofairyesNeg40,那么r =income=medium AND age=40 , 再刪除pos和neg中不滿足規(guī)則r的所有元組之后，pos=0，neg=0,內(nèi)循環(huán)停止。 這時(shí)，執(zhí)行R=R r , 由于pos=0，所以第三次外循環(huán)執(zhí)行之后停止，所有的正例規(guī)則全部找出，R= (student=yes AND credit-rating=fair) OR （ age=3140 ） OR（ income=medium AND age=40 ） FOIL算法舉例（續(xù)）ageincomestudentcredit_ratingbu

22、ys_computerP=30highnofairno40lowyesexcellentno40mediumnofairyes40lowyesfairyes3140lowyesexcellentyes40mediumyesfairyesbuys_computer=no為正例，其它為負(fù)例FOIL算法舉例（續(xù)）我們按照同樣的方法，算出R=（age=40）那么綜合以上所求的兩個(gè)規(guī)則R，我們可以從十條訓(xùn)練集中學(xué)習(xí)出以下結(jié)論： IF(student=yes AND credit-rating=fair)THEN buys_computer=yes; IF(age=3140 ) THEN buys_computer=yes; IF (income=medium AND