曾 毅，張福泉

(1.廣西大學(xué)行健文理學(xué)院 計算機與信息工程系，廣西 南寧 530005； 2.北京理工大學(xué) 計算機學(xué)院，北京 100081)

0 引 言

頻繁模式挖掘問題是當(dāng)前數(shù)據(jù)分析領(lǐng)域的一個研究熱點，許多現(xiàn)實問題中可通過頻繁模式挖掘?qū)?shù)據(jù)實現(xiàn)有效的分析，提取出感興趣的信息[1]。話題預(yù)測、金融行情的預(yù)測、購物籃問題等均為頻繁項集挖掘的主要應(yīng)用領(lǐng)域[2]。頻繁項集挖掘支持向下閉包屬性，該屬性可在剪枝過程中極大減少后續(xù)項集的數(shù)量，提高挖掘的效率。而高效用項集挖掘[3]并不支持向下閉包屬性，因此剪枝過程中保留了過多的候選項集。許多應(yīng)用將事務(wù)以序列形式存儲于數(shù)據(jù)庫中，組成了序列數(shù)據(jù)庫[4]，序列模式的搜索空間明顯大于其它模式，其計算復(fù)雜度也明顯大于其它模式類型。

在高效用序列模式的挖掘問題中，提高剪枝的效率與搜索的速度一直是決定挖掘效果的關(guān)鍵指標(biāo)[5]。文獻[6]提出時空效率均顯著提升的高效用序列模式挖掘算法，該算法提出1-2-UM和2-2-UM的效用信息列表結(jié)構(gòu)，快速剪枝非候選序列。文獻[7]提出了簡潔的高效用模式挖掘算法，該算法設(shè)計了LIT結(jié)構(gòu)保存效用信息，實現(xiàn)了高效的剪枝策略。文獻[8]對候選模式自動計算最適合的間隔約束，并且設(shè)計了3種剪枝策略來提高算法的執(zhí)行效率。文獻[6-8]對于蛋白質(zhì)序列、DNA序列、行為序列等小規(guī)模數(shù)據(jù)集表現(xiàn)出較好的效果，但是對于大規(guī)模數(shù)據(jù)集未能實現(xiàn)理想的效果。

為了提高高效用序列模式挖掘算法對于大規(guī)模數(shù)據(jù)集的處理效果，設(shè)計了基于多效用閾值的分布式高效用序列模式挖掘算法。該算法采用純數(shù)組結(jié)構(gòu)維護效用信息，采用前綴樹trie-tree維護序列模式，這兩種數(shù)據(jù)結(jié)構(gòu)有效地提高挖掘過程的時空效率。設(shè)計了初步剪枝策略與深度剪枝策略，遞歸地從1-項集與2-項集中排除非候選模式。算法在評估前綴樹節(jié)點的過程中，各個節(jié)點的挖掘順序獨立于其它同級節(jié)點，所以可以并行地處理前綴樹中的所有子節(jié)點，并且不會影響結(jié)果。據(jù)此給出了本算法的分布式實現(xiàn)方案，能夠在云計算、GPU(graphics processing unit)、多核處理器等平臺上實現(xiàn)并行計算，從而實現(xiàn)快速的挖掘處理。

1 問題模型

設(shè)I={i1,i2,…,in} 為一個項集的集合，in為一個項集，設(shè)s={e1,e2,…,er} 為一個定量序列，表示一個按時間升序排列的定量模式列表，ej(1≤j≤r) 為一個模式，序列的每個模式ej描述為一個序列形式 (x1,x2,…,xm)，xk(1≤k≤m) 為一個定量的項。定量序列的數(shù)據(jù)庫SDB由若干的定量序列會話集組成，即SDB={s1,s2,…,sz}，sy(1≤y≤z) 為SDB的第y個序列。序列sy包含一個元組 (SIDy,γy)，SIDy為序列的ID，γy為sy序列的內(nèi)容。如果l=|s|， 那么序列s稱為l-序列，其中|s|=∑ej∈s|ej|， |ej| 為模式ej中的項數(shù)量，l為序列s的長度，序列的大小定義為序列中包含的模式集數(shù)量，表示為r。

設(shè)α=，β= 為兩個獨立的序列，如果存在j1

表1 會話數(shù)據(jù)庫實例

表2 項的利潤與最小效用閾值

