翟悅,李楠,于文武

(1.大連科技學(xué)院 數(shù)字技術(shù)學(xué)院，遼寧 大連116052；2.大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028) *

近年來采用關(guān)聯(lián)規(guī)則構(gòu)造分類器的關(guān)聯(lián)分類方法廣泛應(yīng)用于醫(yī)療、社會服務(wù)等領(lǐng)域，然而產(chǎn)生的關(guān)聯(lián)分類規(guī)則CARs(Class Association Rules)往往會包含大量冗余規(guī)則，對此許多學(xué)者展開了帶約束的關(guān)聯(lián)分類算法研究，該類算法主要分為事前處理與事后處理兩種策略，采用約束事前處理方法如： CBC[1]、FP-growth[2]，這類算法當(dāng)用戶關(guān)心的約束條件變化后，算法不得不重新掃描數(shù)據(jù)庫，根據(jù)新約束集重新構(gòu)建分類器，不具備重用性；采用約束事后處理方法如： CCAR[3]、MAC[4]等方法. 該類算法會產(chǎn)生大量候選CARs從而降低算法性能.

本文采用約束事后處理方法，為解決產(chǎn)生候選項目集過多導(dǎo)致效率低下等問題：本文利用擴展概念格結(jié)構(gòu)存儲頻繁項目集FIs (Frequent Itemsets)，運用結(jié)點之間關(guān)系定理快速在概念格中搜索符合約束條件的CARs；格結(jié)點在信息不丟失的前提條件下大大減少形成分類規(guī)則的數(shù)量，差集(diffset)概念引入不僅降低格結(jié)點內(nèi)存占用，還能加快對類屬性支持度和置信度計算，使得改進后的挖掘算法在時間和空間上具備良好性能.當(dāng)約束條件變化時無需重新建立概念格，僅需在格上重新搜索.

1 基本定義

1.1 關(guān)聯(lián)分類規(guī)則相關(guān)概念

設(shè)數(shù)據(jù)庫D=(AEC)，其中：一個項目集合由條件屬性A={A1,A2,…,An}構(gòu)成，每一個條件屬性Ai可以取某一個特定的值，項目集X={(Ai1,ai1), (Ai2,ai2),…,(Ain,ain)}，類屬性C={c1,c2,…,ck}.見表1.

表1 范例數(shù)據(jù)庫D

定義1關(guān)聯(lián)分類規(guī)則R形如蘊含式：X→Cj，其中Cj∈C,X為項目集[5]

例如：a3→Y即為一條關(guān)聯(lián)分類規(guī)則.

定義2在數(shù)據(jù)庫D中包含項目集X記錄集合 記 為 Oidset(X).發(fā) 生 數(shù) ActOcc(X) 定 義 為

|Oidset(X)|[6].

例如：Oidset (a3)={4,5,6}.ActOcc (a3)= |Oidset (a3)|=|{4,5,6}|=3.

定義3關(guān)聯(lián)分類規(guī)則R的支持?jǐn)?shù)Sup(R)定義為：滿足規(guī)則的條件屬性同時滿足類屬性記錄數(shù)目[7].

例如：Sup(a3→Y)=|{4,6}|=2.

定義4關(guān)聯(lián)分類規(guī)則R置信度定義為：Conf(R) =Sup(R)/ ActOcc (R)[7].

例如:Conf(a3→Y)= Sup(a3→Y)/ ActOcc (a3) = |{4,6}|/|{4,5,6}|=2/3.

1.2 約束條件

在數(shù)據(jù)挖掘中常使用的約束類型分為:知識約束、數(shù)據(jù)約束、層次約束、規(guī)則約束、興趣度約束等.本文研究數(shù)據(jù)約束，允許用戶根據(jù)關(guān)注目標(biāo)在規(guī)則挖掘過程中加入項目集約束條件，即僅挖掘包含某些項目的規(guī)則，使得規(guī)則挖掘過程更具效用.

