唐輝軍 王樂 樊成立

序列模式挖掘作為數(shù)據(jù)挖掘領(lǐng)域的一項重要研究內(nèi)容,在風(fēng)險管理、生物信息學(xué)、基因分析等方面具有重要的應(yīng)用[1?3].頻繁序列模式挖掘作為其應(yīng)用的典型代表,突出了序列數(shù)據(jù)集中的高頻模式,傳統(tǒng)數(shù)據(jù)集上的頻繁項集閉包屬性表明:任一個頻繁項集的非空子集都是頻繁項集,非頻繁項集的任一個超集都不是頻繁項集,基于上述閉包屬性計算原則形成了序列集頻繁模式挖掘算法[4?5].然而頻繁模式?jīng)]有考慮序列集中各項的效用值.例如在零售業(yè),冰箱的銷售要比牙刷賣的次數(shù)少的多,但其利潤可能比牙刷高的多,因此在頻繁序列模式的基礎(chǔ)上,提出了高效用序列模式挖掘,即將內(nèi)外效用值引入到序列項集中,目前,高效用序列模式已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的一個熱門研究內(nèi)容[6?8].2010年,Ahmed等[9]給出了高效用序列模式挖掘的完整定義和數(shù)學(xué)模型.其主要任務(wù)為在具有一定效用值的序列數(shù)據(jù)庫中找出效用值不小于預(yù)先給定閾值的所有有序項集.在定義過程中,一個項集X的總效用值為X在該數(shù)據(jù)集中有包含項集X的事務(wù)t上的效用值U(X,t)的總和.而在單一事務(wù)t中可能存在多個相同序列集,文獻(xiàn)選擇其中較大效用值作為項集X在該事務(wù)中的效用.同時,該文獻(xiàn)還提出兩種挖掘算法UtilityLevel 和UtilitySpan,其中UtilityLevel通過事務(wù)中項集按水平次序組合生成候選項集,進(jìn)而判斷和識別其中高效用序列.UtilitySpan通過項集前綴垂直查找,搜索高效用項集.相比之下,UtilitySpan 的實現(xiàn)效率較好,但當(dāng)用戶設(shè)定的閾值比較低或數(shù)據(jù)集中的不同項比較多時,兩類算法會產(chǎn)生眾多的候選項集,造成產(chǎn)生高效用序列項集的時空代價較大.2012年,Yin 等[10]在KDD會議上提出的USPAN算法,被認(rèn)為能較大地提升高效用序列模式挖掘效率.其主要基于項集樹模型設(shè)計了數(shù)據(jù)庫中序列模式,所有序列模式均可從樹中的結(jié)點得到,并且基于高效用挖掘中的閉包屬性原則給出了一個SWU(Sequence-weighted utilization)模型進(jìn)行剪枝操作.即一個項集的SWU值不小于用戶定義的最小效用值,該項集即為一個候選項集;反之,則該項集則不為高效用項集.另外,該文還通過設(shè)置事務(wù)中的項集的Remain-utility 進(jìn)行深度剪枝操作,即一個項集的現(xiàn)有效用加上Remainutility如果小于最小效用值,則停止在樹中搜索該項集.USPAN的算法時空效率高于文獻(xiàn)[9]中的算法.但其算法基于枚舉而產(chǎn)生,時空效率代價也相對較大.Wang 等[11]考慮到在較小閾值下,SWU通常比最小效用值要大,提出了一個不基于閉包屬性原則的HUS-Span 算法,該算法主要設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)表示方法-效用鏈(Utility-chain),通過添加效用鏈剪枝達(dá)到計算效用值的目的.不過,該算法只在最小效用值較低或稀疏數(shù)據(jù)集時,其性能優(yōu)于USPAN.首先采用層次方法或者一定的數(shù)據(jù)結(jié)構(gòu)(樹、鏈)找出候選項集,然后掃描數(shù)據(jù)集計算每個候選項集的真實效用值來判斷該候選項集是否為高效用序列模式是USPAN、HUS-Span等算法的核心思想,很多算法在此基礎(chǔ)上進(jìn)行數(shù)據(jù)結(jié)構(gòu)設(shè)計改進(jìn)[12?14],2017 年,Zihayat等[15]在USPAN的基礎(chǔ)上,提出了HUSP-Miner 算法,該算法主要設(shè)計了兩個新的數(shù)據(jù)結(jié)構(gòu)ItemUtilLists(Item utility lists)和HUSP-Tree(High utility sequential pattern tree),其通過樹形鏈?zhǔn)侥Ｊ浇档屯诰蜻^程中的候選項個數(shù),在與USPAN的實驗比較結(jié)果中可以看到,算法的時空效率得到了一定的提升,時間效率能提高到3倍.高效用序列模式挖掘算法的時空效率有了很大的提高,但算法的代價還比較大,特別是挖掘時間效率的提升仍是本領(lǐng)域的一個挑戰(zhàn),本文在基于高效用模式增長挖掘方法的基礎(chǔ)上,給出一個高效用序列模式新算法HUSP-FP(High utility sequential pattern based on FP-growth).該算法采用模式增長的方法來挖掘高效用序列模式,所有的高效用序列項集均可從樹上得的,而不用再掃描原始數(shù)據(jù)集.基于模式增長的挖掘算法已經(jīng)在高效用無序數(shù)據(jù)集模式挖掘上表現(xiàn)出了獨特的優(yōu)勢.HUIMiner[16]、FHM[17]、HUPM-FP[18]等算法相繼提出,在時空效率上得到了較大提升,目前在序列數(shù)據(jù)集上開展高效用模式增長方法的研究成果還及其罕見.本文首先給出高效用序列模式的相關(guān)數(shù)學(xué)定義;然后,給出HUSP-FP中的全局樹建立過程,重點突出從樹中挖掘高效用序列模式的過程,分析算法的時空效率優(yōu)勢;最后,開展相關(guān)實驗,與前述現(xiàn)有較好的HUSP-Miner、UPSAN和HUS-Span 算法進(jìn)行計算效率對比分析,以驗證新算法的優(yōu)越性,并開展總結(jié)分析提出下一步工作方向.

