基于粗糙集理論的規(guī)則提取算法

1、基于粗糙集理論的規(guī)則提取算法朱穎翠，馬英紅，王常偉(山東師范大學(xué)管理學(xué)院， 山東，濟(jì)南250014)摘 要：粗糙集理論的主要思想是在保持分類(lèi)能力不變的前提下，通過(guò)屬性約簡(jiǎn)和值約簡(jiǎn)，提取決策規(guī)則。本文主要是提出了利用隸屬度函數(shù)進(jìn)行值約簡(jiǎn)的同時(shí)提取決策規(guī)則的算法。利用該算法可在不求得核值表的情況下，直接找到各規(guī)則的最小條件屬性集，獲得決策表的所有決策規(guī)則。關(guān)鍵詞：粗糙集；隸屬度函數(shù)；規(guī)則提取中圖分類(lèi)號(hào)：TP182 文獻(xiàn)標(biāo)識(shí)碼：AAn Algorithm for Rule Extraction Based on Rough Set TheoryZHU Ying-cui，MA Ying-hong，WA

2、NG Chang-wei(School of Management Shandong Normal University, Shandong Jinan250014, China)Abstract: The main idea of rough set theory is to extract decision rules by attribute reduction and value reduction in the premises of keeping the ability of classification. In this paper, an algorithm on value

3、 reduction, and for extracting decision rule based on the membership function is proposed. All the decision rules on decision table and the minimal rule set of reduced condition attribute set without core-valued table would be attained by this algorithm. Keywords: rough set；membership function；rule

4、extraction0引言粗糙集理論是一種刻畫(huà)模糊的、不完整性和不確定性的數(shù)學(xué)工具。它的主要思想是是在保持分類(lèi)能力不變的前提下，通過(guò)屬性約簡(jiǎn)和值約簡(jiǎn)，導(dǎo)出決策規(guī)則。但在目前研究的粗糙約簡(jiǎn)算法中，大多都比較關(guān)注屬性的約簡(jiǎn)，把求得最佳屬性約簡(jiǎn)作為設(shè)計(jì)目標(biāo)。但在很多的實(shí)際應(yīng)用中，有時(shí)我們并不是特別關(guān)注屬性約簡(jiǎn)，而只關(guān)心求得用戶(hù)所需的決策規(guī)則。以文獻(xiàn) 1 中全球變暖的決策表為例，如表1所示，其中Solar energy，Volcanic activity，Residual CO2 為條件屬性，Temperature為決策屬性，Days count是每一個(gè)對(duì)象在一年中出現(xiàn)的頻次。FactSolar en

5、ergyVolcanic activityResidual CO2TemperatureDays count1MediumHighLowHigh202HighHighHighHigh303MediumLowHighHigh904LowLowLowLow1205HighHighMediumHigh706MediumLowHighLow34表利用可辨矩陣進(jìn)行約簡(jiǎn)2可知，屬性約簡(jiǎn)為Solar energy，Volcanic activity，Solar energy，Residual CO2，Volcanic activity，Residual CO2。以Solar energy，Volcanic

6、activity為條件屬性約簡(jiǎn)可得到5條決策規(guī)則：(Volcanic Activity，high) (Temperature，high);作者簡(jiǎn)介：朱穎翠(1982)，女，山東省菏澤人，山東師范大學(xué)管理學(xué)院2005級(jí)研究生，研究方向：決策支持理論與系統(tǒng)。E-mail:(Solar energy，high) (Temperature，high); (Solar energy，low) (Temperature，low);(Solar energy，Medium) (Volcanic Activity，low) (Temperature，high);(Solar e

7、nergy，Medium) (Volcanic Activity，low) (Temperature，low);其中，前三條為一致性決策規(guī)則，后兩條為不一致性的決策規(guī)則。同樣以Solar energy，Residual CO2和Volcanic activity，Residual CO2為條件屬性約簡(jiǎn)也可得到相應(yīng)的決策規(guī)則。但在具體的應(yīng)用中，也許我們只關(guān)心哪些條件屬性之間有關(guān)系，哪些條件屬性之間沒(méi)有關(guān)聯(lián)，哪些條件屬性是對(duì)決策毫無(wú)用處的，不管約簡(jiǎn)是Solar energy，Volcanic activity、Solar energy，Residual CO2還是Volcanic activity