定義5設(shè)β為項目集約束條件集,β={X1,X2, …,Xn},其中每個Xi形如ii1∧ii2∧ii3∧……∧ii2∧iik∈I,I={i1,i2,…,im}是m個不同項目的一個集合.

定義6滿足約束條件集β的關(guān)聯(lián)分類規(guī)則R=X→Cj必須滿足：iff?Xi?β，且Xi?X[8].

例如: 假設(shè)約束集β={<(A,a3),(B,b3)>,},針對第一約束條件<(A,a3),(B,b3)>，形如<(A,a3), (B,b3)>→Y,<(A,a3),(B,b3),(C,c1)>→Y滿足約束要求，而規(guī)則< (B,b3)>→Y，< (A,a3)>→Y不滿足約束要求.針對第二約束條件，形如<(A,a3), (C,c1)>→Y滿足約束要求，即規(guī)則中包含約束條件中的數(shù)據(jù)項目.

2 擴展概念格結(jié)構(gòu)

2.1 結(jié)點結(jié)構(gòu)與格定義

定義7設(shè)T與W為k-項集，它們共同擁有相同 (k-1)-項集作為前綴，由T直接生成其孩子結(jié)點(k+1)-項集記為：childrenEC(T)={TX|TX∈(k+1)-項集，且X屬于W后項}[9].

定義8設(shè)T為k-項集，由T間接生成孩子結(jié)點(k+1)-項集記為:childrenL(T)={Y|Y∈(k+1)-項集，T?Y,Y?childrenEC(T)}[9].

例如：圖1所示，其中由T直接生成的孩子結(jié)點childrenEC(T)均表示為實線，由T間接生成的孩子結(jié)點childrenL(T)均表示為虛線.假設(shè)T為bc，根據(jù)定義7由T直接生成的(k+1)-項集childrenEC(bc) ={bcd},根據(jù)定義8由T間接

圖1 概念格結(jié)點鏈接過程

生成的孩子結(jié)點childrenL(bc)={abc}.定義9擴展概念格第一層結(jié)點定義為五元組Node表示，其中：

(1)id為存儲結(jié)點id，根據(jù)該項目集所包含屬性二進制表示.

(2)atts屬性集為頻繁1-項集.

(3)Oidset(o1,o2,…om)記錄集為包含(2)中屬性集atts在每個類屬性中的集合.

(4)countL(c1,c2,…ck)為統(tǒng)計(3)中記錄集在每一個類屬性中的數(shù)目ci=|oi|.

(5)pos為maxi∈[1,j]{Ci},如果每個分類的統(tǒng)計值相等，則pos默認(rèn)為C1.

2.2 差集概念diffset

差集概念首先由Zaki等人[10]在2003年提出，本文將差集引入關(guān)聯(lián)分類規(guī)則挖掘，在擴展概念格高層的結(jié)點所存儲信息中，使用差集替代定義9中Oidset，可有效減少格中結(jié)點所占用存儲空間，還能利用差集快速計算類屬性的支持?jǐn)?shù)和置信度.

定義10假設(shè)兩個項目集PX與PY均以P為前綴的等價類，d(PXY)= Oidset (PX)- Oidset (PY)[11].

定理1已知兩個項目集PX、PY與d(PX)、d(PY)，可證明d(PXY)=d(PX) -d(PY).

證明：因為d(PXY)= Oidset (PX)-Oidset (PY)=Oidset(PX)-Oidset(PY)+Oidset(P)-Oidset(P)=(Oidset (P)-Oidset(PY))- (Oidset(P)- Oidset(PX))=d(PY)-d(PX).差集計算示意如圖2所示.

圖2 差集計算過程

定義11擴展概念格高層次的結(jié)點定義為五元組Node(id, atts, diffset(d1,d2,…dk), countL(c1,c2,…ck) ,pos)表示，其中：

(1) diffset(d1,d2,…，dk)為對應(yīng)記錄集oi的差集.

