基于差異節(jié)點(diǎn)集的加權(quán)頻繁項(xiàng)集挖掘算法

王 斌,房新秀,魏天佑

(青島理工大學(xué) 信息與控制工程學(xué)院,山東 青島 266520)

0 概述

自AGRAWAL提出關(guān)聯(lián)規(guī)則[1-2]以來(lái),關(guān)聯(lián)規(guī)則挖掘[3-4]引起相關(guān)學(xué)者的廣泛關(guān)注。傳統(tǒng)的關(guān)聯(lián)挖掘算法通常忽略數(shù)據(jù)庫(kù)中各個(gè)項(xiàng)目重要程度的區(qū)別,而在分析實(shí)際數(shù)據(jù)時(shí),利用加權(quán)關(guān)聯(lián)規(guī)則[5-6]能夠發(fā)現(xiàn)出現(xiàn)頻率較低但權(quán)值較大的重要頻繁項(xiàng)集。加權(quán)數(shù)據(jù)庫(kù)往往出現(xiàn)在真實(shí)的應(yīng)用程序或智能系統(tǒng)中,如銷售數(shù)據(jù)庫(kù)、股票數(shù)據(jù)庫(kù)、文本數(shù)據(jù)庫(kù)以及醫(yī)療數(shù)據(jù)庫(kù)等。

文獻(xiàn)[7]較早提出加權(quán)頻繁項(xiàng)集挖掘(WFIM)算法,該算法使用平均函數(shù)來(lái)評(píng)估權(quán)重的一個(gè)項(xiàng)目集。研究人員根據(jù)加權(quán)對(duì)象的不同,將加權(quán)頻繁模式挖掘方法分為兩類。一類為高效用項(xiàng)集的挖掘[8],如EFIM[9]、MHUI[10]等算法,其考慮項(xiàng)的數(shù)量和權(quán)重大小,但是,該類算法在挖掘頻繁項(xiàng)集時(shí)進(jìn)行了多次重復(fù)的計(jì)算,降低了挖掘的效率。另一類考慮項(xiàng)的權(quán)重信息,如PWAI[11]、IWS[12]和FWI-WSD[13]等算法,其根據(jù)項(xiàng)集的加權(quán)支持度來(lái)確定加權(quán)頻繁項(xiàng)集,該類算法廣泛應(yīng)用于挖掘加權(quán)頻繁閉項(xiàng)集[14]、加權(quán)可消除模式挖掘[15]、加權(quán)最大頻繁項(xiàng)集[16]等任務(wù)中。但是,上述算法需要多次掃描數(shù)據(jù)庫(kù)或多次遍歷樹結(jié)構(gòu)來(lái)挖掘FWIs[17],因此,在挖掘效率方面仍然存在一定不足。

文獻(xiàn)[18]提出了一種基于WN-list的算法NFWI,其采用WN-List數(shù)據(jù)結(jié)構(gòu),該數(shù)據(jù)結(jié)構(gòu)是N-List[18]的擴(kuò)展。NFWI算法用于大型稀疏的數(shù)據(jù)集時(shí)性能良好,但是在密集數(shù)據(jù)集中,由于WN-list需要前序編碼和后序編碼來(lái)表示節(jié)點(diǎn),因此NFWI需要進(jìn)行大量的交集運(yùn)算,從而降低了挖掘效率。

文獻(xiàn)[19]提出一種最大頻繁項(xiàng)集挖掘算法DNMFIM,其采用DiffNodeset[20]數(shù)據(jù)結(jié)構(gòu),本文在該數(shù)據(jù)結(jié)構(gòu)中加入權(quán)值得到WDiffNodeset數(shù)據(jù)結(jié)構(gòu)。針對(duì)NFWI算法挖掘效率低的問(wèn)題,本文提出一種使用WDiffNodeset數(shù)據(jù)結(jié)構(gòu)的加權(quán)頻繁項(xiàng)集挖掘算法DiffNFWI。該算法采用集合枚舉樹和混合搜索策略相結(jié)合的方法查找加權(quán)頻繁項(xiàng)集,利用差集策略計(jì)算項(xiàng)集的加權(quán)支持度。在此基礎(chǔ)上,采用集合枚舉樹生成加權(quán)頻繁項(xiàng)集,并通過(guò)剪枝策略修剪搜索空間。