8、，Residual CO2都是我們感興趣的，因?yàn)槿绻挥脤傩约s簡(jiǎn)Solar energy，Volcanic activity得到的決策規(guī)則進(jìn)行決策，那么當(dāng)出現(xiàn)含有屬性Residual CO2的規(guī)則時(shí)，將不能做出正確的決策來(lái)判斷是否導(dǎo)致全球變暖。也就是說(shuō)，我們有必要求出全部的決策規(guī)則。我們只需求條件屬性中對(duì)于決策屬性一定可省略的屬性，將它約簡(jiǎn)掉即可。本文針對(duì)此問(wèn)題提出了一種不找核值表的情況下，直接得到各規(guī)則的最小條件屬性集，獲得決策表的所有決策規(guī)則的算法，該算法對(duì)于一致性決策表和不一致決策表 3 都適用。1粗糙集理論的相關(guān)概念一個(gè)知識(shí)表達(dá)系統(tǒng)S可表達(dá)為：S=，其中U表示對(duì)象的集合，即論域；A是屬

9、性的集合；VaAVa是屬性值的集合，即屬性的值域集，其中Va是屬性aA的值域；f是信息函數(shù)，f：UAV，即f(x，a)V，它指定了U中每一對(duì)象x的屬性值。決策表根據(jù)知識(shí)表達(dá)系統(tǒng)定義為：S=(U，A)為一知識(shí)表達(dá)系統(tǒng)，C，DA為兩個(gè)屬性子集，且CD=A,CD=，C, D分別稱(chēng)為條件屬性集和決策屬性集，具有條件屬性和決策屬性的知識(shí)表達(dá)系統(tǒng)稱(chēng)為決策表，記作T(U，A，C，D),或簡(jiǎn)稱(chēng)CD決策表。在決策表中，對(duì)于屬性子集RA,不可分辨關(guān)系IND(R)定義為：IND(R)(x，y)UU| rR，r(x)=r(y)。顯然，IND(R)是一個(gè)等價(jià)關(guān)系，x在屬性集R上的等價(jià)類(lèi)xIND(R)定義為：xIND(R

10、)y| yU, y IND(R) x。為方便起見(jiàn)，在不產(chǎn)生混淆的情況下用R代替IND(R)。關(guān)系IND(C)和IND(D)的等價(jià)類(lèi)分別稱(chēng)為條件類(lèi)和決策類(lèi)。在文獻(xiàn) 4 中，隸屬度定義中的參數(shù)x表示數(shù)據(jù)對(duì)象，修改參數(shù)為屬性集值，重新表示屬性集B對(duì)Yi的隸屬度函數(shù)。在決策表中，D為決策屬性，YiU/D，i0, 1，|IND(D)|1。即Yi是根據(jù)決策屬性D得到的各個(gè)等價(jià)類(lèi)，每一個(gè)等價(jià)類(lèi)對(duì)應(yīng)著一種決策分類(lèi)類(lèi)別。B為條件屬性集的子集，即BC，x1，x2，.， x|B|為屬性集B所對(duì)應(yīng)的屬性值，屬性集B對(duì)Yi的隸屬度函數(shù)為： 其中，x表示x1, x2 ，.，x|B|所對(duì)應(yīng)的對(duì)象，|*|表示集合中元素的個(gè)數(shù)

