基于加權(quán)構(gòu)造鏈表的頻繁加權(quán)項(xiàng)集挖掘算法

文 凱，許萌萌，耿小海

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065；3.重慶信科設(shè)計(jì)有限公司，重慶 401121)

0 引 言

頻繁項(xiàng)集(FIs)是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究?jī)?nèi)容。近年來(lái)，由于挖掘需求和任務(wù)不同，頻繁項(xiàng)集的挖掘可分為頻繁閉項(xiàng)集[1]、top-rank-k頻繁項(xiàng)集[2]、可擦除項(xiàng)集[3]、最大頻繁項(xiàng)集[4]等，并為此提出了很多有效的數(shù)據(jù)結(jié)構(gòu)，包括Node-list、Nodeset、N-list[5]以及B-list[6]等。

FIs挖掘算法應(yīng)用廣泛，如購(gòu)物籃數(shù)據(jù)分析、智能系統(tǒng)[7]等，但其往往只關(guān)注項(xiàng)集外觀而忽略項(xiàng)集重要性。為發(fā)現(xiàn)加權(quán)數(shù)據(jù)庫(kù)價(jià)值，頻繁加權(quán)項(xiàng)集挖掘(FWIs)算法應(yīng)運(yùn)而生。Lee等[8]提出了FWI*WSD和FWI*TCD算法，它們使用帶有二維數(shù)組的新型前綴樹結(jié)構(gòu)來(lái)存儲(chǔ)和壓縮數(shù)據(jù)庫(kù)信息，以此挖掘FWIs。但其掃描數(shù)據(jù)庫(kù)多次，處理大數(shù)據(jù)庫(kù)時(shí)時(shí)間消耗大。Lan等[9]提出PWAI算法，使用最大序列模型來(lái)收緊子序列加權(quán)支持度的上邊界，減少挖掘中的候選個(gè)數(shù)。而WIT-FWIs-Diff算法是采用WIT-tree并結(jié)合Diffset策略來(lái)挖掘FWIs的算法。Nguyen等[10]利用IWS結(jié)構(gòu)來(lái)存儲(chǔ)和處理標(biāo)識(shí)符集合，通過(guò)消除交易集中位向量表示的所有0-字來(lái)減少內(nèi)存消耗，并創(chuàng)建映射數(shù)組，以更快地計(jì)算項(xiàng)集的加權(quán)支持度，提高FWIs的挖掘效率。

本文提出了BFWI算法，將項(xiàng)集信息完整地壓縮到構(gòu)建出的WB-tree中，以集合枚舉樹為搜索空間來(lái)保證所挖掘項(xiàng)集的完整性，采用包含索引避免復(fù)雜的項(xiàng)集連接以減少連接次數(shù)，并結(jié)合超集等價(jià)性質(zhì)加快確定FWIs的加權(quán)支持度，以此來(lái)提高算法的時(shí)間效率，減少內(nèi)存消耗。

1 相關(guān)知識(shí)

1.1 基本概念

定義1 加權(quán)數(shù)據(jù)庫(kù)WD：給定一數(shù)據(jù)庫(kù)交易集，其表示為T={t1,t2,…,tm}，I={i1,i2,…,in} 是由n個(gè)不同項(xiàng)組成的集合，其中ik(k=1,2,…,n) 表示項(xiàng)。集合I中對(duì)應(yīng)項(xiàng)的權(quán)重由w={w1,w2,…,wn} 表示。WD是由 元組組成。

定義2 交易集的權(quán)重tw：交易集tk的權(quán)重表示如式(1)所示，其中∑ix∈tkwx為tk項(xiàng)權(quán)重之和， |tk| 為tk中項(xiàng)的數(shù)量

(1)

定義3 加權(quán)支持度ws：設(shè)項(xiàng)集X={i1,i2,…,ik},ij的權(quán)值是wj(0≤wj≤1)， 則X的ws如式(2)所示，t(X)為包含X的交易集合

