基于DiffNodeset結(jié)構(gòu)的最大頻繁項集挖掘算法

尹 遠，張 昌，文 凱，鄭云俊

(1.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065； 2.中國電信股份有限公司 重慶分公司，重慶 401121; 3.重慶信科設(shè)計有限公司，重慶 401121)(*通信作者電子郵箱wszhangchang@yeah.net)

0 引言

數(shù)據(jù)挖掘指的是挖掘大量數(shù)據(jù)之間的隱藏關(guān)系，數(shù)據(jù)挖掘的分析方法包括分類、估計預(yù)測、頻繁項集挖掘和聚類等。其中頻繁模式和關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的主要研究領(lǐng)域，Agrawal等[1]于1994年提出頻繁模式挖掘算法——Apriori算法，Han等[2]于2004年提出了頻繁模式增長(Frequent Pattern growth, FP-growth)算法等。但如果數(shù)據(jù)庫比較龐大并且支持度閾值設(shè)置較低時，頻繁項集的數(shù)量就會非常龐大，這是頻繁項集挖掘所面臨的一個問題。

在數(shù)據(jù)挖掘中，通過挖掘最大頻繁項集來代替挖掘頻繁項集可以大大地提升系統(tǒng)的運行效率，近年來已經(jīng)有很多專家學(xué)者對最大頻繁項集挖掘算法進行了較為深入的研究。Bayardo[3]最先提出了最大頻繁項集挖掘的概念并提出了一種最大頻繁項集挖掘算法——Max-Miner算法,該算法主要采用了廣度優(yōu)先搜索的思想,然后結(jié)合了前瞻剪枝策略以及動態(tài)排序技術(shù)，由于廣度優(yōu)先搜索用于挖掘最大頻繁項集時有缺陷，所以該算法性能不夠好。Agrawal等[4]提出了DepthProject算法，該算法融合了深度優(yōu)先搜索的思想以及動態(tài)記錄的技術(shù)，其算法性能較Max-Miner算法提升了一個數(shù)量級。Burdick等[5]提出了一種最大頻繁項集挖掘算法(MAximal Frequent Itemset Algorithm, MAFIA)，該算法將項集網(wǎng)格和子集樹作為框架，同時采用縱向位圖來存儲數(shù)據(jù)，然后結(jié)合了父等價剪枝、前瞻剪枝等多種剪枝技術(shù)，其算法性能較DepthProject算法提升了3～5倍。Zou等[6]提出SmartMiner算法并采用了與MAFIA相似的數(shù)據(jù)存儲結(jié)構(gòu)，但該算法采用了動態(tài)記錄啟發(fā)式深度優(yōu)先搜索策略，所以該算法特點在于產(chǎn)生的搜索樹相對MAFIA與GenMax[7]算法更小，算法性能相對更優(yōu)。沈戈暉等[8]提出了基于N-list的MAFIA(N-list based MAFIA, NB-MAFIA)，該算法在基于深度優(yōu)先搜索的框架之下，引入了基于項集前綴樹節(jié)點鏈表的項集表示方法N-list[9]來表示項集，最后再結(jié)合相應(yīng)的優(yōu)化剪枝策略和超集檢測策略來提升算法的效率，但還可以針對稀疏數(shù)據(jù)集場景下的NB-MAFIA的性能進行進一步優(yōu)化。

針對現(xiàn)有的最大頻繁項集挖掘算法挖掘的時間消耗較大的問題，本文提出了一種基于DiffNodeset[10]結(jié)構(gòu)的最大頻繁項集挖掘(DiffNodeset Maximal Frequent Itemset Mining, DNMFIM)算法。該算法采用了一種新的數(shù)據(jù)結(jié)構(gòu)DiffNodeset來實現(xiàn)高效的求交集運算以及支持度的快速計算，并引入一種新的線性復(fù)雜度的連接方法來降低兩個DiffNodeset在連接過程中的復(fù)雜度，避免了多次的無效計算。實驗結(jié)果表明，DNMFIM算法在時間效率方面優(yōu)于MAFIA與NB-MAFIA，該算法在不同類型數(shù)據(jù)集中進行最大頻繁項集挖掘時均有良好的效果。

