一種無候選項(xiàng)的閉合序列模式挖掘算法

楊　斐　張萬楨　陸垂偉

1(湖北理工學(xué)院計(jì)算機(jī)學(xué)院　湖北 黃石 435003)2(桂林電子科技大學(xué)　廣西 桂林 541004)

?

一種無候選項(xiàng)的閉合序列模式挖掘算法

楊斐1張萬楨2陸垂偉1

1(湖北理工學(xué)院計(jì)算機(jī)學(xué)院湖北 黃石 435003)2(桂林電子科技大學(xué)廣西 桂林 541004)

算法CloSpan在挖掘閉合序列模式時(shí)分兩階段進(jìn)行，首先產(chǎn)生候選的閉合序列模式，然后在此基礎(chǔ)上挖掘閉合序列模式。針對(duì)CloSpan算法中大量候選模式影響挖掘效率的問題，提出改進(jìn)的算法ssCloSpan。該算法在序列模式增長時(shí)，利用支持度和末節(jié)點(diǎn)哈希表剪枝非閉合模式，同時(shí)利用頻繁項(xiàng)頭表進(jìn)行閉合性檢測(cè)。實(shí)驗(yàn)結(jié)果表明，對(duì)于不含項(xiàng)集項(xiàng)的序列，當(dāng)存在較長頻繁序列時(shí)，挖掘效率得到了有效的提高。

閉合序列模式支持?jǐn)?shù)剪枝末節(jié)點(diǎn)哈希表頻繁項(xiàng)頭表

0　引　言

傳統(tǒng)序列模式挖掘算法主要是從序列數(shù)據(jù)庫中挖掘出所有滿足支持度閾值的頻繁序列。從AprioriAll算法到PrefixSpan算法，雖然算法性能總體上得到了提高，但當(dāng)支持度閾值較低時(shí)，都會(huì)產(chǎn)生大量符合條件的序列模式。一方面不能高效地從挖掘結(jié)果中提取有用的信息；另一方面也使得挖掘效率大大降低，當(dāng)挖掘時(shí)面臨的是長序列模式數(shù)據(jù)庫，類似的情況更容易出現(xiàn)[1]。分析得知挖掘得到的序列模式存在大量冗余信息，因此挖掘最大序列模式和挖掘閉合序列模式的問題被提出。

閉合序列模式挖掘的CloSpan算法分兩個(gè)階段進(jìn)行，第一階段是產(chǎn)生候選集階段，同時(shí)生成前綴序列搜索樹；第二階段是剪枝掉非閉合序列階段，從而得到全部的閉合序列。在第一階段中，該算法采用公共前綴及子模式回溯、超模式回溯等策略剪枝生成的前綴序列搜索樹，使得PrefixSpan算法結(jié)構(gòu)框架下不斷生成投影序列數(shù)據(jù)庫的過程可以提早結(jié)束。分析發(fā)現(xiàn)，CloSpan算法存在保留候選閉合序列從而影響效率的問題，因此本文提出改進(jìn)后的ssCloSpan算法，考慮在第一階段生成前綴搜索樹的同時(shí)消除所有的非閉合序列，直接得到所有閉合序列模式。

1　相關(guān)概念

前綴搜索樹中的層： 給定一棵空樹，則其層數(shù)為0。從根節(jié)點(diǎn)開始深度優(yōu)先遍歷其節(jié)點(diǎn)時(shí)，必定由底層向高層遍歷。具體如圖1所示。

圖1　前綴搜素樹層次圖

前綴搜索樹節(jié)點(diǎn)：前綴搜索樹節(jié)點(diǎn)由六部分組成，分別是項(xiàng)名、支持?jǐn)?shù)、層數(shù)、閉合性標(biāo)記、父節(jié)點(diǎn)指針域、下一閉合節(jié)點(diǎn)指針域[2]。其中項(xiàng)名即該節(jié)點(diǎn)的名稱，由于節(jié)點(diǎn)亦代表從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的序列，所以支持?jǐn)?shù)即為該序列的支持?jǐn)?shù)，父節(jié)點(diǎn)指針域指向父節(jié)點(diǎn)，即序列中的上一個(gè)節(jié)點(diǎn)，下一閉合節(jié)點(diǎn)指針域指向一個(gè)閉合序列，該序列的結(jié)束項(xiàng)與本節(jié)點(diǎn)項(xiàng)相同。

