第6章 序列模式挖掘

第6章序列模式挖掘

序列數(shù)據(jù)是由有序元素或事件的序列組成的，可以不包括具體的時間概念，序列數(shù)據(jù)的例子有客戶購物序列、Web點擊流和生物學(xué)序列等。這類數(shù)據(jù)處理的不是一個時間點上的數(shù)據(jù)，而是大量時間點上的數(shù)據(jù)，因而具有自身的特殊性。6.1序列模式挖掘概述6.1.1序列數(shù)據(jù)庫設(shè)I={i1，i2，…，in}是所有項的集合，在購物籃例子中，每種商品就是一個項。項集是由項組成的一個非空集合。

定義6.1

事件（events）是一個項集，在購物籃例子中，一個事件表示一個客戶在特定商店的一次購物，一次購物可以購買多種商品，所以事件表示為（x1，x2，…，xq），其中xk（1≤k≤q）是I中的一個項，一個事件中所有項均不相同，每個事件可以有一個事件時間標(biāo)識TID，也可以表示事件的順序。

定義6.2

序列（sequence）是事件的有序列表，序列s記作<e1，e2，…，el>，其中ej（1≤j≤l）表示事件，也稱為s的元素。通常一個序列中的事件有時間先后關(guān)系，也就是說，ej（1≤j≤l）出現(xiàn)在ej+1之前。序列中的事件個數(shù)稱為序列的長度，長度為k的序列稱為k-序列。在有些算法中，將含有k個項的序列稱為k-序列。

定義6.3

序列數(shù)據(jù)庫（sequencedatabases）S是元組<SID，s>的集合，其中SID是序列編號，s是一個序列，每個序列由若干事件構(gòu)成。在序列數(shù)據(jù)庫中每個序列的事件在時間或空間上是有序排列的?？蛻籼朣ID交易時間TID商品列表（事件）s16月25日

6月30日3080s26月10日6月15日6月20日10，203040，60，70s36月25日30，50，70s46月25日6月30日7月25日3040，7080s56月12日80客戶號客戶序列s1<{30}，{80}>s2<{10，20}，{30}，{40，60，70}>s3<{30，50，70}>s4<{30}，{40，70}，{80}>s5<{80}>交易數(shù)據(jù)庫D序列數(shù)據(jù)庫S

定義6.4

對于序列t和s，如果t中每個有序元素都是s中一個有序元素的子集，則稱t是s的子序列。形式化表述為，序列t=<t1，t2，…，tm>是序列s=<s1，s2，…，sn>的子序列，如果存在整數(shù)1≤j1<j2<…<jm≤n，使得t1

，t2

，…，tm

。如果t是s的子序列，則稱t包含在s中。例如序列<{2}，{1，3}>是序列<{1，2}，{5}，{1，3，4}>的子序列，因為{2}包含在{1，2}中，{1，3}包含在{1，3，4}中。而<{2，5}，{3}>不是序列<{1，2}，{5}，{1，3，4}>的子序列，因為前者中項2和項5是一次購買的，而后者中項2和項5是先后購買的，這就是區(qū)別所在。

定義6.5

如果一個序列s不包含在序列數(shù)據(jù)庫S中的任何其他序列中，則稱序列s為最大序列。

定義6.6

一個序列α的支持度計數(shù)是指在整個序列數(shù)據(jù)庫S中包含α的序列個數(shù)。即：

supportS(α)=|{(SID，s)|(SID，s)∈S∧α是s的子序列}|其中，|·|表示集合中·出現(xiàn)的次數(shù)。若序列α的支持度計數(shù)不小于最小支持度閾值min_sup，則稱之為頻繁序列，頻繁序列也稱為序列模式。長度為k的頻繁序列稱為頻繁k-序列。6.1.2序列模式挖掘算法1.什么是序列模式挖掘序列模式挖掘的問題定義為：給定一個客戶交易數(shù)據(jù)庫D以及最小支持度閾值min_sup，從中找出所有支持度計數(shù)不小于min_sup的序列，這些頻繁序列也稱為序列模式。有的算法還可以找出最大序列，即這些最大序列構(gòu)成序列模式。2.經(jīng)典的序列模式挖掘算法（1）候選碼生成—測試框架的序列挖掘算法候選碼生成—測試框架基于Apriori理論，即序列模式的任一子序列也是序列模式，這類算法統(tǒng)稱為Aprior類算法。主要包括AprioriAll、AprioriSome、DynamicSome、GSP和SPADE算法等。這類算法通過多次掃描數(shù)據(jù)庫，根據(jù)較短的序列模式生成較長的候選序列模式，然后計算候選序列模式的支持度，從而獲得所有序列模式。根據(jù)數(shù)據(jù)集的不同分布方式，Aprior類算法又可以分為水平格式算法和垂直格式算法。水平分布的數(shù)據(jù)集是由一系列序列標(biāo)識符和序列組成，對應(yīng)的算法有AprioriAll、AprioriSome、DynamicSome和GSP，其中AprioriSome和DynamicSome只求最大序列模式。垂直分布的數(shù)據(jù)集是由一系列序列標(biāo)識符（SID）、項集和事件標(biāo)識符（TID）組成，對應(yīng)的算法有SPADE等。（2）模式增長框架的序列挖掘算法模式增長框架挖掘算法的最大特點：在挖掘過程中不產(chǎn)生候選序列，通過分而治之的思想，迭代的將原始數(shù)據(jù)庫進行劃分，同時在劃分的過程中動態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元，進行下一次的挖掘過程，從而獲得長度不斷增長的序列模式。主要有FreeSpan和PrefixSpan算法。3.經(jīng)典算法比較分析算法是否產(chǎn)生候選序列存儲結(jié)構(gòu)數(shù)據(jù)庫是否縮減原數(shù)據(jù)庫掃描次數(shù)算法執(zhí)行AprioriAll是Hash樹否最長模式長度循環(huán)GSP是Hash樹否最長模式長度循環(huán)SPADE是序列格是3遞歸PrefixSpan否前綴樹是2遞歸6.2Apriori類算法6.2.1AprioriAll算法對于含有n個事件的序列數(shù)據(jù)庫S，其中k-序列總數(shù)為，因此，具有9個事件的序列包含+

+…+

=29-1=511個不同的序列。序列模式挖掘可以采用蠻立法枚舉所有可能的序列，并統(tǒng)計它們的支持度計數(shù)。但計算量非常大。

