徐啟寒 徐開勇 郭 松 戴樂育

(信息工程大學(xué) 河南 鄭州 450001)

0 引 言

用戶行為序列模式挖掘是指挖掘出所有滿足指定最小支持度的用戶所有頻繁行為序列的過(guò)程，在用戶行為模式分析與用戶輪廓刻畫等方面均具有突出的模式表達(dá)能力。

序列模式挖掘最早于1995年由Agrawal等[1]提出。區(qū)別于關(guān)聯(lián)規(guī)則挖掘，序列模式挖掘引入時(shí)間屬性，具備更強(qiáng)的數(shù)據(jù)表達(dá)能力。除Apriori算法[2]、GSP算法[3]、Prefixspan[4]以及SPAM算法[5]等經(jīng)典算法外，近幾年以來(lái)，一些擴(kuò)展性更強(qiáng)、挖掘效率更高的方法不斷被提出。Le等[6]通過(guò)對(duì)候選序列提前剪枝來(lái)縮小搜索空間，提出一種高效的挖掘算法STATE-SPADE；Zihayat等[7]提出一種基于內(nèi)存自適應(yīng)的HUSP算法MAHUSP，解決數(shù)據(jù)流更新引起的內(nèi)存資源限制問(wèn)題；Kemmar等[8]提出一種前綴投影全局約束方法，壓縮子序列關(guān)聯(lián)以及頻率約束，解決現(xiàn)有模型約束規(guī)模過(guò)大問(wèn)題。

現(xiàn)有研究雖在算法性能和挖掘效果上具有一定的優(yōu)勢(shì)，但由于采用基于單一支持度的支持度閾值設(shè)置方式，未考慮用戶自身行為之間的差異性，無(wú)法滿足用戶行為模式分析的實(shí)際應(yīng)用需求。在模式挖掘過(guò)程中，若支持度閾值設(shè)置過(guò)高，將導(dǎo)致遺漏發(fā)生頻率低但重要性高的操作，影響挖掘結(jié)果的準(zhǔn)確性。若支持度閾值設(shè)置過(guò)低，則將導(dǎo)致待挖掘數(shù)據(jù)規(guī)模過(guò)大，嚴(yán)重影響挖掘效率，同時(shí)產(chǎn)生大量對(duì)分析無(wú)用的冗余信息。所以在用戶行為模式分析中需要采用基于多支持度的模式挖掘方法。

多支持度是指為不同項(xiàng)分別設(shè)置不同的最小支持度。該概念最早由Liu等[9]提出，并提出了基于Apriori算法的擴(kuò)展算法MSApriori。該算法利用向下封閉性來(lái)縮減搜索空間，但是很容易導(dǎo)致組合爆炸。文獻(xiàn)[10]提出一種基于MIS-Tree結(jié)構(gòu)的條件頻繁模式增長(zhǎng)算法CFP-growth，它通過(guò)遞歸地創(chuàng)建條件樹來(lái)生成頻繁模式；文獻(xiàn)[11]提出了一種CFP-growth算法的增強(qiáng)算法CFP-growth++，采用壓縮樹結(jié)構(gòu)挖掘頻繁模式；文獻(xiàn)[12]提出一種多最小支持度下基于MapReduce的頻繁模式挖掘框架，挖掘效率更高。

目前現(xiàn)有的基于多支持度的模式挖掘研究多集中在頻繁項(xiàng)集的挖掘上，針對(duì)帶有時(shí)序?qū)傩缘男蛄心Ｊ酵诰蜓芯枯^少。Liu[13]首次將多最小支持度概念引入序列模式挖掘中，并提出MS-GSP算法。但該算法采用候選序列生成測(cè)試的方式，導(dǎo)致運(yùn)行時(shí)間以及內(nèi)存消耗急劇增加；Huang[14]在挖掘模糊量級(jí)序列模式(FQSP)問(wèn)題中引入多支持度概念及可調(diào)整的隸屬度函數(shù)，以此來(lái)解決單一支持度閾值及單一隸屬度函數(shù)所致的實(shí)際不可用性問(wèn)題。