1 相關(guān)知識

1.1 基本概念

假定I={i1,i2,…,im}是m個不同項組成的集合，包含n(0≤n≤m)個項的集合稱為項集。

定義1[9]頻繁項集。若項集X的支持度大于或等于用戶規(guī)定的最小支持度閾值，則稱X是頻繁項集。

定義2[5]最大頻繁項集。若頻繁項集X的任意超集Y均不是頻繁項集，則稱X為最大頻繁項集。

1.2 前序后序編碼樹

首先給定一個數(shù)據(jù)庫和設(shè)置一個最小支持度閾值，然后開始構(gòu)建前序后序編碼樹(Pre-order and Post-order Code tree, PPC-tree)[9]。

PPC-tree由根節(jié)點(root)以及項目的前綴子樹組成。項目前綴子樹的每個節(jié)點由5個部分構(gòu)成(item-name、count、children-list、pre-order、post-order)，這5部分分別表示節(jié)點的項目名稱、經(jīng)過該節(jié)點的事務(wù)數(shù)目、子節(jié)點、前序編碼、后序編碼。構(gòu)建PPC-tree的算法[9]如算法1所示(詳細的構(gòu)建過程參考文獻[9])。

算法1 Construct-PPC-tree(DB,minSup)。

輸入 事務(wù)數(shù)據(jù)庫DB和minSup；

輸出 生成所有頻繁1-項集和PPC-tree。

1)

[Frequent 1-itemsets generation]

2)

According tominSup,scanDBonce to findF1, the set of

frequent 1-itemsets (frequent items), and their supports.

3)

SortF1in support descending order asL1,

4)

for each transactionTransinDBdo

5)

Select the frequent items inTransand sort out them according

to the order ofF1. Let the sorted frequent-item list inTrans

be [p|P], wherepis the first element andPis the remaining list.

6)

Call insert tree([p|P],Tr).

7)

Scan PPC-tree to generate the pre-order and the post-order of

each node.

8)

ReturnTrandL1.

根據(jù)算法1來構(gòu)建TB-tree，設(shè)事務(wù)數(shù)據(jù)庫DB如表1所示(minSup=0.4),圖1是針對事務(wù)數(shù)據(jù)庫DB運行算法之后構(gòu)建成的PPC-tree。

表1 事務(wù)數(shù)據(jù)集DBTab. 1 Transaction data set DB

圖1 PPC-treeFig. 1 PPC-tree

根據(jù)圖1的PPC-tree，各節(jié)點的節(jié)點編碼歸納如表2所示，該1-項集的Nodesets表有助于更加清楚地理解DiffNodeset的連接過程。

表2 1-項集的NodesetsTab.2 Nodesets of 1-itemsets

給定一個PPC-tree，有以下的性質(zhì)[9]：

性質(zhì)1 對于PPC樹中的任意兩個節(jié)點N1和N2(N1≠N2),當且僅當N1.pre-orderN2.post-order時，則稱N1是N2的祖先。

證明 由PPC-tree構(gòu)建算法可知，祖先節(jié)點總是先于子孫節(jié)點構(gòu)建，因此，祖先節(jié)點對應(yīng)的pre-order總是小于子孫節(jié)點的pre-order；又因為祖先節(jié)點總是晚于孩子節(jié)點構(gòu)建完成，因此祖先節(jié)點對應(yīng)的pre-post值總是大于子孫節(jié)點的pre-post。

性質(zhì)2 對于在PPC-tree中任何兩個具有相同節(jié)點名稱的N1和N2(N1≠N2)，如果N1.pre-order

證明 若N1.pre-order

1.3 DiffNodeset結(jié)構(gòu)