AprioriAll本質(zhì)上是Apriori思想的擴張，只是在產(chǎn)生候選序列和頻繁序列方面考慮序列元素有序的特點，將項集的處理改為序列的處理。基于水平格式的Apriori類算法將序列模式挖掘過程分為5個具體階段，即排序階段、找頻繁項集階段、轉(zhuǎn)換階段、產(chǎn)生頻繁序列階段以及最大化階段。1.排序階段對原始數(shù)據(jù)表（如表6.1）按客戶號（作為主關(guān)鍵字）和交易時間（作為次關(guān)鍵字）進行排序，排序后通過對同一客戶的事件進行合并得到對應(yīng)的序列數(shù)據(jù)庫（如表6.2）?？蛻籼柨蛻粜蛄衧1<{30}，{80}>s2<{10，20}，{30}，{40，60，70}>s3<{30，50，70}>s4<{30}，{40，70}，{80}>s5<{80}>2.找頻繁項集階段這個階段根據(jù)min_sup找出所有的頻繁項集，也同步得到所有頻繁1-序列組成的集合L1，因為這個集合正好是{<l>|l∈所有頻繁項集集合}。這個過程是從所有項集合I開始進行的。

【例6.1】對表6.2的序列數(shù)據(jù)庫，假設(shè)min_sup=2。找頻繁項集的過程如下：最后求得的頻繁1-序列L1={{30}，{40}，{70}，{40，70}，{80}}。然后將頻繁1-項集映射成連續(xù)的整數(shù)。例如，將上面得到的L1映射成表6.4對應(yīng)的整數(shù)。由于比較頻繁項集花費一定時間，這樣做后可以減少檢查一個序列是否被包含于一個客戶序列中的時間，從而使處理過程方便且高效。頻繁項集映射成整數(shù){30}1{40}2{70}3{40，70}4{80}53.轉(zhuǎn)換階段在尋找序列模式的過程中，要不斷地進行檢測一個給定的大序列集合是否包含于一個客戶序列中。為此做這樣的轉(zhuǎn)換：每個事件被包含于該事件中所有頻繁項集替換。如果一個事件不包含任何頻繁項集，則將其刪除。如果一個客戶序列不包含任何頻繁項集，則將該序列刪除。這樣轉(zhuǎn)換后，一個客戶序列由一個頻繁項集組成的集合所取代。每個頻繁項集的集合表示為{e1，e2，…，ek}，其中ei（1≤i≤k）表示一個頻繁項集?！纠?.2】給出表6.2序列數(shù)據(jù)庫經(jīng)過轉(zhuǎn)換后的結(jié)果?？蛻籼栐蛻粜蛄性蛻粜蛄杏成浜髎1<{30}，{80}><{30}，{80}><{1}，{5}>s2<{10，20}，{30}，{40，60，70}><{30}，{{40}，{70}，{40，70}}><{1}，{2，3，4}>:s3<{30，50，70}><{{30}，{70}}><{1，3}>s4<{30}，{40，70}，{80}><{30}，{{40}，{70}，{40，70}}，{80}><{1}，{2，3，4}，{5}>s5<{80}><{80}><{5}>4.產(chǎn)生頻繁序列階段利用轉(zhuǎn)換后的序列數(shù)據(jù)庫尋找頻繁序列，AprioriAll算法如下：輸入：轉(zhuǎn)換后的序列數(shù)據(jù)庫S，所有項集合I，最小支持度閾值min_sup輸出：序列模式集合L方法：其過程描述如下：L1={i|i∈Iand{i}.sup_count≥min_sup};

//找出所有頻繁1-序列for(k=2;Lk-1≠Φ;k++){利用頻繁序列Lk生成候選k-序列Ck;for(對于序列數(shù)據(jù)庫S中每個序列s){ if(Ck的每個候選序列c包含在s中)

c.sup_count++; //c的支持度計數(shù)增1}

Lk={c|c∈Ckandc.sup_count≥min_sup}; //由Ck中計數(shù)大于min_sup的候選序列組成頻繁k-序列集合Lk}L=∪kLk;上述算法中利用頻繁序列Lk-1生成候選k-序列Ck的過程說明如下：（1）連接對于Lk-1中任意兩個序列s1和s2，如果s1與s2的前k-2項相同，即s1=<e1，e2，…，ek-2，f1>，s2=<e1，e2，…，ek-2，f2>，則合并序列s1和s2，得到候選k-序列<e1，e2，…，ek-2，f1，f2>和<e1，e2，…，ek-2，f2，f1>。即：insertintoCkselectp.itemset1,p.itemset2,…,p.itemsetk-1,q.itemsetk-1fromLk-1p,Lk-1qwherep.itemset1=q.itemset1andp.itemset2=q.itemset2and…

andp.itemsetk-2=q.itemsetk-2（2）剪枝剪枝的原則：一個候選k-序列，如果它的(k-1)-序列有一個是非頻繁的，則刪除它。由Ck剪枝產(chǎn)生Lk的過程如下：for(所有c∈Ck的序列)

for(所有c的(k-1)-序列s) if(s不屬于Lk-1)

從Ck中刪除c;Ck

Lk; //由Ck剪枝后得到Lk

【例6.3】以表6.6所示的序列數(shù)據(jù)庫S1為例，給出ApriorAll算法的執(zhí)行過程，這里I={1，2，3，4，5}，每個數(shù)字表示一個項。假設(shè)min_sup=2?？蛻籼柨蛻粜蛄衧1<{1，5}，{2}，{3}，{4}>s2<{1}，{3}，{4}，{3，5}>s3<{1}，{2}，{3}，{4}>s4<{1}，{3}，{5}>s5<{4}，{5}>一個序列數(shù)據(jù)庫S1

①先求出L1，由其產(chǎn)生L2的過程如圖6.2所示，實際上這個過程不需要剪枝，因為C2中每個2-序列的所有子序列一定屬于L1。產(chǎn)生L2的過程②由L2連接并剪枝產(chǎn)生C3，掃描序列數(shù)據(jù)庫S1，刪除小于min_sup的序列得到L3，其過程如圖6.3所示。產(chǎn)生L3的過程③由L3連接并剪枝產(chǎn)生C4，掃描序列數(shù)據(jù)庫S1，刪除小于min_sup的序列得到L4，其過程如圖6.4所示。產(chǎn)生L4的過程④L4中只有一個序列，由它產(chǎn)生的C5為空，L5也為空。算法結(jié)束。5.最大化階段在頻繁序列模式集合中持出最大頻繁序列模式集合。由于在產(chǎn)生頻繁模式階段發(fā)現(xiàn)了所有頻繁模式集合L，下面的過程可用來發(fā)現(xiàn)最大序列。設(shè)最長序列的長度為n，則：for(k=n;k>1;k--)

for(每個k-序列sk)

從L中刪除sk的所有子序列;

【例6.4】對于表6.5所示的序列數(shù)據(jù)庫S1，從前面的過程看到，產(chǎn)生的所有頻繁序列集合：