本文以LP-tree結(jié)構(gòu)[15]為基礎(chǔ)，提出一種基于多最小支持度的前綴樹結(jié)構(gòu)MSLP-tree，并進(jìn)一步提出基于MSLP-tree的序列模式增長(zhǎng)算法MSLP-growth。LP-tree是一種線性前綴樹，本文在此基礎(chǔ)上引入多最小支持度等屬性，來(lái)解決用戶行為序列模式挖掘中敏感稀有項(xiàng)的問(wèn)題。在樹的構(gòu)成上，采用相同前綴序列分枝整合的方法壓縮結(jié)構(gòu)，節(jié)約內(nèi)存空間，并且該結(jié)構(gòu)能夠存儲(chǔ)所有的序列模式，便于序列模式的分析和增量更新的需求。同時(shí)，本文所提出的算法無(wú)需多次掃描數(shù)據(jù)庫(kù)，不產(chǎn)生候選序列，挖掘效率較高，空間資源消耗較小。

1 用戶行為序列模式相關(guān)定義

設(shè)I={i1，i2，…，in}為項(xiàng)目的非空集合，集合t?I為項(xiàng)集，項(xiàng)集內(nèi)各項(xiàng)間無(wú)先后順序。序列數(shù)據(jù)庫(kù)S中序列s可記為(sid，s)，其中sid為s在S中的標(biāo)識(shí)符。序列s由項(xiàng)集有序排列而成，s可記為s=。表1為示例序列數(shù)據(jù)庫(kù)，庫(kù)中各序列有唯一標(biāo)識(shí)符。

表1 示例序列數(shù)據(jù)庫(kù)

給定序列s1=<α1，α2，…，αn>，序列s2=<β1，β2，…，βm>，n≤m，如果存在1≤j1

定義1支持度。對(duì)于序列數(shù)據(jù)庫(kù)S中序列s，s的支持度為S中包含序列s的個(gè)數(shù)占S中序列總數(shù)的比值，記為sup(s)。給定支持度閾值min_sup，如果序列s在S中的支持度不低于min_sup，即sup(s)≥min_sup，則稱序列s為頻繁序列模式。

定義2項(xiàng)集最小支持度。設(shè)項(xiàng)目集合I中數(shù)據(jù)項(xiàng)ij的最小支持度為mis(ij)，則I中所有項(xiàng)的最小支持度可記為{mis(i1)，mis(i2)，…，mis(in)}。對(duì)于項(xiàng)集t={i1,i2,…，ik},t?I,項(xiàng)集t的最小支持度記為MIS(t)=min{mis(i1)，mis(i2)，…，mis(ik)}。表1中各數(shù)據(jù)項(xiàng)最小支持度如表2所示。

表2 最小支持度表

定義3序列最小支持度。給定序列s=，序列s的最小支持度可記為MIS(s)，MIS(s)=min{mis(t1)，mis(t2)，…，mis(tn)}。

定義4極小最小支持度。設(shè)LMS(least minimum support)為項(xiàng)目集合I中所有項(xiàng)目最小支持度的最小值，則LMS可記為min{mis(i1)，mis(i2)，…，mis(in)}。

定義5對(duì)于任意序列s，如果sup(s)≥MIS(s)，則s為頻繁序列或者說(shuō)s是頻繁的；如果sup(s)

性質(zhì)1在多支持度下的序列模式中，如果一個(gè)序列是不頻繁的，但它的超序列可能是頻繁的。

性質(zhì)2對(duì)于序列模式X和Y，X?Y，如果sup(X)

2 MSLP-tree

本節(jié)首先描述MSLP-tree的結(jié)構(gòu)，然后介紹構(gòu)造過(guò)程。

2.1 MSLP-tree結(jié)構(gòu)

MSLP-tree主要由四部分構(gòu)成，包括根節(jié)點(diǎn)Root、頭表Header List、樹節(jié)點(diǎn)LPNc以及枝節(jié)點(diǎn)信息表BNL：

1) 根節(jié)點(diǎn)標(biāo)記為Root，值為空。

2) 頭表(Header List)中主要包括四個(gè)屬性：數(shù)據(jù)項(xiàng)名稱item.name、支持度support、數(shù)據(jù)項(xiàng)最小支持度mis、連接具有相同名稱數(shù)據(jù)項(xiàng)節(jié)點(diǎn)之間的連接點(diǎn)node.link。