(2)countL(c1,c2,…，ck)為計算方法公式ci=X.ci- |diffseti|.

(3) 其他結(jié)點信息與定義9一致.

圖3 擴展概念格結(jié)點鏈接舉例

3 擴展概念格構(gòu)建方法

3.1 相關(guān)定理

定理2已知兩個概念格中結(jié)點X、Y，如果兩個結(jié)點具有相同的條件屬性，且屬性值不相等，則Oidset(X)∩Oidset(Y)=?.

定理3已知概念格中兩個結(jié)點XA、XB，如果?XB∈childrenEC(X),且XA結(jié)點先與XB生成,則?Y∈childrenEC(XB)∪children(XB),使得Y∈children(XA).

定理3說明擴展概念格中childrenL(XA)間接孩子結(jié)點確定時僅需搜索滿足如下條件的結(jié)點，條件1：Y∈children(X);條件2：YZ∈childrenEC(Y);條件3：判斷如果XA?YZ，那么YZ∈children(XA).運用定理3削減了大量候選項目集結(jié)點.

3.2 基于差集的擴展概念格構(gòu)建算法

本文提供一種基于差集的擴展概念格結(jié)構(gòu)LD (Lattice basedDiffset)，該結(jié)構(gòu)包含全部的頻繁項目集信息.基于差集的擴展概念格LD生成算法Build_LD步驟如下:

步驟1：輸入數(shù)據(jù)庫D，初始化最小支持度minsup；初始化擴展概念格Li←?;

步驟2：搜索數(shù)據(jù)庫D生成滿足minsup的頻繁1-項集，調(diào)用概念格更新算法構(gòu)建Lr，生成擴展概念格第1層結(jié)點;

步驟3：進行格結(jié)點鏈接操作，根據(jù)定理2，如果lx.id≠ly.id，使用lx.Oidset∪ly.Oidset計算格中結(jié)點的記錄集;

步驟4：根據(jù)定義9和定理1，如果lx為概念格第2層結(jié)點，使用Oidset(lx) -Oidset(ly)計算格結(jié)點差集，如果lx為高層次結(jié)點，使用ly.diffseti-lx.diffseti計算格結(jié)點差集;

步驟5：統(tǒng)計步驟3中記錄集在每一個類屬性中的數(shù)目ci=|oi|.計算pos并標(biāo)記;

步驟 6：如果pos≥minsup,則調(diào)用概念格更新算法，更新lx.childrenEC和ly.childrenL,轉(zhuǎn)步驟3;

3.3 基于差集的擴展概念格構(gòu)建實例

首先針對表1所示數(shù)據(jù)庫D(minsup=25%)，利用Build_LD算法產(chǎn)生的擴展概念格結(jié)構(gòu)見圖4.擴展概念格LD根結(jié)點為空結(jié)點，調(diào)用Build_LD算法生成擴展概念格第一層結(jié)點為〈{a1},{a2},{a3},{b1}, {b2}, {b3},{c1},{c2}〉,其中{b1}結(jié)點2,b1(1,5)(1,1)不滿足最小支持度minsup要求，故LD中不產(chǎn)生該結(jié)點.此后根據(jù)定義11和定理2生成第二層結(jié)點，分別為〈{a1b2},{a1b3},{a1c1},{a1c2},{a2b2},{a2b3},{a2c1},{a2c2},{a3b2},{a3b3},{a3c1},{a3c2},{b2c1},{b2c2},{b3c1},{b3c2}〉.其中僅有〈{a2b2}, {a3b3},{a3c1},{b2c1},{b3c1}〉五個結(jié)點滿足最小支持度minsup要求.如圖5(a)所示，計算結(jié)點3,a3b2(46,5)(0,0)不滿足minsup要求，不產(chǎn)生該結(jié)點.由算法Build_LD可知，生成概念格二層結(jié)點差集計算公式為O.diffseti= Oidset(lx) -Oidset(ly)，而在計算高層概念格結(jié)點差集計算公式為O.diffseti=ly.diffseti-lx.diffseti.如圖5(b)所示.

