第6章 序列模式挖掘

第6章序列模式挖掘

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

定義6.1

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

定義6.2

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

定義6.3

序列數(shù)據(jù)庫(kù)（sequencedatabases）S是元組<SID，s>的集合，其中SID是序列編號(hào)，s是一個(gè)序列，每個(gè)序列由若干事件構(gòu)成。在序列數(shù)據(jù)庫(kù)中每個(gè)序列的事件在時(shí)間或空間上是有序排列的?？蛻?hù)號(hào)SID交易時(shí)間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客戶(hù)號(hào)客戶(hù)序列s1<{30}，{80}>s2<{10，20}，{30}，{40，60，70}>s3<{30，50，70}>s4<{30}，{40，70}，{80}>s5<{80}>交易數(shù)據(jù)庫(kù)D序列數(shù)據(jù)庫(kù)S

定義6.4

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

，t2

，…，tm

。如果t是s的子序列，則稱(chēng)t包含在s中。例如序列<{2}，{1，3}>是序列<{1，2}，{5}，{1，3，4}>的子序列，因?yàn)閧2}包含在{1，2}中，{1，3}包含在{1，3，4}中。而<{2，5}，{3}>不是序列<{1，2}，{5}，{1，3，4}>的子序列，因?yàn)榍罢咧许?xiàng)2和項(xiàng)5是一次購(gòu)買(mǎi)的，而后者中項(xiàng)2和項(xiàng)5是先后購(gòu)買(mǎi)的，這就是區(qū)別所在。

定義6.5

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

定義6.6

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

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

+…+

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

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

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

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

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

Lk={c|c∈Ckandc.sup_count≥min_sup}; //由Ck中計(jì)數(shù)大于min_sup的候選序列組成頻繁k-序列集合Lk}L=∪kLk;上述算法中利用頻繁序列Lk-1生成候選k-序列Ck的過(guò)程說(shuō)明如下：（1）連接對(duì)于Lk-1中任意兩個(gè)序列s1和s2，如果s1與s2的前k-2項(xiàng)相同，即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）剪枝剪枝的原則：一個(gè)候選k-序列，如果它的(k-1)-序列有一個(gè)是非頻繁的，則刪除它。由Ck剪枝產(chǎn)生Lk的過(guò)程如下：for(所有c∈Ck的序列)

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

從Ck中刪除c;Ck

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

【例6.3】以表6.6所示的序列數(shù)據(jù)庫(kù)S1為例，給出ApriorAll算法的執(zhí)行過(guò)程，這里I={1，2，3，4，5}，每個(gè)數(shù)字表示一個(gè)項(xiàng)。假設(shè)min_sup=2?？蛻?hù)號(hào)客戶(hù)序列s1<{1，5}，{2}，{3}，{4}>s2<{1}，{3}，{4}，{3，5}>s3<{1}，{2}，{3}，{4}>s4<{1}，{3}，{5}>s5<{4}，{5}>一個(gè)序列數(shù)據(jù)庫(kù)S1

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

for(每個(gè)k-序列sk)

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

【例6.4】對(duì)于表6.5所示的序列數(shù)據(jù)庫(kù)S1，從前面的過(guò)程看到，產(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>}刪除子序列得到最大序列的過(guò)程如下：由于最長(zhǎng)的序列是4，因此所有4-序列都是最大序列，這里只有<1，2，3，4>是最大序列。對(duì)于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>是最大序列。對(duì)于3-序列<1，3，5>，從L中刪除它的2-子序列<1，5>、<3，5>和1-子序列<5>，剩下的2-序列<4，5>是最大序列。到此，L中已沒(méi)有可以再刪除的子序列了，得到的序列模式如下表所示。序列模式計(jì)數(shù)<1，2，3，4>2<1，3，5>2<4，5>2當(dāng)求出所有序列模式集合L后，可以采用類(lèi)似Apriori算法生成所有的強(qiáng)關(guān)聯(lián)規(guī)則。生成所有的強(qiáng)關(guān)聯(lián)規(guī)則RuleGen(L，min_conf)算法如下：輸入：所有序列模式集合L，最小置信度閾值min_conf輸出：強(qiáng)關(guān)聯(lián)規(guī)則集合R方法：其過(guò)程描述如下：R=Φ;for(對(duì)于L中每個(gè)頻繁序列β)