3) 樹節(jié)點(diǎn)LPN(Liner Prefix Node)內(nèi)節(jié)點(diǎn)存儲(chǔ)頻繁項(xiàng)信息，包括數(shù)據(jù)項(xiàng)名稱item.name、該項(xiàng)支持度support、序列當(dāng)前最小支持度值mis、連接點(diǎn)node.link以及枝節(jié)點(diǎn)信息branch information。其中，各LPN內(nèi)首節(jié)點(diǎn)為該LPN表頭，用以連接其父節(jié)點(diǎn)；LPN結(jié)構(gòu)組成可表示為L(zhǎng)PN={，，，…，}。

4) 枝節(jié)點(diǎn)表BNL(Branch Node List)包括各枝節(jié)點(diǎn)及其對(duì)應(yīng)各子節(jié)點(diǎn)信息。BNL表示為BNL={{B1→C1,1，C1,2，…，C1,j}，{B2→C2,1，C2,2,…，C2,j}，…，{Bi→Ci,1，Ci,2，…,Ci,j}}，Bi為第i個(gè)枝節(jié)點(diǎn)指針，Ci,j為Bi第j個(gè)子節(jié)點(diǎn)指針。設(shè)Pc,k為L(zhǎng)PN內(nèi)某一節(jié)點(diǎn)的指針，它表示LPNc第k個(gè)節(jié)點(diǎn)的指針，PRoot為指向根節(jié)點(diǎn)的指針。

綜上，MSLP-tree可記為MSLP-tree={Header List，BNL，LPN1，LPN2，…，LPNc}形式，其中c為樹中LPN的總個(gè)數(shù)。MSLP-tree的結(jié)構(gòu)示例如圖1所示。

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

2.2 構(gòu)造MSLP-tree

MSLP-tree構(gòu)造流程如算法1。具體構(gòu)造過(guò)程如下：

Step1掃描序列數(shù)據(jù)庫(kù)S(其中所有序列已按最小支持度值升序排列)，找出所有數(shù)據(jù)項(xiàng)i，并對(duì)其進(jìn)行支持度計(jì)數(shù)，將支持度小于LMS的項(xiàng)刪除，所有滿足LMS模式的項(xiàng)記入頭表中，并按mis升序排列。

Step2在樹中插入第一個(gè)序列，序列首項(xiàng)記為ik，長(zhǎng)度為1。若某一項(xiàng)i為項(xiàng)集擴(kuò)展項(xiàng)，則在該項(xiàng)前添加符號(hào)“_”，記為_i。各項(xiàng)按序列中順序依次記入LPN中，各項(xiàng)支持度計(jì)數(shù)+1，記為L(zhǎng)PN1。LPN1內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)為序列長(zhǎng)度+1，即包括LPN1表頭。將LPN1與根節(jié)點(diǎn)相連，LPN1內(nèi)首節(jié)點(diǎn)指針指向根節(jié)點(diǎn)Root，P1,1→PRoot。此時(shí)生成BNL，BNL(PRoot)→BNL(Pc,1)。

Step3繼續(xù)將數(shù)據(jù)庫(kù)其他序列插入樹中，數(shù)據(jù)處理同Step2。此時(shí)分三種情況，若新序列與樹中已插入序列LPNc前k項(xiàng)相同，則將前k項(xiàng)插入LPNc中，其余n-k項(xiàng)生成新LPN，LPNc前k項(xiàng)支持度+1，LPNnew首項(xiàng)即原序列第k+1項(xiàng)，且Pnew,k+1→Pc,k，BNL(Pc,k)→BNL(Pnew,k+1)；若新插入序列與樹中已插入序列首項(xiàng)均不同，則將序列所有項(xiàng)記入新LPN中，此時(shí)根節(jié)點(diǎn)產(chǎn)生新子節(jié)點(diǎn)，Pnew,1→PRoot，BNL(PRoot)→BNL(Pnew,1)；若新序列所有項(xiàng)與已插入序列前k項(xiàng)相同，則將原序列前k項(xiàng)支持度+1，自第k+1項(xiàng)移出生成新LPN，Pnew,1→Pc,k，BNL(Pc,k)→BNL(Pnew,1)。