1 相關(guān)定義

設(shè)D=t1,t2,···,tn為一個序列數(shù)據(jù)庫,tj為構(gòu)成該數(shù)據(jù)庫的各個事務(wù),I=i1,i2,···,im為構(gòu)成該數(shù)據(jù)庫的所有項的集合.在每一個事務(wù)tj中,設(shè)置(xj1:cj1),(xj2:cj2),···,(xj v:cj v)為該事務(wù)的具體項和內(nèi)部效應(yīng)表示.x j k(k=1,2,···,v)為I具體的項,cj k(k=1,2,···,v)=q(x j k,tj)為其相應(yīng)的效用值.p(x j k)為事務(wù)中該項相應(yīng)的外部效用值.表1、表2分別為某一序列數(shù)據(jù)庫和外部效用表實例.

表1 高效用數(shù)據(jù)集Table 1 High utility dataset

定義1.項x在事務(wù)t中的效用值,記為u(x,t),其定義如下:

例如項A在事務(wù)t1中的效用值為12.由于項B在事務(wù)t2中有兩個效用值,分別為6,3.這里設(shè)定在事務(wù)中出現(xiàn)多個相同項集情況下,取較大值為該項的效用值,即項B的效用值為6.

表2 利潤表(外部效用值)Table 2 A Prof it Table (External utility value)

定義2.項集X在事務(wù)t中的效用值,記為u(X,t),其定義如下:

例如項集A,B在事務(wù)t1的效用值為12+9=21.考慮到項集在某一事務(wù)中可能多次出現(xiàn),例如有序項集B,C在事務(wù)t4中效用值分別為3+2=5和3+4=7,這里按照定義1中的設(shè)定,取較大值7 為該有序項集在事務(wù)t4中的效用值.

定義3.序列項集X在數(shù)據(jù)集D中的效用值,設(shè)為u(X).

例如序列項集A,B在數(shù)據(jù)集中的效用為21+15+12=48.

