文 凱，許萌萌，耿小海

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065；3.重慶信科設計有限公司，重慶 401121)

0 引 言

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

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

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

1 相關知識

1.1 基本概念

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

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

(1)

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

(2)

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

1.2 B-list結構

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

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

2 BFWI算法

2.1 加權構造樹(WB-tree)和節(jié)點(WB-code)

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

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

由定義5，WB-tree的構造過程如算法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 設m、n是WB-tree中兩不同節(jié)點，其對應WB-code依次為 和 。 若m是n的祖先節(jié)點，則smfn。 證明參見文獻[6]。

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

2.2 加權構造鏈表(WB-list)

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

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

(1)對每個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é)點進行合并得到新WB-code，其權值為這些WB-code的權值之和。

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

(3)

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

(4)

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

(5)

由定義3知

(6)

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

(7)

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

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

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

圖1 示例集合枚舉樹

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

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

2.3 改進的WB-list交集

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

(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-項集挖掘

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

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

(8)

其中，g(A)表示項集A的事務集合。

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

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

3 算法描述

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

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

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

(3)將包含索引與之對應的F1直接合并可得到F2，并將其插入到結果當中，其ws為F1的ws；

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

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

圖2 BFWI算法流程

4 實驗結果分析

4.1 算法的完整性和準確性

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

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

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

圖3 運行時間對比

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

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

4.2 時間和內(nèi)存對比

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

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

4.3 實驗效果分析

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

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

5 結束語

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