L={<1>，<2>，<3>，<4>，<5>，<1，2>，<1，3>，<1，4>，<1，5>，<2，3>，<2，4>，<3，4>，<3，5>，<4，5>，<1，2，3>，<1，2，4>，<1，3，4>，<1，3，5>，<2，3，4>，<1，2，3，4>}刪除子序列得到最大序列的過程如下：由于最長的序列是4，因此所有4-序列都是最大序列，這里只有<1，2，3，4>是最大序列。對于4-序列<1，2，3，4>，從L中刪除它的3-子序列<1，2，3>、<1，2，4>、<1，3，4>、<2，3，4>，2-子序列<1，2>、<1，3>、<1，4>、<2，3>、<2，4>、<3，4>和1-子序列<1>、<2>、<3>、<4>，剩下的3-序列<1，3，5>是最大序列。對于3-序列<1，3，5>，從L中刪除它的2-子序列<1，5>、<3，5>和1-子序列<5>，剩下的2-序列<4，5>是最大序列。到此，L中已沒有可以再刪除的子序列了，得到的序列模式如下表所示。序列模式計數(shù)<1，2，3，4>2<1，3，5>2<4，5>2當(dāng)求出所有序列模式集合L后，可以采用類似Apriori算法生成所有的強關(guān)聯(lián)規(guī)則。生成所有的強關(guān)聯(lián)規(guī)則RuleGen(L，min_conf)算法如下：輸入：所有序列模式集合L，最小置信度閾值min_conf輸出：強關(guān)聯(lián)規(guī)則集合R方法：其過程描述如下：R=Φ;for(對于L中每個頻繁序列β)

for(對于β的每個子序列α)

{ conf=β.sup_count/α.sup_count; if(conf≥min_conf)

R=R∪{α→β}; //產(chǎn)生一條新規(guī)則α→β

}returnR;例如，假設(shè)有一個頻繁3-序列<{D}，{B，F(xiàn)}，{A}>，其支持度計數(shù)為2，它的一個子序列<{D}，{B，F(xiàn)}>的支持度計數(shù)也為2。若置信度閾值min_conf=75%，則：

<{D}，{B，F(xiàn)}>→<{D}，{B，F(xiàn)}，{A}>是一條強關(guān)聯(lián)規(guī)則，因為它的置信度=2/2=100%。6.2.2AprioriSome算法

AprioriSome算法可以看作是AprioriAll算法的改進，它們的主要查找序列的思路是基本一致的，僅在策略上有所差異，AprioriSome算法主要在于將具體過程分為以下兩個階段：前推階段（或前半部分）：此階段只對指定長度的序列進行計數(shù)?；厮蓦A段（或后半部分）：此階段跳過已經(jīng)計數(shù)過的序列。AprioriSome算法描述如下：輸入：找頻繁項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫S，最小支持度閾值min_sup輸出：序列模式集合L方法：其過程描述如下：//前推階段（前半階段）L1={頻繁1-序列};C1=L1;last=1; //計數(shù)的序列長度for(k=2;Ck-1andLlast

;k++){if(Lk-1已知) //Lk-1已知求出

Ck=產(chǎn)生于Lk-1新的候選序列;

else //Lk-1尚未求出

Ck=產(chǎn)生于Ck-1新的候選序列;if(k==next(last)) { for(對于序列數(shù)據(jù)庫S中的每一個客戶序列c)

所有在Ck中包含在c中的候選者的計數(shù)增1;

Lk=在Ck中滿足最小支持度的候選者; last=k;}}//回溯階段（后半階段）for(k--;k>=1;k--)if(Lk在前推階段沒有確定){ 刪除所有在Ck中包含在某些Li（i>k）中的序列; for(對于在S中的每一個客戶序列c)

對在Ck中包含在c中的所有的候選者的計數(shù)增1;

Lk=在Ck中滿足最小支持度的候選者;}else{ //Lk已知刪除所有在Lk中包含在某些Li（i>k）中的序列;}L=∪kLk; //求Lk的并集產(chǎn)生所有序列模式在前推階段中，只對特定長度的序列進行計數(shù)。比如，前推階段對長度為1、2、4和6的序列計數(shù)（計算支持度），而長度為3和5的序列則在回溯階段中計數(shù)。

next函數(shù)以上次遍歷的序列長度作為輸入，返回下次遍歷中需要計數(shù)的序列長度。該函數(shù)確定了哪一個序列將被計數(shù)，在對非最大序列計數(shù)時間的浪費和計算擴展小候選序列之間作出權(quán)衡。當(dāng)next(k)=k+1（k是最后計數(shù)候選者的長度）時，這時所有的子序列都被計算，而候選序列集合最小，此時退化為AprioriAll算法。當(dāng)next(k)遠大于k，如next(k)=100×k時，這時幾乎所有的子序列都不被計算，但候選序列數(shù)卻大大增加。下面給出按經(jīng)驗所使用的next函數(shù)。int

next(int

k){

if(hitk<0.666)returnk+1;

elseif(hitk<0.75)returnk+2;elseif(hitk<0.80)returnk+3;elseif(hitk<0.85)returnk+4;elsereturnk+5;}在掃描開始階段，hitk較大，也就是說候選序列較少，將k設(shè)置為較大的值，可以減少對子序列的計數(shù)。在以后掃描過程中，hitk越來越小，將k設(shè)置為較小的值，可以減少候選序列數(shù)。

【例6.5】以表6.6的序列數(shù)據(jù)庫S1為例，給出AprioriSome算法的執(zhí)行過程，設(shè)定min_sup=2。假設(shè)前推階段只計算長度k為1、2、4、6、…的序列（即next(1)=2，next(2)=4，next(3)=6，…）。在前推階段中，先置last=1，過程如下：①對序列數(shù)據(jù)庫進行一次掃描得到L1?？蛻籼柨蛻粜蛄衧1<{1，5}，{2}，{3}，{4}>s2<{1}，{3}，{4}，{3，5}>s3<{1}，{2}，{3}，{4}>s4<{1}，{3}，{5}>s5<{4}，{5}>②當(dāng)k=2循環(huán)時，由L1計算C2，由于k==next(1)成立，則掃描序列數(shù)據(jù)庫計算支持度得到L2，其過程與圖6.2類似，并置last=2。產(chǎn)生L2的過程③當(dāng)k=3循環(huán)時，由C2產(chǎn)生C3，其過程如圖6.5所示，由于k==next(2)不成立，所以不會計算C3的支持度計數(shù)，因此不產(chǎn)生L3。產(chǎn)生的C3

④當(dāng)k=4循環(huán)時，由C3產(chǎn)生C4，此時k=next(2)成立，所以掃描序列數(shù)據(jù)庫計算支持度得到L4，其過程如圖6.6所示。產(chǎn)生的L4

⑤當(dāng)k=5循環(huán)時，求出C5為空。由于C5為空，前推階段結(jié)束。然后算法進入回溯階段，首先k=5，執(zhí)行k--得到k=4：①當(dāng)k=4循環(huán)時，L4已求出，因為沒有更長的序列，沒有內(nèi)容從L4中刪除。②當(dāng)k=3循環(huán)時，L3未求出，先刪除C3中包含在L4的子序列，即刪除<1，2，3>、<1，2，4>、<1，3，4>、<2，3，4>，再掃描序列數(shù)據(jù)庫計算支持度得到L3，其過程如圖6.7所示。求得的<1，3，5>是最大序列（因為它不是4-序列的子序列）。產(chǎn)生的L3

③當(dāng)k=2循環(huán)時，L2已求出，刪除L2中包含在L3和L4中的子序列，只剩下<4，5>。④當(dāng)k=1循環(huán)時，L1中的所作序列都已被刪除。最后得到的序列模式如表6.6相同。序列模式計數(shù)<1，2，3，4>2<1，3，5>2<4，5>2AprioriSome和AprioriAll比較有以下幾個不同：AprioriAll用Lk-1去算出所有的候選Ck，而AprioriSome會直接用Ck-1去計算出所有的候選Ck，因為Ck-1包含Lk-1，所以AprioriSome會產(chǎn)生比較多的候選。雖然AprioriSome跳躍式計算候選，但因為它所產(chǎn)生的候選比較多，可能在回溯階段前就占滿內(nèi)存。如果內(nèi)存滿了，AprioriSome就會被強迫去計算最后一組的候選（即使原本是要跳過此項）。這樣，會影響并減少已計算好的兩個候選間的跳躍距離，而使得AprioriSome會變的跟AprioriAll一樣。對于較低的支持度，有比較長的頻繁序列，也因此有比較多的非最大序列，此時AprioriSome較好。6.2.3DynamicSome算法

DynamicSome算法類似于AprioriSome算法，由函數(shù)確定要計數(shù)的序列長度，分為四個階段（部分）。但與AprioriAll、AprioriSome

不同，DynamicSome算法的剪枝在后半階段，并不像AprioriAll、AprioriSome

那樣計數(shù)后就進行剪枝，因此在支持度較小時，會產(chǎn)生大量的候選序列。DynamicSome算法主要特點如下：由變量step來決定要計數(shù)的候選序列。在初始化階段，所有達到并且包括step長度的候選序列都要進行計數(shù)。前半階段跳過對一定長度的候選序列的計數(shù)，對所有長度為step倍數(shù)的序列進行計數(shù)。中間階段產(chǎn)生候選序列。后半階段的算法與AprioriSome算法的后半階段完全相同。需要對半階段未計數(shù)的序列進行計數(shù)。DynamicSome算法描述如下：輸入：找頻繁項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫S，最小支持度閾值min_sup輸出：序列模式集合L方法：其過程描述如下：step≥1并且為整數(shù);//初始化階段L1=頻繁1-序列;for(k=2;k<=stepandLk-1≠Φ;k++){Ck=產(chǎn)生于Lk-1的新候選者;for(每個在序列數(shù)據(jù)庫S中的客戶序列c)

對在Ck中的包含在c中所有候選者的計數(shù)增1;

Lk=Ck中大于或等于min_sup的候選者;}//前半階段for(k=step;Lk≠Φ;k+=step) //從Lk及Lstep中發(fā)現(xiàn)Lk+step{Ck+step=Φ;for(每個在序列數(shù)據(jù)庫S中的客戶序列c){ X=otf_generate(Lk,Lstep,c); for(在X中的每個序列x) if(x包含在Ck+step中)

