一種決策形式背景中挖掘決策規(guī)則的新方法

毛華，鄭珍，劉曉慶

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002)

概念格1982年由Wille[1]首次提出，作為一種知識(shí)發(fā)現(xiàn)和數(shù)據(jù)分析的有效工具，已在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)、軟件工程和信息獲取等領(lǐng)域中有著廣泛的應(yīng)用[2-7].

在概念格研究領(lǐng)域中，利用頻繁項(xiàng)集進(jìn)行關(guān)聯(lián)規(guī)則的提取和頻繁模式的發(fā)現(xiàn)是至關(guān)重要的.將頻繁閉項(xiàng)集用于概念格挖掘關(guān)聯(lián)規(guī)則，可使規(guī)則數(shù)量大大減少，但同樣能夠得出與全部規(guī)則集相同的決策.Rakesh[8]提出了著名的Apriori先驗(yàn)算法用來(lái)挖掘頻繁項(xiàng)集，并生成關(guān)聯(lián)規(guī)則；付沙等[9]改進(jìn)了關(guān)聯(lián)規(guī)則挖掘Apriori算法，基于構(gòu)造輔助表和項(xiàng)集求交集策略，改進(jìn)算法顯著提高了頻繁項(xiàng)集的生成效率，從而使算法達(dá)到更高的運(yùn)算效率；Hafida等[10]定義語(yǔ)義模式，通過(guò)頻繁概念格進(jìn)行查找與語(yǔ)義模式相關(guān)聯(lián)的服務(wù)集合.在一些實(shí)際應(yīng)用中，基于頻繁閉項(xiàng)集在概念格中提取關(guān)聯(lián)規(guī)則的研究也有不少成果[10-16].

目前，有關(guān)決策規(guī)則的挖掘仍然是決策形式背景中研究的重要內(nèi)容[17-23]，但有些決策規(guī)則提取方法并沒(méi)有給出可操作的算法過(guò)程[19,22-23]，甚至已有的一些算法不能適用于大規(guī)模決策形式背景的決策規(guī)則提取[20]，即如何在大規(guī)模決策形式背景中挖掘決策規(guī)則的問(wèn)題目前還沒(méi)有得到很好的解決.

由于頻繁閉項(xiàng)集可用來(lái)壓縮數(shù)據(jù)集規(guī)模，過(guò)濾掉大量的冗余決策規(guī)則，故而可以考慮將頻繁閉項(xiàng)集與決策形式背景相聯(lián)系，提取具有較高可信度的決策規(guī)則集，并給出可實(shí)現(xiàn)的算法過(guò)程，利用此決策規(guī)則集快速、精準(zhǔn)地做出決策.

1 預(yù)備知識(shí)

定義1[24]假設(shè)給定形式背景(U,A,I)為三元組，其中U是對(duì)象集合，A是屬性集合，I是U和A之間的一個(gè)二元關(guān)系，I?U×A，若(x，a)∈I,則稱x具有屬性a，記為xIa.

對(duì)于形式背景(U,A,I)，在對(duì)象集X?U和屬性B?A上分別定義運(yùn)算：X′={a|a∈A,?x∈X,xIa},B′={x|x∈U,?a∈B,xIa}.

定義2[25]1)設(shè)I={i1,i2,…，in}s是n個(gè)不同項(xiàng)目的集合，如果對(duì)于一個(gè)集合X，有k=|X|，X?I，則稱X為k項(xiàng)集.設(shè)D為事物T的集合，T?Ω，對(duì)于給定的事物數(shù)據(jù)庫(kù)D，定義X的支持度為D中包含X的事物個(gè)數(shù)，記為sup(X)，用戶自定義一個(gè)小于|D|的最小支持度，記為α.

2) 給定事物數(shù)據(jù)庫(kù)D和α，對(duì)于項(xiàng)集X?I，若sup(X)≥α,則稱X為D中的頻繁項(xiàng)集.

3) 設(shè)項(xiàng)目集X?I，如果滿足Y″=Y，則稱X為閉項(xiàng)集.如果X同時(shí)是頻繁項(xiàng)集，則稱X為最大頻繁閉項(xiàng)集，簡(jiǎn)稱頻繁閉項(xiàng)集,記為FCI.頻繁閉項(xiàng)集中所包含的項(xiàng)目的數(shù)目|X|稱為閉項(xiàng)集的長(zhǎng)度.

引理1[13]設(shè)(U,A,I)為一個(gè)形式背景，稱(A,B)為這個(gè)形式背景的一個(gè)概念，則概念(A,B)對(duì)應(yīng)的內(nèi)涵是頻繁閉項(xiàng)集當(dāng)且僅當(dāng)內(nèi)涵B是頻繁項(xiàng)集，此時(shí)稱(A,B)為頻繁概念.