定義4.事務(wù)t的效用值設(shè)為stu(t).其包含了所在事務(wù)中的項效用值的和,定義公式如下:

例如事務(wù)t3的效用值為9+8=17.

定義5.在數(shù)據(jù)集D的事務(wù)效用值為swu(D).其定義如下:

例如表1數(shù)據(jù)集中的事務(wù)效用值為29+17 +17 +9+34+17 +18=141.

定義6.基于數(shù)據(jù)集D,一個項集X的事務(wù)效用集不小于最小效用值,則該項集為候選項集,否則,則為非候選項集.

例如序列項集A,B在數(shù)據(jù)集中的事務(wù)效用值為29+34+18=81.

定義7.基于數(shù)據(jù)集D,一個項集的效用值u(X)大于或等于最小效用值,則該項集為高效用項集,否則為非高效用集.

性質(zhì)1.高效用序列項集的事務(wù)效用值必須滿足閉包屬性:任一候選項集的非空子集是一個候選項集,任一非候選項集的超集是一個非候選項集.證明:假設(shè)序列項集X是序列項集Y 的一個子集,也即Y是X的一個超集.因為X是Y的一個子集,因此數(shù)據(jù)集D中包含Y的事務(wù)項集一定也包含X,而包含X的事務(wù)項集不一定包含Y,即包含X的事務(wù)項集個數(shù)不會小于包含Y的事務(wù)項集個數(shù),因此swu(X)一定大于等于swu(Y).所以若Y滿足閉包屬性是一個候選項集,則X一定也是一個候選項集;若X不滿足閉包屬性,即不是一個候選項集,則Y一定也不是一個候選項集.

2 HUSP-FP算法

在本節(jié)中,我們主要介紹基于模式增長的HUSP-FP算法在高效用序列模式挖掘中的應(yīng)用.其中,第2.1節(jié)給出了全局樹的建立,其可將效用事務(wù)集壓縮到一棵樹上,樹上存儲了所有效用信息.第2.2節(jié)描述了如何從全局樹上挖掘到所有的高效用序列項集模式.

2.1 全局樹的建立

以表1和表2的數(shù)據(jù)為例,設(shè)置最小閾值為35,構(gòu)建全局樹步驟如下:

步驟1.掃描一遍數(shù)據(jù)集,統(tǒng)計各項的效用值(Utility),事務(wù)效用值(swu),進(jìn)而形成數(shù)據(jù)頭表H計算結(jié)果如圖1(a)所示

步驟2.將頭表中事務(wù)效用值swu小于35的項刪除,由于F、G的swu均小于35,故刪除F、G,更新后的頭表如圖1(b)所示.

步驟3.再次掃描原始數(shù)據(jù)集,將不在頭表中出現(xiàn)的項刪除,并按原始項出現(xiàn)順序依次添加到一顆樹中.

表1中的第一個序列集(A,4)(B,3)(D,3)(E,1)添加到樹中的結(jié)果如圖1(c)所示.葉子節(jié)點保留了全部項的效用值List=[12,9,6,2].圖1(c)表示了第一個事務(wù)添加后的結(jié)果.圖1(d)為添加表1中第2個事務(wù)項集后的結(jié)果,由于在該事務(wù)中出現(xiàn)了兩個B項,在最后出現(xiàn)的B項中記錄下前一個B項在路徑中出現(xiàn)的位置,這里用S=1來表示,并設(shè)置鏈接指針到前一項.在添加的過程中,如果項集對應(yīng)的最后一個節(jié)點在樹上已經(jīng)存在了,則只需要將各項對應(yīng)的效用值累加到List的對應(yīng)項上.第4個事務(wù)項集添加到樹上后的結(jié)果如圖1(f)所示,依次添加第5、第6和第7 個事務(wù)集,在添加第7 個事務(wù)集中,A、B項出現(xiàn)了多項,第二個A中記錄第一個A出現(xiàn)的下標(biāo)位置,第三個A記錄第二個A的下標(biāo)位置,依次類推,將所有效用值保留在葉子節(jié)點中.所有事務(wù)項集添加后的結(jié)果如圖1(g)所示.頭表中的link 對相同節(jié)點按照事務(wù)出現(xiàn)順序進(jìn)行鏈接,以便于計算相同項集的效用值.相關(guān)事務(wù)內(nèi)容項指針鏈接如圖1(c)～(e)所示,為了圖例看起來清晰,圖1(f)～(g)上沒有畫出link 對應(yīng)的事務(wù)內(nèi)容項之間的鏈接線.