在Ck+step中x的計數(shù)增1; else

將x加入到Ck+step中;}

Lk+step=在Ck+step中計數(shù)大于或等于min_sup的候選者;}//中間階段for(k--;k>1;k--){if(Lk仍未確定){ if(Lk-1已知)

Ck=產(chǎn)生于Lk-1的新候選者; else

Ck=產(chǎn)生于Ck-1的新候選者;}}//后半階段與AprioriSome算法的后半階段相同;L=∪kLk; //求Lk的并集產(chǎn)生所有序列模式對于DynamicSome算法，若step設(shè)為3，在初始化階段對長度為1、2、3的序列計數(shù)。然后在前半部分對長度為6、9、12、…的序列計數(shù)。若只想對長度為6、9、12、…的序列計數(shù)時，通過兩個長度為3的序列進行連接運算可得到長度為6的序列，同理，通過一個長度為6的序列與一個長度為3的序列進行連接運算可得到長度為9的序列，以此類推。但是，要想得到長度為3的序列，就需要長度為1及長度為2的序列，因此，就需要有初始化階段。

otf_generate(Lk,Lstep,c)算法的參數(shù)分別為頻繁k-序列、頻繁step-序列和客戶序列，結(jié)果返回包含在c中的候選(k+step)-序列的集合。例如，step=3、k=6時，執(zhí)行X=otf_generate(Lk,Lstep,c)將L6和L3連接產(chǎn)生9-序列集合，并將其中所有包含在c中候選9-序列存放到X中。

otf_generate(Lk,Lstep,c)的連接方式是：如果sk∈Lk，sj∈Lj都包含在c中且相互不重疊，則<sk，sj>是一個候選(k+j)-序列。對于c中的每個事件x，若x∈Lk中序列sk=<…，xl>，取x.end=min{xl}；對于c中的每個事件y，若y∈Lj中序列sj=<yl，…>，取y.start=max{yl}。然后在滿足連接條件x.end<y.start的情況下，將sk和sj兩個序列合并得到一個候選(k+j)-序列，所有這樣序列集合即為返回的候選X。例如，以圖6.2中的L2為例，設(shè)c=<1，2，4>，執(zhí)行X=otf_generate(L2,L2,c)，c1對應(yīng)事件1，c2對應(yīng)事件2，c3對應(yīng)事件4。求出的長度為2的序列集X2如表6.8所示，只有序列<1，2>和<3，4>滿足連接條件，其結(jié)果為單個序列<1，2，3，4>，即返回的候選4-序列集合X={<1，2，3，4>}。序列集X2x.endy.start<1，2>21<1，3>31<1，4>41<2，3>32<2，4>42<3，4>43開始與結(jié)束值

【例6.6】以表6.6的序列數(shù)據(jù)庫S1為例說明DynamicSome算法的執(zhí)行過程，設(shè)定min_sup=2，step=2。其過程如下：客戶號客戶序列s1<{1，5}，{2}，{3}，{4}>s2<{1}，{3}，{4}，{3，5}>s3<{1}，{2}，{3}，{4}>s4<{1}，{3}，{5}>s5<{4}，{5}>產(chǎn)生L2的過程①初始化階段：求出L2的過程與圖6.2相同。

②前半階段：k=step（2）時，由Lk與Lstep連接，通過掃描序列數(shù)據(jù)庫S1，求得C4如表6.9所示，得到L4={<1，2，3，4>}。執(zhí)行k+=step，得到k=4，將C4與C2連接得到C6為空。前半階段結(jié)束。序列計數(shù)<1，2，3，4>2<1，3，4，5>1候選4-序列集合C4

③中間階段：k=4，執(zhí)行k--，得到k=3，L3未確定，L2已求出，則由L2產(chǎn)生C3。產(chǎn)生的C3