Step4記LPN內(nèi)節(jié)點(diǎn)為qc,k，將所有LPN中具有子節(jié)點(diǎn)的內(nèi)節(jié)點(diǎn)的“branch information”記為“true”，否則記為“false”。將所有同名稱項(xiàng)節(jié)點(diǎn)自node.link起始鏈接，若無(wú)節(jié)點(diǎn)間連接信息node.link位記為null，BNL信息依據(jù)LPN連接情況補(bǔ)充完整。

至此，MSLP-tree構(gòu)造完畢。

算法1MSLP-tree構(gòu)造算法

輸入：序列數(shù)據(jù)庫(kù)S，數(shù)據(jù)項(xiàng)集合I，項(xiàng)目最小支持度表，極小最小支持度LMS

輸出：MSLP-tree

Step1

1) 掃描序列數(shù)據(jù)庫(kù)S，找出所有數(shù)據(jù)項(xiàng)i；

2) Generate Root；

//創(chuàng)建樹的根節(jié)點(diǎn)

3) For each itemiinI；

4) Count the support ofi；

//對(duì)i進(jìn)行支持度計(jì)數(shù)；

5) If sup(ij)

//刪除非LMS模式項(xiàng)

6) end if；

7) Create Header List；

//生成頭表，數(shù)據(jù)項(xiàng)按MIS升序排列；

8) end for；

Step2

9) For each itemiins；

10)ik←first item，l←the length；

//ik為s首項(xiàng)，l為s長(zhǎng)度

11) end for；

12) 在樹中插入序列s，記為L(zhǎng)PNc；

13) If i is an extension item，i=_i；

//i為項(xiàng)集擴(kuò)展，在i前添加“_”

14)Pc,kS++；

//各項(xiàng)支持度+1

15) Link theLPNcwith Root；

16)PRoot←Pc,1；

17) Generate BNL；

//生成BNL；

18)BNL(PRoot)→BNL(Pc,1)；

//將PRoot記入branch node list中，Pc,1記入child node list中；

19) end if；

Step3

20) Insert next sequence；

//繼續(xù)將剩余序列插入樹中

21) Ifik=Pc,k，ik?Snew，Pc,1?BNL(PRoot)，

//新序列中前k項(xiàng)與LPNc中前k項(xiàng)相同

22) ThenPc,kS++；

//LPNc前k項(xiàng)支持度各+1

23) GenerateLPNnew，ik+1=Pnew,1；

//序列第k+1項(xiàng)為L(zhǎng)PN首項(xiàng)，序列長(zhǎng)度為l=n-k+1

24)Pc,k←Pnew,1；

25)BNL(Pc,k)→BNL(Pnew,1)；

26) Else ifi1≠Pc,1，i1?Snew，Pc,1?BNL(PRoot)；

//新序列的第1項(xiàng)和Root所有子節(jié)點(diǎn)均不等

27) GenerateLPNnew；

//生成新LPN

28)Pnew,kS++；

29)PRoot←Pnew,1；

30)BNL(Pc,k)→BNL(Pnew,1)；

31) Else ifin=Pc,k，k≠n，in?Snew，Pc,k?BNL(PRoot)；

//如果新序列的所有項(xiàng)與LPNc前k項(xiàng)相同

32)Pc,kS++；

//LPNc前k項(xiàng)支持度+1

33) Remove the restn-kitem ofLPNcas the newLPN；

34)Pnew,kS++；

35)Pc,k←Pnew,1；

36)BNL(Pc,k)→BNL(Pnew,1)；

37) end if；

38) Go to line 17 for next sequence ；

Step4

39) ifqc,k有子節(jié)點(diǎn)，thenb=true；

40) elseb=false；

41) link all nodes with same name；

//將相同名稱節(jié)點(diǎn)相連

42) Ifqhas no link， then node.link=null；

43) end if；

44) Return tree

對(duì)于表1中序列，其MSLP-tree構(gòu)建過(guò)程如下：