2.2 從全局樹上挖掘所有序列模式

上述過程對序列全局樹進(jìn)行了有效構(gòu)建,將序列數(shù)據(jù)集維護(hù)到了一顆樹和一張頭表中,算法HUSP-FP采用模式增長方式挖掘全部高效用序列集.具體算法過程如算法1所示.

圖1 序列全局樹構(gòu)建實例Fig.1 An example of constructing a sequential global tree

算法1.Mining(T,H,X,minUti)

輸入:全局樹T,頭表H,初始值為空的項集X,最小效用值minUti.

輸出:高效用序列模式集HUSPs.

算法1在頭表和子頭表的創(chuàng)建過程中,將項集X的效用值存放在頭表中的字段Utility,因此在算法1的第4行中可以直接判斷項集X是否是高效用模式.

從頭表出發(fā),計算包含以頭表中每一項為尾節(jié)點的項集效用值.具體到全局樹的路徑中,則對應(yīng)以路徑中的葉子節(jié)點為出發(fā)點,依次處理每一項得到其相應(yīng)的子表和子樹,處理完每一項即可挖掘到以該項為尾項的序列項集.在計算過程中,先通過判斷事務(wù)效用值swu是否滿足閉包屬性進(jìn)而計算其序列模式是否為高效用序列模式.在圖1(g)的路徑出現(xiàn)過程中,A-B-D-E為第一個路徑,包含C的路徑B-C-B為第二個路徑,由于頭表中只有這5項已經(jīng)全部出現(xiàn),則挖掘頭表中項的順序為E-D-B-A-C.

這里以圖1(g)中的全局樹和頭表為例,說明算法1構(gòu)建子樹和子頭表的過程.由于項E、D的包含項集比較簡單,這里選擇挖掘以項B為尾節(jié)點的高效用序列項集作為演示例子.當(dāng)處理頭表(圖1(g))中項B時,因為頭表中項B的swu值不小于最小閾值35,因此可以為項集X=B創(chuàng)建子樹和子頭表,構(gòu)建步驟如下:

步驟1.按照從頭表指針鏈中B點出發(fā)鏈接形成的路徑,分別按照從下往上的順序從路徑A-B上分析帶有B項的項集為A、B.從路徑B-C-B項獲取項集C、B、B、B.從路徑A-B-A-A-B(這里指針鏈接到第二個B項)上獲取項集A、B、B、B.按照項集效用和事務(wù)效用值計算規(guī)則,得到B的子頭表如圖2(a)所示.按照前述第2.1節(jié)全局樹建立規(guī)則,刪除swu 不滿足最小效用值要求的無用項集B、B和C、B得到優(yōu)化后的子頭表如圖2(b)所示.

步驟2.由于子頭表不為空,繼續(xù)以子頭表中的某一項集為基項,構(gòu)建以該子頭表為基礎(chǔ)的子樹.按照原始序列挖掘順序添加相關(guān)節(jié)點,添加第一條路徑后得到項集B的子樹如圖2(c)所示,其中Base表示了路徑基項B的效用值.所有路徑添加完畢后的結(jié)果如圖2(d)所示.繼續(xù)以子頭表中的某一項為基項得到后續(xù)子集A、A、B和B、A、B,發(fā)現(xiàn)其swu均小于最小效用值,基項B的序列項集處理完畢,計算得到A、B,A、A、B和B、A、B為高效用序列項集.依次類推,圖2(e)則表示了處理D為基項后的子樹和子頭表.

2.3 HUSP-FP理論分析