執(zhí)行k--，得到k=2，L2已確定，不做任何事情。執(zhí)行k--，得到k=1，L1已確定，不做任何事情。中間階段結(jié)束。

④后半階段：k取前半階段結(jié)束時的k值即4，執(zhí)行k--，得到k=3，由于L3在前半部分沒有計數(shù)，則對C3計數(shù)得到L3。

執(zhí)行k--，得到k=2，L2已確定，從中刪除包含在L3、L4中的序列。執(zhí)行k--，得到k=1，L1已確定，從中刪除包含在L2、L3、L4中的子序列。最后得到的序列模式如表6.6相同。序列模式計數(shù)<1，2，3，4>2<1，3，5>2<4，5>26.2.4GSP算法1.GSP算法描述GSP算法主要包括三個步驟：掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集合。根據(jù)長度為i的種子集合Li通過連接操作和剪枝操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計算每個候選序列模式的支持度計數(shù)，產(chǎn)生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集合。重復(fù)第②步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。整個過程為：L1→C2→L2→C3→L3→C4→L4→…

注意：在GSP算法中，k-序列是指序列中包含k個項，這種前面的定義有所不同。每個候選序列比產(chǎn)生它的種子序列多包含一個項（序列中每個事件可能包含一個或多個項），這樣給定一次掃描中得到的所有候選序列將有相同的長度。其中，產(chǎn)生候選序列模式主要分兩步：

①連接階段：設(shè)有種子集合Lk-1，候選序列集合Ck通過將種子集合Lk-1與Lk-1連接得到。設(shè)s1、s2分別為種子集合Lk-1中的兩個(k-1)-序列：

如果去掉s1的第一個項與去掉s2的最后一個項所得到的子序列相同，則可以將s1與s2進行連接，產(chǎn)生候選k-序列的規(guī)則是將序列s1與序列s2的末項相連，若s2的末項為x，而{x}恰好為s2的最后一個元素（事件項集），則將{x}變成s1的最后一個元素；否則，x變成s1最后一個元素的最后一項。特殊地，若k=2，即種子集合為L1，設(shè)s1=<{x}>，s2=<{y}>，則項y既再成為s1的最后一個項，又可成為s1的最后一個元素的最后一項，即產(chǎn)生候選2-序列<{x}，{y}＞、<{x，y}>。

②剪枝階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。頻繁3-序列候選4-序列連接后剪枝后<{1，2}，{3}><{1，2}，{4}><{1}，{3，4}><{1，3}，{5}><{2}，{3，4}><{2}，{3}，{5}><{1，2}，{3，4}><{1，2}，{3}，{5}><{1，2}，{3，4}>例如：GSP算法如下：輸入：找頻繁項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫S，最小支持度閾值min_sup輸出：序列模式集合L方法：其過程描述如下：L1={頻繁1-序列}; //頻繁項集階段得到L1for(k=2;Lk-1≠Φ;k++) //循環(huán)迭代，直到不能找到頻繁k-序列模式{Ck=GSP_generate(Lk-1);//由Lk-1中的頻繁(k-1)-序列生成候選k-序列;for(對序列數(shù)據(jù)庫S中的每個客戶序列c)//掃描序列數(shù)據(jù)庫S

被包含于c中的Ck內(nèi)的所有候選者的計數(shù)增1;

Lk={c∈Ck|c.sup_count≥min_sup}; //生成頻繁k-序列集合Lk}L=∪kLk; //求Lk的并集產(chǎn)生所有序列模式2.利用哈希樹計算候選序列的支持度計數(shù)對于一組候選序列模式，構(gòu)造哈希樹的過程是：

從根結(jié)點開始，用哈希函數(shù)對序列的第一個項做映射來決定從哪個分支向下，依次在第k層對序列的第k個項作映射來決定從哪個分支向下，直到到達一個葉子結(jié)點。

將序列儲存在此葉子結(jié)點。初始時所有結(jié)點都是葉子結(jié)點，當(dāng)一個葉子結(jié)點所存放的序列個數(shù)達到一個閾值，它將轉(zhuǎn)化為一個內(nèi)部結(jié)點。假如，有如圖6.8所示的哈希樹，哈希函數(shù)為“模5”，哈希表的尺寸為5。一個葉子結(jié)點轉(zhuǎn)換為內(nèi)部結(jié)點的閾值為3個項集。對于一個事件{1，4}，第一層的桶1、4需要考慮，故僅有候選項集{1，2}、{1，4}被考察。一棵哈希樹給定序列數(shù)據(jù)庫中的一個序列s，計算候選序列的支持度計數(shù)的過程如下：對于根結(jié)點，用哈希函數(shù)對序列s的每一個單項做映射來并從相應(yīng)的表項向下迭代的進行操作。對于內(nèi)部結(jié)點，如果s是通過對單個項x做哈希映射來到此結(jié)點的，則對s中每一個和x在一個元素中的單個項以及在x所在元素之后第一個元素的第一個單項做哈希映射，然后從相應(yīng)的表項向下迭代做操作。對一個葉子結(jié)點，檢查每個候選序列c是不是s的子序列。如果是，則相應(yīng)的候選序列的支持度計數(shù)增1。3.有時間約束的序列模式挖掘基于時間約束的序列模式挖掘為用戶提供了挖掘定制模式的方法。用戶可以通過設(shè)置一些時間參數(shù)對挖掘的范圍進行限制。常用的時間參數(shù)如下：序列長度與寬度的約束：序列的長度是指序列中事件的個數(shù)，寬度是指最長事件的長度。最小間隔的約束：指事件之間的最小時間間隔mingap。最大間隔的約束：指事件之間的最大時間間隔maxgap。時間窗口約束：指整個序列都必須發(fā)生在某個時間窗口ws內(nèi)。在考察某個數(shù)據(jù)序列S是否包含某個候選k-序列s時，需分成兩個階段：（1）向前階段在S中尋找從s的首項開始的連續(xù)子序列xi…xj（i<j）直至time(xj)-time(xi)>maxgap（這里time(x)表示事件x的交易時間），此時轉(zhuǎn)入向后階段，否則，如在S中不能找到s的某個元素，則s不是S的子序列。（2）向后階段由于此時time(xj)-time(xi)>maxgap，故此時應(yīng)從時間值為time(xj)-maxgap后重新搜索xj-1，但同時應(yīng)保持xj-2位置不變。當(dāng)新找到的xj-1仍不滿足time(xj)-time(xi)≤maxgap時，從時間值為time(xj-1)-maxgap后重新搜索xj-2，同時保持xj-3位置不變，直至某位置元素xj-i滿足條件或x1不能保持位置不變，此時，返回向前階段。①當(dāng)xj-i滿足time(xj-i)-time(xj-(i+1))≤maxgap時（此時x1保持位置不變），向前階段應(yīng)從xj-i位置后重新搜索xj-i+1及后續(xù)元素。②當(dāng)x1不能保持位置不變時，向前階段應(yīng)從原x1位置后重新搜索x1及后續(xù)元素。