末節(jié)點(diǎn)哈希表：該哈希表中的哈希值即為頻繁項(xiàng)，指針域指向一系列的以該頻繁項(xiàng)為結(jié)束項(xiàng)的閉合序列。

頻繁項(xiàng)頭表：該頭表中的內(nèi)容為頻繁項(xiàng)，每個(gè)頻繁項(xiàng)指向各閉合序列中對(duì)應(yīng)的項(xiàng)節(jié)點(diǎn)。

圖2　子模式回溯

推論1(子模式回溯)如果一個(gè)序列s

推論2(超模式回溯)如果一個(gè)序列s

圖3　超模式回溯

以圖3為例，序列首先被發(fā)現(xiàn)，下面的三角形代表序列的子孫。序列后來被發(fā)現(xiàn)，當(dāng)發(fā)現(xiàn)序列時(shí)，首先檢測(cè)已發(fā)現(xiàn)的序列模式，看是否存在當(dāng)前序列的子模式或超模式，在圖2中，可以找到的超模式，即當(dāng)前為子模式，于是停止搜索序列下的三角形區(qū)域子孫，將合并至處。圖3中序列在序列之后被發(fā)現(xiàn)，即當(dāng)前序列為超模式，此時(shí)立即停止對(duì)序列子孫的搜索，直接將序列的子孫移植到的子孫處。

2　ssCloSpan算法

2.1前綴搜索樹和超序

通過不斷深度優(yōu)先增長序列實(shí)現(xiàn)前綴搜索樹的構(gòu)建，即在某一序列的基礎(chǔ)上增長其后續(xù)節(jié)點(diǎn)，因此，在同一分支上可能有明顯的超序產(chǎn)生，形如序列及其超序。另一方面，深度優(yōu)先仍以一定的劃分為前提。若頻繁項(xiàng)為a、b、c三項(xiàng)，設(shè)定字典序a≤b≤c，先將搜索空間按a、b、c劃分為三部分，再分別對(duì)a、b、c上深度優(yōu)先搜索，因此容易先產(chǎn)生形如的序列，而后產(chǎn)生或的子序列或后產(chǎn)生或的超序列。

同一分支上，超序在子序后產(chǎn)生；不同分支上，子序與超序產(chǎn)生的先后關(guān)系不確定[3]。因此在不同分支上確定超序的難度較大。然而基于前綴搜索樹中各節(jié)點(diǎn)有對(duì)應(yīng)的層信息，由超序的基本定義，至少滿足超序的長度比子序長，在不同分支上進(jìn)行超序判斷時(shí)可借鑒層信息[4]，提高閉合性檢測(cè)的效率。

2.2深度優(yōu)先策略與支持?jǐn)?shù)剪枝

在序列模式挖掘中，基于序列模式的時(shí)間順序性和連續(xù)性，通常采用深度優(yōu)先的方式挖掘序列[5,6]。在PrefixSpan算法被提出后，幾乎所有的算法都是基于此框架結(jié)構(gòu)，閉合序列模式挖掘也不例外。

根據(jù)閉合序列的概念，假定在深度優(yōu)先挖掘過程中會(huì)產(chǎn)生閉合序列，那么序列的支持?jǐn)?shù)和序列分支的組合情況如圖4所示。

(a)　　　(b)　　　　　(c)　　　　(d)圖4　前綴搜索樹中支持?jǐn)?shù)大小分布情況