1 相關(guān)定義與問(wèn)題描述

1.1 相關(guān)定義

定義1事務(wù)權(quán)重tw(tk)指加權(quán)數(shù)據(jù)庫(kù)(WD)記錄事務(wù)tk中各項(xiàng)目權(quán)重的平均值[18],即為:

(1)

其中,|tk|是事務(wù)中項(xiàng)目的總數(shù)。

定義2項(xiàng)集X的加權(quán)支持度ws(X)是包含該項(xiàng)目的事務(wù)權(quán)重與總事務(wù)權(quán)重的比值[18],即為:

(2)

其中,t(X)是包含X的事務(wù)集。

定義3?i1,i2∈F1,F1是一系列頻繁項(xiàng)集,當(dāng)且僅當(dāng)ws(i2)>ws(i1),有i2>i1。

定義4?i1i2…ik,L1={ik,…,i2,i1},L1為有序的加權(quán)頻繁項(xiàng)集,并按照加權(quán)支持度降序排列。

1.2 加權(quán)節(jié)點(diǎn)樹

WDiffNodeset數(shù)據(jù)結(jié)構(gòu)采用加權(quán)節(jié)點(diǎn)樹(WN-tree)[18]節(jié)點(diǎn)編碼模型,給定WD并設(shè)置一個(gè)minws后創(chuàng)建加權(quán)節(jié)點(diǎn)樹,然后生成加權(quán)頻繁1-項(xiàng)集L1和一個(gè)WN-tree。假設(shè)WD如表1所示(隨機(jī)設(shè)minws=0.5),所構(gòu)建的WN-tree如圖1所示。創(chuàng)建WN-tree的算法(constructing_WN_tree)參考文獻(xiàn)[18]。

表1 樣本加權(quán)數(shù)據(jù)庫(kù)WD

圖1 WN-tree結(jié)構(gòu)

性質(zhì)1對(duì)于WN-tree中的任意2個(gè)節(jié)點(diǎn)N1和N2(N1≠N2),當(dāng)且僅當(dāng)N1.pre-valueN2.post-value時(shí),稱N1是N2的祖先[18]。

1.3 WNodeset和WDiffNodeset

WDiffNodeset是一種基于WNodeset的數(shù)據(jù)結(jié)構(gòu)。

定義5(加權(quán)頻繁1-項(xiàng)集的WNodeset) 給定一個(gè)WN-tree,對(duì)于加權(quán)頻繁1-項(xiàng)集i,將所有節(jié)點(diǎn)名稱為i的WN-code[18]組成的集合定義為i的WNodeset。每一個(gè)i的節(jié)點(diǎn)集都按照WN-code中的pre-value值升序排列,加權(quán)頻繁1-項(xiàng)集中的WNodeset如下所示:

C→{(1,8,2.4)},E→{(2,6,2)},A→{(3,3,1.4),(9,7,0.4)},D→{(4,1,1),(7,5,0.4)},F→{(5,0,0.5),(6,2,0.4),(8,4,0.4)}

性質(zhì)2給定一個(gè)項(xiàng)集,假設(shè){(x1,y1,z1),(x2,y2,z2),…,(xl,yl,zl)}是相應(yīng)的WNodeset,則存在x1x2…xl且y1y2…yl。

定義6(加權(quán)頻繁k-項(xiàng)集的WNodesets) 令P=i1i2…ik-1ik為一個(gè)項(xiàng)集(ij∈L1,i1i2…ik),將P=i1i2…ik-1ik的加權(quán)節(jié)點(diǎn)集表示為WNodesetP,將P1=i1i2…ik-2ik-1的加權(quán)節(jié)點(diǎn)集表示為WNodesetP1,將P2=i1i2…ik-2ik的加權(quán)節(jié)點(diǎn)集表示為WNodesetP2,則有WNodesetP=WNodesetP1∩WNodesetP2。