【例6.7】表6.11給出了某個事務(wù)數(shù)據(jù)庫的一個數(shù)據(jù)序列S?，F(xiàn)假設(shè)最大事務(wù)時間間隔maxgap=30，最小事務(wù)時間間隔mingap=5，滑動時間窗口ws=0，考察候選數(shù)據(jù)序列s=<{1，2}，{3}，{4}>是否包含在該數(shù)據(jù)序列中。事件時間事件項集10{1，2}25{4，6}45{3}50{1，2}65{3}90{2，4}95{6}事務(wù)項的事務(wù)時間鏈表事務(wù)項事務(wù)時間1→10→50→NULL2→10→50→90→NULL3→45→65→NULL4→25→90→NULL5→NULL6→25→95→NULL7→NULL結(jié)論：數(shù)據(jù)序列S包含候選序列s=<{1，2}，{3}，{4}>。GSP算法的特點如下：如果序列數(shù)據(jù)庫的規(guī)模比較大，則有可能會產(chǎn)生大量的候選序列模式。需要對序列數(shù)據(jù)庫進行循環(huán)掃描。對于序列模式的長度比較長的情況，由于其對應(yīng)的短的序列模式規(guī)模太大，算法很難處理。6.2.5SPADE算法1.SPADE算法的相關(guān)概念

SPADE是一種基于數(shù)據(jù)垂直數(shù)據(jù)格式的Aprior類算法，垂直數(shù)據(jù)分布的數(shù)據(jù)集由一系列序列標(biāo)識符、事件標(biāo)識符和項集組成。例如，表6.13所示是一個客戶交易的垂直數(shù)據(jù)庫D，它是由相應(yīng)客戶交易數(shù)據(jù)庫轉(zhuǎn)換而來的。客戶號SID交易時間TID項集（事件）s110{C，D}s115{A，B，C}s120{A，B，F(xiàn)}s125{A，C，D，F(xiàn)}s215{A，B，F(xiàn)}s220{E}s310{A，B，F(xiàn)}s410{D，G，H}s420{B，F(xiàn)}s425{A，G，H}所有的頻繁序列都可以通過搜索序列格的方式被挖掘出來，其基本運算是兩個序列的組合。兩個k-序列組合的結(jié)果為(k+1)-序列的集合，它們在序列格中恰好處于這兩個k-序列的上一層，該運算用“∨”表示。如圖6.9中，A、B是兩個1-序列，它們的組合A∨B={<A，B>，<AB>，<B，A>}，見圖中帶陰影的圓圈。

【例6.8】假設(shè)最小支持度閾值min_sup=2，對于表6.13所示的垂直數(shù)據(jù)庫，構(gòu)建的長度為1的序列的id-list表如表6.14所示。

1-序列<A>的id-list表L(A)中有6行，但只有4個不同的序列號SID，所以該序列的支持度計數(shù)為4。由于1-序列<C>的支持度計數(shù)小于min_sup，表中沒有列出，因此，頻繁1-序列集合F1={<A>，<B>，<D>，<F>}。L(A)L(B)L(D)L(F)SIDTIDSIDTIDSIDTIDSIDTIDs115s115s110s120s120s120s125s125s125s215s410s215s215s310s310s310s420s420s425客戶號SID交易時間TID項集（事件）s110{C，D}s115{A，B，C}s120{A，B，F(xiàn)}s125{A，C，D，F(xiàn)}s215{A，B，F(xiàn)}s220{E}s310{A，B，F(xiàn)}s410{D，G，H}s420{B，F(xiàn)}s425{A，G，H}長度為1的序列的id-list表

定義6.7

前綴形式化定義如下：定義一個函數(shù)p：(S，N)→S，其中S是一個序列集合，N是一個非負整數(shù)，p(X，k)=X[1:k]，換句話說，p(X，k)返回X的k長度的前綴。在序列格S上定義一個等價關(guān)系如下：X，Y∈S，當(dāng)且僅當(dāng)p(X，k)=p(Y，k)，也就是說這兩個序列共享長度為k的前綴，則它們是θk等價的，記為。由X構(gòu)成的等價類記為。在該序列格上由θ1導(dǎo)出的等價類集合是{[A]，[B]，[D]，[F]}，稱這些第一層的類為父類，在圖中下方?？梢钥吹?，所有具有共同前綴的序列被劃分到同一等價類中，每個等價類都是序列格的一個子格。只有同一個類中的兩個k-序列才能進行時態(tài)連接運算，并產(chǎn)生長度為(k+1)的候選序列。因此，為了產(chǎn)生所有(k+1)-序列，僅需要在每個前綴等價類中執(zhí)行一個簡單的時態(tài)連接即可，而這種連接可被獨立處理。根據(jù)被連接的原子類型，可得3種可能的頻繁序列：兩個事件原子項連接：<AB>和<AC>進行連接得到<ABC>。事件原子項與序列原子項之間連接：<AB>和<A，B>進行連接得到<AB，C>。序列原子項與序列原子項之間連接：<A，B>與<A，C>進行連接得到<A，BC>、<A，B，C>或<A，C，B>。一個特殊的情況是，當(dāng)對<A，B>進行自連接時，則只能產(chǎn)生唯一的新序列<A，B，B>。

【例6.9】如圖6.11所示，給定<P，A>和<P，F(xiàn)>兩個id-list表，為了求事件原子<P，AF>的id-list表，需要檢查<P，A>和<P，F(xiàn)>的所有相等（SID，TID）對，求得結(jié)果為{（8，30），（8，50），（8，80）}。對于序列格S中的任何k-序列X，設(shè)X1和X2表示它的以字典順序排列的開頭兩個(k-1)-子序列，則X=X1∨X2，且它的支持度計數(shù)X.sup_count=|L(X1)∩L(X2)|，其中|X|表示序列X對應(yīng)的id-list表中不同SID的數(shù)據(jù)序列的個數(shù)。

【例6.10】求序列<D，BF，A>的id-list表的過程。通過等價關(guān)系θk將可以將每個父類遞歸分解為更小的子類，如圖6.13所示是將分解為更小的子類的過程，這產(chǎn)生了一個等價類的格。SPADE算法可以采用DFS或BFS方式來搜尋每一個子類。