定義1 序列s中項ij的內(nèi)部效用定義為s中ij全部定量的總和，記為iu(ij,s)。 最大內(nèi)部效用定義為s中ij的最大值，記為iumax(ij,s)。 項ij的外部效用定義為項ij的外部權(quán)重(例如：超市購物籃模型的利潤)，記為eu(ij)。

定義2 序列s中項ij的效用定義為外部效用與內(nèi)部效用的乘積，記為u(ij,s)=eu(ij)×iu(ij,s)。

定義3 序列s中項ij的最大效用定義為外部效用與最大內(nèi)部效用的乘積，記為umax(ij,s)=eu(ij)×iumax(ij,s)。

定義4 序列s的效用定義為序列s中所有項的效用總和，記為

(1)

定義5s中模式p的效用定義為s中p的最大效用，記為u(p,s)。

定義6SDB中模式p的實際效用定義為SDB所有序列的模式效用之和，記為

(2)

定義7 序列數(shù)據(jù)庫SDB的效用定義為SDB所有序列的效用之和，記為

(3)

定義8 最小效用閾值的百分比記為δ，最小效用閾值記為MIU，定義為

λ=δ×su(SDB)

(4)

定義9 模式p的序列加權(quán)效用(sequence weighted utility，SWU)定義為SDB中所有p的序列效用之和，記為SWU(p)。 如果SWU(p)≥λ， 則稱p為高效用序列模式

(5)

2 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計

2.1 會話序列的字典樹(前綴樹)結(jié)構(gòu)

定義10 滿足以下3個條件的數(shù)據(jù)結(jié)構(gòu)定義為字典樹trie-treeT：①T的每個節(jié)點包含一個序列與其效用值，根節(jié)點為空。②T中每個節(jié)點p的子節(jié)點可分為I-級聯(lián)形式或者S-級聯(lián)形式。③T的所有節(jié)點按照字母順序升序排列。本文修改了trie-tree結(jié)構(gòu)，根節(jié)點設(shè)為“<>”，其它節(jié)點包含SDB中所有序列的模式與效用值，稱為索引效用列表。

2.2 基于數(shù)組的低內(nèi)存快速挖掘策略

大多數(shù)算法[9]使用效用矩陣與剩余效用矩陣分別保存序列的效用與剩余效用，效用矩陣存儲效用值的效果較好，但是需要消耗大量的內(nèi)存。為了解決這個問題，設(shè)計了純數(shù)組的效用數(shù)據(jù)結(jié)構(gòu)，減少了內(nèi)存的消耗。將序列的效用與剩余效用分別保存于3個數(shù)組中，分別稱為會話序列數(shù)組、效用數(shù)組與剩余效用數(shù)組。

定義11 分界項定義為將序列分為子項集的項，記為ditem，ditem的值設(shè)為0。

定義12 會話序列數(shù)組定義為保存s中所有項的一維數(shù)組，記為seq，seq的大小等于s的大小r加s的長度l。seq中索引i的元素表示為seq[i]，其中seq[i]為索引i的項。

定義13 給定一個序列s，項i在s中索引j的外部效用定義為i對于j的定量，記為iu(i,j,s)。

定義14 效用列表定義為保存序列s所有項效用的一維數(shù)組，記為ulist，ulist的大小等于s的大小r加s的長度l。

定義15 剩余效用記為ru，剩余效用列表定義為保存序列s所有項剩余效用的一維數(shù)組，記為rlist。rlist的大小等于s的大小r加上s的長度l。rlist中索引i的項剩余效用等于在ulist中j>i的項集效用之和

(6)

圖1是3個列表的例子，seq、ulist、rlist這3個列表中的分界項分別為索引3、7、11，序列中e的第一個索引為2，因此ulist中e的效用為ulist[2]=iu(e,2,S2)×eu(e)=6×4=24。 索引5的剩余效用值為rlist(S2)[5]=ulist[6]+ulist[8]+ulist[9]+ulist[10]=8+12+72+12=104。

圖1 3個列表的例子

2.3 索引效用列表

定義16 序列模式的索引記為ilist(p)。假設(shè)序列s包含n個模式，每個模式為p=，s中p的索引集稱為p的索引列表，記為ilist(p)。

本文設(shè)置一個索引效用列表保存p的所有索引與效用。