for(對(duì)于β的每個(gè)子序列α)

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

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

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

<{D}，{B，F(xiàn)}>→<{D}，{B，F(xiàn)}，{A}>是一條強(qiáng)關(guān)聯(lián)規(guī)則，因?yàn)樗闹眯哦?2/2=100%。6.2.2AprioriSome算法

AprioriSome算法可以看作是AprioriAll算法的改進(jìn)，它們的主要查找序列的思路是基本一致的，僅在策略上有所差異，AprioriSome算法主要在于將具體過(guò)程分為以下兩個(gè)階段：前推階段（或前半部分）：此階段只對(duì)指定長(zhǎng)度的序列進(jìn)行計(jì)數(shù)。回溯階段（或后半部分）：此階段跳過(guò)已經(jīng)計(jì)數(shù)過(guò)的序列。AprioriSome算法描述如下：輸入：找頻繁項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)S，最小支持度閾值min_sup輸出：序列模式集合L方法：其過(guò)程描述如下：//前推階段（前半階段）L1={頻繁1-序列};C1=L1;last=1; //計(jì)數(shù)的序列長(zhǎng)度f(wàn)or(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(對(duì)于序列數(shù)據(jù)庫(kù)S中的每一個(gè)客戶(hù)序列c)

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

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

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

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

next函數(shù)以上次遍歷的序列長(zhǎng)度作為輸入，返回下次遍歷中需要計(jì)數(shù)的序列長(zhǎng)度。該函數(shù)確定了哪一個(gè)序列將被計(jì)數(shù)，在對(duì)非最大序列計(jì)數(shù)時(shí)間的浪費(fèi)和計(jì)算擴(kuò)展小候選序列之間作出權(quán)衡。當(dāng)next(k)=k+1（k是最后計(jì)數(shù)候選者的長(zhǎng)度）時(shí)，這時(shí)所有的子序列都被計(jì)算，而候選序列集合最小，此時(shí)退化為AprioriAll算法。當(dāng)next(k)遠(yuǎn)大于k，如next(k)=100×k時(shí)，這時(shí)幾乎所有的子序列都不被計(jì)算，但候選序列數(shù)卻大大增加。下面給出按經(jīng)驗(yàn)所使用的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;}在掃描開(kāi)始階段，hitk較大，也就是說(shuō)候選序列較少，將k設(shè)置為較大的值，可以減少對(duì)子序列的計(jì)數(shù)。在以后掃描過(guò)程中，hitk越來(lái)越小，將k設(shè)置為較小的值，可以減少候選序列數(shù)。

【例6.5】以表6.6的序列數(shù)據(jù)庫(kù)S1為例，給出AprioriSome算法的執(zhí)行過(guò)程，設(shè)定min_sup=2。假設(shè)前推階段只計(jì)算長(zhǎng)度k為1、2、4、6、…的序列（即next(1)=2，next(2)=4，next(3)=6，…）。在前推階段中，先置last=1，過(guò)程如下：①對(duì)序列數(shù)據(jù)庫(kù)進(jìn)行一次掃描得到L1?？蛻?hù)號(hào)客戶(hù)序列s1<{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)時(shí)，由L1計(jì)算C2，由于k==next(1)成立，則掃描序列數(shù)據(jù)庫(kù)計(jì)算支持度得到L2，其過(guò)程與圖6.2類(lèi)似，并置last=2。產(chǎn)生L2的過(guò)程③當(dāng)k=3循環(huán)時(shí)，由C2產(chǎn)生C3，其過(guò)程如圖6.5所示，由于k==next(2)不成立，所以不會(huì)計(jì)算C3的支持度計(jì)數(shù)，因此不產(chǎn)生L3。產(chǎn)生的C3

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

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

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

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

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

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

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

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

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

