基于多效用閾值的分布式高效用序列模式挖掘

曾 毅，張福泉

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

0 引 言

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

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

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

1 問題模型

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

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

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

表2 項(xiàng)的利潤(rùn)與最小效用閾值

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

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

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

定義4 序列s的效用定義為序列s中所有項(xiàng)的效用總和，記為

(1)

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

定義6SDB中模式p的實(shí)際效用定義為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è)計(jì)

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

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

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

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

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

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

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

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

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

(6)

圖1是3個(gè)列表的例子，seq、ulist、rlist這3個(gè)列表中的分界項(xiàng)分別為索引3、7、11，序列中e的第一個(gè)索引為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個(gè)列表的例子

2.3 索引效用列表

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

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

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

iulist(p′,i,s)=max{iulist(p,j,s)|?p的序號(hào)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é)點(diǎn)p的效用上限記為peu，節(jié)點(diǎn)p在trie-Tree的子節(jié)點(diǎn)上限也是peu。如果peu(p)<λ， 那么可安全地剪枝p的子樹，縮小挖掘程序的搜索空間。SDB中模式p的peu定義為

(12)

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

(13)

SDB中序列p的rsu定義為

(14)

2.4 生成序列的iulist

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

圖2 序列iulist的例子

包含a的序列中通過I-級(jí)聯(lián)與S-級(jí)聯(lián)對(duì)a進(jìn)行擴(kuò)展?？紤]序列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-級(jí)聯(lián)與S-級(jí)聯(lián)從序列p產(chǎn)生p′的過程中，僅僅掃描了序列中p之后的子序列，節(jié)約了掃描的時(shí)間。

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

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

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

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

(15)

理論1 給定一個(gè)序列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é)果的情況下對(duì)s前綴的超序列進(jìn)行安全的剪枝。

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

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

(16)

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

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

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

(17)

式中：xi與xj為2-項(xiàng)集的兩個(gè)項(xiàng)。

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

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

(6)s_exts← S-級(jí)聯(lián)項(xiàng)；

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

(8)FOREACH 項(xiàng)i∈i_extsDO

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

(10) 建立iulist(p′)；

(11) IFasu(p′)≥λTHEN

(12) RETURNp′；

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

(14)FOREACH 項(xiàng)i∈s_extsDO

(15)p′←S_concatenation(p,i)；//S-級(jí)聯(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è)計(jì)

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

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

圖5 修改的1-項(xiàng)集效用列表

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

針對(duì)多閾值的分布式HUI挖掘問題，補(bǔ)充了3個(gè)新的剪枝屬性，對(duì)HUI進(jìn)行深度的剪枝處理。

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

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

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

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

例：設(shè)一個(gè)項(xiàng)集為p={fe}， 表1中項(xiàng)集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-項(xiàng)集X的EUCS小于SMU(X)，那么X的超集均不是HUI。

證明：因?yàn)镋UCS(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。 因?yàn)镋UCS(gb)

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

3.3 SHEMA算法

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

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

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

算法2：SHEMA算法的主程序

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

輸出：HUI集

(1)掃描D， 計(jì)算所有1-項(xiàng)集的TWU；

(2)foreachTj∈Ddo

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

(4)TUj=0 /*重新計(jì)算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-項(xiàng)集UL；

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

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

算法3：explore_search_tree函數(shù)

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

輸出： 前綴為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的分布式實(shí)現(xiàn)方案

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

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

圖6 SHEMA分布式挖掘

3.5 算 例

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

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

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

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

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

表5 排序后的會(huì)話入口

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

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

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

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

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

采用兩個(gè)公開數(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萬個(gè)序列，規(guī)模較大，Ta-Feng包含3萬多個(gè)序列，規(guī)模中等。表7兩個(gè)數(shù)據(jù)集的基本信息。

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

4.2 剪枝策略的性能

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

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

4.3 挖掘算法的挖掘時(shí)間

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

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

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

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

4.4 挖掘算法的擴(kuò)展性性能

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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