圖4中顯示了樹結(jié)構(gòu)中所有的可能情況，前兩個(gè)圖中深度擴(kuò)展時(shí)僅有一個(gè)分支，后兩個(gè)圖代表深度擴(kuò)展時(shí)有多個(gè)分支。(a)中節(jié)點(diǎn)a的支持?jǐn)?shù)為3，節(jié)點(diǎn)b的支持?jǐn)?shù)為2，很顯然序列<…a>:3和序列<…b>:2都是閉合序列，由兩者不同的支持?jǐn)?shù)值便可推斷。而(b)中兩節(jié)點(diǎn)的支持?jǐn)?shù)都是3，序列<…a>是序列<…b>的子序，閉合序列是<…b>:3。(c)中節(jié)點(diǎn)a和節(jié)點(diǎn)b的支持?jǐn)?shù)是3，節(jié)點(diǎn)c的支持?jǐn)?shù)是2，閉合序列是<…ab>:3和<…ac>:2。(d)中節(jié)點(diǎn)a的支持?jǐn)?shù)是3，節(jié)點(diǎn)b和節(jié)點(diǎn)c的支持?jǐn)?shù)是2，閉合序列是<…ab>:2和<…ac>:2。

由此得出，當(dāng)某節(jié)點(diǎn)的支持?jǐn)?shù)等于其下一級(jí)節(jié)點(diǎn)的最大支持?jǐn)?shù)時(shí)，該節(jié)點(diǎn)所代表的序列一定不是閉合序列。當(dāng)某節(jié)點(diǎn)的支持?jǐn)?shù)大于其下一級(jí)每個(gè)節(jié)點(diǎn)的支持?jǐn)?shù)時(shí)，該節(jié)點(diǎn)所代表的序列一定是閉合序列。而對(duì)于序列數(shù)較長的序列，該方法能有效提高對(duì)非閉合序列的判斷效率。

2.3基于末節(jié)點(diǎn)哈希表的閉合性檢測(cè)

序列模式增長的同時(shí)，對(duì)當(dāng)前存在的閉合性序列集進(jìn)行檢測(cè)。若當(dāng)前節(jié)點(diǎn)為a，此檢測(cè)以末節(jié)點(diǎn)為基礎(chǔ)，僅檢測(cè)以末節(jié)點(diǎn)哈希表中哈希值為a的所指鏈表中的序列。若其中有以a為末節(jié)點(diǎn)的子序列，則將該序列從閉合序列中刪除。以此對(duì)非永久性的閉合序列進(jìn)行剪枝。

對(duì)于給定的字典序a≤b≤c≤d≤e，若有序列，則其同一分支上的子序列容易處理，已經(jīng)產(chǎn)生在其他分支上可能的子序列為、 、、和，即子序列的末節(jié)點(diǎn)分別為c、d、f。由于序列增長過程是從末節(jié)點(diǎn)e到c再逐步到f和d，因此對(duì)子序列的閉合性檢測(cè)會(huì)依照序列、、、、的順序逐一剪枝。由此亦可得知基于末節(jié)點(diǎn)的閉合性檢測(cè)對(duì)于子序列修剪的完備性。

在基于末節(jié)點(diǎn)哈希表的閉合性檢測(cè)中，通過支持?jǐn)?shù)和層數(shù)的信息加速檢測(cè)效率。當(dāng)末節(jié)點(diǎn)哈希表中的節(jié)點(diǎn)支持?jǐn)?shù)與當(dāng)前序列的支持?jǐn)?shù)相同，且層數(shù)不大于當(dāng)前序列的層數(shù)時(shí)，則進(jìn)行比較判斷子序列的過程，否則直接提前終止。

2.4基于頻繁項(xiàng)頭表的閉合性檢測(cè)

受Pei等在文獻(xiàn)[7]中提出的H-struct的啟發(fā)，構(gòu)建基于頻繁項(xiàng)的頭表。H-struct中是將首項(xiàng)相同的各交易鏈成不同的queues，將各queue的對(duì)應(yīng)項(xiàng)保存在一個(gè)占用極少空間的頭表中。本文將所有閉合序列中相同的項(xiàng)鏈接成鏈表，由頻繁項(xiàng)頭表中相對(duì)應(yīng)的項(xiàng)作為頭節(jié)點(diǎn)指向該鏈表。