定義17 給定一個模式p，對p進行I-級聯(lián)或S-級聯(lián)操作獲得超模式p′，s中索引i處的索引效用值定義為p′的索引效用值，記為iulist(p′,i,s)

iulist(p′,i,s)=max{iulist(p,j,s)|?p的序號ins∧j∧i}+ulist(s)[i]

(7)

定義18 序列s中模式p的索引效用列表記為iulist(p)，定義為

(8)

SDB中模式p的索引效用列表定義為

(9)

定義19 序列s中模式p的前綴效用記為peu，定義為

(10)

式中：模式p的peu定義為

peu(p,s)=max{peu(p,i,s)|?iins}

(11)

定義20 節(jié)點p的效用上限記為peu，節(jié)點p在trie-Tree的子節(jié)點上限也是peu。如果peu(p)<λ， 那么可安全地剪枝p的子樹，縮小挖掘程序的搜索空間。SDB中模式p的peu定義為

(12)

定義21 減少的序列效用記為rsu，對模式p進行I-級聯(lián)或者S-級聯(lián)處理產(chǎn)生超模式p′，序列s中p的rsu定義為

(13)

SDB中序列p的rsu定義為

(14)

2.4 生成序列的iulist

算法對序列p進行I-級聯(lián)或者S-級聯(lián)處理需要獲得超序列p′的iulist?？紤]一個1-項模式a，模式a同時出現(xiàn)于序列S2,S3,S4,S5中。S2中a分別出現(xiàn)于索引1、4、8處，對應(yīng)的效用分別為12、6、12。S2、S3、S4、S5的iulist(a)如圖2所示。

圖2 序列iulist的例子

包含a的序列中通過I-級聯(lián)與S-級聯(lián)對a進行擴展?？紤]序列ae，從iulist(a)生成iulist(ae)。S2中ae出現(xiàn)于索引2與10處，其效用值分別為12+24=36、12+12=24。采用上述方法可獲得S3、S4與S5的iulist(ae)，最終的iulist(ae)如圖3所示。

圖3 最終的iulist例子

從iulist(a)也可產(chǎn)生iulist(ae)。S2中ae出現(xiàn)于索引10處，而S2中a出現(xiàn)于索引1、4處，效用值分別為12與6。模式a也出現(xiàn)于S2的索引8處，但是并未生成該索引的ae，即iulist(ae,10,S2)=max(12,6)+12=24。 以相同的方式建立S4的iulist(ae)，最終的iulist(ae)如圖4所示。

圖4 最終的iulist(ae)例子

采用I-級聯(lián)與S-級聯(lián)從序列p產(chǎn)生p′的過程中，僅僅掃描了序列中p之后的子序列，節(jié)約了掃描的時間。

2.5 效用上限與初步剪枝策略

如果算法在構(gòu)建候選序列集之前，初步剪枝S-級聯(lián)與I-級聯(lián)的項，則可以加快挖掘程序的速度。考慮算法第一階段的1-項模式集，每個模式p包含1個項i與其peu值，表示為peu(i)。第一階段的iulist為空，根據(jù)定義20計算peu(i)值，如果項i滿足peu(i)<λ，那么稱之為低效項。提出一個剪枝策略來過濾S-級聯(lián)與I-級聯(lián)項集的低效項。

定義22 效用的上限記為euu(s′)，假設(shè)s′為序列s的超序列，那么euu(s′)定義為

euu(s′)=u(s)+peu(i)

(15)

理論1 給定一個序列s，其超序列為s′，如果s是s′的前綴或者s′=s， 那么u(s′)≤euu(s′)。

證明：設(shè)s′為序列s的超序列，那么u(s′)=u(s)+u(i)， 可得u(i)≤peu(i)。 因此u(s′)≤u(s)+peu(i)， 且u(s′)≤euu(s′)。 根據(jù)理論1，euu(s) 是s的效用上限，所以當(dāng)euu(s)<λ， 可在不影響挖掘結(jié)果的情況下對s前綴的超序列進行安全的剪枝。

定義23 后綴最小效用記為SMU，定義為

SMU(p)=min(MIU(p),MIU(ext(p)))

(16)

式中：ext()為模式的級聯(lián)擴展，MIU為模式的最小效用。

定義24 引入文獻[10]的估計效用共生結(jié)構(gòu)，記為EUCS，EUCS是一個三角矩陣，其2-項集入口定義為