2 無(wú)冗余決策規(guī)則提取

基于概念格的頻繁閉項(xiàng)集提取算法[13]在概念格中遍歷了全部概念，提取頻繁閉項(xiàng)集.本文算法1中利用概念節(jié)點(diǎn)間的父子關(guān)系，無(wú)需遍歷全部概念節(jié)點(diǎn)，改進(jìn)頻繁閉項(xiàng)集在概念格中的挖掘算法，算法思路如下：

算法過(guò)程如下.

算法1頻繁閉項(xiàng)集挖掘的改進(jìn)算法

輸入：概念格L1(U,A,I)，最小支持度α；輸出：頻繁閉項(xiàng)集FCI.

步驟1 inti=0,FCI=φ，rooti=(Xi,Yi)

步驟2 fori=1 ton{Red-lattice(rooti)

ifrooti≠ΦRed-lattice(rootj)

else

end if

else

end if}

end for}

步驟3 PrintfFCI

定理1對(duì)于2個(gè)概念C1=(A1,B1)和C2=(A2,B2)，且C2是C1的父節(jié)點(diǎn)，若|A1|≥min sup，則必有|A2|≥min sup.

證明：由于C2是C1的父節(jié)點(diǎn)，必有A1?A2，則|A1|≤|A2|，故|A1|≥min sup，證畢.

定理2算法1中當(dāng)循環(huán)i=n+1時(shí)，算法程序結(jié)束.當(dāng)算法1結(jié)束時(shí)，輸出的FCI必為頻繁閉項(xiàng)集.

證明：當(dāng)i=n+1時(shí)，根節(jié)點(diǎn)rooti=Φ，循環(huán)終止，算法程序結(jié)束；又由引理1可知，每一個(gè)概念的內(nèi)涵必為一個(gè)頻繁項(xiàng)集，故保留下來(lái)的每個(gè)概念都是頻繁的，從而證明FCI必為頻繁閉項(xiàng)集，證畢.

由定理1可知，若父概念不是一個(gè)頻繁概念，那么它的子概念必定不是頻繁概念.由定理2可知，算法1在概念格中得到頻繁閉項(xiàng)集，進(jìn)而說(shuō)明了算法1的正確性.另外，算法1過(guò)濾掉了部分概念，這也在一定程度上壓縮了決策規(guī)則集.

定義3對(duì)于Y∈FCI,Y′=X,(B,C)∈L(U,D,J),若X∩B≠Φ,則可將概念擴(kuò)充為(X∩B,Y,C),稱之為頻繁決策概念，其中X∩B稱為頻繁決策概念外延，Y稱為頻繁決策概念內(nèi)涵，C稱為頻繁決策集.

定義41) 從頻繁決策概念中可直接得到?jīng)Q策規(guī)則為Y→C，表明由條件屬性Y可做出決策C，若E?Y且E→C成立，則稱決策規(guī)則Y→C是冗余的.

決策形式背景中決策規(guī)則提取的算法思路如下：利用算法1中得到的全部頻繁閉項(xiàng)集FCI，對(duì)每一個(gè)頻繁閉項(xiàng)集Y計(jì)算其概念外延Y′=X，用漸進(jìn)式算法[26-27]建立概念格L2(U,D,J)={(Bj,Cj)|j=1,2,…，m},對(duì)每一個(gè)(Bj,Cj)中的外延判斷是否滿足條件X∩Bj≠Φ,若滿足，則可得到頻繁閉項(xiàng)集對(duì)應(yīng)的頻繁決策概念(X∩Bj,Y,C).提取決策規(guī)則Y→C,并由定義4判斷其是否冗余，進(jìn)而得到無(wú)冗余的決策規(guī)則集，計(jì)算出規(guī)則置信度.

具體實(shí)現(xiàn)過(guò)程如下.

算法2決策形式背景中決策規(guī)則的提取

輸入:頻繁閉項(xiàng)集FCI={Yi|i=1,2,…,n}，L2(U,D,J)；輸出:無(wú)冗余決策規(guī)則R和置信度conf.

步驟1 inti=1,Mt=Φ,R=Φ

{ifXi∩Bj≠Φ thenMi=(Xi∩Bj,Yi,Cj)R=R∪(Yi→Cj)

else

end if}

end for}

end for

ifE→CjandE?Yithen

R=R-(E→Cj)

else

end if

end