(2)

定義4 FWIs：已知用戶給定的minws閾值，若某一項(xiàng)集的ws不小于minws，則稱這樣的項(xiàng)集為FWIs，即頻繁加權(quán)項(xiàng)集。從WD中挖掘FWIs的問(wèn)題主要是找到滿足minws的所有FWIs。

1.2 B-list結(jié)構(gòu)

B-list結(jié)構(gòu)是在BTK算法中為挖掘top-rank-kFIs而提出的，該結(jié)構(gòu)將數(shù)據(jù)庫(kù)信息壓縮到只需掃描一次即可建樹完成的TB-tree中。B-list結(jié)構(gòu)還可挖掘FIs，如BLFPM算法[11]，以及最大頻繁項(xiàng)集，如BMFI算法。

近些年，研究者通常改進(jìn)數(shù)據(jù)結(jié)構(gòu)來(lái)提高FIs的挖掘效率。N-list結(jié)構(gòu)[12]計(jì)算交集的速度快，但不宜兩個(gè)短項(xiàng)集求交來(lái)生成更長(zhǎng)項(xiàng)集。DiffNodeset結(jié)構(gòu)[13]利用差集計(jì)算Nodeset，但其工作在數(shù)量較大的葉子節(jié)點(diǎn)集上。在挖掘FIs方面B-list結(jié)構(gòu)具有許多優(yōu)點(diǎn)。①事務(wù)數(shù)據(jù)庫(kù)被壓縮到樹中，因此B-list的存儲(chǔ)空間很小且節(jié)點(diǎn)信息只需一次掃描即可得到。②B-list結(jié)構(gòu)可計(jì)算項(xiàng)集支持度，減少運(yùn)算過(guò)程。③利用線性復(fù)雜度的交叉算子，可快速確定k-項(xiàng)集(k>2)的B-list。而其擴(kuò)展結(jié)構(gòu)WB-list也具此類優(yōu)點(diǎn)。

2 BFWI算法

2.1 加權(quán)構(gòu)造樹(WB-tree)和節(jié)點(diǎn)(WB-code)

傳統(tǒng)算法通常將信息壓縮到PPC-tree、FP-tree中，存在多次掃描效率低下的問(wèn)題。因此BFWI算法采用一次掃描即可獲得各節(jié)點(diǎn)開始和結(jié)束建立的全部信息的WB-tree結(jié)構(gòu)。

定義5 WB-tree：加權(quán)構(gòu)造樹是由根節(jié)點(diǎn)“Root”和一系列作為根節(jié)點(diǎn)子樹的項(xiàng)前綴樹組成。項(xiàng)前綴樹的各個(gè)節(jié)點(diǎn)信息由item-name, weight, parent-pointer, start-build和finish-build共5部分組成。其中item-name存儲(chǔ)當(dāng)前節(jié)點(diǎn)的名稱，weight是通過(guò)該節(jié)點(diǎn)的tw值之和。parent-pointer是該節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。start-build和finish-build分別存儲(chǔ)一個(gè)v值和w值，v表示樹開始構(gòu)建時(shí)的第v個(gè)節(jié)點(diǎn)，w表示樹完成構(gòu)建時(shí)的第w個(gè)節(jié)點(diǎn)。

由定義5，WB-tree的構(gòu)造過(guò)程如算法1所示。

算法1： Build-WB-tree(WD,minws)

輸入： WD，minws

輸出： the corresponding WB-tree,F1

(1) Scan WD and calculatetw,wsof the 1-itemsets andsumtw

(2) Find out the set of 1-itemsets withws≥minws,F1, sort the element in descending order of theirwsvalues

(3) Build a root node named ‘Root’, initialize global variablestart=0,finish=0

(4)foreach different first itempin DBdo//pandqare the itemsets of WD, Node is the node of WB-tree

(5) CallWeightBuildTree(p, Node) to insertpinto WB-tree