算法HUSP-FP將所有項的效用值維護(hù)在全局樹的葉子節(jié)點上,并且其存儲的是所有的真實效用值而不是估計值.這使得其計算中不需要產(chǎn)生候選項集.在子樹的創(chuàng)建過程中(如圖2),依據(jù)路徑葉子節(jié)點,可以得到子樹節(jié)點中每一項的真實效用值.依據(jù)事務(wù)項集閉包屬性要求,一旦子樹中的項集事務(wù)效用值swu小于最小閾值,則拋棄該項集,最終使得創(chuàng)建子樹和子頭表的次數(shù)得到了大幅度減少,計算效率得到了有效提升.

以下證明HUSP-FP能夠挖掘到所有的高效用序列模式.首先假設(shè)項集Z是任何一個高效用序列模式.因為Z是一個高效用序列模式,則其任何一個非空子集的swu值都不會小于最小閾值.根據(jù)算法HUSP-FP,序列項集Z中的所有項都會出現(xiàn)在全局樹對應(yīng)的頭表中,當(dāng)Z中第一個項Z1被處理,并為之創(chuàng)建子頭表時,因為項集Z1和Z中其余各項的組合的swu 值都不小于最小閾值,因此這些序列組合的項集都會出現(xiàn)在子頭表中,當(dāng)處理子頭表中項Z1和Z中的第二項Z2的序列組合時,同樣項集Z1、Z2和Z中其余各項的序列組合會出現(xiàn)在新的子頭表中,依次處理下去,一定能夠得到Z所包含的全部高效用序列模式.

與前述基于候選集的已有算法HUSPMiner、USPAN和HUS-Span 相比,HUSP-FP能夠依據(jù)模式增長方法挖掘得到所有高效用序列模式,并且在挖掘過程中無候選項.

全局樹中的事務(wù)效用存儲結(jié)構(gòu)也相對簡單,這與其他三類基于候選項剪枝進(jìn)而得到高效用序列模式的方法有本質(zhì)不同,這也是HUSP-FP能夠取得較好時空效率的主要原因,相關(guān)算法的復(fù)雜度比較內(nèi)容可見表3所示.

圖2 序列子樹構(gòu)建實例Fig.2 An example of constructing a sequential sub-tree

表3 算法復(fù)雜度比較Table 3 Comparisons of algorithm complexity

3 實驗與結(jié)果

3.1 實驗算法與平臺

算法HUSP-Miner、USPAN和HUS-Span是目前時空效率較好的高效用序列模式挖掘算法,本文新提出的算法HUSP-FP和這三類算法做了對比分析.算法均采用java 編程語言實現(xiàn),實驗平臺:Windows 7,10 GB Memory (Java heap size is 1.5 GB),Intel(R)Core(TM)i5-3320 CPU@2.60 GHz.

3.2 實驗數(shù)據(jù)

本節(jié)采用的數(shù)據(jù)來自SPNF[19]和文獻(xiàn)[20],共4個真實數(shù)據(jù)集,包括Bible,FIFA,Kosarak 10k,SIGN.其中,Bible是一個具有中等序列長度的稠密數(shù)據(jù)集,FIFA 是一個具有較多長序列的稠密數(shù)據(jù)集,Kosarak 10k則是一個包含短序列的稀疏數(shù)據(jù)集,SIGN是一個具有超長序列類型的稠密數(shù)據(jù)集,數(shù)據(jù)集的類型豐富性是足夠的,關(guān)于數(shù)據(jù)集的具體內(nèi)在特征,可見表4所示.

表4 算法復(fù)雜度比較Table 4 Data characteristics

3.3 時空效率

算法運行時間會隨著最小效用值(最小閾值)的增加而降低.第一個實驗測試了不同最小閾值下,算法的運行時間和內(nèi)存消耗對比.圖3給出了在不同閾值要求下的4種算法在4個數(shù)據(jù)集的運行時間對比.

圖3 運行時間Fig.3 Running time

