楊　斐　張萬楨　陸垂偉

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

?

一種無候選項的閉合序列模式挖掘算法

楊斐1張萬楨2陸垂偉1

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

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

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

0　引　言

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

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

1　相關(guān)概念

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

圖1　前綴搜素樹層次圖

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

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

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

圖2　子模式回溯

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

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

圖3　超模式回溯

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

2　ssCloSpan算法

2.1前綴搜索樹和超序

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

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

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

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

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

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

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

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

2.3基于末節(jié)點哈希表的閉合性檢測

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

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

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

2.4基于頻繁項頭表的閉合性檢測

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

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

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

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

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

① 計算I(Ds)；默認(rèn)字序為深度優(yōu)先挖掘的順序即：a≤b≤c≤d≤e≤f。首先計算I(D)=21。同時得到頻繁項:4，:4，:3，:3。

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

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

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

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

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

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

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

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

2.5ssCloSpan算法的主要步驟

ssCloSpan算法的主要步驟如下：

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

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

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

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

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

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

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

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◇α一遍，找出每個頻繁項β及其支持?jǐn)?shù)

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

9：return；

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

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

12：ifflag2=0then

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

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

15：endfor

16：endif

17：endif

18：endif

19：for每一個βdo

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

21：endfor

22：return；

其中代碼第1行是用來提前終止模式增長的判斷，在此過程中已實現(xiàn)超模式回溯和子模式回溯的剪枝；第8行和第9行根據(jù)支持度的值進(jìn)行當(dāng)前分支非閉合序列的判斷，并提前結(jié)束；第10行和第11行根據(jù)已有閉合序列集中是否存在當(dāng)前分支閉合序列的超序來確定當(dāng)前序列是否為最終閉合性序列。第14行是對子程序SubS的調(diào)用，由支持度值和flag2的值共同決定，其中flag2的值為0，表示在頻繁項頭表中不存在當(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檢測到k值對應(yīng)的序列鏈中有(S◇α)?S′或者S′?(S◇α)then

8：flag1=0;

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

10：endif

11：returnflag1；

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

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

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

輸出：更新的末節(jié)點哈希表LH和更新的頻繁項頭表FH

方法：

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

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

3：if在LH中找到值tthen

4:fort指向的鏈表中的每一個序列Tdo

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

6：刪掉LH中的序列T

7：刪掉FH中的序列T

8：endif

9：endfor；

10：endif；

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

12：return；

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

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

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

輸出：更新的末節(jié)點哈希表LH和更新的頻繁項頭表FH

方法：

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

2：flag2=0；

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

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

5：ifT?(S◇α)then

6：flag2=1;break;

7：returnflag2；

8：endif

9：endfor；

10：endif；

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

12：returnflag2；

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

3　實驗及分析

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

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

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

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

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

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

4　結(jié)　語

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

[5] 公偉,劉培玉,賈嫻. 基于改進(jìn)PrefixSpan的序列模式挖掘算法[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ī)工程,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é)報,2013,30(4):49-54.

[10] 付宇,于艷華,宋美娜,等.時序關(guān)系下的閉合序列模式挖掘算法[J].北京郵電大學(xué)學(xué)報,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é)基金項目(2013CFB039)；湖北省教育廳重點科學(xué)研究項目(D20144403)；湖北省教育廳科學(xué)研究項目(B2013064)；湖北理工學(xué)院優(yōu)秀青年科技創(chuàng)新團(tuán)隊項目(13xtz10)。楊斐，講師，主研領(lǐng)域：可重構(gòu)技術(shù)、嵌入式系統(tǒng)可信計算。張萬楨，講師。陸垂偉，副教授。

TP311.13

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