(6)endfor

(7)end

functionWeightBuildTree(p, parent)

(1) LetTPbe a list of transactions in DB which contain prefixp

(2) Build a new nodeN∶N.name = name of the last item inp;N.weight=thesumoftwvalues of transactions passing throughN;N.parent = parent

(3)N.start = ++start

(4)foreach different first itemqinTPdo

(5) CallWeightBuildTree(p∪q,N)

(6)endfor

(7)N.finish = ++finish

(8)end

性質(zhì)1 設(shè)m、n是WB-tree中兩不同節(jié)點(diǎn)，其對(duì)應(yīng)WB-code依次為 和 。 若m是n的祖先節(jié)點(diǎn)，則smfn。 證明參見文獻(xiàn)[6]。

WB-code是不會(huì)丟失節(jié)點(diǎn)信息的數(shù)據(jù)庫(kù)壓縮內(nèi)容。若已知兩節(jié)點(diǎn)s和f，由性質(zhì)1可快速判定兩者的祖孫關(guān)系，加快挖掘FWIs的進(jìn)程。

2.2 加權(quán)構(gòu)造鏈表(WB-list)

定義6 WB-list：給定WB-tree，項(xiàng)集X的WB-list是由形如 <(s1,f1,w1),(s2,f2,w2),…,(sn,fn,wn)> 的WB-code組成的序列，并按s升序排序，其序列中的每個(gè) 是WB-tree中已注冊(cè)過(guò)的項(xiàng)集X節(jié)點(diǎn)的WB-code。

定義7k-項(xiàng)集的WB-list：設(shè)PX和PY是兩個(gè) (k-1)-項(xiàng)集，有相同前綴P(P可為空)，根據(jù)F1的順序，X在Y之后，WBL(PX)、WBL(PY)、WBL(PXY)分別是PX、PY、PXY的WB-list，則WBL(PXY)由以下決定：

(1)對(duì)每個(gè)WB-code，Ci(si,fi,wi)∈WBL(PX) 和Cj(sj,fj,wj)∈WBL(PY)， 若Cj是Ci的祖先，則將 (sj,fj,wi) 添加到WBL(PXY)；

(2)遍歷WBL(PXY)， 將具有相同(s,f)信息的節(jié)點(diǎn)進(jìn)行合并得到新WB-code，其權(quán)值為這些WB-code的權(quán)值之和。

性質(zhì)2 給定一項(xiàng)集P=X1X2…Xn，Xi在Xi+1后面(按F1的排序)，且P的WB-list是WBL(P)={(s1,f1,w1),(s2,f2,w2),…,(sm,fm,wm)}， 則項(xiàng)集P的ws計(jì)算如下

(3)

證明：設(shè) 為項(xiàng)集P的WB-code，則從以下兩點(diǎn)證明。①存在一節(jié)點(diǎn)，該節(jié)點(diǎn)滿足注冊(cè)了項(xiàng)Xn并在其WB-code中具有相同 (si,fi)； ②wi是包含P的交易集tw之和，且其遍歷以Xn為根節(jié)點(diǎn)的子樹；設(shè)Ti(P)為包含P的事務(wù)集，且遍歷有根節(jié)點(diǎn)Xn的子樹。每遍歷一節(jié)點(diǎn)，每個(gè)事務(wù)的tw值都會(huì)被添加到節(jié)點(diǎn)的權(quán)重中，即

(4)

假設(shè)T(P)為包含P的交易集，則由條件①可得

(5)

由定義3知

(6)

由式(4)和式(5)可得式(7)，性質(zhì)2由此得證

(7)

性質(zhì)3 給定一項(xiàng)集P和項(xiàng)X，X?P，若ws(P)=ws(P∪{X})， 對(duì)于任一個(gè)滿足S∩P=?且X?S條件的項(xiàng)集S，都有ws(S∪P)=ws(S∪P∪{X})。