項的外部效用值采用文獻(xiàn)[21?22]中的方法,設(shè)定為隨機產(chǎn)生的一個數(shù)值(大于等于0.0100,小于等于10.0000).從圖3中可以看到,新算法的時間效率得到了較大提升,個別數(shù)據(jù)集上可以提高達(dá)到1個數(shù)量級以上.建立全局樹然后基于樹進(jìn)行高效用序列模式挖掘是HUSP-FP算法時間消耗的兩大部分,不過隨著閾值的增加,相比其他算法來說,HUSP-FP的挖掘時間變化比較平穩(wěn).對于短序列數(shù)據(jù)集Bible和Kosarak 10k 來說,由于HUSPMiner、USPAN和HUS-Span 在實現(xiàn)過程中產(chǎn)生了較多的候選項集,從而導(dǎo)致算法的時間消耗較大.對于長序列稠密數(shù)據(jù)集FIFA和SIGN,三類算法更是付出了較多的時間代價,例如對于數(shù)據(jù)集SIGN,當(dāng)最小閾值達(dá)到0.018%時,此時已無高效用序列模式產(chǎn)生,三類算法仍然消耗了大量時間進(jìn)行候選項判斷,由此可見,新算法HUSP-FP在時間運行效率上取得了良好的領(lǐng)先結(jié)果.

3.4 算法擴展性測試

第2個實驗測試在不同數(shù)據(jù)量下算法的運行時間和內(nèi)存消耗性能,分別選取稠密數(shù)據(jù)集Bible和稀疏數(shù)據(jù)集Kosarak 10k 作為測試對象,數(shù)據(jù)選擇方式為從Bible數(shù)據(jù)集中從頭到尾順序添加5 000、10 000、15 000、20 000、25 000、30 000事務(wù)數(shù)據(jù)量,且設(shè)置其最小閾值為0.026%.從Kosarak 10k 數(shù)據(jù)集中選擇100 000、200 000、300 000、400 000、500 000、600 000事務(wù)數(shù)據(jù)量,且設(shè)置其最小閾值為0.0176%.其中圖5、圖6分別表示了4類算法在不同數(shù)據(jù)量下的時空效率.從圖中可以看到,隨著數(shù)據(jù)測試集數(shù)據(jù)量的增大,HUSP-FP算法產(chǎn)生的高效用序列模式增多,但是HUSP-FP的時間消耗量卻相對較為穩(wěn)定,這是由于算法按照閉包屬性,在模式增長過程中及時的拋棄了一些無用序列項,從而使得運行時間保持了平穩(wěn).HUSP-Miner、USPAN和HUS-Span基于層次的搜索方法產(chǎn)生了較多的候選項,雖然三類算法大都采用樹形結(jié)構(gòu),但它們在全局樹建立過程中采用枚舉搜索的方式增加了較大的計算時間.通過對算法的內(nèi)存消耗對比,發(fā)現(xiàn)4類算法的內(nèi)存消耗都隨著數(shù)據(jù)量的增加成線性增加模式(該測試結(jié)果不包含垃圾節(jié)點占用空間,垃圾節(jié)點累積到一定程度,系統(tǒng)會自動回收垃圾所占用的空間),但總體上看,HUSP-FP消耗的內(nèi)存更少.由此可見,新算法在數(shù)據(jù)量增多的情形下時空效率都優(yōu)于其他三類算法,特別是計算時間上優(yōu)勢明顯.

圖4 內(nèi)存消耗Fig.4 Memory consumption

圖5 不同數(shù)據(jù)量運行時間Fig.5 Running time under different data size

圖6 不同數(shù)據(jù)量內(nèi)存消耗Fig.6 Memory consumption under different data size