EUCS(X={xi,xj})=TWU(X={xi,xj})

(17)

式中：xi與xj為2-項集的兩個項。

2.6 串型高效用模式挖掘算法(string high efficient pattern mining algorithm，SHEPMA)

SHEPMA算法的偽代碼如算法1所示。第一階段，SHEPMA聚集所有的1-項模式，根據(jù)SWU過濾低效用的項，同時刪除數(shù)據(jù)庫中的空序列。第二階段，初始化搜素空間p=NULL,iulist(p)=φ，asu(p)=0， 然后基于候選項集生成iulist。如果peu(p)小于λ，則搜素模式p的父節(jié)點，掃描p的投影數(shù)據(jù)庫，發(fā)現(xiàn)其中I-連接或S-連接的項。根據(jù)理論1初步刪除兩個列表中的低效項，根據(jù)定義22計算euu(p′)，如果滿足條件，則將該模式分別放入i-exts與s-exts兩個列表中。使用定義6的asu剪枝剩余的低效項。對于i-exts中的I-連接項，通過I-連接產(chǎn)生p′與iulist，如果序列p′的效用大于λ，則直接輸出p′。

算法1：SHEPMA算法

輸入： 序列數(shù)據(jù)庫SDB， 最小效用閾值λ， 前綴p， 索引效用列表iulist(p)，asu(p)

輸出： 前綴p的HUSP集

(1) IFpeu(p)<λTHEN

(2) RETURN NULL；

(3) 一次掃描p-投影數(shù)據(jù)庫；

(4)IFeuu(p′)≥λTHEN

(5)i_exts← I-級聯(lián)項；

(6)s_exts← S-級聯(lián)項；

(7)刪除i_exts與s_exts中的低rsu項；

(8)FOREACH 項i∈i_extsDO

(9)p′←I_concatenation(p,i)； // I-級聯(lián)

(10) 建立iulist(p′)；

(11) IFasu(p′)≥λTHEN

(12) RETURNp′；

(13)SHEPMA(p′,iulist(p′),asu(p′))；

(14)FOREACH 項i∈s_extsDO

(15)p′←S_concatenation(p,i)；//S-級聯(lián)

(16) 建立iulist(p′)；

(17) IFasu(p′)≥λTHEN

(18) RETURNp′；

(19)SHEPMA(p′,iulist(p′),asu(p′))；

3 分布式高效用模式挖掘算法(distributed high efficient pattern mining algorithm，SHEMA)

3.1 分布式效用列表設(shè)計

設(shè)計了適用于分布式挖掘程序的效用列表數(shù)據(jù)結(jié)構(gòu)。項集的效用列表中包含以下兩個信息：①項集的主要信息MIU(p),u(p),ru(p)， ②三元組格式的序列信息 ，tid為序列id，u為p在序列中的效用，ru為p在序列中的剩余效用。

圖5是修改后的1-項集效用列表，例如：模式f的MIU(f)=44,u(f)=9，ru(f)=63。f出現(xiàn)于序列3、7、8中，因此f的效用列表包含3個入口，每個入口包含序列的效用值與剩余效用值。例如：模式f出現(xiàn)于序列3中，效用值為5，剩余效用值為28。模式f出現(xiàn)于序列7中，效用值為3，剩余效用值為15。

圖5 修改的1-項集效用列表

3.2 分布式多閾值挖掘的深度剪枝屬性

針對多閾值的分布式HUI挖掘問題，補充了3個新的剪枝屬性，對HUI進行深度的剪枝處理。

屬性1：TWU-屬性。如果TWU(p)

證明：根據(jù)apriori屬性[11]：Sup(X′)≤Sup(X)， 說明TWU(X′)≤TWU(X)

例：設(shè)一個項集為X={fde}， 表1中項集fde出現(xiàn)于序列3中，TWU(fde)=33

屬性2：SMU-屬性。如果模式p的后綴效用總和小于SMU(p)， 那么p的超集都不是HUI。如果u(p)+ru(p)

例：設(shè)一個項集為p={fe}， 表1中項集fe出現(xiàn)于序列3與8中。fe的效用與剩余效用分別為u(fe)=(5+3)+(1+3)=12、ru(fe)=(9+13)=22。u(fe)+ru(fe)=12+22=34， 滿足條件u(fe)+ru(fe)