近年來，數(shù)據(jù)挖掘領(lǐng)域為了提高頻繁項集的挖掘效率，已經(jīng)有很多種數(shù)據(jù)結(jié)構(gòu)被提出，例如：Node-list[11]、N-list、Nodeset[12]等。它們都是基于前綴編碼樹來存儲頻繁項集的信息，Nodeset相對于N-list、Node-list的區(qū)別在于N-list和Node-list需要前序編碼和后序編碼來表示節(jié)點,而Nodeset只需要前序(或后序)編碼來表示節(jié)點,所以Nodeset結(jié)構(gòu)對內(nèi)存的消耗更小。但在很多數(shù)據(jù)集中采用Nodeset結(jié)構(gòu)時，產(chǎn)生的節(jié)點集基數(shù)會很大。針對這一問題，引入了一種新的項集表示方法DiffNodeset[10],它只表示項集在生成頻繁項集產(chǎn)生的差異節(jié)點集，產(chǎn)生的DiffNodeset基數(shù)相對于Nodeset結(jié)構(gòu)少得多。DiffNodeset是一種高度壓縮且結(jié)構(gòu)簡便的數(shù)據(jù)結(jié)構(gòu)，可以高效地挖掘頻繁項集。

DiffNodeset是一種基于Nodeset的一種數(shù)據(jù)結(jié)構(gòu)，這里介紹一下Nodeset結(jié)構(gòu)及定義[10](以下定義及詳細證明過程參考文獻[10])。

定義3 設(shè)L1是按支持度降序排列的頻繁項集，對于任意兩個項集i1，i2(i1，i2∈L1) ，若存在項集i2在i1之前，則用i1?i2來表示。

定義4 前序后序編碼(Pre-Post code, PP-code)給定一個PPC-tree，節(jié)點N的PP-code為(N.pre-order,N.post-order,count)。該PP-code包含前序編碼和后序編碼，文獻[12]中的原始定義只包含前序編碼，由于前序和后序都可以唯一標識PPC樹中的節(jié)點，所以差異可以忽略不計。在本文中，采用定義4來定義項目的節(jié)點集是為了設(shè)計出構(gòu)建2-項集DiffNodeset的有效方法。

定義5 1-項集的Nodesets。假設(shè)一個PPC-tree，每一個i的節(jié)點集都按PP-codes中的pre-order的升序排列(1-項集的Nodesets如表2所示)。

性質(zhì)3 給定一個項集，假設(shè){(x1,y1,z1), (x2,y2,z2),…, (xl,yl,zl)}是相應(yīng)的Nodeset，在此存在x1

證明 根據(jù)定義5，有x1

定義6 2-項集DiffNodesets。假設(shè)兩個項集i1和i2(i1,i2∈L1∩i1?i2),給它們的節(jié)點集分別定義為Nodesesti2和Nodesetsi2。2-項集i1i2的節(jié)點集可以用DiffNodesetsi1i2表示，定義如下：

DiffNodesetsi1i2= {(x.pre-order,x.count) |x∈Nodesetsi1∩?(?y∈Nodesetsi2,the node corresponding toyis an ancestor of the node corresponding tox)}(DiffNodesetsi1i2中的元素按前序編碼pre-order的升序排序)。

為了較好地理解該定義，以b和f的Nodeset為例說明，從表2可得b和f的Nodeset分別為(6，11，4)和(3，3，1)(12，10，3)(10，7，1)。bf的DiffNodeset連接過程如下：顯然根據(jù)性質(zhì)1可得(6，11，4)是(12，10，3)(10，7，1)的祖先而不是(3，3，1)的祖先，那么根據(jù)該定義可得bf的DiffNodeset為(3，1)，同理可得bc的DiffNodeset為(2，1)。