定義7(加權(quán)頻繁2-項(xiàng)集的WDiffNodesets) 給定2個(gè)項(xiàng)集i1、i2(i1、i2∈L1∧i1i2),用WNodeseti1和WNodeseti2分別表示i1和i2的加權(quán)節(jié)點(diǎn)集。加權(quán)2-項(xiàng)集i1i2的WDiffNodesets用WDiffNodesetsi1i2來(lái)表示,即:WDiffNodesetsi1i2={(x.pre-value,x.weight)|x∈WNodeseti1∧(?y∈WNodeseti2,與y對(duì)應(yīng)的節(jié)點(diǎn)是與x對(duì)應(yīng)的節(jié)點(diǎn)的祖先)}。WDiffNodesetsi1i2中的元素按pre-order的升序排列。例如:A→{(3,3,1.4),(9,7,0.4)},F→{(5,0,0.5),(6,2,0.4),(8,4,0.4)},其中,根據(jù)性質(zhì)2可得(3,3,1.4)是(6,2,0.4)和(5.0.0.5)的祖先而不是(8,4,0.4)的祖先,而(9,7,0.4)不是任何節(jié)點(diǎn)的祖先,因此,FA的WDiffNodesets為(8,0.4)。同理,FD的WDiffNodesets為(6,0.4)。

定義8(加權(quán)頻繁k-項(xiàng)集的WDiffNodesets) 令P=i1i2…ik-1ik是一個(gè)項(xiàng)集(滿足ij∈L1∧i1i2…ik)。將P1=i1i2…ik-2ik-1的加權(quán)節(jié)點(diǎn)集表示為WNodesetP1,P2=i1i2…ik-2ik的加權(quán)節(jié)點(diǎn)集表示為WNodesetP2。則P的WDiffNodesetP計(jì)算公式為:

WDiffNodesetP=WDiffNodesetP1/WDiffNodesetP2

(3)

其中,“/”表示集合差。

性質(zhì)3給定2個(gè)項(xiàng)集P1=i1i2…ik-2ik-1、P=i1i2…ik-1ik,將WDiffNodesetP表示為WDNP,則ws(P)的計(jì)算公式為:

(4)

證明令P2=i1i2…ik-2ik,將WNSP、WNS1、WNS2表示為P、P1、P2的加權(quán)節(jié)點(diǎn)集,由定義6、定義8分別得到WNSP=WNS1∩WNS2,WDNP=WNS1/WNS2。

性質(zhì)4令P=i1i2…ik-1ik是一個(gè)項(xiàng)集(滿足ij∈L1∧i1i2…ik),將P1=i1i2…ik-2ik-1的WDiffNodeset表示為WDN1,P2=i1i2…ik-2ik的WDiffNodeset表示為WDN2,P的WDiffNodeset表示為WDNP,則WDNP的計(jì)算公式為:

WDNP=WDN2/WDN1

(5)

證明令X=i1i2…ik-3ik-2,Y=i1i2…ik-3ik-1,則X、Y、P1、P2的WNodeset分別定義為WNSx、WNSY、WNS1、WNS2。由定義6和定義8分別可得:

WNS1=WNSX∩WNSY

(6)

(7)

由式(6)、式(7)可得:

WNSX=(WNSX∩WNSY)∪(WNSX/WNSY)=

WNS1∪WDN1

WNS1∩WDN1=?,WNS1=WNSX/WDN1

同理:

WNSX=WNS2∪WDN2,WNS2∩WDN2=?,

WNS2=WNSX/WNS2

最后結(jié)果為:

WDNP=WNS1/WNS2=(WNSX/WDN1)/

(WNSX/WDN2)=WNSX∩(WDN1)T∩