將x加入到Ck+step中;}

Lk+step=在Ck+step中計(jì)數(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)生所有序列模式對(duì)于DynamicSome算法，若step設(shè)為3，在初始化階段對(duì)長(zhǎng)度為1、2、3的序列計(jì)數(shù)。然后在前半部分對(duì)長(zhǎng)度為6、9、12、…的序列計(jì)數(shù)。若只想對(duì)長(zhǎng)度為6、9、12、…的序列計(jì)數(shù)時(shí)，通過(guò)兩個(gè)長(zhǎng)度為3的序列進(jìn)行連接運(yùn)算可得到長(zhǎng)度為6的序列，同理，通過(guò)一個(gè)長(zhǎng)度為6的序列與一個(gè)長(zhǎng)度為3的序列進(jìn)行連接運(yùn)算可得到長(zhǎng)度為9的序列，以此類(lèi)推。但是，要想得到長(zhǎng)度為3的序列，就需要長(zhǎng)度為1及長(zhǎng)度為2的序列，因此，就需要有初始化階段。

otf_generate(Lk,Lstep,c)算法的參數(shù)分別為頻繁k-序列、頻繁step-序列和客戶(hù)序列，結(jié)果返回包含在c中的候選(k+step)-序列的集合。例如，step=3、k=6時(shí)，執(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>是一個(gè)候選(k+j)-序列。對(duì)于c中的每個(gè)事件x，若x∈Lk中序列sk=<…，xl>，取x.end=min{xl}；對(duì)于c中的每個(gè)事件y，若y∈Lj中序列sj=<yl，…>，取y.start=max{yl}。然后在滿足連接條件x.end<y.start的情況下，將sk和sj兩個(gè)序列合并得到一個(gè)候選(k+j)-序列，所有這樣序列集合即為返回的候選X。例如，以圖6.2中的L2為例，設(shè)c=<1，2，4>，執(zhí)行X=otf_generate(L2,L2,c)，c1對(duì)應(yīng)事件1，c2對(duì)應(yīng)事件2，c3對(duì)應(yīng)事件4。求出的長(zhǎng)度為2的序列集X2如表6.8所示，只有序列<1，2>和<3，4>滿足連接條件，其結(jié)果為單個(gè)序列<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開(kāi)始與結(jié)束值

【例6.6】以表6.6的序列數(shù)據(jù)庫(kù)S1為例說(shuō)明DynamicSome算法的執(zhí)行過(guò)程，設(shè)定min_sup=2，step=2。其過(guò)程如下：客戶(hù)號(hào)客戶(hù)序列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的過(guò)程①初始化階段：求出L2的過(guò)程與圖6.2相同。

②前半階段：k=step（2）時(shí)，由Lk與Lstep連接，通過(guò)掃描序列數(shù)據(jù)庫(kù)S1，求得C4如表6.9所示，得到L4={<1，2，3，4>}。執(zhí)行k+=step，得到k=4，將C4與C2連接得到C6為空。前半階段結(jié)束。序列計(jì)數(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é)束時(shí)的k值即4，執(zhí)行k--，得到k=3，由于L3在前半部分沒(méi)有計(jì)數(shù)，則對(duì)C3計(jì)數(shù)得到L3。

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

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

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

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

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

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

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

從根結(jié)點(diǎn)開(kāi)始，用哈希函數(shù)對(duì)序列的第一個(gè)項(xiàng)做映射來(lái)決定從哪個(gè)分支向下，依次在第k層對(duì)序列的第k個(gè)項(xiàng)作映射來(lái)決定從哪個(gè)分支向下，直到到達(dá)一個(gè)葉子結(jié)點(diǎn)。

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

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

SPADE是一種基于數(shù)據(jù)垂直數(shù)據(jù)格式的Aprior類(lèi)算法，垂直數(shù)據(jù)分布的數(shù)據(jù)集由一系列序列標(biāo)識(shí)符、事件標(biāo)識(shí)符和項(xiàng)集組成。例如，表6.13所示是一個(gè)客戶(hù)交易的垂直數(shù)據(jù)庫(kù)D，它是由相應(yīng)客戶(hù)交易數(shù)據(jù)庫(kù)轉(zhuǎn)換而來(lái)的?？蛻?hù)號(hào)SID交易時(shí)間TID項(xiàng)集（事件）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}所有的頻繁序列都可以通過(guò)搜索序列格的方式被挖掘出來(lái)，其基本運(yùn)算是兩個(gè)序列的組合。兩個(gè)k-序列組合的結(jié)果為(k+1)-序列的集合，它們?cè)谛蛄懈裰星『锰幱谶@兩個(gè)k-序列的上一層，該運(yùn)算用“∨”表示。如圖6.9中，A、B是兩個(gè)1-序列，它們的組合A∨B={<A，B>，<AB>，<B，A>}，見(jiàn)圖中帶陰影的圓圈。

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