假設(shè)兩個項集i1、i2的長度分別為m和n，可以通過檢查i1中每個元素與i2中每個元素之間的祖先-子孫關(guān)系來構(gòu)建DiffNodesetsi1i2。這種遍歷所有元素的方法顯然效率會比較低下，因為它的計算復(fù)雜度是O(m*n)。在此，通過性質(zhì)1和性質(zhì)3來引入一種線性復(fù)雜度的方法來構(gòu)建2-項集DN(),這種方法的復(fù)雜度為O(m+n)，大大降低了計算的復(fù)雜度。

定義7k-項集DiffNodesets。假設(shè)P=i1i2…ik-2ik-1ik是一個項集(滿足ij∈L1且i1?i2?i3?…?ik)。P1=i1i2…ik-2ik-1的Nodeset記為NodesetP1，P2=i1i2…ik-2ik的Nodeset記為NodesetP2。P的DiffNodeset記為DiffNodesetP可以由如下計算得到：

DiffNodesetP=NodesetP1/NodesetP2

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

性質(zhì)4 假設(shè)P=i1i2…ik-2ik-1ik，P1=i1i2…ik-2ik-1，那么P的支持度計算方式如下：

support(P)=support(P1)-∑(E∈DNP)E.count

其中DNP即為DiffNodesetP。

證明 假設(shè)X=i1i2…ik-3ik-2，Y=i1i2…ik-3ik-1。X、Y、P1和P2的Nodeset記為NSX、NSY、NS1、NS2。在k-項集的Nodeset中存在NS1=NSX∩NSY，在k-項集的DiffNodeset中存在DN1=NSX/NSY。

support(P1)=∑(E∈NS1)E.count=

∑(E∈NSP∪DNP)E.count=

∑(E∈NSP)E.count+∑(E∈DNP)E.count=

support(P)+∑(E∈DNP)E.count

性質(zhì)5 假設(shè)P=i1i2…ik-2ik-1ik是一個項集(滿足ij∈L1且i1?i2?i3?…?ik)。P1=i1i2…ik-2ik-1的DiffNodeset記為DN1，P2=i1i2…ik-2ik的DiffNodeset記為DN2。P的DiffNodeset記為DNp，其計算式如下：

DNP=DN2/DN1

證明 假設(shè)X=i1i2…ik-3ik-2，Y=i1i2…ik-3ik-1。X、Y、P1和P2的Nodeset記為NSX、NSY、NS1、NS2。在k-項集的Nodeset中存在NS1=NSX∩NSY，在k-項集的DiffNodeset中存在DN1=NSX/NSY。

根據(jù)上述兩個條件可以得到：

NSX=(NSX∩NSY)∪(NSX/NSY)=NS1∪DN1

NS1∩DN1=?

然后得到NS1=NSX/DN1。

同理可得:

NSX=NS2∪DN2

NS2∩DN2=?

NS2=NSX/DN2

最后可得:

DNP=NS1/NS2=

(NSX/DN1)/(NSX/DN2)=NSX∩(DN1)T∩DN2=

DN2∩(DN1)T=DN2/DN1

DiffNodeset采用性質(zhì)5可以使DiffNodeset直接計算構(gòu)成k-項集的DiffNodeset,不需要再進行Nodeset的計算。

2 DNMFIM算法

2.1 基于DiffNodeset的深度優(yōu)先搜索算法

DNMFIM算法采用了集合枚舉樹作為搜索空間，然后集合深度優(yōu)先搜索的思想進行處理，即對于集合枚舉樹中的每個節(jié)點，都需要與右側(cè)的鄰居節(jié)點進行合并產(chǎn)生子節(jié)點，同時求并集得到子節(jié)點所表示的項集。

定義8 在集合枚舉樹中的節(jié)點C的項集記為C.head,該節(jié)點的可擴展項的集合記為C.tail,每個擴展項集都是C節(jié)點的可擴展1-項集。