WDN2=WDN2∩(WDN1)T=

WDN2/WDN1

2 DiffNFWI算法

2.1 搜索空間

加權(quán)頻繁項(xiàng)集挖掘問(wèn)題可以用一個(gè)集合枚舉樹表示,以數(shù)據(jù)庫(kù)WD(表1)為例,其項(xiàng)xi∈I={F,D,A,E,C},且F

圖2 集合枚舉樹

算法1所示為構(gòu)建2-項(xiàng)集WDN的偽代碼。

算法1Build 2-itemset-WDN(ixiy)

1.WDNxy←?,k←0 and j←0;

2.lx← the length of WNx(WNodeset of ix) and ly←the length of WNy(WNodeset of iy);

4.if WNx[k].post-value>WNy[j].post-value then:

5.j←j+1;

6.Else

7.if WNx[k].post-valueWNy[j].pre-value then

8.k←k+1;

9.Else

10.WDNxy←WDNxy∪{(WNx[k].post-value,WNx[k].weight)};

11.k←k+1;

12.End if

13.End if

16.WDNxy←WDNxy∪{(WNx[k].post-value,WNx[k].weight)};

17.k←k+1;

18.End whlie

19.Return WDNxy

構(gòu)建2-項(xiàng)集WDN時(shí)采用混合搜索策略來(lái)構(gòu)建ixiy的WDiffNodeset。比較WNodeset中的2個(gè)WN-code,直到其中一個(gè)WNodeset的所有元素都比較完畢?？梢酝ㄟ^(guò)“祖先-后代”的關(guān)系來(lái)比較2個(gè)節(jié)點(diǎn)集中的所有元素以創(chuàng)建WDiffNodeset,但是該操作效率很低,復(fù)雜度為O(x·y)。根據(jù)性質(zhì)2和性質(zhì)4,本文提出算法1,并根據(jù)如下3種情況來(lái)減少2個(gè)元素之間的比較次數(shù),此時(shí)時(shí)間復(fù)雜度為O(x+y)。

情況1若WNx[k].post-value>WNy[j].post-value,此時(shí),與WNy[j]對(duì)應(yīng)的節(jié)點(diǎn)不是與WNx[k]對(duì)應(yīng)的節(jié)點(diǎn)的祖先。由性質(zhì)2可得,各項(xiàng)集WNodeset均是按照post-value升序排列,因此,WNy[j]不符合要求,繼續(xù)選取WNy[j+1]與WNx[k]進(jìn)行對(duì)比。

情況2若WNx[k].post-valueWNy[j].pre-value,由性質(zhì)1可得,與WNy[j]對(duì)應(yīng)的節(jié)點(diǎn)是與WNx[k]對(duì)應(yīng)的節(jié)點(diǎn)的祖先,由定義7可得,WNx[k]不符合要求,因此,選取WNx[q]的下一個(gè)元素WNx[k+1]來(lái)進(jìn)行對(duì)比。

情況3若WNx[k].post-value

2.2 主要剪枝性質(zhì)

DiffNFWI算法采用NFWI算法的剪枝策略來(lái)修剪搜索空間。

性質(zhì)5(剪枝策略[18]) 給定項(xiàng)目集P、Q和一個(gè)項(xiàng)目i,滿足P∩Q=?,i∈P且i∈Q,如果ws(P)=ws(P∪{i}),則有:

ws(P∪Q)=ws(P∪Q∪{i})

(8)

例如在表1中,令P=F,i=E,Q=C,ws(F)=ws(FE)=1.3,因此,ws(FC)=ws(FEC)=1.3。證明過(guò)程參考文獻(xiàn)[18]。

2.3 DiffNFWI算法描述