頻繁項(xiàng)頭表主要用于對(duì)超序的檢測(cè)，由于子序出現(xiàn)在超序中的位置的不確定性，判斷當(dāng)前序列S是否為子序，可以通過S序列的末節(jié)點(diǎn)開始，在頭表中找到該項(xiàng)，然后進(jìn)入鏈表入口，逐一判斷已產(chǎn)生的閉合序列集中是否有自身的超序出現(xiàn)[8]。如果檢測(cè)到超序，則表明序列S是非閉合序列，可能存在其他非閉合序列，利用末節(jié)點(diǎn)哈希表可將其修剪掉。反之，若未檢測(cè)到超序，則序列S則為閉合序列，加入到閉合序列集中。

在檢測(cè)時(shí)通過支持?jǐn)?shù)和層數(shù)以提高檢測(cè)的效率。當(dāng)頻繁項(xiàng)頭表中序列節(jié)點(diǎn)的支持?jǐn)?shù)與當(dāng)前序列的支持?jǐn)?shù)相同，且層數(shù)不小于當(dāng)前序列的層數(shù)，則進(jìn)行比較判斷，否則直接提前終止。序列數(shù)據(jù)庫如表1所示。

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

對(duì)于表1所示的數(shù)據(jù)庫，以頻繁項(xiàng)a為例，對(duì)于第一層：

① 計(jì)算I(Ds)；默認(rèn)字序?yàn)樯疃葍?yōu)先挖掘的順序即：a≤b≤c≤d≤e≤f。首先計(jì)算I(D)=21。同時(shí)得到頻繁項(xiàng):4，:4，:3，:3。

② 根據(jù)情況判斷是否將該點(diǎn)加入數(shù)據(jù)庫大小哈希表IH中對(duì)應(yīng)的指針鏈表，并更新前綴搜索樹L；將a加入到前綴搜索樹L；IH中無哈希值21，故將21加入到IH中，同時(shí)將a鏈入到相應(yīng)的指針域。

③ 根據(jù)支持?jǐn)?shù)情況判斷是否需要更新末節(jié)點(diǎn)哈希表LH以及頻繁項(xiàng)頭表FH；由于support()=support()=support()，故a不必加入到頻繁項(xiàng)頭表FH中。且由支持度信息可知，節(jié)點(diǎn)a不能構(gòu)成現(xiàn)有的閉合序列，故將a的閉合性標(biāo)志記為0，不必加入到末節(jié)點(diǎn)哈希表LH中。此時(shí)前綴搜索樹L及各哈希表的情況如圖5所示。

圖5　前綴搜索樹中加入節(jié)點(diǎn)a后的圖示

第二層：根據(jù)深度優(yōu)先挖掘的原則，且a存在下一層節(jié)點(diǎn):4，:4，:3，:3，以字典序首先考慮b節(jié)點(diǎn)，具體步驟順序與第一層處理方式相同。

第三層：采用與第二層同樣的步驟考慮節(jié)點(diǎn):4；獲得前綴搜索樹L及各哈希表的情況如圖6所示。

圖6　前綴搜索樹中加入多個(gè)節(jié)點(diǎn)后的圖示

根據(jù)遞歸算法，返回第二層繼續(xù)對(duì):4，:3，:3進(jìn)行序列模式挖掘。以此類推，最終獲得如圖7所示a分支深度優(yōu)先挖掘結(jié)束后的前綴搜索樹。

圖7　a分支深度優(yōu)先挖掘結(jié)束后的前綴搜索樹

2.5ssCloSpan算法的主要步驟

ssCloSpan算法的主要步驟如下：

(1) 掃描數(shù)據(jù)庫一遍，得到滿足支持度閾值min_sup的所有頻繁項(xiàng)，即頻繁1-序列。根據(jù)頻繁項(xiàng)劃分搜索空間。

(2) 在各搜索空間上，分別遞歸執(zhí)行以下操作步驟:

① 對(duì)于當(dāng)前的節(jié)點(diǎn)a，掃描其投影數(shù)據(jù)庫，得到投影數(shù)據(jù)庫中的頻繁項(xiàng)及各頻繁項(xiàng)的支持?jǐn)?shù)，同時(shí)得到當(dāng)前節(jié)點(diǎn)的I(Ds)值。