1) 掃描數(shù)據(jù)庫(kù)S，找出所有項(xiàng)并對(duì)各項(xiàng)支持度進(jìn)行計(jì)數(shù)，其中a=4，b=4，c=3，d=3，e=3，f=3，g=1；根據(jù)表2中各項(xiàng)最小支持度值，LMS=0.3，sup(g)

2) 構(gòu)建樹的根節(jié)點(diǎn)Root，將序列s1=插入樹中，對(duì)于項(xiàng)集(abc),(ac),(cf)在項(xiàng)集擴(kuò)展項(xiàng)前添加”_”，即“_bc”“_c”“_f”，生成LPN1；LPN1內(nèi)各節(jié)點(diǎn)支持度計(jì)數(shù)記為1；將第一個(gè)內(nèi)節(jié)點(diǎn)指針P1,1指向根節(jié)點(diǎn)PRoot，在BNL中，將PRoot記錄到枝節(jié)點(diǎn)表中，P1,1記錄到子節(jié)點(diǎn)表中，BNL(PRoot)→BNL(P1,1)，LPN1表頭記為PRoot。

3) 將序列s2=<(ad)c(bc)(ae)>插入樹中，檢查序列中各項(xiàng)均在頭表中，其與s1具有相同前綴a，故將”_d”作為a的子節(jié)點(diǎn)，構(gòu)造新的LPN，新的LPN首節(jié)點(diǎn)為”_d”，其指針指向LPN1中節(jié)點(diǎn)a，同時(shí)節(jié)點(diǎn)a支持度加1，將所有項(xiàng)按在序列中的順序依次記入LPN2中，LPN2中各節(jié)點(diǎn)支持度記為1；在BNL中，將P1,1記錄到枝節(jié)點(diǎn)表中，P2,1記錄到子節(jié)點(diǎn)表中，BNL(P1,1)→BNL(P2,1)，LPN2表頭記為P1,1。

4) 將序列s3=<(ef)(ab)(df)cb>插入樹中，s3中各項(xiàng)均在頭表項(xiàng)中，s3與s1具有不同前綴，創(chuàng)建新的LPN，將各項(xiàng)按順序記入LPN中，新LPN3內(nèi)首節(jié)點(diǎn)項(xiàng)為e，其指針P3,1指向根節(jié)點(diǎn)Root，LPN3中所有節(jié)點(diǎn)支持度記為1；在BNL中，將P3,1添加到PRoot對(duì)應(yīng)的子節(jié)點(diǎn)表中，BNL(PRoot)→BNL(P3,1)，LPN3表頭記為PRoot。

5) 將序列s4=插入樹中，刪除不滿足sup(i)≥LMS的項(xiàng)g，并將其余項(xiàng)按各項(xiàng)在序列中前后順序依次記入數(shù)組中，s4與s3具有相同前綴e，故將a作為e的子節(jié)點(diǎn)，創(chuàng)建新LPN，將各項(xiàng)按順序記入LPN中，新LPN4首節(jié)點(diǎn)為a，其指針P4,1指向節(jié)點(diǎn)P3,1，節(jié)點(diǎn)e支持度加1，LPN4中所有節(jié)點(diǎn)支持度記為1；在BNL中，將P3,1記錄到枝節(jié)點(diǎn)表中，P4,1記錄到子節(jié)點(diǎn)表中，BNL(P3,1)→BNL(P4,1)，LPN4表頭記為P3,1。

6)S中所有序列插入完畢，頭表中自node.Link起始，鏈接所有名稱相同項(xiàng)，各LPN內(nèi)節(jié)點(diǎn)屬性信息node.link及branch information補(bǔ)充完整，至此，MSLP-tree構(gòu)造完畢。前綴樹的最終結(jié)構(gòu)如圖2所示。

圖2 示例前綴樹

基于MSLP-tree結(jié)構(gòu)，序列數(shù)據(jù)庫(kù)中所有序列都可以在樹中找到其唯一路徑，且樹中只存在所有滿足mis和LMS模式的項(xiàng)。對(duì)于所有滿足最小支持度條件的序列模式，根據(jù)頭表node.link鏈接信息，遍歷整個(gè)MSLP-tree，即可得到所有符合支持度要求的模式。在MSLP-tree的構(gòu)建過(guò)程中，將序列重合部分進(jìn)行分枝整合，能夠壓縮樹的結(jié)構(gòu)，減少路徑遍歷次數(shù)。同時(shí)可以提前過(guò)濾不可能成為頻繁項(xiàng)的信息，從而減少中間冗余信息。