SPADE算法通過頻繁2-序列將每個子類逐個構(gòu)建出來，即將形式為<XY>或者<X，Y>的序列添加到前綴類[X]中。在處理每個子類時，采用Apriori剪枝原理進行剪枝，一旦某個子類被剪枝，就不再繼續(xù)它的處理。2.完整的SPADE算法SPADE算法的基本過程如下：把客戶交易數(shù)據(jù)庫轉(zhuǎn)化為垂直表示格式id-list表。第一次掃描產(chǎn)生1-序列模式F1。第2次掃描生成2-序列模式F2，同時構(gòu)建格，使有相同前綴項的序列在同一格內(nèi)。第3次掃描，動態(tài)連接產(chǎn)生所有的序列模式，即通過BFS或DFS在每個類中進行搜索，枚舉所有頻繁序列。在挖掘過程中，隨著序列模式長度的增長，表越來越小，表連接的次數(shù)和候選序列的產(chǎn)生大大減小，比水平格式算法效率大大提高。在生成F2時，可以由F1得到，但id-list表的連接非常耗時，可以將垂直格式轉(zhuǎn)化為水平格式，這樣來高效地計算F2。之后只對id-list表進行操作，無需掃描原數(shù)據(jù)庫。因此該算法產(chǎn)生序列模式時只需要3次掃描數(shù)據(jù)庫。實驗結(jié)果表明，SPADE算法的性能比GSP算法要高出2倍。如果不考察產(chǎn)生2-序列的代價，極端情況下SPADE的性能將高出GSP一個數(shù)量級，理由是SPADE利用一個更加高效的基于id-list表結(jié)構(gòu)的算法實現(xiàn)支持度計算。而且SPADE算法利用格理論將原始搜索空間進行分解，除了為產(chǎn)生頻繁1-序列和2-序列而掃描原始搜索空間外，其余的操作在每個序列的id-list表上獨立執(zhí)行，這樣，在挖掘過程中，搜索空間逐漸變小。因此，SPADE對序列的數(shù)量呈現(xiàn)出線性可擴展性。6.3模式增長框架的序列挖掘算法前面介紹的Apriori類算法的主要問題是產(chǎn)生大量候選集（例如，如果有100個頻繁1-序列，產(chǎn)生候選2-序列個數(shù)為100×100+100×99/2，前者是形如<ab>的序列個數(shù)，其中a、b位置上均可以取100個項，后者是形如<(ab)>的序列個數(shù)，其中a、b不能重復(fù)出現(xiàn)，且<(ab)>和<(ba)>被認為是相同的）、多遍掃描數(shù)據(jù)庫和大易挖掘長模式序列。模式增長框架的算法基于分治的思想，迭代地將原始數(shù)據(jù)集進行劃分，減少數(shù)據(jù)規(guī)模，不產(chǎn)生候選序列，同時在劃分的過程中動態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元。典型的代表有FreeSpan算法和PrefixSpan算法。6.3.1FreeSpan算法

FreeSpan（frequentpattern-projectedsequentialpatternmining，頻繁模式投影的序列模式挖掘）算法是由JiaweiHan等于2000年提出的，它利用已產(chǎn)生的頻繁集遞歸產(chǎn)生投影數(shù)據(jù)庫，然后在投影數(shù)據(jù)庫中增長子序列。算法不僅可以挖掘所有序列模式，還減少了產(chǎn)生候選序列所需開銷，提高算法效率。FreeSpan算法執(zhí)行的過程如下：（1）對于給定的序列數(shù)據(jù)庫S及最小支持度閾值min_sup，首先掃描S，找到S中所有頻繁項的集合，并以降序排列生成頻繁項表即f-list表，設(shè)f-list=（x1，x2，…，xn）。（2）將S中所有的序列模式集合可以劃分成n個互不重疊的子集，即根據(jù)生成的f-list表把序列數(shù)據(jù)庫S分成幾個不相交的子集即i投影數(shù)據(jù)庫：只包含項x1的序列模式集合。包含項x2，但不包含（x3，…，xn）中項的序列模式集合。包含項x3，但不包含（x4，…，xn）中項的序列模式集合?！梮n-1，但不包含項xn的序列模式集合。包含項xn的序列模式集合。（3）在<xi>投影數(shù)據(jù)庫中通過掃描找出頻繁2-序列集合，對于其中的每個頻繁2-序列，再次掃描<xi>投影數(shù)據(jù)庫生成該頻繁2-序列的投影數(shù)據(jù)庫，從中找出頻繁3-序列集合，…依此類推，直到某個投影數(shù)據(jù)庫中找不到更長的序列為止。

【例6.11】給定如表6.16所示的序列數(shù)據(jù)庫S，全局項集I={a，b，c，d，e，f，g}（本節(jié)中序列采用簡寫方式，如<eg(af)cbc>序列是<{e}，{g}，{a，f}，{c}，，{c}>的簡寫形式，本節(jié)用小括號代替大括號表示，如果一個事件只有單個項，則省略括號）。假設(shè)最小支持度閾值min_sup為2。下面給出用FreeSpan算法求序列模式的過程。SID序列序列的項集10<a(abc)(ac)d(cf)>{a，b，c，d，f}20<(ad)c(bc)(ae)>{a，b，c，d，e}30<(ef)(ab)(df)cb>{a，b，c，d，e，f}40<eg(af)cbc>{a，b，c，e，f，g}第一次掃描序列數(shù)據(jù)庫，找出所有的頻繁項，并將這些頻繁項按支持度遞減排序構(gòu)成一個頻繁項表，即：

f-list=f-list=（a:4，b:4，c:4，d:3，e:3，f:3）這樣生成6個長度為1的頻繁序列：<a>:4，<b>:4，<c>:4，<d>:3，<e>:3，<f>:3，其中“<模式>:計數(shù)”表示模式和它的支持度計數(shù)。然后將序列數(shù)據(jù)庫按α投影操作劃分成6個互不重疊的子數(shù)據(jù)庫。α投影數(shù)據(jù)庫是由那些包含α且不包含任何非頻繁項，也不包含在f-list表中居于α之后項的序列所組成的數(shù)據(jù)庫。

例如，對于頻繁項e，初始時<e>投影數(shù)據(jù)庫為空，掃描序列數(shù)據(jù)庫S，第1個序列中不含有e，不予考慮；第2個序列含有e，從中刪除所有f項得到<(ad)c(bc)(ae)>，將其加入到<e>投影數(shù)據(jù)庫中；第3個序列含有e，從中刪除所有f項得到<e(ab)dcb>，將其加入到<e>投影數(shù)據(jù)庫中；第4個序列含有e，從中刪除所有f項和不頻繁項g得到<eacbc>，將其加入到<e>投影數(shù)據(jù)庫中。得到的6個投影數(shù)據(jù)庫及其序列如表6.17所示。子數(shù)據(jù)庫包含的序列子數(shù)據(jù)庫包含的序列僅包含a的<aaa><aa><a><a>包含d但不包含e～f<a(abc)(ac)dc><(ad)c(bc)a><(ab)dcb>包含b但不包含c～f<a(ab)a><aba><(ab)b><ab>包含e但不包含f<(ad)c(bc)(ae)><e(ab)dcb><eacbc>包含c但不包含d～f<a(abc)(ac)c><ac(bc)a><(ab)cb><acbc>包含f<a(abc)(ac)d(cf)><(ef)(ab)(df)cb><e(af)cbc>挖掘每個投影數(shù)據(jù)庫的過程如下：