DiffNFWI算法以事務(wù)數(shù)據(jù)庫(kù)、一個(gè)minws作為輸入,算法2所示為DiffNFWI的偽代碼。首先進(jìn)行初始化,DiffNFWI框架由3個(gè)部分組成:第一階段,掃描WD,刪除小于minws的項(xiàng),對(duì)每一個(gè)事務(wù)里的項(xiàng)排序,從而創(chuàng)建WN-tree樹;第二階段,遍歷WN-tree確定所有的頻繁1-項(xiàng)集及其WNodesets,構(gòu)造所有層次為1的集合枚舉樹(即加權(quán)頻繁項(xiàng)集樹);第三階段,確定所有的加權(quán)k-項(xiàng)集及其WDiffNodesets(k≥2),構(gòu)造層次為k的集合枚舉樹。其中,第三階段細(xì)分為確定加權(quán)頻繁2-項(xiàng)集和加權(quán)頻繁3-項(xiàng)集。DiffNFWI算法采用性質(zhì)5作為剪枝策略,將滿足剪枝策略的項(xiàng)集放入等價(jià)項(xiàng)集中,最后輸出集合枚舉樹和等價(jià)項(xiàng)集中的所有結(jié)果。

算法2DiffNFWI算法

輸入WD,minws

輸出加權(quán)頻繁項(xiàng)集F

//第1步創(chuàng)建WN-tree

1.F=?;//初始化F為空集

2.調(diào)用constructing_WN_tree(WD,minws)

3.F=F∪L1;//L1為有序的頻繁1-項(xiàng)集

//第2步遍歷WN-tree,確定頻繁1-項(xiàng)集

4.Scan WN-tree to find WNodesets//找到WNodesets

5.Create the node childi with level 1;//構(gòu)造層次為1的//集合枚舉樹

//第3步確定所有的頻繁k-項(xiàng)集(k≥2)

6. For each 2-itemsets ixiydo//頻繁2-項(xiàng)集循環(huán)

7.call Build 2-itemset-WDN(ixiy);//調(diào)用算法1產(chǎn)生//WDiffNodeset;

9.if ixiy.wsminws*|WD|,then

10.F2=F2∪{ixiy};

11.Create the node childi with level 2;//構(gòu)造層次為2的//集合枚舉樹

12.End For

13.For each weighted frequent itemsets do//頻繁k-項(xiàng)集

14.call constructing_frequent_ itemset_tree;

15.End For

16.Return F//輸出集合枚舉樹與等價(jià)項(xiàng)集中的所有集合

算法2在挖掘加權(quán)頻繁k-項(xiàng)集時(shí)調(diào)用了算法3的函數(shù),然后采用性質(zhì)3計(jì)算加權(quán)支持度計(jì)數(shù),再利用性質(zhì)5修剪搜索空間,將滿足條件的項(xiàng)放入等價(jià)項(xiàng)集中,若不滿足剪枝策略再判斷是否滿足minws,接著對(duì)滿足條件的節(jié)點(diǎn)創(chuàng)建集合枚舉樹。算法3第7行描述了剪枝策略,其中,N表示當(dāng)前節(jié)點(diǎn),將滿足條件的項(xiàng)保存在等價(jià)項(xiàng)集中,該項(xiàng)無(wú)需構(gòu)建當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn),原因是與這些項(xiàng)集相關(guān)的加權(quán)頻繁項(xiàng)集的所有信息都保存在當(dāng)前節(jié)點(diǎn)中,從而大幅降低了搜索空間。

算法3constructing_frequent_itemset_tree算法

1.For each k-itemset WDiffNodeset(P) do:

2.X=WNd.itemset;//X=i1i2…ik-1

3.Y=(X-X.last_item)∪{i};//X-X.last_item是從X//中刪除的最后一項(xiàng)子集,即Y= i1i2…ik-2

4.P=X∪{i};//P= i1i2…ik-2ik

5.P.WDN=X.WDN/Y.WDN;//利用性質(zhì)4構(gòu)造WDN

7.if P.ws=X.ws then://剪枝策略

8.N.equivalent_items=N.N.equivalent_items∪{i}; //將滿足剪枝策略的項(xiàng)集放入等價(jià)項(xiàng)集中