1-序列<A>的id-list表L(A)中有6行，但只有4個(gè)不同的序列號(hào)SID，所以該序列的支持度計(jì)數(shù)為4。由于1-序列<C>的支持度計(jì)數(shù)小于min_sup，表中沒(méi)有列出，因此，頻繁1-序列集合F1={<A>，<B>，<D>，<F>}。L(A)L(B)L(D)L(F)SIDTIDSIDTIDSIDTIDSIDTIDs115s115s110s120s120s120s125s125s125s215s410s215s215s310s310s310s420s420s425客戶(hù)號(hào)SID交易時(shí)間TID項(xiàng)集（事件）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}長(zhǎng)度為1的序列的id-list表

定義6.7

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

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

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

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

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

【例6.11】給定如表6.16所示的序列數(shù)據(jù)庫(kù)S，全局項(xiàng)集I={a，b，c，d，e，f，g}（本節(jié)中序列采用簡(jiǎn)寫(xiě)方式，如<eg(af)cbc>序列是<{e}，{g}，{a，f}，{c}，，{c}>的簡(jiǎn)寫(xiě)形式，本節(jié)用小括號(hào)代替大括號(hào)表示，如果一個(gè)事件只有單個(gè)項(xiàng)，則省略括號(hào)）。假設(shè)最小支持度閾值min_sup為2。下面給出用FreeSpan算法求序列模式的過(guò)程。SID序列序列的項(xiàng)集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ù)庫(kù)，找出所有的頻繁項(xiàng)，并將這些頻繁項(xiàng)按支持度遞減排序構(gòu)成一個(gè)頻繁項(xiàng)表，即：

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

例如，對(duì)于頻繁項(xiàng)e，初始時(shí)<e>投影數(shù)據(jù)庫(kù)為空，掃描序列數(shù)據(jù)庫(kù)S，第1個(gè)序列中不含有e，不予考慮；第2個(gè)序列含有e，從中刪除所有f項(xiàng)得到<(ad)c(bc)(ae)>，將其加入到<e>投影數(shù)據(jù)庫(kù)中；第3個(gè)序列含有e，從中刪除所有f項(xiàng)得到<e(ab)dcb>，將其加入到<e>投影數(shù)據(jù)庫(kù)中；第4個(gè)序列含有e，從中刪除所有f項(xiàng)和不頻繁項(xiàng)g得到<eacbc>，將其加入到<e>投影數(shù)據(jù)庫(kù)中。得到的6個(gè)投影數(shù)據(jù)庫(kù)及其序列如表6.17所示。子數(shù)據(jù)庫(kù)包含的序列子數(shù)據(jù)庫(kù)包含的序列僅包含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>挖掘每個(gè)投影數(shù)據(jù)庫(kù)的過(guò)程如下：

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

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

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

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

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

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

定義6.8

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

定義6.9

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

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

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

定義6.10

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