證明：由于ws(P)=ws(P∪{X})， 則對(duì)任意包含P的項(xiàng)集必然包含項(xiàng)X，所以對(duì)于S∪P的項(xiàng)集也必包含項(xiàng)X，即ws(S∪P)=ws(S∪P∪{X})。

采用性質(zhì)3可很大程度地減少搜索空間，圖1是以c,e,d,a,f為示例構(gòu)造的集合枚舉樹。構(gòu)造過(guò)程見文獻(xiàn)[5]。

圖1 示例集合枚舉樹

性質(zhì)4 假設(shè)已知頻繁k-項(xiàng)集P的WB-list，WBL(P)={(s1,f1,w1),(s2,f2,w2),…,(sm,fm,wm)}， 則s1

證明：由于項(xiàng)集的WB-list是按WB-code中s的升序排列，因此s1

2.3 改進(jìn)的WB-list交集

由定義7，可對(duì)兩(k-1)-項(xiàng)集求交得到k-項(xiàng)集的WB-list，求交集如算法2。根據(jù)算法2，WB-list交集的時(shí)間復(fù)雜度為O(l)，其中l(wèi)是最大長(zhǎng)度的WB-list。以PX和PY的WB-list，Ci(s1i,f1i,w1i) 和Cj(s2j,f2j,w2j) 為例，用性質(zhì)1判斷子孫關(guān)系，若Cj為Ci的祖先，則將 (s2j,f2j,w1i) 插入到PXY的WB-list中。偽代碼(5)-(12)行使用性質(zhì)4來(lái)減少求WB-list交集的復(fù)雜度。如當(dāng)s2j

算法2： Function WB-Intersection(WBLA,WBLB)

輸入：PA、PB的WB-list,WBLA={(s11,f11,w11),(s12,f12,w12), …, (s1m,f1m,w1m)},WBLB={(s21,f21,w21),(s22,f22,w22),…,(s2n,f2n,w2n)},minws

輸出：WBLC={(s31,f31,w31),(s32,f32,w32),…,(s3r,f3r,w3r)} 和ws//交集PAB的WB-list

(1)WBLC←null

(2) leti=0;j=0;r=0

(3)sum=ws(PA)+ws(PB)//sumis used to judge the ending

(4)while(i≤mandj≤n)do//m和n分別為WBLA和WBLB的長(zhǎng)度

(5)if(s1i>s2j)then