② 從數(shù)據(jù)庫大小哈希表IH中查找是否存在與I(Ds)值相同的子序或超序，以此進(jìn)行子模式回溯或超模式回溯，達(dá)到提前終止掃描投影數(shù)據(jù)庫的目的，以提高算法效率[9]。

③ 若當(dāng)前節(jié)點(diǎn)a未被②剪枝掉，則加入構(gòu)建的前綴搜索樹中，否則結(jié)束。

④ 若a節(jié)點(diǎn)的支持?jǐn)?shù)等于后續(xù)頻繁項(xiàng)的最大支持?jǐn)?shù)，則可確定該序列為非閉合序列，同時(shí)利用基于末節(jié)點(diǎn)的閉合性檢測(cè)方法，檢測(cè)已有閉合序列在各分支上的閉合性，之后進(jìn)行深度優(yōu)先模式增長。若a節(jié)點(diǎn)的支持?jǐn)?shù)大于其后續(xù)各頻繁項(xiàng)的最大支持?jǐn)?shù)，則該序列是當(dāng)前分支的閉合序列，利用基于頻繁項(xiàng)頭表的閉合性檢測(cè)方法檢測(cè)其在不同分支上的閉合性。如果檢測(cè)后發(fā)現(xiàn)該序列為不同分支上的閉合序列，則反向以該序列為基礎(chǔ)，通過基于末節(jié)點(diǎn)的閉合性檢測(cè)，反測(cè)已發(fā)現(xiàn)序列的閉合性。如果該序列不是閉合序列，則進(jìn)行深度優(yōu)先模式增長。

反復(fù)執(zhí)行以上各步驟，最后形成的末節(jié)點(diǎn)哈希表就是所有閉合序列模式的鏈表。

2.6ssCloSpan算法的偽代碼

為了更清晰地描述ssCloSpan算法的基本思想及主要步驟，特給出如下的形式化偽代碼加以說明。

算法ssCloSpan(S◇α，DS◇α，min_sup，L，LH，F(xiàn)H)

輸入：序列S◇α及其投影數(shù)據(jù)庫DS◇α和最小支持度閾值min_sup

輸出：前綴搜索樹L

方法：

1：調(diào)用子程序flag1=CheckProjection(S◇α，k，IH，L)

2：ifflag1=0then

3：return;

4：endif

5：ifflag1=1then

6：令flag2=1；

7：掃描DS◇α一遍，找出每個(gè)頻繁項(xiàng)β及其支持?jǐn)?shù)

8：if?support(α)=support(β) 或FH為空then

9：return；

10：elseif?support(α)>support(β) 或 不存在頻繁項(xiàng)βthen

11：調(diào)用flag2=SupS(S◇α，LH，F(xiàn)H)；

12：ifflag2=0then

13：for當(dāng)前分支上閉合性標(biāo)記為0的節(jié)點(diǎn)

14: 調(diào)用SubS(S◇α，LH，F(xiàn)H)；

15：endfor

16：endif

17：endif

18：endif

19：for每一個(gè)βdo

20：調(diào)用ssCloSpan(S◇α◇β，DS◇α◇β，min_sup，L，LH，F(xiàn)H)

21：endfor

22：return；

其中代碼第1行是用來提前終止模式增長的判斷，在此過程中已實(shí)現(xiàn)超模式回溯和子模式回溯的剪枝；第8行和第9行根據(jù)支持度的值進(jìn)行當(dāng)前分支非閉合序列的判斷，并提前結(jié)束；第10行和第11行根據(jù)已有閉合序列集中是否存在當(dāng)前分支閉合序列的超序來確定當(dāng)前序列是否為最終閉合性序列。第14行是對(duì)子程序SubS的調(diào)用，由支持度值和flag2的值共同決定，其中flag2的值為0，表示在頻繁項(xiàng)頭表中不存在當(dāng)前序列的超序。

子程序CheckProjection(S◇α，k，IH，L)

輸入：序列S◇α及其關(guān)鍵碼k(即為I(DS◇α))和數(shù)據(jù)庫大小哈希表IH,前綴搜索樹L

輸出：更新的哈希表IH