圖4給出了在上述4個數(shù)據(jù)集運算中的內(nèi)存消耗量對比.本節(jié)實驗中的內(nèi)存消耗值的提取方法如下:在算法運行過程中,設(shè)置不同的點,提取每個點上的所用內(nèi)存量,然后從所有不同點上取出最大的內(nèi)存消耗量作為當(dāng)前算法的內(nèi)存消耗.在不同的最小閾值下,相比其他三類算法,算法HUSP-FP在空間使用效率上也有較大的優(yōu)勢.當(dāng)最小閾值減小,數(shù)據(jù)集中包含的高效用模式會增加,從而使得新算法HUSP-FP創(chuàng)建的全局樹占用空間增加,同時創(chuàng)建的子樹棵數(shù)也會增加,所以算法HUSP-FP會隨著最小閾值的降低而消耗更多的內(nèi)存空間.但與其他三類算法相比較,HUSP-FP還是取得了較大的優(yōu)勢.

第3個實驗進(jìn)一步測試了在數(shù)據(jù)流窗口下的算法運算效率.圖7 給出在不同最小閾值下,4個算法在上述4類典型數(shù)據(jù)集下的運行時間(這里設(shè)置一個時間窗口包含5個序列批次,每一批次包含事務(wù)容量不大于20 k).從圖7 的實驗中可以發(fā)現(xiàn),HUSP-FP的運行時間明顯小于其他三類算法,隨著實驗中最小閾值的增大,其他算法的運行時間也得到了一定的下降,但下降后的值與HUSP-FP相比,差距仍然較大.這說明HUSP-FP能夠在時間窗口數(shù)據(jù)流挖掘上具備較好的運行時間優(yōu)勢.從圖8的內(nèi)存消耗比較中也可以看出,HUSP-FP在數(shù)據(jù)流窗口下內(nèi)存計算消耗量相對較小.圖7 和圖8表明新算法HUSP-FP在數(shù)據(jù)流窗口高效用序列模式挖掘中能夠顯示出較好的運行效率優(yōu)勢.

分別設(shè)置Bible、FIFA、K0sarak 10k、SIGN的最小閾值為0.026%、0.10%、0.176%、0.014%,圖9給出了不同批處理數(shù)據(jù)容量(例如Bible-10k 表示劃分Bible 單一批處理數(shù)據(jù)集的大小不超過10k)和不同批處理數(shù)據(jù)數(shù)量(Bible-3表示一個時間窗口有3個批處理集)下的運行時間對比,從圖7 中可以看出,HUSP-Miner 相比USPAN和HUS-Span,運行時間更少,故圖9對HUSP-Miner 和HUSPFP開展了對比分析,隨著相關(guān)批處理數(shù)據(jù)容量和數(shù)量的增大,在對同一數(shù)據(jù)集的分析中可以發(fā)現(xiàn),HUSP-FP和HUSP-Miner 都會增長運行時間,但HUSP-FP的增長值相對HUSP-Miner 更小,能夠保持相對的穩(wěn)定,這更進(jìn)一步說明了HUSP-FP在時間窗口高效用序列模式挖掘中的優(yōu)越性.

4 總結(jié)

本文提出一種新的高效用序列模式挖掘算法HUSP-FP,該算法基于模式增長方式可直接挖掘高效用序列模式,而不是傳統(tǒng)的先得到候選項集再篩選的過程,因此算法的時空效率都得到了提升.本文采用4個典型真實數(shù)據(jù)集(包含短序列、長序列、稀疏數(shù)據(jù)集、稠密數(shù)據(jù)集)進(jìn)行了靜態(tài)和時間窗口動態(tài)實驗驗證,實驗結(jié)果也表明給出算法的時間和空間效率相比目前較好的HUSP-Miner、USPAN和HUS-Span都有較大程度的提高,特別是時間效率得到了較大幅度的提高,證明該方法是可行的.同時通過實驗運行,發(fā)現(xiàn)HUSP-FP算法即使在最小閾值較大情況下,在維護(hù)全局和子樹環(huán)節(jié)仍然需要消耗大量時間和空間,下一步將針對此問題進(jìn)行優(yōu)化.

圖7 數(shù)據(jù)流運行時間Fig.7 Running time based on data stream

圖8 數(shù)據(jù)流內(nèi)存消耗Fig.8 Memory consumption based on data stream

圖9 HUSP-FP和HUSP-Miner 的對比評價Fig.9 Evaluation of HUSP-FP and HUSP-Miner