毛華，鄭珍，劉曉慶

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

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

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

算法過程如下.

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

輸入：概念格L1(U,A,I)，最小支持度α；輸出：頻繁閉項集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對于2個概念C1=(A1,B1)和C2=(A2,B2)，且C2是C1的父節(jié)點，若|A1|≥min sup，則必有|A2|≥min sup.

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

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

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

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

定義3對于Y∈FCI,Y′=X,(B,C)∈L(U,D,J),若X∩B≠Φ,則可將概念擴充為(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中得到的全部頻繁閉項集FCI，對每一個頻繁閉項集Y計算其概念外延Y′=X，用漸進(jìn)式算法[26-27]建立概念格L2(U,D,J)={(Bj,Cj)|j=1,2,…，m},對每一個(Bj,Cj)中的外延判斷是否滿足條件X∩Bj≠Φ,若滿足，則可得到頻繁閉項集對應(yīng)的頻繁決策概念(X∩Bj,Y,C).提取決策規(guī)則Y→C,并由定義4判斷其是否冗余，進(jìn)而得到無冗余的決策規(guī)則集，計算出規(guī)則置信度.

具體實現(xiàn)過程如下.

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

輸入:頻繁閉項集FCI={Yi|i=1,2,…,n}，L2(U,D,J)；輸出:無冗余決策規(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時，說明L2(U,D,J)中的概念已經(jīng)全部遍歷完，內(nèi)循環(huán)結(jié)束.外循環(huán)i>n時說明已找到全部的頻繁閉項集的外延，外循環(huán)結(jié)束，所以算法2必在經(jīng)過第n×m次循環(huán)后結(jié)束.

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

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

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

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

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

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

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

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

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

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

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

3 實例驗證

從UCI機器學(xué)習(xí)數(shù)據(jù)庫中，隨機選取ABALONE數(shù)據(jù)集的前50個對象進(jìn)行實驗，整理之后得到如表1所示的決策形式背景(U,A,I,D,J),其中對象集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代表長度，a2代表直徑，a3代表高度，a4代表全重，a5代表去殼的重量，a6代表臟器的重量，a7代表環(huán)數(shù).決策屬性集分別代表鮑魚的性別，d1代表雄性，d2代表雌性，d3代表幼兒.

在此決策形式背景中，條件屬性集所對應(yīng)的形式背景(U,A,I)共有12個概念，即(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)}.決策屬性所對應(yīng)的形式背景(U,D,J)共有5個概念，即L(U,D,J)={(U,Φ),(110,a),(256 789,b),(34,c),(Φ,D)}.

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

表1 決策形式背景

算法1尋找FCI的復(fù)雜度為O(|FCI|)=O(5),算法2提取全部的無冗余規(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í)行時間比較Fig.1 Comparison of execution time of two algorithms with different fornal decision content

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

4 結(jié)論

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