深度優(yōu)先搜索策略的核心思想是檢測每個節(jié)點的項集C.head與該節(jié)點的可擴展項集C.tail中的每個可擴展項i的并集C.head∪i的支持度,如果每個并集的支持度都小于minSup,那么說明在頻繁模式樹中C就是一個葉節(jié)點。然后再檢測C.head是否是最大頻繁項集MFI中任意集合的子集，若不是，就將C.head加入到MFI。如果C.head∪i支持度均大于minSup，則繼續(xù)向下遞歸。結(jié)合DiffNodeset的深度優(yōu)先搜索算法融合了文獻[10]中基于DiffNodeset交集的思想，算法的流程如算法2所示。集合枚舉樹示例如圖2所示。

圖2 集合枚舉樹Fig.2 Set-enumeration tree

算法2 基于DiffNodeset交集求解算法[10]。

輸入 當前節(jié)點N1與右側(cè)鄰居節(jié)點N2；

輸出 子節(jié)點DiffNodeset。

1)

DNxy←?;

2)

k←0 andj←0;

3)

lx← the length ofNx(Nodeset ofix) andly←the length of

Ny(Nodeset ofiy);

4)

Whileklydo

5)

IfNx[k].post-order>Ny[j].post-orderthen

6)

j←j+1;

7)

Else

8)

IfNx[k].post-order

Nx[k].pre-order>Ny[j].pre-orderthen

9)

k←k+1;

10)

Else

11)

DNxy←DNxy∪{(Nx[k].post-order,

Nx[k].count)};

12)

k←k+1;

13)

Endif

14)

Endif

15)

Endwhile

16)

Ifk

17)

Whilek

18)

DNxy←DNxy∪{(Nx[k].post-order,Nx[k].count)};

19)

k←k+1;

20)

Endwhile

21)

Endif

22)

ReturnDNxy

實際上，構(gòu)建2-項集DN()采用了雙向比較的策略來構(gòu)建ixiy的DiffNodeset。根據(jù)雙向比較原理，構(gòu)建2-項集DN()的計算復(fù)雜度為O(m+n)，其中m和n分別為對應(yīng)節(jié)點集的長度。構(gòu)建過程的偽代碼如算法2所示。

構(gòu)建2-項集DN()需要比較兩個Nodeset中PP-codes，直到其中一個Nodeset的所有元素都比較完畢。對于這種兩個元素之間的比較，有三條原則來降低比較的復(fù)雜度。

原則一 如偽代碼的第5)行，若存在Nx[k].post-order>Ny[j].post-order，則表明對應(yīng)于Ny[j]的節(jié)點不是對應(yīng)于Nx[k]的節(jié)點的祖先，由于各項集的Nodeset都是按照post-order的升序(根據(jù)性質(zhì)3),因此就不用再考慮Ny[j]，并選擇Ny[j+1]與Nx[k]進行比較，如偽代碼第5)、6)行所示。

原則二 如偽代碼的第8)行，若存在Nx[k].post-orderNy[j].pre-order，這種情況表示對應(yīng)于Ny[j]的節(jié)點是對應(yīng)于Nx[k]的節(jié)點的祖先(根據(jù)性質(zhì)1)。根據(jù)定義6，Nx[k]是不可取的，所以就選擇Nx[k]的下一個元素Nx[k+1]來進行比較，如偽代碼的第9)行所示。

原則三 如偽代碼第10)行，若存在Nx[k].post-order

當所有的比較完成之后，需檢查在ix的Nodeset中是否存在一些未參與比較的元素，根據(jù)定義6，這些元素是可取的。然后生成與這些元素相對應(yīng)的所有結(jié)果，并添加到ixiy的DiffNodeset，如偽代碼第16)行到第21)行所示。最后輸出所有2-項集的DiffNodeset。

2.2 優(yōu)化策略

性質(zhì)6[13]設(shè)X∈C.head，y∈C.tail，若存在X的事務(wù)集與X∪{y}完全相同，即t(X)=t(X∪{y})，那么?S∈C.tail，都有X∪S與X∪{y}∪S的支持度相同。