11、，b表示B中元素的個(gè)數(shù)即|B|。表示根據(jù)屬性集B中的某一個(gè)等價(jià)類(lèi)能確定歸于某一個(gè)決策類(lèi)Yi的對(duì)象的個(gè)數(shù)與該類(lèi)對(duì)象的個(gè)數(shù)的比例。隸屬度函數(shù)反映的是：如果已知屬性集B的某值對(duì)應(yīng)的對(duì)象屬于某個(gè)等價(jià)類(lèi)，那么這個(gè)屬性集值對(duì)應(yīng)的對(duì)象屬于決策類(lèi)Yi的概率為。顯然，越大，屬于決策類(lèi)Yi的概率越大。若=1，可以肯定這個(gè)屬性集值對(duì)應(yīng)的對(duì)象一定屬于決策類(lèi)Yi。若0說(shuō)明屬性集值對(duì)應(yīng)的對(duì)象一定不屬于決策類(lèi)Yi，即在決策表中不存在這樣一條決策規(guī)則。若(0,1) 那么這個(gè)屬性集值對(duì)應(yīng)的對(duì)象可能屬于決策類(lèi)Yi也可能不屬于決策類(lèi)Yi。在非數(shù)據(jù)集的情況下，利用可辨矩陣得到一個(gè)差別函數(shù)，通過(guò)對(duì)該差別函數(shù)進(jìn)行化簡(jiǎn)可以得到所有屬性約簡(jiǎn)

12、5，則在任何屬性約簡(jiǎn)中都不包含的屬性，稱(chēng)之為條件屬性中相對(duì)于決策屬性一定可以省略的屬性。令X是U中根據(jù)條件屬性C定義的分類(lèi)，Y是U中根據(jù)決策屬性D定義的分類(lèi)，對(duì)于每個(gè)xi，yi U，定義一個(gè)函數(shù)dx：desc(xi)desD(yi)：xi yi，xi X，yiY，稱(chēng)函數(shù)dx為決策表T中的決策規(guī)則。定理5：設(shè)dx是一條被消去所有過(guò)剩條件屬性值的決策規(guī)則，條件屬性集C的等價(jià)類(lèi)xc中任何最少屬性a的等價(jià)類(lèi)xa 的交集相應(yīng)的決策類(lèi)xD中，則由最小條件屬性a組成的新決策規(guī)則dx是dx的一個(gè)決策規(guī)則約簡(jiǎn)。2規(guī)則提取算法算法的思想如下：輸入：決策表S，條件屬性的個(gè)數(shù)m輸出：規(guī)則集RSTEP1：進(jìn)行屬性約簡(jiǎn)，

13、刪除條件屬性中相對(duì)于決策屬性一定可以省略的屬性。STEP2: R=F，n=1。其中n代表屬性集B中屬性的個(gè)數(shù)STEP3: 計(jì)算各屬性集的等價(jià)類(lèi)劃分及根據(jù)隸屬度函數(shù)計(jì)算各隸屬度。STEP4：若1，提取對(duì)應(yīng)的決策規(guī)則dx，R=Rdx，將該隸屬度刪除。 若0，直接將該隸屬度刪除。若(0,1)，將Yi相同的中屬性集B及其對(duì)應(yīng)的屬性值，每?jī)蓚€(gè)組合使屬性集B的個(gè)數(shù)擴(kuò)展為n+1個(gè)。若規(guī)則集R中存在由屬性集B 的含有n個(gè)屬性的子集及對(duì)應(yīng)的屬性集值所提取的決策規(guī)則，將此刪除。 STEP5：n=n+1STEP6：重復(fù)3至5，直到n=m+1或者所有的隸屬度都被刪除。STEP7：若n=m+1時(shí)結(jié)束，說(shuō)明存在不一致的決