圖4 表1構(gòu)建擴展概念格結(jié)構(gòu)

圖5 擴展概念格二層結(jié)點與高層結(jié)點計算過程

圖4展示出算法1的執(zhí)行過程，可以看出根據(jù)算法Build_LD構(gòu)建基于差集的擴展概念格有效縮減了結(jié)點數(shù)目，F(xiàn)Is又在不丟失有效信息的前提下降低了建造整個格的復(fù)雜度.差集的運用進一步節(jié)省了存儲空間和計算時間.

4 帶約束關(guān)聯(lián)分類規(guī)則提取

在約束型關(guān)聯(lián)分類規(guī)則挖掘過程中，約束條件會隨著實際應(yīng)用場景中用戶需求而不斷變化，本文提出規(guī)則提取算法是在構(gòu)建的擴展概念格結(jié)構(gòu)上進行挖掘，LD結(jié)構(gòu)本身包含頻繁項目集完整信息，以便于當(dāng)約束條件改變，僅需按照新約束條件在LD中重新搜索且無需重復(fù)構(gòu)建格，從而加快挖掘速度.

4.1 帶約束的關(guān)聯(lián)分類規(guī)則提取算法LD-CAR

在帶項目集約束下，本文提供一種基于差集的概念格提取關(guān)聯(lián)分類規(guī)則方法LD-CAR (Diffset and Lattice based algorithm for CAR mining)，該算法挖掘步驟如下：首先根據(jù)算法Build_LD建立完成的基于差集的概念格結(jié)構(gòu)，遍歷概念格LD，根據(jù)用戶給定約束集生成符合條件的CARs，并為符合約束結(jié)點做flag標(biāo)記；然后算法清空結(jié)點flag標(biāo)記以備下次利用新約束進行掃描.帶約束的關(guān)聯(lián)分類規(guī)則提取算法Find_CARs步驟如下：

步驟1:輸入LD，初始化約束條件集β,最小置信度minconf;

步驟2:遍歷LD中結(jié)點，對于每個itemseti∈β，搜索LD尋找包含itemseti的結(jié)點li;

步驟3:判斷如果ifl.flag=false且conf≥minconf，則將該規(guī)則并入CARs中，CARs←CARs∪{l.itemset→cpos},設(shè)置l.flag=true;

步驟4:遞歸調(diào)用遍歷LD中結(jié)點方法;

步驟5:輸出滿足約束條件集β的關(guān)聯(lián)分類規(guī)則；

步驟6:重置LD結(jié)點的flag=false,以 便給定下一組新的約束條件下繼續(xù)生成CARs.

4.2 帶約束的關(guān)聯(lián)分類規(guī)則提取實例

Ruler1: ;

Ruler2: ;

Ruler3: ;

Ruler4: ;

Ruler5: ;

Ruler6: ;

Find_CARs算法挖掘出的關(guān)聯(lián)分類規(guī)則集是滿足約束添加下的不重復(fù)完備規(guī)則集.在Find_CARs算法最后一步將全部結(jié)點flag標(biāo)簽重置以備下一組新約束集的挖掘.

5 實驗結(jié)果

為了進一步驗證算法的有效性，實驗主要比較本文算法LD-CAR、文獻3所提到的CCAR算法和文獻4提出的MAC算法3者之間的性能差異.測試的硬件平臺為：Intel Core i5-6200 CPU 2.4GHz，內(nèi)存8GB，操作系統(tǒng)Windows10,使用C#在Visual studio2013運行環(huán)境中實現(xiàn)三種算法，測試數(shù)據(jù)集來自http://fimi. uantwerpen.be/data/.如表2所示選取3個不同特點的數(shù)據(jù)庫進行關(guān)聯(lián)分類規(guī)則挖掘性能實驗.

表2 實驗數(shù)據(jù)庫特征

