基于擴展概念格的帶約束關聯分類規則挖掘方法

翟悅,李楠,于文武

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

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

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

1 基本定義

1.1 關聯分類規則相關概念

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

表1 范例數據庫D

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

例如：a3→Y即為一條關聯分類規則.

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

|Oidset(X)|[6].

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

定義3關聯分類規則R的支持數Sup(R)定義為：滿足規則的條件屬性同時滿足類屬性記錄數目[7].

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

定義4關聯分類規則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 約束條件

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

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

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

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

2 擴展概念格結構

2.1 結點結構與格定義

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

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

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

圖1 概念格結點鏈接過程

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

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

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

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

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

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

2.2 差集概念diffset

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

定義10假設兩個項目集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擴展概念格高層次的結點定義為五元組Node(id, atts, diffset(d1,d2,…dk), countL(c1,c2,…ck) ,pos)表示，其中：

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

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

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

圖3 擴展概念格結點鏈接舉例

3 擴展概念格構建方法

3.1 相關定理

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

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

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

3.2 基于差集的擴展概念格構建算法

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

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

步驟2：搜索數據庫D生成滿足minsup的頻繁1-項集，調用概念格更新算法構建Lr，生成擴展概念格第1層結點;

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

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

步驟5：統計步驟3中記錄集在每一個類屬性中的數目ci=|oi|.計算pos并標記;

步驟 6：如果pos≥minsup,則調用概念格更新算法，更新lx.childrenEC和ly.childrenL,轉步驟3;

3.3 基于差集的擴展概念格構建實例

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

圖4 表1構建擴展概念格結構

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

圖4展示出算法1的執行過程，可以看出根據算法Build_LD構建基于差集的擴展概念格有效縮減了結點數目，FIs又在不丟失有效信息的前提下降低了建造整個格的復雜度.差集的運用進一步節省了存儲空間和計算時間.

4 帶約束關聯分類規則提取

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

4.1 帶約束的關聯分類規則提取算法LD-CAR

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

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

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

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

步驟4:遞歸調用遍歷LD中結點方法;

步驟5:輸出滿足約束條件集β的關聯分類規則；

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

4.2 帶約束的關聯分類規則提取實例

Ruler1: ;

Ruler2: ;

Ruler3: ;

Ruler4: ;

Ruler5: ;

Ruler6: ;

Find_CARs算法挖掘出的關聯分類規則集是滿足約束添加下的不重復完備規則集.在Find_CARs算法最后一步將全部結點flag標簽重置以備下一組新約束集的挖掘.

5 實驗結果

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

表2 實驗數據庫特征

5.1 挖掘時間

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

(a) Chess數據庫

(b) Mushroom數據庫

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

5.2 內存使用

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

表3 兩種算法內存使用對比

6 結論

本文在深入研究關聯分類理論的基礎上，提出了一種基于擴展概念格的帶約束關聯分類挖掘方法. 該方法主要分為兩個步驟：擴展概念格的建立和在其上的帶約束關聯規則提取. 算法設計基于差集的擴展概念格結點結構，根據用戶需求引入約束條件控制挖掘方向，并給出了相應格構建算法和在其上的關聯分類規則提取算法；該方法優勢如下：

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

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

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

進一步的工作可以考慮將本文算法推廣到大數據環境中，研究分布式輔助關聯分類，還可以對分類器進行動態調整[12]，使算法挖掘的結果更具參考價值.