方法：

1：根據(jù)關(guān)鍵碼k索引數(shù)據(jù)庫大小哈希表IH

2：ifIH中不存在哈希值kthen

3：flag1=1;

4：將k值加入到IH中

5：將α插入到L中

6：else

7：if檢測(cè)到k值對(duì)應(yīng)的序列鏈中有(S◇α)?S′或者S′?(S◇α)then

8：flag1=0;

9：修改前綴搜索樹L中的指針鏈接

10：endif

11：returnflag1；

該子程序用來提前結(jié)束序列模式的增長，以flag1為結(jié)束的標(biāo)志。對(duì)于數(shù)據(jù)庫大小哈希表IH中哈希值與I(DS◇α)相等的序列鏈，若發(fā)現(xiàn)有S◇α的超序或者子序，則可以提前終止。

子程序SubS(S◇α，LH，F(xiàn)H)

輸入：序列S◇α，末節(jié)點(diǎn)哈希表LH和頻繁項(xiàng)頭表FH

輸出：更新的末節(jié)點(diǎn)哈希表LH和更新的頻繁項(xiàng)頭表FH

方法：

1：對(duì)于當(dāng)前節(jié)點(diǎn)α及其順序遞增的閉合性標(biāo)記為0的父節(jié)點(diǎn)

2：記當(dāng)前的末節(jié)點(diǎn)為t，根據(jù)關(guān)鍵碼t，索引末節(jié)點(diǎn)哈希表LH

3：if在LH中找到值tthen

4:fort指向的鏈表中的每一個(gè)序列Tdo

5：if該序列T是當(dāng)前序列的子序列then

6：刪掉LH中的序列T

7：刪掉FH中的序列T

8：endif

9：endfor；

10：endif；

11：將α加入到索引末節(jié)點(diǎn)哈希表LH中

12：return；

該子程序用來檢測(cè)閉合序列集中是否存在S◇α的子序列，以修剪掉臨時(shí)性的閉合序列。第1行中，當(dāng)某父節(jié)點(diǎn)的閉合性標(biāo)記為1，則停止向上一級(jí)父節(jié)點(diǎn)檢測(cè)。第4行至第9行是發(fā)現(xiàn)子序列的處理，可以利用層數(shù)和支持?jǐn)?shù)信息加速對(duì)比查找。

子程序SupS(S◇α，LH，F(xiàn)H)

輸入：序列S◇α，末節(jié)點(diǎn)哈希表LH和頻繁項(xiàng)頭表FH

輸出：更新的末節(jié)點(diǎn)哈希表LH和更新的頻繁項(xiàng)頭表FH

方法：

1：根據(jù)關(guān)鍵碼α，索引頻繁項(xiàng)頭表FH

2：flag2=0；

3：ifFH中關(guān)鍵碼αthen

4：forFH中α指向的鏈表中的每一個(gè)序列Tdo

5：ifT?(S◇α)then

6：flag2=1;break;

7：returnflag2；

8：endif

9：endfor；

10：endif；

11：將S◇α序列中以α為開始，直到某個(gè)父節(jié)點(diǎn)閉合性標(biāo)記為1之間的所有節(jié)點(diǎn)加入到頻繁項(xiàng)頭表FH中

12：returnflag2；

該子程序用來檢測(cè)閉合序列集中是否存在S◇α的超序列，并以flag2的值作為判斷的標(biāo)志。其中第5行判斷超序列時(shí)，利用支持?jǐn)?shù)和層數(shù)的信息加速比較判斷。第7行中的break語句表示只要找到一個(gè)超序則停止繼續(xù)查找，因?yàn)榇藭r(shí)足以確定序列S◇α不可能為閉合序列。第11行中實(shí)現(xiàn)了對(duì)加入頻繁項(xiàng)頭表FH中的節(jié)點(diǎn)的剪枝，以減少后續(xù)的比較次數(shù)。

3　實(shí)驗(yàn)及分析