14、策規(guī)則，提取對(duì)應(yīng)的決策規(guī)則dx，R=Rdx，隸屬度的值表示屬于決策類(lèi)的概率。STEP8: 結(jié)束，輸出規(guī)則集R。以表1中的數(shù)據(jù)為例進(jìn)行算法過(guò)程演示。用S代表Solar energy，V代表Volcanic activity，R代表 Residual CO2，T代表Temperature，M代表Medium，H代表High，L代表Low。算法過(guò)程如下：1進(jìn)行屬性約簡(jiǎn)。經(jīng)計(jì)算容易得出表中的沒(méi)有屬性是T一定可省略的。2n=1，R=F。3計(jì)算每個(gè)屬性的等價(jià)類(lèi)劃分和對(duì)應(yīng)的隸屬度。如下所示：U/S1,3,62,54，U/V1,2,53,4,6，U/R1,42,3,65，U/TY1, Y2=1,2,3,54,

15、6計(jì)算各隸屬度如下：，其中x為條件屬性S的值M所對(duì)應(yīng)的對(duì)象。同理可計(jì)算：4由可得到規(guī)則集R：SHY1，VHY1，RMY1，SLY2并將其對(duì)應(yīng)的隸屬度刪除，將值為0的隸屬度也刪除。剩余的所有隸屬度擴(kuò)展為含有兩個(gè)屬性如下：。5n=2。6重復(fù)以上過(guò)程直到結(jié)束，可得到規(guī)則集R：SHY1，VHY1，RMY1，SLY2，SMRLY1，VLRLY2。7n=m=4退出循環(huán)，提取各隸屬度對(duì)應(yīng)的不一致性決策規(guī)則：SMVLRHY1，SMVLRHY2。8算法結(jié)束，輸出規(guī)則集R：SHY1，VHY1，RMY1，SLY2，SMRLY1，VLRLY2，SMVLRHY1，SMVLRHY2。綜上所述，我們可以得到以下8條規(guī)則：(

16、Solar energy, High)(Temperature, High),(Solar energy, Low)(Temperature, Low),(Volcanic activity, High)(Temperature, High),(Residual CO2, Medium)(Temperature, High),(Solar energy, Medium) (Residual CO2, Low)(Temperature, High),(Volcanic activity, Low) (Residual CO2, Low) (Temperature, Low),(Solar ene

17、rgy, Medium) (Volcanic activity, Low) (Residual CO2, High) (Temperature, High),(Solar energy, Medium) (Volcanic activity, Low) (Residual CO2, High) (Temperature, Low),由于前六條是一致性決策規(guī)則其隸屬度都為1，后兩條是不一致性決策規(guī)則其隸屬度分別為，可得到如下結(jié)論：如果Solar energy是High，則Temperature一定是High；如果Solar energy是Low，則Temperature一定是Low；如果Volc

18、anic activity是High，則Temperature一定是High；如果Residual CO2是Medium，則Temperature一定是High；如果Solar energy是Medium并且Residual CO2是Low，則Temperature一定是High；如果Volcanic activity是Low并且Residual CO2是Low，則Temperature一定是Low；如果Solar energy是Medium，Volcanic activity是Low并且Residual CO2是High，則Temperature是High的概率為0.73；如果Solar energy是Medium，Volcanic activity是Low并且Residual CO2是High，則Temperature是Low的概率為0.27。3結(jié)束語(yǔ)本算法適用于一致性決策表和不一致性決策表，在不求核值表的情況下，從約簡(jiǎn)后的決策表中通過(guò)隸屬度函數(shù)，直接得到各規(guī)則的最少條件屬性集，獲得決策表的所有決策規(guī)則。另外，在該算法得到的所有規(guī)則中，只要將對(duì)應(yīng)同一分類(lèi)結(jié)果的冗余規(guī)則去掉，可以提取出各個(gè)屬性約簡(jiǎn)下的決策規(guī)則。不足之處在于由于本算法的迭代次數(shù)較多，使得時(shí)間復(fù)雜性比普通的規(guī)則提取算法要高。參考文獻(xiàn)： 1ZPawlakRough sets