步驟3 Printf(Randconf(Yi→Cj)

算法2中當(dāng)內(nèi)循環(huán)j>m時(shí)，說(shuō)明L2(U,D,J)中的概念已經(jīng)全部遍歷完，內(nèi)循環(huán)結(jié)束.外循環(huán)i>n時(shí)說(shuō)明已找到全部的頻繁閉項(xiàng)集的外延，外循環(huán)結(jié)束，所以算法2必在經(jīng)過(guò)第n×m次循環(huán)后結(jié)束.

定理3決策規(guī)則集R數(shù)量上大大減少，且一定是無(wú)冗余的決策規(guī)則集.

證明：顯然，由定義3和定義4可直接證明.

由定理3可知，算法2結(jié)束可得到數(shù)量少且無(wú)冗余的決策規(guī)則集，進(jìn)而說(shuō)明了算法2的正確性.

下面將分別對(duì)本文中給出的算法1和算法2進(jìn)行復(fù)雜度分析，并通過(guò)與已有的產(chǎn)生頻繁項(xiàng)集以及提取決策規(guī)則的相關(guān)著名算法和方法進(jìn)行比較，分析得出本算法的優(yōu)勢(shì).

算法1在概念格的基礎(chǔ)上，更新概念節(jié)點(diǎn)后每個(gè)概念的內(nèi)涵便是頻繁閉項(xiàng)集，針對(duì)每一個(gè)節(jié)點(diǎn)內(nèi)涵(即頻繁閉項(xiàng)集)進(jìn)行搜索，故算法1中最壞的情況下的時(shí)間復(fù)雜度為O(|FCI|).

與已有算法相比較，分析得出算法1優(yōu)勢(shì)如下：

1)Aprior算法[9]是產(chǎn)生頻繁閉項(xiàng)集提取關(guān)聯(lián)規(guī)則的著名算法，主要有以下缺點(diǎn)：一方面，算法中需要生成的候選項(xiàng)集數(shù)目龐大，呈指數(shù)級(jí)增長(zhǎng)，例如一家超市有一千種商品，則就會(huì)有21 000-1 個(gè)候選項(xiàng)集；另一方面，每個(gè)候選項(xiàng)集都要和每個(gè)事務(wù)相比較，事務(wù)數(shù)量越大，計(jì)算次數(shù)就會(huì)越多，且再由其產(chǎn)生關(guān)聯(lián)規(guī)則的時(shí)間復(fù)雜度為O(|FCI|2)，其中|FCI|是頻繁閉項(xiàng)集的數(shù)目.顯然本文算法1中基于概念格的節(jié)點(diǎn)關(guān)系得到頻繁項(xiàng)集大大節(jié)省了尋找頻繁閉項(xiàng)集的時(shí)間.

2)翟悅等[13]在概念格的基礎(chǔ)上生成頻繁閉項(xiàng)集的算法需要遍歷概念格中全部的概念節(jié)點(diǎn)，而本文算法1中，利用了概念節(jié)點(diǎn)的特化與泛化關(guān)系，以及深度優(yōu)先搜索的思想，無(wú)需遍歷全部概念節(jié)點(diǎn)，降低了算法的復(fù)雜度.

算法2中通過(guò)頻繁決策概念格提取全部決策規(guī)則的算法復(fù)雜度為O(m×n)(m、n分別為頻繁決策概念和頻繁閉項(xiàng)集的個(gè)數(shù))，生成無(wú)冗余決策規(guī)則的算法復(fù)雜度為O(r2)(r為全部決策規(guī)則數(shù))，最終算法2的時(shí)間復(fù)雜度為O(m×n+r2).

與已有算法相比較、分析，得出算法2優(yōu)勢(shì)如下：1) 魏玲等[19,23]僅是從理論方面給出了決策規(guī)則的提取方法，并沒(méi)有給出算法過(guò)程，無(wú)法直接實(shí)現(xiàn).本文不僅給出了理論分析，還將理論通過(guò)可行的算法加以實(shí)現(xiàn)，因此，本文的思想和方法可操作性較強(qiáng)；2) 李金海等[18]在決策形式背景中給出了一個(gè)更為高效的算法用來(lái)挖掘無(wú)冗余的決策規(guī)則，但得到的是全部規(guī)則集，時(shí)間復(fù)雜度為O((|U|+|A|)|LA|+|D||LA|2)，對(duì)于具有一定規(guī)模的決策形式背景，隨著對(duì)象個(gè)數(shù)和屬性個(gè)數(shù)的不斷增加，算法的復(fù)雜度相當(dāng)高，而本文給出的算法的時(shí)間復(fù)雜度會(huì)略低于文獻(xiàn)[18].

由以上分析看出，本文給出的2個(gè)算法與現(xiàn)有算法和方法相比，生成無(wú)冗余決策規(guī)則的算法復(fù)雜度較低，并且利用頻繁決策概念格壓縮了數(shù)據(jù)集規(guī)模，空間復(fù)雜度降低，更適用于具有一定規(guī)模的數(shù)據(jù)集的處理，因此本文算法要優(yōu)于其他一些已有算法或方法.