算法CloSpan在挖掘閉合序列模式的第一階段采用子模式回溯和超模式回溯，提前結(jié)束在某些分支上的挖掘，減少不必要的投影，獲得全部頻繁模式。第二階段在此基礎(chǔ)上逐一排除非閉合模式，由于基數(shù)較大，在一定程度上影響了算法的效率[10]。而算法ssCloSpan在第一階段就直接獲得閉合模式，考慮在同一分支上，閉合序列與非閉合序列的支持?jǐn)?shù)特征，直接刪除同一分支上的非閉合序列，同時(shí)采用子模式回溯、超模式回溯、頻繁項(xiàng)頭表剪枝、末節(jié)點(diǎn)哈希表剪枝的綜合策略，刪除不同分支的非閉合序列，特別在處理長序列模式時(shí)，同一分支上的優(yōu)勢(shì)更為突出，算法性能的優(yōu)化也更明顯。

本文實(shí)驗(yàn)環(huán)境為CPUIntelCore2.00GHz，2GB內(nèi)存，Windows7操作系統(tǒng)，算法代碼采用C++編寫，在VisualC++ 6.0環(huán)境下進(jìn)行編譯。實(shí)驗(yàn)測(cè)試數(shù)據(jù)采用IBMQuestSyntheticDataGenerator生成，對(duì)數(shù)據(jù)集D10C10N10S6和數(shù)據(jù)集D5C20N10S10進(jìn)行測(cè)試。測(cè)試數(shù)據(jù)集生成過程中相關(guān)的參數(shù)為：D表示顧客數(shù)，默認(rèn)值為1000；C表示每個(gè)顧客的平均事務(wù)數(shù)，默認(rèn)值為10；T表示每個(gè)事務(wù)的平均項(xiàng)數(shù)，默認(rèn)值為2.5；N表示總項(xiàng)數(shù)，設(shè)為1000；I表示最長頻繁序列的平均長度，設(shè)為1.25。實(shí)驗(yàn)結(jié)果如圖8和圖9所示。

圖8　D10C10N10S6數(shù)據(jù)集

圖9　D5C20N10S10數(shù)據(jù)集

圖8以數(shù)據(jù)集D10C10N10S6為測(cè)試數(shù)據(jù)，圖中可以看出在支持度較高時(shí)，兩算法的執(zhí)行時(shí)間比較接近，隨著支持度的減小，挖掘出來的序列模式越來越多，相應(yīng)的閉合序列模式也會(huì)越來越多，此時(shí)算法ssCloSpan的優(yōu)勢(shì)得以體現(xiàn)。圖9以數(shù)據(jù)集D5C20N10S10為測(cè)試數(shù)據(jù)的實(shí)驗(yàn)結(jié)果圖，由于在生成數(shù)據(jù)集時(shí)，該數(shù)據(jù)集的序列長度參數(shù)要比D10C10N10S6數(shù)據(jù)集的序列長度參數(shù)設(shè)置得更大，因此支持度的設(shè)置也相應(yīng)提高。在挖掘較長的序列模式時(shí)，采用不同支持度的情況下ssCloSpan算法性能均優(yōu)于CloSpan算法。與理論上采用支持?jǐn)?shù)剪枝，快速確定閉合性序列的策略相吻合。

實(shí)驗(yàn)結(jié)果證明，ssCloSpan算法在挖掘閉合序列模式方面優(yōu)于CloSpan算法，尤其是在處理含較長序列的數(shù)據(jù)集時(shí)，優(yōu)勢(shì)更為突出，實(shí)驗(yàn)結(jié)果符合理論分析。

4　結(jié)　語

本文在分析當(dāng)前主要閉合序列模式挖掘算法的基礎(chǔ)上，根據(jù)算法CloSpan中存在候選閉合序列模式的問題，提出了無候選閉合序列的序列模式挖掘算法ssCloSpan。該算法利用子模式回溯和超模式回溯加速深度優(yōu)先挖掘的前提下，對(duì)每次產(chǎn)生的頻繁序列進(jìn)行非閉合性剪枝。剪枝的策略一方面有賴于支持度的數(shù)值，另一方面由末節(jié)點(diǎn)哈希表快速剪枝掉閉合序列的子序列。同時(shí)根據(jù)頻繁項(xiàng)頭表迅速判斷當(dāng)前序列的閉合性。實(shí)驗(yàn)結(jié)果表明，在處理含較長序列的數(shù)據(jù)集時(shí)該算法在執(zhí)行效率上優(yōu)于CloSpan算法。