屬性3：EUCS-屬性。如果2-項集X的EUCS小于SMU(X)，那么X的超集均不是HUI。

證明：因為EUCS(X={xi,xj})=TWU(X)， 可得TWU(X′)≤TWU(X)。 如果EUCS(X)=TWU(X)

例：表1中EUCS(X={gb})=TWU(gb)=27，SMU(gb)=min(MIU(gb),MIU(ext(gb)))=min(MIU(gb),MIU(eac))=min(64,62)=62。 因為EUCS(gb)

在SHEMA算法的不同階段應(yīng)用上述3個剪枝屬性，以提高HUI的挖掘效率。

3.3 SHEMA算法

SHEMA算法的輸入為會話數(shù)據(jù)庫D，最小效用閾值MMU。首先掃描數(shù)據(jù)庫，計算所有1-項集的TWU值，第2次掃描數(shù)據(jù)庫，進行以下的剪枝操作：步驟①應(yīng)用TWU-屬性(屬性1)處理，然后重新計算候選項集的TU值；步驟②計算所有候選1-項集的EUCS；步驟③構(gòu)建1-項集的效用列表。

算法2所示是SHEMA主程序的偽代碼，第(1)-(12)行是掃描數(shù)據(jù)庫的關(guān)鍵操作。之后explore_search_tree()函數(shù)搜索候選項集，挖掘所有的HUI。

算法3是前綴樹的搜索程序，如果項集X滿足TWU-屬性，那么搜索X的前綴樹。算法3的第(6)行應(yīng)用了EUCS剪枝機制，在項集X與Y的效用列表構(gòu)建之前縮小了候選項集的空間。搜索過程中項集X與Y具有相同的前綴，所以在應(yīng)用EUCS屬性的時候，排除相同的前綴項P(算法3的第(6)行)。

算法2：SHEMA算法的主程序

輸入： 輸入數(shù)據(jù)庫D， 多個最小效用閾值MMU。

輸出：HUI集

(1)掃描D， 計算所有1-項集的TWU；

(2)foreachTj∈Ddo

(3)Tj中xi按照TWU值升序排列；

(4)TUj=0 /*重新計算TU值*/

(5) foreachxi∈Tjdo

(6) ifTWU(xi)≥SMU(xi) then /*TWU-M-Prune屬性*/

(7)TUj=TUj+U(xi,Tj)；

(8) foreachxi∈Tjdo

(9) foreachxk∈Tj/xido

(10)EUCS(xi,xk)=EUCS(xi,xk)+TUj；

(11) 建立1-項集UL；

(12)按照TWU值將1-項集UL升序排列；

(13)HUI=explore_search_tree({},UL,MMU)；

算法3：explore_search_tree函數(shù)

輸入：P(前綴項集P的UL)，UL(所有P的UL集)，MMU(多個最小效用閾值)

輸出： 前綴為P的所有HUI

(1)foreach 效用列表XinULdo

(2) ifU(X)≥MIU(X) thenHUI={HUI∪X}；

(3) ifU(X)+RU(X)≥SMU(X) then

(4)exUL={}；

(5) foreachX之后的效用列表YinUL

(6) ifEUCS(X-P,Y-P)≥SMU(X) then

(7) ifUL(XY)≠NULL

(8)exUL={exUL∪UL(XY)}；

(9)explore_search_tree({},UL,MMU)；

3.4 SHEMA的分布式實現(xiàn)方案

SHEMA算法使用廣度優(yōu)先搜索(breadth-first search，BFS)遍歷前綴樹。SHEMA算法評估前綴樹節(jié)點的過程中，各個節(jié)點的挖掘順序獨立于其它的同級節(jié)點，所以前綴樹中任意節(jié)點的所有子節(jié)點可以同時被處理，并且不會影響結(jié)果。

圖6是SHEMA分布式的一種實現(xiàn)方案。為每個候選序列會話p′建立一個并行的任務(wù)(進程)，并且放入進程列表tasklist中[12]，通過多核處理器分布式地處理tasklist內(nèi)的所有任務(wù)，設(shè)置一個同步機制保證分布式任務(wù)的同步性。采用共享內(nèi)存機制保存候選項集。

圖6 SHEMA分布式挖掘

3.5 算 例