樹的遍歷過(guò)程采用深度優(yōu)先方式，從根節(jié)點(diǎn)開始依次遍歷所有節(jié)點(diǎn)。首先，找到當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)，以及所有與其同名項(xiàng)；然后，通過(guò)子節(jié)點(diǎn)以及相同項(xiàng)找到該路徑下在樹中最后一個(gè)節(jié)點(diǎn)；最后，遍歷所有的子節(jié)點(diǎn)及其兄弟節(jié)點(diǎn)，直到不再有未遍歷的節(jié)點(diǎn)。

3 MSLP-growth算法

算法主要思想是將不同前綴項(xiàng)下的所有路徑劃分于不同搜索空間進(jìn)行挖掘。由于該項(xiàng)條件下的前綴樹結(jié)構(gòu)已包含所有該項(xiàng)的條件序列，故可挖掘出所有符合最小支持度條件的完整的序列模式的集合。挖掘過(guò)程如算法2。

記K={k1，k2，…，kn}為頻繁序列模式集合，ki(1≤i≤n)為頻繁模式，ki=。

首先，從頭表中第一項(xiàng)開始，由node.link信息找到所有同名項(xiàng)進(jìn)行支持度計(jì)數(shù)，其中，i與_i分別計(jì)數(shù)，同一序列中具有相同前綴項(xiàng)不重復(fù)計(jì)數(shù)。根據(jù)當(dāng)前計(jì)數(shù)以及當(dāng)前最小支持度值與模式判斷條件相比較，滿足sup≥LMS且sup≥mis的輸出到K中，并以i為條件前綴繼續(xù)在i的前綴樹中挖掘；滿足sup≥LMS但不滿足sup≥mis條件的予以保留以待繼續(xù)挖掘其可能存在的頻繁超序列模式；對(duì)于不滿足sup≥LMS的，不再繼續(xù)挖掘。

其次，對(duì)于存在后綴以及子節(jié)點(diǎn)的模式，記i′為i在附加某一i之后的超序列，記R為前綴集合，將i′記入R中。對(duì)i′繼續(xù)挖掘，對(duì)所有i′模式進(jìn)行支持度計(jì)數(shù)，計(jì)數(shù)方式同i。根據(jù)當(dāng)前計(jì)數(shù)及最小支持度值，判斷是否為頻繁模式，若當(dāng)前i′模式仍有后綴模式存在，則照此法繼續(xù)挖掘；若已無(wú)超序列模式，則對(duì)當(dāng)前前綴項(xiàng)終止挖掘。

最后，將頭表中所有項(xiàng)按以上步驟遞歸挖掘。

算法2MSLP-growth算法

輸入：MSLP-tree結(jié)構(gòu)，Header List，LMS

輸出：頻繁序列模式集K

Step1

1) For each i in Header List；

2) For each node q，q.name=i.name；

//q為i的node.link鏈接同名項(xiàng)

3) Count support of q；

4) If同一序列中有多個(gè)q，then只做一次計(jì)數(shù)；

5) Count q and _q separately；

6) If sup(q)≥LMS and sup(q)≥mis，

//mis為當(dāng)前m值

7) Then output q；

8) If q有后綴節(jié)點(diǎn)或子節(jié)點(diǎn)；

9) Put q into R；

//R為前綴根節(jié)點(diǎn)集合

10) If sup(q)≥LMS，but sup(q)≥mis，then retain q；

11) If sup(q)

Step2

12) For q in R；

13) Append i after q as q′；

14) Count support of q′；

15) If sup(q′)≥LMS and sup(q′)≥mis；

16) Then output q′ into K；

17) If q′有后綴節(jié)點(diǎn)或子節(jié)點(diǎn)；

18) Put q′ into R；

19) If sup(q′)≥LMS but sup(q′)≥mis，then retain q′；