[1]YanX,HanJ,AfsharR.CloSpan:MiningClosedSequentialPatternsinLargeDatasets[C]//Proc.ofthe3rdSLAMInt.Conf.onDataMining.SanFrancisco,USA:2003:166-177.

[2]HanJW,KamberM.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2007.

[3]HalawaniSM,ZubairKhanM.AStudyofCustomerBehaviorandSalesPromotionUsingGeneralizedSequentialPatternMining[J].InternationalJournalofEngineeringandTechnology,2010,2(2):149-154.

[4] 王丹丹,蔣文娟.一種新的工作流頻繁閉合模式挖掘算法研究[J].計(jì)算機(jī)科學(xué),2012,39(11):153-156.

[5] 公偉,劉培玉,賈嫻. 基于改進(jìn)PrefixSpan的序列模式挖掘算法[J].計(jì)算機(jī)應(yīng)用,2011,31(9):2405-2407.

[6]PeiJ,HanJ,LuH,etal.H-Mine:Hyper-StructureMiningofFrequentPatternsinLargeDatabases[C]//Proc.ofthe2001IEEEInt.Conf.onDataMining.SanJose,USA:2009:441-448.

[7] 王翠青,陳未如.序列模式挖掘支持度閾值的確定方法[J].計(jì)算機(jī)工程,2010,36(8):93-95.

[8]LinJR,HsiehCY,YangDL,etal.AFlexibleandEfficientSequentialPatternMiningAlgorithm[J].InternationalJournalofIntelligentInformationandDatabaseSystems,2009(3):291-310.

[9] 張巍,劉峰,滕少華.改進(jìn)的PrefixSpan算法及其在序列模式挖掘中的應(yīng)用[J].廣東工業(yè)大學(xué)學(xué)報(bào),2013,30(4):49-54.

[10] 付宇,于艷華,宋美娜,等.時(shí)序關(guān)系下的閉合序列模式挖掘算法[J].北京郵電大學(xué)學(xué)報(bào),2013,36(4):19-22.

ACLOSEDSEQUENTIALPATTERNMININGALGORITHMWITHOUTCANDIDATETERMS

YangFei1ZhangWanzhen2LuChuiwei1

1(School of Computer Science, Hubei Polytechnic University, Huangshi 435003,Hubei,China)2(School of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin 541004,Guangxi,China)

Whenminingtheclosedsequentialpatterns,thealgorithmCloSpandoesitintwophases.First,itwillgeneratethecandidateclosedsequentialpatterns,andthenbasedonthisitminestheclosedsequentialpatterns.AimingattheproblemofnumerouscandidatepatternsimpactingtheminingefficiencyinCloSpanalgorithm,weproposedanimprovedalgorithmcalledssCloSpan.Thisalgorithmprunesthenon-closedpatternsusingsupportdegreeandlastnodehashtableinthecourseofsequentialpatterngrowth,meanwhileitusesfrequentitemheadertableforclosurechecking.Experimentalresultsshowedthatforthesequenceswithoutitemsetsandwithlongerfrequentsequence,theminingefficiencywaswellimproved.

ClosedsequentialpatternSupportnumberpruningLastnodehashtableFrequentitemheadertable

2014-08-30。湖北省自然科學(xué)基金項(xiàng)目(2013CFB039)；湖北省教育廳重點(diǎn)科學(xué)研究項(xiàng)目(D20144403)；湖北省教育廳科學(xué)研究項(xiàng)目(B2013064)；湖北理工學(xué)院優(yōu)秀青年科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目(13xtz10)。楊斐，講師，主研領(lǐng)域：可重構(gòu)技術(shù)、嵌入式系統(tǒng)可信計(jì)算。張萬楨，講師。陸垂偉，副教授。

TP311.13

ADOI:10.3969/j.issn.1000-386x.2016.03.066