5.1 挖掘時間

實驗對比了三種算法挖掘帶約束CARs消耗的時間,實驗中minconf=50%,約束集β根據(jù)屬性值的選擇率s進行模擬.例如：Pumsb數(shù)據(jù)庫擁有2113不同的屬性值，20%選擇率約為423個屬性值作為數(shù)據(jù)約束.由圖6測試結(jié)果可知，隨著minsup降低，本文提出算法LD-CAR性能優(yōu)于改進的CCAR算法與類Apriori的MAC算法，尤其在隨著minsup不斷變小的過程中，LD-CAR算法時間消耗增加緩慢，尤其在Pumsb這類數(shù)據(jù)集龐大且稠密的數(shù)據(jù)集上性能優(yōu)勢更加明顯.經(jīng)試驗分析可明顯看出，本文引入基于差集的擴展概念格結(jié)構(gòu)后，通過存儲差集信息能夠快速計算子結(jié)點類別支持度，有效提高結(jié)點生成效率，關(guān)聯(lián)分類規(guī)則提取算法有效壓縮了搜索空間，從而加快了算法的收斂速度.

(a) Chess數(shù)據(jù)庫

(b) Mushroom數(shù)據(jù)庫

(c)Pumsb數(shù)據(jù)庫圖6 擴展概念格二層結(jié)點與高層結(jié)點計算過程

5.2 內(nèi)存使用

實驗對比了CCAR與本文算法LD-CAR的內(nèi)存使用情況，內(nèi)存占用主要取決于算法采用存儲結(jié)構(gòu)，CCAR采用樹形結(jié)構(gòu)，本文LD-CAR采用基于差集的擴展概念格結(jié)構(gòu)，對比結(jié)果如表3所示.可以看出在不同數(shù)據(jù)庫中LD-CAR算法均占用較少內(nèi)存，尤其在記錄數(shù)龐大的稠密數(shù)據(jù)庫Chess與Pumsb中，兩個項目集鏈接后的孩子結(jié)點僅存儲差集信息極大降低了格空間占用.

表3 兩種算法內(nèi)存使用對比

6 結(jié)論

本文在深入研究關(guān)聯(lián)分類理論的基礎(chǔ)上，提出了一種基于擴展概念格的帶約束關(guān)聯(lián)分類挖掘方法. 該方法主要分為兩個步驟：擴展概念格的建立和在其上的帶約束關(guān)聯(lián)規(guī)則提取. 算法設(shè)計基于差集的擴展概念格結(jié)點結(jié)構(gòu)，根據(jù)用戶需求引入約束條件控制挖掘方向，并給出了相應(yīng)格構(gòu)建算法和在其上的關(guān)聯(lián)分類規(guī)則提取算法；該方法優(yōu)勢如下：

(1)設(shè)計擴展概念格結(jié)構(gòu)，每個結(jié)點中包含全部的頻繁項集信息，該結(jié)構(gòu)在不丟失有效信息的前提下降低了建造整個格的復(fù)雜度，應(yīng)用定理可有效縮減了擴展概念格中結(jié)點的數(shù)目，避免了由于候選項目集結(jié)點產(chǎn)生過多導(dǎo)致效率低下問題；

(2)在擴展概念格高層結(jié)點結(jié)構(gòu)中引入差集概念，可加快結(jié)點鏈接操作運算時間.高層格結(jié)點中存儲差集信息代替存儲記錄集也可有效減少內(nèi)存占用；

(3)該算法非常適合重用.當(dāng)約束條件集根據(jù)用戶需求發(fā)生改變時，格無需重新建立，重新挖掘的時間大大減少了,滿足重用性要求.

進一步的工作可以考慮將本文算法推廣到大數(shù)據(jù)環(huán)境中，研究分布式輔助關(guān)聯(lián)分類，還可以對分類器進行動態(tài)調(diào)整[12]，使算法挖掘的結(jié)果更具參考價值.