20) If sup(q′)

21) If q′沒有超序列，then stop mining；

22) Output q′ into K；

Step3

23) Loop until there is no prefix node exist；

24) End；

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

本文的實(shí)驗(yàn)平臺(tái)為Intel(R)Core(TM)i7-4790處理器，CPU3.6 GHz，2.0 GB運(yùn)行內(nèi)存，64位windows 7操作系統(tǒng)。算法采用C++語(yǔ)言實(shí)現(xiàn)，編譯環(huán)境Visual C++6.0。實(shí)驗(yàn)數(shù)據(jù)采用IBM公司數(shù)據(jù)生成器生成的標(biāo)準(zhǔn)數(shù)據(jù)集[1]。數(shù)據(jù)集相關(guān)參數(shù)設(shè)置如下：D為客戶數(shù)；T為客戶平均事務(wù)數(shù)；I為事務(wù)平均項(xiàng)數(shù)，設(shè)為2.5；N為項(xiàng)數(shù)，設(shè)為10 000；L為最大頻繁序列平均長(zhǎng)度，設(shè)為4。

本文采用文獻(xiàn)[9]中提出的多最小支持度設(shè)置方法，定義各項(xiàng)mis值取為：

mis(ij)=max{βf(ij),LMS}

式中：β為常量，取值范圍為[0,1]；f(ij)為各項(xiàng)的頻率函數(shù)，即各項(xiàng)的支持度；LMS為設(shè)定的極小最小支持度。當(dāng)β=0時(shí)，mis(ij)=LMS，即所有項(xiàng)最小支持度相同，皆為L(zhǎng)MS；當(dāng)β=1時(shí)，由于f(ij)≥LMS，所以mis(ij)=f(ij)。

4.1 性能測(cè)試

實(shí)驗(yàn)首先對(duì)LMS值固定、β值改變的情況下，MSLP-growth算法和MS-GSP算法的性能進(jìn)行比較。兩算法的執(zhí)行時(shí)間與內(nèi)存消耗對(duì)比結(jié)果分別如圖3及圖4所示。

圖3 算法執(zhí)行時(shí)間比較(LMS=0.015，D=100×103，T=10)

圖4 算法空間消耗比較(LMS=0.015，D=100×103，T=10)

如圖3所示，MSLP-growth算法的執(zhí)行時(shí)間明顯低于MS-GSP算法。這是因?yàn)镸S-GSP算法在執(zhí)行過(guò)程中產(chǎn)生大量的候選序列，導(dǎo)致算法的執(zhí)行時(shí)間更長(zhǎng)。MSLP-growth算法由于不需要生成候選序列，而是采用“邊挖掘邊檢驗(yàn)”的策略，在挖掘中即生成頻繁模式，而且對(duì)于那些不會(huì)產(chǎn)生頻繁超序列的前綴模式不再繼續(xù)挖掘，節(jié)省了大量不必要的運(yùn)算時(shí)間。隨著β值的增大，滿足條件的模式數(shù)量逐漸減少，MSLP-growth算法和MS-GSP算法的執(zhí)行時(shí)間都相對(duì)縮短，但MSLP-growth算法性能仍然高于MS-GSP算法。

圖4描述了MSLP-growth算法和MS-GSP算法的內(nèi)存消耗對(duì)比結(jié)果。從圖4中可以看出，本文所提出的MSLP-growth算法具有較小的內(nèi)存消耗。這是因?yàn)镸SLP-growth算法采用線性結(jié)構(gòu)，并且采用分枝整合策略實(shí)現(xiàn)MSLP-tree的最大化壓縮。同時(shí)在挖掘前刪除大量的非頻繁項(xiàng)，從而有效降低內(nèi)存使用量。

4.2 可擴(kuò)展性測(cè)試

在算法可擴(kuò)展性測(cè)試中，設(shè)定LMS與β為0.025和0.5，客戶數(shù)量D從100×103到500×103，每次增加100×103，兩算法的執(zhí)行時(shí)間對(duì)比結(jié)果如圖5所示?？梢园l(fā)現(xiàn)，隨著數(shù)據(jù)集容量逐漸變大，MSLP-growth算法的運(yùn)算時(shí)間趨于穩(wěn)定，而MS-GSP算法的執(zhí)行時(shí)間則顯著增加。由以上分析可知，MSLP-growth算法具有良好的可擴(kuò)展性。