9.Else if P.ws≥|WD|×minws then//判斷閾值

10.Create the node childi with leve k;

11.End if

12.End if

13.F為集合枚舉樹與等價(jià)項(xiàng)集的并集

14.End For

2.4 NFWI算法和DiffNFWI算法的對(duì)比

NFWI算法采用WN-List數(shù)據(jù)結(jié)構(gòu),而本文DiffNFWI算法采用WDiffNodeset數(shù)據(jù)結(jié)構(gòu)。WN-List和WDiffNodeset都是基于WN-tree來(lái)存儲(chǔ)加權(quán)頻繁項(xiàng)集的信息。DiffNFWI算法采用了集合枚舉樹和混合搜索策略相結(jié)合的方法來(lái)查找加權(quán)頻繁項(xiàng)集,其中,有3條搜索原則,而NFWI算法僅采用性質(zhì)2作為搜索原則。因此,DiffNFWI算法可以實(shí)現(xiàn)高效的查找。其次,DiffNFWI采用性質(zhì)3高效地計(jì)算加權(quán)支持度,再結(jié)合NFWI算法中的剪枝策略,從而取得了良好的效果。

2.5 DiffNFWI算法復(fù)雜度分析

DiffNFWI算法各階段復(fù)雜度分析如下:

1)第一階段:DiffNFWI算法調(diào)用constructing_WN_tree(WD,minws)算法中的constructing_WN_tree函數(shù)。首先掃描WD,移除不滿足minws的項(xiàng)目,并將每一個(gè)事務(wù)中剩余的項(xiàng)進(jìn)行排序,最壞情況下的復(fù)雜度為O(m·lt);然后DiffNFWI根據(jù)排序后的WD創(chuàng)建WN-tree,最壞情況下的復(fù)雜度為O(lt·logalk)。因此,算法第一階段的復(fù)雜度為O(m·lt·logalt·lt)。其中,m為WD中的項(xiàng)目數(shù)量,lk為WD中的事務(wù)最大長(zhǎng)度。

2)第二階段:算法產(chǎn)生頻繁1-項(xiàng)集的過(guò)程。DiffNFWI遍歷WN-tree并且產(chǎn)生WNodesets的加權(quán)頻繁1-項(xiàng)集,因此,該階段的復(fù)雜度為O(m·lt),在最壞情況下,m·lt是樹的大小。

3)第三階段:算法產(chǎn)生頻繁k-項(xiàng)集的過(guò)程(k≥2)。該算法采用集合枚舉樹與混合搜索策略相結(jié)合的方法查找加權(quán)頻繁項(xiàng)集。算法1中的混合搜索策略的時(shí)間復(fù)雜度為O(x+y),其中,x和y分別對(duì)應(yīng)2個(gè)節(jié)點(diǎn)集的長(zhǎng)度。集合枚舉樹的節(jié)點(diǎn)數(shù)為2n-1(n為加權(quán)頻繁1-項(xiàng)集的數(shù)量),最壞情況下NFWI算法執(zhí)行WDiffNodeset交集運(yùn)算后,創(chuàng)建了集合枚舉樹的所有節(jié)點(diǎn)(沒(méi)有剪枝),因此,該階段的復(fù)雜度為O(2n·(x+y))。

綜合上述分析,DiffNFWI算法的時(shí)間復(fù)雜度為O(m·lt·logalt·lt+m·lt+2n·(x+y)),由于m·lt·logalt·lt+m·lt遠(yuǎn)小于2n·(x+y),因此DiffNFWI算法的時(shí)間復(fù)雜度為O(2n·(x+y))。

影響NFWI、DiffNFWI算法運(yùn)行時(shí)間的是系數(shù)(x+y)。在NFWI算法中,x和y分別為2個(gè)WN-List的長(zhǎng)度,在DiffNFWI算法中,x和y分別為2個(gè)WDiffNodeset的長(zhǎng)度,WDiffNodeset表示差異節(jié)點(diǎn)集,是不包含頻繁k-項(xiàng)集的集合,而WN-List是包含該項(xiàng)目的集合。在密集數(shù)據(jù)集中,DiffNFFWI算法的(x+y)系數(shù)相對(duì)于NFWI算法較小,因此,DiffNFWI算法在密集數(shù)據(jù)集中性能明顯優(yōu)于NFWI算法。