(6)if(f1i

(7)if(|WBLC|>0) and (s2j=s3r)thenw3r+=w1i

(8)elser++; add (s2j,f2j,w1i) intoWBLC;i++

(9)elsesum=sum-w2j;j++

(10)elsesum=sum-w1i;i++

(11)ifsum

(12) returnWBLC

2.4 基于包含索引的頻繁2-項(xiàng)集挖掘

定義8 包含索引：頻繁項(xiàng)集A的包含索引用 subsume(A) 表示，即

subsume(A)={B∈F1|g(A)?g(B)}

(8)

其中，g(A)表示項(xiàng)集A的事務(wù)集合。

性質(zhì)5 設(shè)項(xiàng)集A包含索引為subsume(A)={A1,A2,…,Am}, 則 {A1,A2,…,Am} 與A相結(jié)合的2m-1非空子集的每個(gè)ws等于A的ws。證明參見文獻(xiàn)[12]。

本文將包含索引與項(xiàng)集求交方法結(jié)合，通過(guò)將F1與不是其包含索引的F1進(jìn)行連接合并，即可獲得頻繁候選2-項(xiàng)集，接著使用算法2產(chǎn)生k-FWIs；對(duì)含包含索引的F1，只需將之與其包含索引合并而無(wú)需計(jì)算ws，合并后的ws等于它本身的ws。利用包含索引減少了頻繁2-項(xiàng)集的連接次數(shù)，不需產(chǎn)生項(xiàng)集與其包含索引子集結(jié)合的候選項(xiàng)，并結(jié)合性質(zhì)3來(lái)減少計(jì)算k-FWIs的k(>2)時(shí)間，從而提高了算法效率。

3 算法描述

從以上基礎(chǔ)，本文提出挖掘FWIs的BFWI算法。算法具體流程如圖2所示，步驟如下：

(1)使用算法1構(gòu)造WB-tree,并根據(jù)已定義的minws產(chǎn)生F1及其對(duì)應(yīng)的WB-list；

(2)獲取所有1-項(xiàng)集的包含索引；

(3)將包含索引與之對(duì)應(yīng)的F1直接合并可得到F2，并將其插入到結(jié)果當(dāng)中，其ws為F1的ws；

(4)遍歷集合枚舉樹并通過(guò)利用算法2對(duì)兩(k-1)-項(xiàng)集的WB-list求交集以確定k-FWIs。將A與其包含索引根據(jù)性質(zhì)5合并，與A相結(jié)合的2m-1非空子集的每個(gè)ws等于A的ws；在某些情況下，使用性質(zhì)3可快速確定項(xiàng)集的ws值，而不需要計(jì)算項(xiàng)集的WB-list，從而減少了搜索空間；

(5)重復(fù)步驟(4)，直到無(wú)新的(k+1)-FWIs產(chǎn)生。

圖2 BFWI算法流程

4 實(shí)驗(yàn)結(jié)果分析

4.1 算法的完整性和準(zhǔn)確性

為驗(yàn)證本算法有效性，將BFWI算法與IWS和WIT-FWIs-Diff算法就運(yùn)行時(shí)間和內(nèi)存兩方面進(jìn)行對(duì)比。實(shí)驗(yàn)環(huán)境為Inter(R) Core(TM) i5 3337U @ 1.80 GHz CPU，內(nèi)存4 GB，64位操作系統(tǒng)。用Java語(yǔ)言在同一機(jī)器上實(shí)現(xiàn)這3種算法，采用的測(cè)試集來(lái)自http://fimi.cs.helsinki.fi/data。實(shí)驗(yàn)所測(cè)試的4個(gè)數(shù)據(jù)庫(kù)特性見表1。

表1 測(cè)試數(shù)據(jù)集特性

其中#Trans是事務(wù)集數(shù)目，#Items是項(xiàng)數(shù)目，Avg.Length是交易集平均長(zhǎng)度。Spare level為數(shù)據(jù)稀疏性，值越小說(shuō)明數(shù)據(jù)稀疏性越大。實(shí)驗(yàn)通過(guò)改變minws來(lái)記錄算法的運(yùn)行時(shí)間和內(nèi)存占用情況，其中運(yùn)行時(shí)間和內(nèi)存占用分別如圖3和圖4所示。

圖3 運(yùn)行時(shí)間對(duì)比

圖4 內(nèi)存占用對(duì)比

如第3節(jié)所示，BFWI算法首先構(gòu)建WB-tree，對(duì)于每個(gè)事務(wù)，刪除不滿足minws的項(xiàng)，其余項(xiàng)在WB-tree中進(jìn)行排序和壓縮。由下閉包屬性，刪除一個(gè)低于minws的項(xiàng)對(duì)整個(gè)結(jié)果沒(méi)有影響。其次算法遍歷WB-tree生成F1的WB-list，并將FWIs的信息存儲(chǔ)于內(nèi)。由性質(zhì)1，值對(duì)(si,fi)在樹中保持子孫關(guān)系，wi值則存儲(chǔ)壓縮在樹中的事務(wù)集權(quán)值之和(性質(zhì)2)。最后算法通過(guò)遍歷和檢查集合枚舉樹來(lái)挖掘FWIs，分別從F1集合開始，依次確定F2、F3等。原則上集合枚舉樹包含F(xiàn)1生成的所有子集，由此在遍歷枚舉樹時(shí)不會(huì)遺漏任何情況，且基于性質(zhì)3，算法可找出不需執(zhí)行WB-list交集的WFIs。從以上分析，BFWI算法完全保證了FWIs的完整性和正確性。

4.2 時(shí)間和內(nèi)存對(duì)比

圖3是BFWI算法與IWS和WIT-FWIs-Diff算法在不同數(shù)據(jù)集上運(yùn)行時(shí)間的比較。為減少算法運(yùn)行時(shí)間之間的差距，縱坐標(biāo)采用對(duì)數(shù)刻度(lb)。分析可知：在稠密數(shù)據(jù)集上，WIT-FWIs-Diff算法消耗時(shí)間較少，但在稀疏數(shù)據(jù)集上則較多。而IWS算法則相反，原因是IWS算法刪除了tidset位向量表示中的所有0-字，因此IWS算法在稀疏數(shù)據(jù)集上有著較好的時(shí)間效果。總體來(lái)說(shuō)，3種算法的運(yùn)行時(shí)間都隨minws的降低而增大，但I(xiàn)WS和WIT-FWIs-Diff算法的運(yùn)行時(shí)間始終高于BFWI算法，表明BFWI算法有較高的時(shí)間效率。

圖4是BFWI算法與其它兩算法內(nèi)存占用的對(duì)比。分析可知：BFWI算法在稠密和稀疏數(shù)據(jù)集上占用的內(nèi)存都較少，表明該算法具有較好的空間效率。原因是BFWI算法中的WB-tree簡(jiǎn)單且高度壓縮，改進(jìn)的求交算法減少了計(jì)算項(xiàng)集ws的過(guò)程，加快確定k-FWIs。刪除非頻繁項(xiàng)縮小搜索空間，從而減少內(nèi)存消耗。但當(dāng)minws很低且在大而稀疏的數(shù)據(jù)集上如Retail和Kosarak(如圖4(c)和圖4(d)所示)，BFWI算法的效率比消除0-字的IWS算法略差。

4.3 實(shí)驗(yàn)效果分析

圖5是在可伸縮性方面的內(nèi)存消耗，可知WIT-FWIs-Diff效果最好，而 BFWI算法在構(gòu)建WB-tree時(shí)需存儲(chǔ)開始和結(jié)束建立的節(jié)點(diǎn)信息，隨著項(xiàng)和交易集數(shù)量的增多，存儲(chǔ)的節(jié)點(diǎn)信息量增多，內(nèi)存占用也越來(lái)越大。如圖5(b)中，當(dāng)交易集數(shù)量從300 k到1100 k時(shí)，BFWI的內(nèi)存增加了3倍，接近WIT-FWIs-Diff(3.1倍)和IWS(3.2倍)內(nèi)存的增加。因此，BFWI算法在其內(nèi)存占用可接受的范圍下，具有良好的運(yùn)行時(shí)間效果。

圖5 內(nèi)存可伸縮性

5 結(jié)束語(yǔ)

本文提出了一種新樹結(jié)構(gòu)WB-tree，該樹簡(jiǎn)單且具高壓縮性，由此提出BFWI算法。BFWI算法通過(guò)使用集合枚舉樹作為搜索空間，以防止漏掉項(xiàng)集；利用包含索引來(lái)減少2-項(xiàng)集的連接次數(shù)，提高了時(shí)間效率；并結(jié)合改進(jìn)的WB-list求交集算法和超級(jí)等價(jià)性質(zhì)，降低算法時(shí)間復(fù)雜度，以快速確定加權(quán)頻繁k-項(xiàng)集，提高算法效率。實(shí)驗(yàn)結(jié)果表明，BFWI算法的性能在不同的數(shù)據(jù)集中均優(yōu)于IWS和WIT-FWIs-Diff算法。根據(jù)不同的挖掘任務(wù)和需求，加權(quán)可擦除項(xiàng)集將會(huì)是下一步的研究方向。