證明 由于t(X)=t(X∪{y}),則support(X)=support(X∪{y})，所以任意包含X的事務(wù)必然包含y。所以，包含S的任意項集也必然包含y，所以support(X∪S)=support(X∪{y}∪S)。

DNMFIM算法根據(jù)性質(zhì)6采用了父等價剪枝技術(shù)來縮小搜索空間。當搜索C節(jié)點時，若遇到性質(zhì)6中的情況，就可以將y從C.tail中刪除，并放入C.head，這樣會提高挖掘的效率,并不會影響最大頻繁項集挖掘的準確性。

性質(zhì)7[14]若當前節(jié)點與右側(cè)所有鄰居節(jié)點的并集是已挖掘的最大頻繁項集的子集，則以當前節(jié)點為根節(jié)點的子樹不可能存在最大頻繁項集。

證明 反證法。若以當前節(jié)點為根節(jié)點的子樹中存在最大頻繁項集，那么該最大頻繁項集必然不是已挖掘的最大頻繁項集的子集。

得證

由于每將一個項集加入MFI時，就必須檢測該項集的超集在MFI中是否存在，這個過程稱之為超集檢測。

定義9 局部最大頻繁項集。給定一個節(jié)點P,MFI中只有一部分是P.head的超集，則這部分項集稱之為P的局部最大頻繁項集(Local MFI, LMFI)。

本文引入一種在MAFIA[5]中所采用的超集檢測策略，從而進一步提升算法效率。對于任意的y∈P.tail，將P.head與P的可擴展1-項集y合并得到節(jié)點P1。顯然，P1的LMFI都包含y元素且P1的LMFI是P的LMFI的子集。將P的LMFI進行排序，包含y的項集集合就是P1節(jié)點的LMFI。若將以P節(jié)點為根節(jié)點的子樹搜索完成時，那么在該子樹上所挖掘到的所有MFI都將是P的超集。所以當有新的項集加入P的MFI的項集時，也會將該項集加入到P的LMFI中。故是否要將一個項集加入到MFI，只需要判斷該節(jié)點的LMFI是否為空即可，即實現(xiàn)超集檢測。超集檢測算法的詳細過程如算法3所示。

算法3 超集檢測算法[5]。

輸入 進行剪枝后的項集M；

輸出 超集檢測之后的MFI。

1)

MFI←?

2)

root.head←?

3)

root.tail←DB

4)

HUT=C.head∪C.tail

5)

If(HUTis inMFI)

6)

Stop searching and return

7)

Endif

8)

Count all children,usePEPto trim the tail,and reorder by

increasing support

9)

For each itemiinC.tail

10)

C.extension=C.head∪{i}

11)

If(all extensions are frequent)

12)

SortMFIby new itemiand update left and rightLMFI

pointers forCn(itemsets put inLMFIleftwhich include

i,else put inLMFIright)

13)

Adjust rightLMFIpointer ofCfor any new itemsets added

toMFI

14)

Endif

15)

Endfor

16)

If(C.LMFIis empty) do

17)

addC.headtoMFI

18)

Endif

NB-MAFIA采用的是基于N-list的的最大頻繁項集挖掘方法，N-list的高壓縮率和高效的求交集方法可以實現(xiàn)項集支持度的快速計算，該算法采用了MAFIA的優(yōu)化剪枝與超集檢測策略，所以NB-MAFIA性能相對于MAFIA提升很多。但NB-MAFIA在稀疏數(shù)據(jù)集中運行時效果還需進一步改善，本文中提出的DNMFIM算法針對這一點進行了改進，DNMFIM算法的優(yōu)勢在于引入一種新的線性復(fù)雜度的連接方法來降低連接兩個DiffNodeset在連接過程中的復(fù)雜度，從而避免了多次無效的計算，由于這一特性,DNMFIM算法能夠快速挖掘稠密數(shù)據(jù)集中的最大頻繁項集，再結(jié)合相應(yīng)的優(yōu)化剪枝策略與超集檢測策略使DNMFIM算法在稀疏數(shù)據(jù)集中依然有良好的效果。