3 實(shí)驗(yàn)驗(yàn)證

本文進(jìn)行3組仿真實(shí)驗(yàn)來(lái)對(duì)比NFWI和DiffNFWI算法的有效性和可行性。實(shí)驗(yàn)環(huán)境如下:操作系統(tǒng)Window7(64位),開發(fā)工具Visual Studio C++2010,語(yǔ)言為C/C++,8 GB內(nèi)存容量,英特爾i5處理器。

3.1 數(shù)據(jù)集介紹

本文選取mushroom、pumsb、T40110D100K和T1014D100K數(shù)據(jù)集進(jìn)行評(píng)估實(shí)驗(yàn),這4個(gè)數(shù)據(jù)集均下載自SPMF[21]文庫(kù)。在4個(gè)數(shù)據(jù)集中,項(xiàng)的權(quán)重在1～10整數(shù)之間隨機(jī)產(chǎn)生(可參考文獻(xiàn)[18]),然后通過(guò)改變最小加權(quán)支持度閾值來(lái)進(jìn)行加權(quán)頻繁項(xiàng)集挖掘,最后對(duì)比分析2種算法在不同數(shù)據(jù)集中的時(shí)間消耗情況。表2所示為數(shù)據(jù)集特征。

表2 數(shù)據(jù)集特征信息

3.2 結(jié)果分析

3.2.1 運(yùn)行時(shí)間比較

在每組實(shí)驗(yàn)中2種算法所挖掘到的加權(quán)頻繁項(xiàng)集均相同,圖3所示為不同minws下2種算法的運(yùn)行時(shí)間對(duì)比。從圖3可以看出,在mushroom、pumsb、T40110D100K、T1014D100K數(shù)據(jù)集中,當(dāng)minws分別為2%、65%、0.4%、0.02%時(shí),與NFWI算法相比,DiffNFWI算法的運(yùn)行效率分別提高64.2%、67.9%、48.4%和27.0%,minws越小,DiffNFWI算法性能優(yōu)勢(shì)越明顯,隨著minws的升高,DiffNFWI算法的優(yōu)勢(shì)逐漸下降,即本文DiffNFWI算法性能優(yōu)于NFWI算法,尤其在密集數(shù)據(jù)集中,算法優(yōu)勢(shì)更明顯。

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

3.2.2 內(nèi)存比較

圖4所示為DiffNFWI和NFWI在挖掘時(shí)的內(nèi)存消耗情況,從圖4可以看出,隨著閾值的不斷減小,與NFWI算法相比,DiffNFWI算法在4種不同數(shù)據(jù)集中的內(nèi)存沒(méi)有明顯的變化,且其內(nèi)存小于NFWI算法。

圖4 2種算法內(nèi)存大小對(duì)比

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

本文提出一種DiffNFWI算法,以解決NFWI算法在數(shù)據(jù)集中因大量交集計(jì)算導(dǎo)致效率低的問(wèn)題。DiffNFWI算法在DiffNodeset結(jié)構(gòu)的基礎(chǔ)上加入權(quán)值得到WDiffNodeset結(jié)構(gòu),利用該結(jié)構(gòu)挖掘加權(quán)頻繁項(xiàng)集,從而降低算法的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果表明,相比NFWI算法,DiffNFWI算法的運(yùn)行效率較高。下一步將采用基于集合位圖表示的前綴編碼模型來(lái)提高算法性能,并針對(duì)加權(quán)最大頻繁項(xiàng)集挖掘、閉頻繁項(xiàng)集挖掘以及top-k頻繁項(xiàng)集挖掘等任務(wù)進(jìn)行深入研究。