3 實(shí)例驗(yàn)證

從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中，隨機(jī)選取ABALONE數(shù)據(jù)集的前50個(gè)對(duì)象進(jìn)行實(shí)驗(yàn)，整理之后得到如表1所示的決策形式背景(U,A,I,D,J),其中對(duì)象集U={1,2,3,4,5,6,7,8,9,10}，條件屬性集A={a1,a2,a3,a4,a5,a6,a7}，決策屬性集D={d1,d2,d3}.

表1中，條件屬性集分別代表鮑魚的體態(tài)特征，a1代表長(zhǎng)度，a2代表直徑，a3代表高度，a4代表全重，a5代表去殼的重量，a6代表臟器的重量，a7代表環(huán)數(shù).決策屬性集分別代表鮑魚的性別，d1代表雄性，d2代表雌性，d3代表幼兒.

在此決策形式背景中，條件屬性集所對(duì)應(yīng)的形式背景(U,A,I)共有12個(gè)概念，即(U,A,I)={(U,Φ),2 567 910,a1),(145 678 910,a7),(2 567,a1a2),(5 789,a3a7),(567 910,a1a7),(567,a1a2a6a7),579,a1a3a7),(57,a1a2a3a6a7),(7,a1a2a3a4a6a7),(Φ,A)}.決策屬性所對(duì)應(yīng)的形式背景(U,D,J)共有5個(gè)概念，即L(U,D,J)={(U,Φ),(110,a),(256 789,b),(34,c),(Φ,D)}.

首先執(zhí)行算法1，計(jì)算決策規(guī)則置信度如下：

表1 決策形式背景

算法1尋找FCI的復(fù)雜度為O(|FCI|)=O(5),算法2提取全部的無(wú)冗余規(guī)則的復(fù)雜度為O(|m×n+r2|)=O(5×6+52)=O(55).因此，本例中的算法復(fù)雜度為O(|FCI)|+O(m×n+r2)=O(5)+O(55)=O(60).

圖1 不同規(guī)模決策形式背景下2種算法的執(zhí)行時(shí)間比較Fig.1 Comparison of execution time of two algorithms with different fornal decision content

為了驗(yàn)證算法的有效性，主要比較本文算法2與文獻(xiàn)[18]中算法的性能差異.實(shí)驗(yàn)環(huán)境為:3.5 GHz CPU I5,16 G內(nèi)存,Windows 10系統(tǒng).算法采用Matlab語(yǔ)言編程，由于隨機(jī)函數(shù)不僅可以靈活地產(chǎn)生所需數(shù)據(jù)集而且無(wú)需預(yù)處理，因此實(shí)驗(yàn)所需數(shù)據(jù)隨機(jī)產(chǎn)生.圖1是針對(duì)不同規(guī)模的決策形式背景，在相同的支持度下，分別采用本文算法與文獻(xiàn)[18]中的算法挖掘決策規(guī)則，圖1可看出，當(dāng)對(duì)象集的數(shù)量n=10時(shí)，2種算法在時(shí)間上相差不大；當(dāng)對(duì)象集的數(shù)量n=20、30時(shí)，本文算法在時(shí)間上略優(yōu)于文獻(xiàn)[18]中的算法，但差距不大，直到n=50時(shí)，本文算法在時(shí)間上大大優(yōu)于文獻(xiàn)[18]中的算法，即隨著決策形式背景規(guī)模的增加，本文算法在執(zhí)行時(shí)間上的優(yōu)越性會(huì)越來(lái)越明顯.因此，通過(guò)以上分析說(shuō)明本文中給出的通過(guò)頻繁決策概念格提取決策規(guī)則的方法效率較高，更適用于在具有一定規(guī)模的數(shù)據(jù)集中挖掘決策規(guī)則.

4 結(jié)論

本文提出了一種在決策形式背景中挖掘決策規(guī)則的新方法,改進(jìn)了概念格中挖掘頻繁閉項(xiàng)集的算法，給出了決策形式背景中挖掘無(wú)冗余決策規(guī)則的算法.利用頻繁閉項(xiàng)集可刪減掉大量冗余規(guī)則，進(jìn)而得到頻繁決策概念，從中挖掘帶有置信度的無(wú)冗余決策規(guī)則.實(shí)例表明，本文給出的算法復(fù)雜度較低，執(zhí)行效率較高，更適用于具有一定規(guī)模的決策形式背景中獲取無(wú)冗余決策規(guī)則.下一步考慮將此思想應(yīng)用到加權(quán)決策形式背景的知識(shí)獲取上，可根據(jù)實(shí)際情況中決策形式背景中的條件屬性和決策屬性的重要程度不同，分別對(duì)其賦予帶有某種意義的權(quán)值，以確保某些有意義的信息不被遺漏.