3 實驗結(jié)果及分析

將DNMFIM算法與經(jīng)典的最大頻繁項集挖掘算法MAFIA及其改進算法NB-MAFIA進行比較。在不同類型的數(shù)據(jù)集中運行這三種算法來對比這三種算法的時間效率。用C++語言在實驗環(huán)境為Inter Core i5 3317U@1.7 GHz CPU，內(nèi)存4 GB，64位操作系統(tǒng)的設(shè)備上實現(xiàn)了DNMFIM算法 MAFIA和NB-MAFIA。在每組實驗中,這三種算法所挖掘到的最大頻繁項集都是相同的,從而驗證了BNMFI算法的正確性。在本次實驗中選取了稠密型數(shù)據(jù)集Connect、稀疏型數(shù)據(jù)集Retail以及由IBM Almaden生成的人工數(shù)據(jù)集T10I4D100K來作為本實驗的測試數(shù)據(jù)集,數(shù)據(jù)集參數(shù)如表3所示。然后，通過改變最小支持度閾值來進行最大頻繁項集的挖掘。最后，通過對比分析了這三種算法在不同數(shù)據(jù)集中的時間消耗情況，結(jié)果如圖3所示。為了保證實驗結(jié)果的準確性，本人在同一臺設(shè)備上進行了實驗。

由圖3可以看出，DNMFIM算法在時間效率方面效果優(yōu)于MAFIA與NB-MAFIA，該算法在不同類型數(shù)據(jù)集中進行最大頻繁項集挖掘時均有良好的效果。當這三種算法在稠密數(shù)據(jù)集Connect中運行時，DNMFIM算法性能優(yōu)于其他兩種算法，在最小支持度閾值設(shè)置得較小時優(yōu)勢更加明顯，隨著最小支持度閾值的逐漸增加算法的運行時間越來越短，DNMFIM算法的優(yōu)勢也越來越不明顯。當這三種算法在稀疏數(shù)據(jù)集Retail中運行時，其運行時間相比在稠密數(shù)據(jù)集中較長一些。當最小支持度閾值為0.05%時，DNMFIM算法的運行時間較少，約為MAFIA運行時間的1/5；隨著最小支持度閾值的升高，DNMFIM算法的優(yōu)勢越來越不明顯，當最小支持度閾值大于0.2%時，三種算法的運行時間基本一致。當這三種算法在人工數(shù)據(jù)集T10I4D100K中運行時，由于在存儲數(shù)據(jù)和處理數(shù)據(jù)方面的結(jié)構(gòu)性優(yōu)勢，DNMFIM算法和NB-MAFIA的運行時間明顯優(yōu)于MAFIA，在該數(shù)據(jù)集中DNMFIM算法仍保持著最優(yōu)的性能。

表2 數(shù)據(jù)集參數(shù)Tab. 2 Dataset parameters

圖3 不同算法運行時間對比Fig. 3 Runtime comparison of different algorithms

4 結(jié)語

本文提出了一種新的最大頻繁項集挖掘整合算法——DNMFIM算法。該算法采用了一種新的數(shù)據(jù)結(jié)構(gòu)DiffNodeset來實現(xiàn)高效的求交集以及支持度的快速計算，并引入一種新的線性復(fù)雜度的連接方法來降低連接兩個DiffNodeset在連接過程中的復(fù)雜度，從而避免了多次無效的計算。實驗結(jié)果表明，DNMFIM算法在不同類型的數(shù)據(jù)集中挖掘最大頻繁項集的性能優(yōu)于MAFIA與NB-MAFIA。隨著互聯(lián)網(wǎng)數(shù)據(jù)的飛速發(fā)展，將DNMFIM算法與Spark平臺相結(jié)合，從而研究出并行化處理大數(shù)據(jù)的最大頻繁項集挖掘算法，將是下一步需要研究的方向。