圖5 算法執(zhí)行時(shí)間比較(LMS=0.025，β=0.5，T=10)

綜上分析，無(wú)論是在以支持度閾值為條件變量，還是在不同容量數(shù)據(jù)集環(huán)境下，本文所提出的MSLP-growth算法都表現(xiàn)出優(yōu)越的性能。

5 結(jié) 語(yǔ)

本文針對(duì)現(xiàn)有主流序列模式挖掘算法無(wú)法有效滿足用戶行為模式挖掘的應(yīng)用需求，提出一種基于前綴樹結(jié)構(gòu)的多支持度序列模式挖掘方法。通過(guò)為序列中各項(xiàng)設(shè)置不同最小支持度，解決了單一支持度閾值下行為模式挖掘的準(zhǔn)確度和效率過(guò)低的問(wèn)題。實(shí)驗(yàn)結(jié)果表明了本文所提算法的高效性和良好的可擴(kuò)展性。下一步工作將進(jìn)一步討論多最小支持度下算法優(yōu)化問(wèn)題以及不同項(xiàng)目權(quán)重對(duì)用戶行為模式生成結(jié)果的影響。

[1] Agrawal R,Srikant R.Mining sequential patterns[C]//Eleventh International Conference on Data Engineering.IEEE Xplore,1995:3-14.

[2] Srikant R,Agrawal R.Mining Sequential Patterns:Generalizations and Performance Improvements[C]//International Conference on Extending Database Technology:Advances in Database Technology.Springer-Verlag,1996:3-17.

[3] Zaki M J.SPADE:an efficient algorithm for mining frequent sequences[J].Machine Learning,2001,42(1):31-60.

[4] Pei J,Han J,Mortazavi-Asl B,et al.PrefixSpan:Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[C]//International Conference on Data Engineering.IEEE Computer Society,2001:215.

[5] Ayres J,Flannick J,Gehrke J,et al.Sequential PAttern mining using a bitmap representation[C]//Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2002:429-435.

[6] Le B,Tran MT,Tran D.A method for early pruning a branch of candidates in the process of mining sequential patterns[C]//Intelligent Information and Database Systems.ACIIDS 2017.Lecture Notes in Computer Science,Springer,2017,vol 10191.

[7] Zihayat M,Chen Y,An A.Memory-adaptive high utility sequential pattern mining over data streams[J].Machine Learning,2017,106(6):799-836.

[8] Kemmar A,Lebbah Y,Loudni S,et al.Prefix-projection global constraint and top- k,approach for sequential pattern mining[J].Constraints,2017,22(2):265-306.

[9] Liu B,Hsu W,Ma Y.Mining association rules with multiple minimum supports[C]//Proceeding of the 5th International Conference on Knowledge Discovery and Data Mining,San Diego,CA,USA.1999.

[10] Hu Y H,Chen Y L.Mining association rules with multiple minimum supports:a new mining algorithm and a support tuning mechanism[J].Decision Support Systems,2006,42(1):1-24.

[11] Kiran R U,Reddy P K.Novel techniques to reduce search space in multiple minimum supports-based frequent pattern mining algorithms[C]//International Conference on Extending Database Technology.ACM,2011:11-20.

[12] Wang C S,Lin S L,Chang J Y.MapReduce-Based frequent pattern mining framework with multiple item support[C]//Intelligent Information and Database Systems.ACIIDS 2017.Lecture Notes in Computer Science,Springer,2017,vol 10192.

[13] Liu B.Web data mining:exploring hyperlinks,Contents,and Usage Data[M].Springer-Verlag Berlin Heidelberg,2007:41-45.

[14] Huang C K.Discovery of fuzzy quantitative sequential patterns with multiple minimum supports and adjustable membership functions[J].Information Sciences,2013,222(3):126-146.

[15] Pyun G,Yun U,Ryu K H.Efficient frequent pattern mining based on Linear Prefix tree[J].Knowledge-Based Systems,2014,55:125-139.