通過算例解釋SHEMA算法的關(guān)鍵步驟。算法共有兩個輸入量：序列數(shù)據(jù)庫D與多個最小效用值MMU。假設(shè)輸入的序列數(shù)據(jù)庫見表3，最小效用值見表4。

表3 會話數(shù)據(jù)庫例子

表4 模式效用與最小效用閾值

首先計算所有1-項集的SWU值，項a-g的SWU值分別為186、128、242、124、180、72、97。然后遍歷每個會話，選出候選1-項集并計算其EUCS值。

序列中的模式按照SWU值排序，獲得的1-項列表為f,g,d,b,e,a,c，排序后的會話見表5。

表5 排序后的會話入口

計算所有候選1-項集的EUCS，例子中有7個1-項集，因此建立的三角矩陣共有21個入口。例：EUCS(gb)=27、EUCS(ge)=97、EUCS(fa)=72。 處理完所有會話，更新1-項集的效用列表，圖1是例子的1-項集最終效用列表。

基于1-項集效用列表挖掘HUI，在后續(xù)的處理中無需再訪問原數(shù)據(jù)庫。通過深度優(yōu)先搜索(DFS)搜索1-項集效用列表，首先，結(jié)合1-項集f與其它的1-項集效用列表產(chǎn)生2-項集，然后基于EUCS屬性刪除其中低效的模式。使用前綴f的2-項集遞歸地產(chǎn)生3-項集。重復(fù)上述搜索過程直至所有的1-項集均作為前綴，在遞歸處理過程中，檢查HUI并且添加到HUI列表中。表6是最終產(chǎn)生的HUI。

表6 最終產(chǎn)生的HUI

4 實驗結(jié)果與分析

實驗環(huán)境為Dell PC機，配置為Intel Xeon 3.7 GHz處理器、64 GB主內(nèi)存，Linux操作系統(tǒng)?；贘ava語言編程實現(xiàn)各個挖掘算法。選擇3個同類型的挖掘算法作為對比文獻，分別為MaHUSPM[13]、MSPC[14]、MHHUSP[15]，MaHUSPM是一種以降低內(nèi)存消耗為目標(biāo)的挖掘算法，MSPC是一種以刪除冗余候選模式為目標(biāo)的深度剪枝策略，MHHUSP是一種以加速挖掘速度為目標(biāo)的隱藏模式挖掘算法。

4.1 實驗數(shù)據(jù)集

采用兩個公開數(shù)據(jù)集作為benchmark數(shù)據(jù)集，分別為Ta-Feng grocery[16]數(shù)據(jù)集與Kosarak[11]數(shù)據(jù)集。Ta-Feng grocery[16]為購物記錄組成的序列數(shù)據(jù)庫，Kosarak[11]為博客記錄組成的序列數(shù)據(jù)庫。Kosarak包含99萬個序列，規(guī)模較大，Ta-Feng包含3萬多個序列，規(guī)模中等。表7兩個數(shù)據(jù)集的基本信息。

表7 實驗數(shù)據(jù)集的基本屬性

4.2 剪枝策略的性能

首先評估SHEMA算法剪枝策略的效果，統(tǒng)計4個挖掘算法產(chǎn)生的候選項集數(shù)量。圖7是4個挖掘算法對于Ta-Feng grocery與Kosarak兩個數(shù)據(jù)集的剪枝效果，圖7(a)中δ=0.06045，圖7(b)中δ=0.0045。圖7(a)顯示，對于中等規(guī)模的數(shù)據(jù)集，SHEMA算法在不同模式長度下的候選模式數(shù)量均低于其它3個挖掘式算法，本算法的3個剪枝屬性效果較好，明顯地縮小來了序列的搜索空間。圖7(b)顯示，對于大規(guī)模的數(shù)據(jù)集，其它3個算法隨著序列數(shù)量的增加而迅速增長，但本算法緩慢提高。主要原因在于SHEMA算法在1-項集與2-項集階段設(shè)計了深度的剪枝策略，有效地抑制了候選模式的保留量。

圖7 4個挖掘算法對于Ta-Feng grocery與Kosarak 兩個數(shù)據(jù)集的剪枝效果

4.3 挖掘算法的挖掘時間