（1）挖掘僅包含a的序列模式通過挖掘<a>投影數(shù)據(jù)庫即{<aaa>，<aa>，<a>，<a>}，其中<aa>:2是頻繁的，將其保留，即得到一個頻繁2-序列<aa>，而包含<aa>的其他序列都是非頻繁的，因此該過程結(jié)束。也就是說，僅含有項a而不含其他任何項的頻繁模式子集為{<a>，<aa>}。

（2）挖掘包含b但不包含c～f的序列模式即挖掘<b>投影數(shù)據(jù)庫即{<a(ab)a>，<aba>，<(ab)b>，<ab>}，其過程如下：①掃描<b>投影數(shù)據(jù)庫，挖掘出長度為2的頻繁序列，共產(chǎn)生3個長度為2的的頻繁序列，即{<ab>:4，<ba>:2，<(ab)>:2}（<aa>:2也是其頻繁2-序列，由于前面已挖掘出來，這里不再考慮）。②處理<ab>:4序列模式：掃描<b>投影數(shù)據(jù)庫生成<ab>投影數(shù)據(jù)庫，得到的<ab>投影數(shù)據(jù)庫為{<a(ab)a>，<aba>，<(ab)b>，<ab>}，并以此生成長度為3的序列模式，即得到結(jié)果為{<aba>:2}。掃描<ab>投影數(shù)據(jù)庫生成<aba>投影數(shù)據(jù)庫為{<a(ab)a>，<aba>}，沒有發(fā)現(xiàn)任何長度為4的序列模式。③處理<ba>:2序列模式：掃描<b>投影數(shù)據(jù)庫生成<ba>投影數(shù)據(jù)庫，得到的<ba>投影數(shù)據(jù)庫為{<a(ab)a>，<aba>}，并以此生成長度為3的序列模式，即得到結(jié)果為{<aba>:2}。該頻繁模式前面已考慮，不再繼續(xù)。④處理<(ab)>:2序列模式：掃描<b>投影數(shù)據(jù)庫生成<(ab)>投影數(shù)據(jù)庫，得到的<(ab)>投影數(shù)據(jù)庫為{<a(ab)a>，<(ab)b>}，沒有發(fā)現(xiàn)任何長度為3的序列模式。這樣，挖掘包含b但不包含c～f的序列模式時，共產(chǎn)生4個頻繁模式{<ab>:4，<ba>:2，<(ab)>:2，<aba>:2}。

（3）挖掘包含c但不包含d～f的序列模式

即挖掘<c>投影數(shù)據(jù)庫即{<a(abc)(ac)c>，<ac(bc)a>，<(ab)cb>，<acbc>}，其過程如下：①掃描<c>投影數(shù)據(jù)庫，挖掘出長度為2的頻繁序列，結(jié)果為{<ac>:4，<(bc)>2，<bc>:3，<cc>:3,<ca>:2，<cb>:3}（前面已求過的頻繁模式不再考慮）。②處理<(ac)>:4序列模式：掃貓<c>投影數(shù)據(jù)庫生成<ac>投影數(shù)據(jù)庫，得到的<ac>投影數(shù)據(jù)庫為{<a(abc)(ac)c>，<ac(bc)a>，<(ab)cb>，<acbc>}，并以此生成長度為3的序列模式，即得到結(jié)果為{<acb>:3，<acc>:3，<(ab)c>:2，<aca>:2，<a(bc)>:2}。③處理<acb>:3序列模式：掃描<ac>投影數(shù)據(jù)庫得到<acb>投影數(shù)據(jù)庫，得到的結(jié)果為{<ac(bc)a>，<(ab)cb>，<acbc>}，此時發(fā)現(xiàn)找不到長度為4的序列模式，這一過程結(jié)束。類似的，其他3-序列的投影數(shù)據(jù)庫中也沒有長度為4的序列模式。這樣<ac>投影數(shù)據(jù)庫的挖掘過程結(jié)束。其他頻繁模式的挖掘過程與此類似。

FreeSpan算法分析：它將頻繁序列和頻繁模式的挖掘統(tǒng)一起來，把挖掘工作限制在投影數(shù)據(jù)庫中，還能限制序列分片的增長。它能有效地發(fā)現(xiàn)完整的序列模式，同時大大減少產(chǎn)生候選序列所需的開銷，比GSP算法快很多。不足之處是可能會產(chǎn)生許多投影數(shù)據(jù)庫，如果一個模式在數(shù)據(jù)庫中的每個序列中出現(xiàn)，該模式的投影數(shù)據(jù)庫將不會縮減；另外，一個長度為k的序列可能在任何位置增長，那么長度為k+1的候選序列必須對每個可能的組合情況進行考察，這樣所需的開銷是比較大的。6.3.2PrefixSpan算法

PrefixSpan算法和FreeSpan算法一樣，也是采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進行序列模式挖掘。但PrefixSpan算法克服FreeSpan算法中序列模式在任何位置增長問題，它只基于頻繁前綴投影，確保序列向后增長，同時也縮減投影數(shù)據(jù)庫的大小。

定義6.8

設(shè)序列中每個事件中的項按字典順序排列。給定序列α=<e1e2…en>（其中ei對應(yīng)序列數(shù)據(jù)庫S中的一個頻繁事件），β=<e1'e2'…em'>（m≤n），如果ei'=ei（i≤m-1），em'?em，并且(em-em')中的所有頻繁項按字母順序排在em'之后，則稱β是α的前綴。例如，<a>、<aa>、<a(ab)>和<a(abc)>都是序列s=<a(abc)(ac)d(cf)>的前綴，而<ab>和<a(bc)>卻不是s的前綴。

定義6.9

給定序列α=<e1e2…en>（其中ei對應(yīng)序列數(shù)據(jù)庫S中的一個頻繁事件），β=<e1e2…em-1em'>（m≤n）是α的前綴。序列γ=<em''em+1…en>稱為α的相對于β的后綴，記為γ=α/β。這里e''=(em-em')，如果e''非空，則該后綴記為<(_em''中的項)

em+1…en>。也可以記為α=β·γ。

注意，如果β不是α的子序列，則α的相對于β的后綴為空。例如，若序列s=<a(abc)(ac)d(cf)>，則<(abc)(ac)d(cf)>是s的相對于前綴<a>的后綴。<(_bc)(ac)d(cf)>是s的相對于前綴<aa>的后綴，其中(_b)表示該前綴的最后一個事件是a，a與b一起形成一個事件。<(_c)(ac)d(cf)>是s的相對于前綴<a(ab)>的后綴。如圖6.14所示。序列s的前綴和后綴

定義6.10

設(shè)α是序列數(shù)據(jù)庫S中的一個序列模式。α投影數(shù)據(jù)庫記為S|α，它是S中所有以α為前綴的序列相對于α的后綴的集合。