縮小候選項集數(shù)量的關(guān)鍵目標(biāo)是降低模式挖掘的處理時間，因此評估了SHEMA算法的挖掘時間。圖8是4個挖掘算法的時間與閾值δ的關(guān)系，MaHUSPM、MSPC與MHHUSP這3個算法的挖掘時間隨著閾值的提高迅速提高，而SHEMA算法的增長速度慢于其它3個算法。

圖8 不用閾值下的挖掘時間(Ta-Feng數(shù)據(jù)集， 模式長度=3)

圖9 不用模式長度的挖掘時間(Ta-Feng數(shù)據(jù)集， δ=0.06045)

圖9是4個挖掘算法的時間與模式長度的關(guān)系，MaHUSPM、MSPC與MHHUSP這3個算法的挖掘時間隨著閾值的提高迅速提高，而SHEMA算法的增長速度慢于其它3個算法。主要原因在于SHEMA算法在1-項集與2-項集階段設(shè)計了深度的剪枝策略，有效地抑制了候選模式的保留量。

4.4 挖掘算法的擴展性性能

大數(shù)據(jù)是高效用項集挖掘的主要應(yīng)用場景，因此評估挖掘算法對于大數(shù)據(jù)集的可擴展性效果。統(tǒng)計4個挖掘算法對于Kosarak數(shù)據(jù)集的擴展性，圖10是不同序列數(shù)量的挖掘時間曲線，MaHUSPM與MSPC算法的挖掘時間隨著序列數(shù)量的增加而迅速提高，MHHUSP與SHEMA算法則隨著序列數(shù)量的提高基本保持穩(wěn)定，SHEMA算法由于采用了分布式挖掘的機制，其挖掘時間保持了較好的穩(wěn)定性。

圖10 不同序列數(shù)量的挖掘時間曲線(Kosarak數(shù)據(jù)集， δ=0.0045)

圖11 不同閾值的挖掘時間曲線(序列數(shù)量=990 000)

圖11是不同閾值的挖掘時間曲線，MaHUSPM、MSPC與MHHUSP算法的挖掘時間受閾值的影響較大，而SHEMA算法設(shè)計了深度的剪枝策略，實現(xiàn)了較為穩(wěn)定的挖掘時間。SHEMA算法隨著閾值的變化呈現(xiàn)較為穩(wěn)定的趨勢，具有較好的可擴展能力。

4.5 挖掘算法消耗的內(nèi)存

在項集的挖掘過程中需要緩存大量的候選項集，該過程需要消耗大量的內(nèi)存資源，因此挖掘算法的內(nèi)存成本也是挖掘算法的一個重要性能指標(biāo)。圖12是不同序列數(shù)量挖掘過程所需的內(nèi)存容量，MaHUSPM與MSPC算法的內(nèi)存消耗隨著序列數(shù)量的增加而迅速提高，MHHUSP與SHEMA算法則隨著序列數(shù)量的提高基本保持穩(wěn)定，可獲得結(jié)論MHHUSP與SHEMA算法的剪枝效果較好，避免了大量的候選項集緩存。

圖12 不同序列數(shù)量挖掘過程所需的內(nèi)存容量 (閾值為3%)

圖13是不同閾值挖掘的內(nèi)存消耗曲線，MaHUSPM算法的內(nèi)存消耗受閾值的影響較大，MSPC與MHHUSP而SHEMA算法則實現(xiàn)了較為穩(wěn)定的內(nèi)存消耗曲線。SHEMA算法設(shè)計了深度的剪枝策略，實現(xiàn)了較低的內(nèi)存消耗結(jié)果。

圖13 不同閾值的內(nèi)存消耗(序列數(shù)量=9.9×105)

5 結(jié)束語

算法在評估前綴樹節(jié)點的過程中，各個節(jié)點的挖掘順序獨立于其它的同級節(jié)點，所以可以并行地處理前綴樹中的所有子節(jié)點，并且不會影響結(jié)果。據(jù)此給出了本算法的分布式實現(xiàn)方案，能夠在云計算、GPU(graphics proces-sing unit)、多核處理器等平臺上實現(xiàn)并行計算。SHEMA算法設(shè)計了深度的剪枝策略，實現(xiàn)了較為穩(wěn)定的挖掘時間。SHEMA算法隨著閾值的變化呈現(xiàn)較為穩(wěn)定的趨勢，具有較好的可擴展能力與穩(wěn)定性。