第6章 序列模式挖掘

1、第6章 序列(xli)模式挖掘序列數(shù)據(jù)(shj)是由有序元素或事件的序列組成的，可以不包括具體的時間概念，序列數(shù)據(jù)的例子有客戶購物序列、Web點擊流和生物學(xué)序列等。這類數(shù)據(jù)處理的不是一個時間點上的數(shù)據(jù)，而是大量時間點上的數(shù)據(jù)，因而具有自身的特殊性。 共一百二十九頁6.1 序列(xli)模式挖掘概述6.1.1 序列(xli)數(shù)據(jù)庫設(shè)I=i1，i2，in是所有項的集合，在購物籃例子中，每種商品就是一個項。項集是由項組成的一個非空集合。定義6.1 事件（events）是一個項集，在購物籃例子中，一個事件表示一個客戶在特定商店的一次購物，一次購物可以購買多種商品，所以事件表示為（x1，x2，xq），其

2、中xk（1kq）是I中的一個項，一個事件中所有項均不相同，每個事件可以有一個事件時間標(biāo)識TID，也可以表示事件的順序。共一百二十九頁定義6.2 序列（sequence）是事件的有序列表，序列s記作，其中ej（1jl）表示事件，也稱為(chn wi)s的元素。通常一個序列中的事件有時間先后關(guān)系，也就是說，ej（1jl）出現(xiàn)在ej+1之前。序列中的事件個數(shù)稱為序列的長度，長度為k的序列稱為k-序列。在有些算法中，將含有k個項的序列稱為k-序列。共一百二十九頁定義(dngy)6.3 序列數(shù)據(jù)庫（sequence databases）S是元組的集合，其中SID是序列編號，s是一個序列，每個序列由若干事

3、件構(gòu)成。在序列數(shù)據(jù)庫中每個序列的事件在時間或空間上是有序排列的。共一百二十九頁客戶號SID交易時間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客戶號客戶序列s1s2s3s4s5交易(jioy)數(shù)據(jù)庫D序列(xli)數(shù)據(jù)庫S共一百二十九頁定義6.4 對于序列t和s，如果t中每個有序元素都是s中一個有序元素的子集，則稱t是s的子序列。形式化表述(bio sh)為，序列t=是序列s=的子序列，如果存在整數(shù)1j1j2jmn，

4、使得t1，t2，tm。如果t是s的子序列，則稱t包含在s中。例如序列是序列的子序列，因為2包含在1，2中，1，3包含在1，3，4中。而不是序列的子序列，因為前者中項2和項5是一次購買的，而后者中項2和項5是先后購買的，這就是區(qū)別所在。共一百二十九頁定義6.5 如果(rgu)一個序列s不包含在序列數(shù)據(jù)庫S中的任何其他序列中，則稱序列s為最大序列。共一百二十九頁定義6.6 一個序列(xli)的支持度計數(shù)是指在整個序列數(shù)據(jù)庫S中包含的序列個數(shù)。即：supportS()=|(SID，s)| (SID，s)S 是s的子序列|其中，|表示集合中出現(xiàn)的次數(shù)。若序列的支持度計數(shù)不小于最小支持度閾值min_su

5、p，則稱之為頻繁序列，頻繁序列也稱為序列模式。長度為k的頻繁序列稱為頻繁k-序列。共一百二十九頁6.1.2 序列模式(msh)挖掘算法1. 什么是序列(xli)模式挖掘序列模式挖掘的問題定義為：給定一個客戶交易數(shù)據(jù)庫D以及最小支持度閾值min_sup，從中找出所有支持度計數(shù)不小于min_sup的序列，這些頻繁序列也稱為序列模式。有的算法還可以找出最大序列，即這些最大序列構(gòu)成序列模式。共一百二十九頁2. 經(jīng)典的序列模式(msh)挖掘算法（1）候選碼生成測試框架(kun ji)的序列挖掘算法候選碼生成測試框架基于Apriori理論，即序列模式的任一子序列也是序列模式，這類算法統(tǒng)稱為Aprior類算

6、法。主要包括AprioriAll、AprioriSome、DynamicSome、GSP和SPADE算法等。這類算法通過多次掃描數(shù)據(jù)庫，根據(jù)較短的序列模式生成較長的候選序列模式，然后計算候選序列模式的支持度，從而獲得所有序列模式。共一百二十九頁根據(jù)數(shù)據(jù)集的不同分布方式(fngsh)，Aprior類算法又可以分為水平格式算法和垂直格式算法。水平(shupng)分布的數(shù)據(jù)集是由一系列序列標(biāo)識符和序列組成，對應(yīng)的算法有AprioriAll、AprioriSome、DynamicSome和GSP，其中AprioriSome和DynamicSome只求最大序列模式。垂直分布的數(shù)據(jù)集是由一系列序列標(biāo)識符（

7、SID）、項集和事件標(biāo)識符（TID）組成，對應(yīng)的算法有SPADE等。共一百二十九頁（2）模式增長框架的序列挖掘(wju)算法模式增長框架挖掘算法的最大特點：在挖掘過程中不產(chǎn)生候選序列，通過分而治之的思想，迭代的將原始數(shù)據(jù)庫進(jìn)行劃分，同時(tngsh)在劃分的過程中動態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元，進(jìn)行下一次的挖掘過程，從而獲得長度不斷增長的序列模式。主要有FreeSpan和PrefixSpan算法。共一百二十九頁3. 經(jīng)典算法比較(bjio)分析算法是否產(chǎn)生候選序列存儲結(jié)構(gòu)數(shù)據(jù)庫是否縮減原數(shù)據(jù)庫掃描次數(shù)算法執(zhí)行AprioriAll是Hash樹否最長模式長度循環(huán)GSP是Ha

8、sh樹否最長模式長度循環(huán)SPADE是序列格是3遞歸PrefixSpan否前綴樹是2遞歸共一百二十九頁6.2 Apriori類算法(sun f)6.2.1 AprioriAll算法(sun f)對于含有n個事件的序列數(shù)據(jù)庫S，其中k-序列總數(shù)為 ，因此，具有9個事件的序列包含 + + =29-1=511個不同的序列。序列模式挖掘可以采用蠻立法枚舉所有可能的序列，并統(tǒng)計它們的支持度計數(shù)。但計算量非常大。 共一百二十九頁AprioriAll本質(zhì)上是Apriori思想的擴(kuò)張，只是在產(chǎn)生候選序列和頻繁序列方面(fngmin)考慮序列元素有序的特點，將項集的處理改為序列的處理?；谒礁袷降腁priori

9、類算法將序列模式挖掘過程分為5個具體階段，即排序階段、找頻繁項集階段、轉(zhuǎn)換階段、產(chǎn)生頻繁序列階段以及最大化階段。共一百二十九頁1. 排序(pi x)階段對原始數(shù)據(jù)表（如表6.1）按客戶號（作為主關(guān)鍵字）和交易時間（作為次關(guān)鍵字）進(jìn)行(jnxng)排序，排序后通過對同一客戶的事件進(jìn)行(jnxng)合并得到對應(yīng)的序列數(shù)據(jù)庫（如表6.2）?？蛻籼柨蛻粜蛄衧1s2s3s4s5共一百二十九頁2. 找頻繁(pnfn)項集階段這個階段根據(jù)min_sup找出所有的頻繁項集，也同步得到所有頻繁1-序列組成的集合L1，因為(yn wi)這個集合正好是 | l所有頻繁項集集合。這個過程是從所有項集合I開始進(jìn)行的。共

10、一百二十九頁【例6.1】對表6.2的序列(xli)數(shù)據(jù)庫，假設(shè)min_sup=2。找頻繁項集的過程如下：最后(zuhu)求得的頻繁1-序列L1=30，40，70，40，70，80。共一百二十九頁然后將頻繁1-項集映射成連續(xù)的整數(shù)。例如，將上面得到的L1映射成表6.4對應(yīng)的整數(shù)。由于比較頻繁項集花費(fèi)一定時間，這樣做后可以減少檢查一個序列(xli)是否被包含于一個客戶序列(xli)中的時間，從而使處理過程方便且高效。 頻繁項集映射成整數(shù)30140270340，704805共一百二十九頁3. 轉(zhuǎn)換(zhunhun)階段在尋找序列模式的過程中，要不斷地進(jìn)行檢測一個給定(i dn)的大序列集合是否包含于

11、一個客戶序列中。為此做這樣的轉(zhuǎn)換：每個事件被包含于該事件中所有頻繁項集替換。如果一個事件不包含任何頻繁項集，則將其刪除。如果一個客戶序列不包含任何頻繁項集，則將該序列刪除。這樣轉(zhuǎn)換后，一個客戶序列由一個頻繁項集組成的集合所取代。每個頻繁項集的集合表示為e1，e2，ek，其中ei（1ik）表示一個頻繁項集。共一百二十九頁【例6.2】給出表6.2序列數(shù)據(jù)庫經(jīng)過轉(zhuǎn)換(zhunhun)后的結(jié)果?？蛻籼栐蛻粜蛄性蛻粜蛄杏成浜髎1s2:s3s4s5共一百二十九頁4. 產(chǎn)生頻繁(pnfn)序列階段利用轉(zhuǎn)換后的序列(xli)數(shù)據(jù)庫尋找頻繁序列(xli)，AprioriAll算法如下：輸入：轉(zhuǎn)換后的序列數(shù)據(jù)

12、庫S，所有項集合I，最小支持度閾值min_sup輸出：序列模式集合L方法：其過程描述如下：共一百二十九頁L1= i | iI and i.sup_countmin_sup;/找出所有頻繁1-序列(xli)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 | cCk and c.sup_countmin_sup;/由Ck中計數(shù)大于min_sup的候選序列組成頻繁k-序列集合LkL=kLk;共一百二十九頁上述算法中利用頻繁序列L

13、k-1生成候選k-序列Ck的過程(guchng)說明如下：（1）連接(linji)對于Lk-1中任意兩個序列s1和s2，如果s1與s2的前k-2項相同，即s1=，s2=，則合并序列s1和s2，得到候選k-序列和。即：insert into Ckselect p.itemset1, p.itemset2, p.itemsetk-1,q.itemsetk-1from Lk-1 p,Lk-1 qwhere p.itemset1=q.itemset1 and p.itemset2=q.itemset2 and and p.itemsetk-2=q.itemsetk-2共一百二十九頁（2）剪枝(jin

14、zh)剪枝的原則：一個候選k-序列，如果它的(k-1)-序列有一個是非頻繁的，則刪除它。由Ck剪枝產(chǎn)生Lk的過程(guchng)如下：for (所有cCk的序列)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ù)字表示(biosh)一個項。假設(shè)min_sup=2?？蛻籼柨蛻粜蛄衧1s2s3s4s5一個(y )序列數(shù)據(jù)庫S1 共一百二十九頁 先求出L1，由其產(chǎn)生L2的過程如圖6.2所示，實際上這個過

15、程不需要剪枝，因為C2中每個2-序列的所有(suyu)子序列一定屬于L1。產(chǎn)生(chnshng)L2的過程 共一百二十九頁 由L2連接并剪枝產(chǎn)生C3，掃描(somio)序列數(shù)據(jù)庫S1，刪除小于min_sup的序列得到L3，其過程如圖6.3所示。產(chǎn)生(chnshng)L3的過程 共一百二十九頁 由L3連接并剪枝產(chǎn)生C4，掃描序列數(shù)據(jù)庫S1，刪除小于min_sup的序列得到(d do)L4，其過程如圖6.4所示。產(chǎn)生(chnshng)L4的過程 L4中只有一個序列，由它產(chǎn)生的C5為空，L5也為空。算法結(jié)束。共一百二十九頁5. 最大化階段(jidun)在頻繁序列模式集合中持出最大頻繁序列模式集合。由

16、于在產(chǎn)生頻繁模式階段發(fā)現(xiàn)了所有頻繁模式集合L，下面(xi mian)的過程可用來發(fā)現(xiàn)最大序列。設(shè)最長序列的長度為n，則：for (k=n;k1;k-)for (每個k-序列sk)從L中刪除sk的所有子序列;共一百二十九頁【例6.4】對于表6.5所示的序列數(shù)據(jù)庫S1，從前面的過程看到，產(chǎn)生的所有頻繁(pnfn)序列集合：L=，刪除子序列得到最大序列的過程如下：共一百二十九頁由于最長的序列是4，因此所有4-序列都是最大序列，這里只有是最大序列。對于(duy)4-序列，從L中刪除它的3-子序列、，2-子序列、和1-子序列、，剩下的3-序列是最大序列。共一百二十九頁對于3-序列，從L中刪除(shnch

17、)它的2-子序列、和1-子序列，剩下的2-序列是最大序列。到此，L中已沒有可以再刪除的子序列了，得到的序列模式如下表所示。序列模式計數(shù)222共一百二十九頁當(dāng)求出所有序列模式集合L后，可以(ky)采用類似Apriori算法生成所有的強(qiáng)關(guān)聯(lián)規(guī)則。生成所有的強(qiáng)關(guān)聯(lián)規(guī)則RuleGen(L，min_conf)算法如下：輸入：所有序列(xli)模式集合L，最小置信度閾值min_conf輸出：強(qiáng)關(guān)聯(lián)規(guī)則集合R方法：其過程描述如下：R=;for (對于L中每個頻繁序列)for (對于的每個子序列)conf=.sup_count/.sup_count;if (confmin_conf)R=R;/產(chǎn)生一條新規(guī)則r

18、eturn R;共一百二十九頁例如，假設(shè)有一個頻繁3-序列，其支持度計數(shù)為2，它的一個子序列的支持度計數(shù)也為2。若置信度閾值min_conf=75%，則：是一條(y tio)強(qiáng)關(guān)聯(lián)規(guī)則，因為它的置信度=2/2=100%。共一百二十九頁6.2.2 AprioriSome算法(sun f)AprioriSome算法可以看作是AprioriAll算法的改進(jìn)，它們的主要查找序列的思路是基本一致的，僅在策略上有所差異(chy)，AprioriSome算法主要在于將具體過程分為以下兩個階段：前推階段（或前半部分）：此階段只對指定長度的序列進(jìn)行計數(shù)?；厮蓦A段（或后半部分）：此階段跳過已經(jīng)計數(shù)過的序列。共一百

19、二十九頁AprioriSome算法(sun f)描述如下：輸入：找頻繁項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫S，最小支持度閾值min_sup輸出：序列模式集合(jh)L方法：其過程描述如下：/前推階段（前半階段）L1=頻繁1-序列; C1=L1;last=1;/計數(shù)的序列長度for (k=2; Ck-1 and Llast ; 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=

20、在Ck中滿足最小支持度的候選者;last= k; 共一百二十九頁/回溯階段（后半階段）for (k-; k=1;k-) if (Lk在前推階段沒有確定) 刪除(shnch)所有在Ck中包含在某些Li（ik）中的序列;for (對于在S中的每一個客戶序列c) 對在Ck中包含在c中的所有的候選者的計數(shù)增1;Lk=在Ck中滿足最小支持度的候選者; else / Lk已知 刪除所有在Lk中包含在某些Li（ik）中的序列; L=kLk;/求Lk的并集產(chǎn)生所有序列模式共一百二十九頁在前推階段中，只對特定長度的序列進(jìn)行計數(shù)。比如(br)，前推階段對長度為1、2、4和6的序列計數(shù)（計算支持度），而長度為3和5

21、的序列則在回溯階段中計數(shù)。next函數(shù)以上次遍歷的序列長度作為輸入，返回下次遍歷中需要計數(shù)的序列長度。該函數(shù)確定了哪一個序列將被計數(shù)，在對非最大序列計數(shù)時間的浪費(fèi)和計算擴(kuò)展小候選序列之間作出權(quán)衡。當(dāng)next(k)=k+1（k是最后計數(shù)候選者的長度）時，這時所有的子序列都被計算，而候選序列集合最小，此時退化為AprioriAll算法。當(dāng)next(k)遠(yuǎn)大于k，如next(k)=100k時，這時幾乎所有的子序列都不被計算，但候選序列數(shù)卻大大增加。共一百二十九頁下面給出按經(jīng)驗(jngyn)所使用的next函數(shù)。int next(int k) if (hitk0.666) return k+1;els

22、e if (hitk0.75) return k+2; else if (hitk0.80) return k+3; else if (hitk0.85) return k+4; else return k+5;在掃描開始階段，hitk較大，也就是說候選序列較少，將k設(shè)置(shzh)為較大的值，可以減少對子序列的計數(shù)。在以后掃描過程中，hitk越來越小，將k設(shè)置為較小的值，可以減少候選序列數(shù)。共一百二十九頁【例6.5】以表6.6的序列數(shù)據(jù)庫S1為例，給出AprioriSome算法的執(zhí)行過程(guchng)，設(shè)定min_sup=2。假設(shè)前推階段只計算長度k為1、2、4、6、的序列(xli)（即n

23、ext(1)=2，next(2)=4，next(3)=6，）。在前推階段中，先置last=1，過程如下： 對序列數(shù)據(jù)庫進(jìn)行一次掃描得到L1?？蛻籼柨蛻粜蛄衧1s2s3s4s5共一百二十九頁 當(dāng)k=2循環(huán)時，由L1計算C2，由于k=next(1)成立，則掃描序列數(shù)據(jù)庫計算支持(zhch)度得到L2，其過程與圖6.2類似，并置last=2。產(chǎn)生(chnshng)L2的過程 共一百二十九頁 當(dāng)k=3循環(huán)時，由C2產(chǎn)生C3，其過程如圖6.5所示，由于(yuy)k=next(2)不成立，所以不會計算C3的支持度計數(shù)，因此不產(chǎn)生L3。產(chǎn)生(chnshng)的C3 共一百二十九頁 當(dāng)k=4循環(huán)時，由C3產(chǎn)生

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

25、一百二十九頁 當(dāng)k=2循環(huán)時，L2已求出，刪除L2中包含(bohn)在L3和L4中的子序列， 只剩下。 當(dāng)k=1循環(huán)時，L1中的所作序列都已被刪除。最后得到的序列模式(msh)如表6.6相同。序列模式計數(shù)222共一百二十九頁AprioriSome和AprioriAll比較(bjio)有以下幾個不同：AprioriAll用Lk-1去算出所有的候選Ck，而AprioriSome會直接用Ck-1去計算出所有的候選Ck，因為Ck-1包含Lk-1，所以AprioriSome會產(chǎn)生比較多的候選。雖然AprioriSome跳躍式計算候選，但因為它所產(chǎn)生的候選比較多，可能在回溯階段前就占滿內(nèi)存。如果內(nèi)存滿了，

26、AprioriSome就會被強(qiáng)迫去計算最后一組的候選（即使原本是要跳過此項）。這樣，會影響并減少已計算好的兩個候選間的跳躍距離，而使得AprioriSome會變的跟AprioriAll一樣(yyng)。對于較低的支持度，有比較長的頻繁序列，也因此有比較多的非最大序列，此時AprioriSome較好。共一百二十九頁6.2.3 DynamicSome算法(sun f)DynamicSome算法類似于AprioriSome算法，由函數(shù)確定要計數(shù)的序列長度，分為四個階段(jidun)（部分）。但與AprioriAll、AprioriSome 不同，DynamicSome算法的剪枝在后半階段，并不像Ap

27、rioriAll、AprioriSome 那樣計數(shù)后就進(jìn)行剪枝，因此在支持度較小時，會產(chǎn)生大量的候選序列。 共一百二十九頁DynamicSome算法(sun f)主要特點如下： 由變量step來決定要計數(shù)的候選序列。在初始化階段(jidun)，所有達(dá)到并且包括step長度的候選序列都要進(jìn)行計數(shù)。前半階段跳過對一定長度的候選序列的計數(shù)，對所有長度為step倍數(shù)的序列進(jìn)行計數(shù)。中間階段產(chǎn)生候選序列。后半階段的算法與AprioriSome算法的后半階段完全相同。需要對半階段未計數(shù)的序列進(jìn)行計數(shù)。共一百二十九頁DynamicSome算法(sun f)描述如下：輸入：找頻繁項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫S，

28、最小支持度閾值min_sup輸出：序列模式(msh)集合L方法：其過程描述如下：step1并且為整數(shù);/初始化階段L1=頻繁1-序列;for (k=2; k1; k-) if (Lk仍未確定) if (Lk-1已知) Ck=產(chǎn)生于Lk-1的新候選者;else Ck=產(chǎn)生于Ck-1的新候選者; /后半階段與AprioriSome算法(sun f)的后半階段相同;L=kLk;/求Lk的并集產(chǎn)生所有序列模式共一百二十九頁對于DynamicSome算法，若step設(shè)為3，在初始化階段對長度為1、2、3的序列(xli)計數(shù)。然后在前半部分對長度為6、9、12、的序列計數(shù)。若只想對長度為6、9、12、的序

29、列計數(shù)時，通過兩個長度為3的序列進(jìn)行連接運(yùn)算可得到長度為6的序列，同理，通過一個長度為6的序列與一個長度為3的序列進(jìn)行連接運(yùn)算可得到長度為9的序列，以此類推。但是，要想得到長度為3的序列，就需要長度為1及長度為2的序列，因此，就需要有初始化階段。共一百二十九頁otf_generate(Lk,Lstep,c)算法的參數(shù)分別為頻繁k-序列、頻繁step-序列和客戶序列，結(jié)果返回包含在c中的候選(hu xun)(k+step)-序列的集合。例如，step=3、k=6時，執(zhí)行X=otf_generate(Lk,Lstep,c)將L6和L3連接產(chǎn)生9-序列集合，并將其中所有包含在c中候選9-序列存放到X

30、中。共一百二十九頁otf_generate(Lk,Lstep,c)的連接方式是：如果skLk，sjLj都包含在c中且相互不重疊，則是一個候選(k+j)-序列。對于c中的每個事件(shjin)x，若xLk中序列sk=，取x.end=minxl；對于c中的每個事件y，若yLj中序列sj=，取y.start=maxyl。然后在滿足連接條件x.endy.start的情況下，將sk和sj兩個序列合并得到一個候選(k+j)-序列，所有這樣序列集合即為返回的候選X。共一百二十九頁例如，以圖6.2中的L2為例，設(shè)c=，執(zhí)行X=otf_generate(L2,L2,c)，c1對應(yīng)事件(shjin)1，c2對應(yīng)事

31、件2，c3對應(yīng)事件4。求出的長度為2的序列集X2如表6.8所示，只有序列和滿足連接條件，其結(jié)果為單個序列，即返回的候選4-序列集合X=。序列集X2x.endy.start213141324243開始(kish)與結(jié)束值 共一百二十九頁【例6.6】以表6.6的序列數(shù)據(jù)庫S1為例說明DynamicSome算法(sun f)的執(zhí)行過程，設(shè)定min_sup=2，step=2。其過程如下：客戶號客戶序列s1s2s3s4s5共一百二十九頁產(chǎn)生(chnshng)L2的過程 初始化階段：求出L2的過程(guchng)與圖6.2相同。共一百二十九頁 前半階段：k=step（2）時，由Lk與Lstep連接(lin

32、ji)，通過掃描序列數(shù)據(jù)庫S1，求得C4如表6.9所示，得到L4=。執(zhí)行k+=step，得到k=4，將C4與C2連接得到C6為空。前半階段結(jié)束。序列計數(shù)21候選(hu xun)4-序列集合C4共一百二十九頁 中間階段：k=4，執(zhí)行(zhxng)k-，得到k=3，L3未確定，L2已求出，則由L2產(chǎn)生C3。產(chǎn)生(chnshng)的C3 共一百二十九頁執(zhí)行k-，得到k=2，L2已確定，不做任何事情。執(zhí)行k-，得到k=1，L1已確定，不做任何事情。中間(zhngjin)階段結(jié)束。共一百二十九頁 后半階段：k取前半階段結(jié)束時的k值即4，執(zhí)行k-，得到k=3，由于(yuy)L3在前半部分沒有計數(shù)，則對C3

33、計數(shù)得到L3。共一百二十九頁執(zhí)行k-，得到k=2，L2已確定，從中刪除包含(bohn)在L3、L4中的序列。執(zhí)行k-，得到k=1，L1已確定，從中刪除包含在L2、L3、L4中的子序列。 最后得到的序列模式(msh)如表6.6相同。序列模式計數(shù)222共一百二十九頁6.2.4 GSP算法(sun f)1. GSP算法(sun f)描述GSP算法主要包括三個步驟：掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集合。根據(jù)長度為i的種子集合Li通過連接操作和剪枝操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計算每個候選序列模式的支持度計數(shù)，產(chǎn)生長度為i+1的序列模式Li+1

34、，并將Li+1作為新的種子集合。重復(fù)第步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。整個過程為：L1C2L2C3L3C4L4共一百二十九頁注意(zh y)：在GSP算法中，k-序列是指序列中包含k個項，這種前面的定義有所不同。每個候選序列比產(chǎn)生它的種子序列多包含一個項（序列中每個事件可能包含一個或多個項），這樣給定一次掃描中得到的所有候選序列將有相同的長度。共一百二十九頁其中，產(chǎn)生候選(hu xun)序列模式主要分兩步： 連接階段：設(shè)有種子集合Lk-1，候選序列集合Ck通過將種子集合Lk-1與Lk-1連接得到。設(shè)s1、s2分別為種子集合Lk-1中的兩個(k-1)-序列：如果去掉(q di

35、o)s1的第一個項與去掉s2的最后一個項所得到的子序列相同，則可以將s1與s2進(jìn)行連接，產(chǎn)生候選k-序列的規(guī)則是將序列s1與序列s2的末項相連，若s2的末項為x，而x恰好為s2的最后一個元素（事件項集），則將x變成s1的最后一個元素；否則，x變成s1最后一個元素的最后一項。特殊地，若k=2，即種子集合為L1，設(shè)s1=，s2=，則項y既再成為s1的最后一個項，又可成為s1的最后一個元素的最后一項，即產(chǎn)生候選2-序列x，y、。共一百二十九頁 剪枝階段：若某候選序列模式(msh)的某個子序列不是序列模式(msh)，則此候選序列模式(msh)不可能是序列模式(msh)，將它從候選序列模式(msh)中刪

36、除。頻繁3-序列候選4-序列連接后剪枝后 例如(lr) ：共一百二十九頁GSP算法(sun f)如下：輸入：找頻繁項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫S， 最小支持度閾值(y zh)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=cCk | c.sup_co

37、untmin_sup ; /生成頻繁k-序列集合LkL=kLk; /求Lk的并集產(chǎn)生所有序列模式共一百二十九頁2. 利用哈希樹計算(j sun)候選序列的支持度計數(shù)對于(duy)一組候選序列模式，構(gòu)造哈希樹的過程是：從根結(jié)點開始，用哈希函數(shù)對序列的第一個項做映射來決定從哪個分支向下，依次在第k層對序列的第k個項作映射來決定從哪個分支向下，直到到達(dá)一個葉子結(jié)點。將序列儲存在此葉子結(jié)點。初始時所有結(jié)點都是葉子結(jié)點，當(dāng)一個葉子結(jié)點所存放的序列個數(shù)達(dá)到一個閾值，它將轉(zhuǎn)化為一個內(nèi)部結(jié)點。共一百二十九頁假如，有如圖6.8所示的哈希樹，哈希函數(shù)為“模5”，哈希表的尺寸為5。一個葉子結(jié)點轉(zhuǎn)換為內(nèi)部結(jié)點的閾值為

38、3個項集。對于一個事件1，4，第一層的桶1、4需要考慮(kol)，故僅有候選項集1，2、1，4被考察。一棵哈希樹 共一百二十九頁給定序列(xli)數(shù)據(jù)庫中的一個序列(xli)s，計算候選序列的支持度計數(shù)的過程如下：對于根結(jié)點，用哈希函數(shù)對序列s的每一個單項做映射來并從相應(yīng)(xingyng)的表項向下迭代的進(jìn)行操作。對于內(nèi)部結(jié)點，如果s是通過對單個項x做哈希映射來到此結(jié)點的，則對s中每一個和x在一個元素中的單個項以及在x所在元素之后第一個元素的第一個單項做哈希映射，然后從相應(yīng)的表項向下迭代做操作。對一個葉子結(jié)點，檢查每個候選序列c是不是s的子序列。如果是，則相應(yīng)的候選序列的支持度計數(shù)增1。共一百

39、二十九頁3. 有時間約束(yush)的序列模式挖掘基于時間約束(yush)的序列模式挖掘為用戶提供了挖掘定制模式的方法。 用戶可以通過設(shè)置一些時間參數(shù)對挖掘的范圍進(jìn)行限制。常用的時間參數(shù)如下：序列長度與寬度的約束：序列的長度是指序列中事件的個數(shù)，寬度是指最長事件的長度。最小間隔的約束：指事件之間的最小時間間隔mingap。最大間隔的約束：指事件之間的最大時間間隔maxgap。時間窗口約束：指整個序列都必須發(fā)生在某個時間窗口ws內(nèi)。共一百二十九頁在考察某個數(shù)據(jù)(shj)序列S是否包含某個候選k-序列s時，需分成兩個階段：（1）向前階段在S中尋找從s的首項開始(kish)的連續(xù)子序列xixj（im

40、axgap（這里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位置不變，直至某位置元素(yun s)xj-i滿足條件或x1不能保持位置不變，此時，返回向前階段。 當(dāng)xj-i滿足time(xj-i)

41、-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，考察(koch)候選數(shù)據(jù)序列s=是否包含在該數(shù)據(jù)序列中。事件時間事件項集101，2254，6453501，2653902，4956共一百二十九頁事務(wù)(shw)項的事務(wù)(shw)時間鏈表 事務(wù)項事務(wù)時間1 10 50 NULL2

42、 10 50 90 NULL3 45 65 NULL4 25 90 NULL5 NULL6 25 95 NULL7 NULL結(jié)論：數(shù)據(jù)(shj)序列S包含候選序列s = 。共一百二十九頁GSP算法(sun f)的特點如下：如果序列數(shù)據(jù)庫的規(guī)模比較大，則有可能會產(chǎn)生大量的候選序列模式(msh)。需要對序列數(shù)據(jù)庫進(jìn)行循環(huán)掃描。對于序列模式的長度比較長的情況，由于其對應(yīng)的短的序列模式規(guī)模太大，算法很難處理。共一百二十九頁6.2.5 SPADE算法(sun f)1. SPADE算法(sun f)的相關(guān)概念SPADE是一種基于數(shù)據(jù)垂直數(shù)據(jù)格式的Aprior類算法，垂直數(shù)據(jù)分布的數(shù)據(jù)集由一系列序列標(biāo)識符、

43、事件標(biāo)識符和項集組成。 共一百二十九頁例如，表6.13所示是一個客戶交易(jioy)的垂直數(shù)據(jù)庫D，它是由相應(yīng)客戶交易數(shù)據(jù)庫轉(zhuǎn)換而來的?？蛻籼朣ID交易時間TID項集（事件） s1 10C，D s1 15A，B，C s1 20A，B，F(xiàn) s1 25A，C，D，F(xiàn) s215A，B，F(xiàn) s2 20E s310A，B，F(xiàn)s410D，G，Hs420B，F(xiàn)s425A，G，H共一百二十九頁所有的頻繁序列都可以通過(tnggu)搜索序列格的方式被挖掘出來，其基本運(yùn)算是兩個序列的組合。兩個k-序列組合的結(jié)果為(k+1)-序列的集合，它們在序列格中恰好處于這兩個k-序列的上一層，該運(yùn)算用“”表示。共一百二十九頁

44、如圖6.9中，A、B是兩個(lin )1-序列，它們的組合AB=，見圖中帶陰影的圓圈。共一百二十九頁【例6.8】假設(shè)最小支持(zhch)度閾值min_sup=2，對于表6.13所示的垂直數(shù)據(jù)庫，構(gòu)建的長度為1的序列的id-list表如表6.14所示。1-序列的id-list表L(A)中有6行，但只有4個不同的序列號SID，所以該序列的支持度計數(shù)為4。由于1-序列的支持度計數(shù)小于min_sup，表中沒有列出，因此，頻繁1-序列集合F1=，。共一百二十九頁L(A)L(B)L(D)L(F)SIDTIDSIDTIDSIDTIDSIDTIDs115s115s110s120s120s120s125s125

45、s125s215s410s215s215s310s310s310s420s420s425客戶號SID交易時間TID項集（事件）s110C，Ds115A，B，Cs120A，B，F(xiàn)s125A，C，D，F(xiàn)s215A，B，F(xiàn)s220Es310A，B，F(xiàn)s410D，G，Hs420B，F(xiàn)s425A，G，H長度(chngd)為1的序列的id-list表 共一百二十九頁定義6.7前綴形式化定義如下：定義一個函數(shù)p：(S，N)S，其中S是一個序列集合，N是一個非負(fù)整數(shù)，p(X，k)=X1:k，換句話說，p(X，k)返回X的k長度的前綴。在序列格S上定義一個等價關(guān)系如下：X，YS，當(dāng)且僅當(dāng)p(X，k)=p(Y，k

46、)，也就是說這兩個序列共享長度為k的前綴，則它們(t men)是k等價的，記為。由X構(gòu)成的等價類記為。共一百二十九頁在該序列格上由1導(dǎo)出的等價類集合是A，B，D，F(xiàn)，稱這些第一層的類為父類，在圖中下方?？梢?ky)看到，所有具有共同前綴的序列被劃分到同一等價類中，每個等價類都是序列格的一個子格。 共一百二十九頁只有同一個類中的兩個k-序列才能(cinng)進(jìn)行時態(tài)連接運(yùn)算，并產(chǎn)生長度為(k+1)的候選序列。因此，為了產(chǎn)生所有(k+1)-序列，僅需要在每個前綴等價類中執(zhí)行一個簡單的時態(tài)連接即可，而這種連接可被獨(dú)立處理。共一百二十九頁根據(jù)(gnj)被連接的原子類型，可得3種可能的頻繁序列： 兩個事

47、件原子項連接：和進(jìn)行連接得到。事件原子項與序列原子項之間連接：和進(jìn)行連接得到。序列原子項與序列原子項之間連接：與進(jìn)行連接得到、或。一個特殊的情況是，當(dāng)對進(jìn)行自連接時，則只能產(chǎn)生(chnshng)唯一的新序列。共一百二十九頁【例6.9】如圖6.11所示，給定和兩個id-list表，為了求事件原子的id-list表，需要(xyo)檢查和的所有相等（SID，TID）對，求得結(jié)果為（8，30），（8，50），（8，80）。 共一百二十九頁對于序列格S中的任何k-序列X，設(shè)X1和X2表示它的以字典順序排列的開頭兩個(k-1)-子序列，則X=X1X2，且它的支持(zhch)度計數(shù)X.sup_count=|

48、L(X1)L(X2)|，其中|X|表示序列X對應(yīng)的id-list表中不同SID的數(shù)據(jù)序列的個數(shù)。共一百二十九頁【例6.10】求序列(xli)的id-list表的過程 。 共一百二十九頁通過等價關(guān)系k將可以將每個父類遞歸分解為更小的子類，如圖6.13所示是將分解為更小的子類的過程，這產(chǎn)生(chnshng)了一個等價類的格。共一百二十九頁SPADE算法可以(ky)采用DFS或BFS方式來搜尋每一個子類。SPADE算法通過頻繁2-序列將每個子類逐個構(gòu)建出來，即將形式為或者的序列添加到前綴(qinzhu)類X中。在處理每個子類時，采用Apriori剪枝原理進(jìn)行剪枝，一旦某個子類被剪枝，就不再繼續(xù)它的處

49、理。共一百二十九頁2. 完整(wnzhng)的SPADE算法SPADE算法(sun f)的基本過程如下：把客戶交易數(shù)據(jù)庫轉(zhuǎn)化為垂直表示格式id-list表。第一次掃描產(chǎn)生1-序列模式F1。第2次掃描生成2-序列模式F2，同時構(gòu)建格，使有相同前綴項的序列在同一格內(nèi)。第3次掃描，動態(tài)連接產(chǎn)生所有的序列模式，即通過BFS或DFS在每個類中進(jìn)行搜索，枚舉所有頻繁序列。在挖掘過程中，隨著序列模式長度的增長，表越來越小，表連接的次數(shù)和候選序列的產(chǎn)生大大減小，比水平格式算法效率大大提高。共一百二十九頁在生成F2時，可以由F1得到，但id-list表的連接非常耗時，可以將垂直格式轉(zhuǎn)化(zhunhu)為水平格式

50、，這樣來高效地計算F2。之后只對id-list表進(jìn)行操作，無需掃描原數(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算法利用格理論將原始搜索空間進(jìn)行分解，除了為產(chǎn)生頻繁1-序列和2-序列而掃描原始搜索空間外，其余的操作在每個序列的id-list表上獨(dú)立(dl)執(zhí)行，這樣，在挖掘過程中，搜索空間逐漸變小。因此，SPADE對序列的數(shù)量呈現(xiàn)出線性可擴(kuò)展

51、性。共一百二十九頁6.3 模式增長框架(kun ji)的序列挖掘算法前面介紹的Apriori類算法的主要問題是產(chǎn)生大量候選集（例如，如果有100個頻繁1-序列，產(chǎn)生候選2-序列個數(shù)為100100+10099/2，前者是形如的序列個數(shù)，其中a、b位置上均可以取100個項，后者是形如的序列個數(shù)，其中a、b不能重復(fù)出現(xiàn)，且和被認(rèn)為是相同的）、多遍掃描數(shù)據(jù)庫和大易挖掘長模式序列。模式增長框架的算法基于分治的思想，迭代地將原始數(shù)據(jù)集進(jìn)行劃分，減少數(shù)據(jù)規(guī)模，不產(chǎn)生候選序列，同時在劃分的過程中動態(tài)(dngti)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元。典型的代表有FreeSpan算法和Prefix

52、Span算法。共一百二十九頁6.3.1 FreeSpan算法(sun f)FreeSpan（frequent pattern-projected sequential pattern mining，頻繁模式投影的序列模式挖掘）算法是由Jiawei Han等于2000年提出的，它利用已產(chǎn)生的頻繁集遞歸產(chǎn)生投影數(shù)據(jù)庫，然后(rnhu)在投影數(shù)據(jù)庫中增長子序列。算法不僅可以挖掘所有序列模式，還減少了產(chǎn)生候選序列所需開銷，提高算法效率。共一百二十九頁FreeSpan算法執(zhí)行的過程(guchng)如下： （1）對于給定的序列數(shù)據(jù)庫S及最小支持度閾值min_sup，首先掃描S，找到S中所有頻繁項的集合，并

53、以降序排列生成頻繁項表即f-list表，設(shè)f-list=（x1，x2，xn）。（2）將S中所有的序列模式(msh)集合可以劃分成n個互不重疊的子集，即根據(jù)生成的f-list表把序列數(shù)據(jù)庫S分成幾個不相交的子集即i投影數(shù)據(jù)庫：只包含項x1的序列模式集合。包含項x2，但不包含（x3，xn）中項的序列模式集合。包含項x3，但不包含（x4，xn）中項的序列模式集合。包含項xn-1，但不包含項xn的序列模式集合。包含項xn的序列模式集合。共一百二十九頁（3）在投影(tuyng)數(shù)據(jù)庫中通過掃描找出頻繁2-序列集合，對于其中的每個頻繁2-序列，再次掃描投影數(shù)據(jù)庫生成該頻繁2-序列的投影數(shù)據(jù)庫，從中找出頻繁

54、3-序列集合，依此類推，直到某個投影數(shù)據(jù)庫中找不到更長的序列為止。共一百二十九頁【例6.11】給定如表6.16所示的序列數(shù)據(jù)庫S，全局(qunj)項集I=a，b，c，d，e，f，g（本節(jié)中序列采用簡寫方式，如序列是的簡寫形式，本節(jié)用小括號代替大括號表示，如果一個事件只有單個項，則省略括號）。假設(shè)最小支持度閾值min_sup為2。下面給出用FreeSpan算法求序列模式的過程。SID序列序列的項集10a，b，c，d，f20a，b，c，d，e30a，b，c，d，e，f40a，b，c，e，f，g共一百二十九頁第一次掃描(somio)序列數(shù)據(jù)庫，找出所有的頻繁項，并將這些頻繁項按支持度遞減排序構(gòu)成一個

55、頻繁項表，即：f-list= f-list=（a:4，b:4，c:4，d:3，e:3，f:3）這樣生成6個長度為1的頻繁序列：:4，:4，:4，:3，:3，:3，其中“:計數(shù)”表示模式和它的支持度計數(shù)。共一百二十九頁然后(rnhu)將序列數(shù)據(jù)庫按投影操作劃分成6個互不重疊的子數(shù)據(jù)庫。投影數(shù)據(jù)庫是由那些包含且不包含任何非頻繁項，也不包含在f-list表中居于之后項的序列所組成的數(shù)據(jù)庫。例如，對于頻繁項e，初始時投影數(shù)據(jù)庫為空，掃描序列數(shù)據(jù)庫S，第1個序列中不含有e，不予考慮；第2個序列含有e，從中刪除所有f項得到，將其加入到投影數(shù)據(jù)庫中；第3個序列含有e，從中刪除所有f項得到，將其加入到投影數(shù)據(jù)

56、庫中；第4個序列含有e，從中刪除所有f項和不頻繁項g得到，將其加入到投影數(shù)據(jù)庫中。共一百二十九頁得到(d do)的6個投影數(shù)據(jù)庫及其序列如表6.17所示。 子數(shù)據(jù)庫包含的序列子數(shù)據(jù)庫包含的序列僅包含a的包含d但不包含ef包含b但不包含cf包含e但不包含f包含c但不包含df包含f共一百二十九頁挖掘每個投影(tuyng)數(shù)據(jù)庫的過程如下：（1）挖掘僅包含a的序列模式通過挖掘投影數(shù)據(jù)庫即，其中:2是頻繁的，將其保留，即得到(d do)一個頻繁2-序列，而包含的其他序列都是非頻繁的，因此該過程結(jié)束。也就是說，僅含有項a而不含其他任何項的頻繁模式子集為，。共一百二十九頁（2）挖掘(wju)包含b但不包含

57、cf的序列模式即挖掘投影數(shù)據(jù)庫即，其過程如下： 掃描(somio)投影數(shù)據(jù)庫，挖掘出長度為2的頻繁序列，共產(chǎn)生3個長度為2的的頻繁序列，即:4，:2，:2（:2也是其頻繁2-序列，由于前面已挖掘出來，這里不再考慮）。 處理:4序列模式：掃描投影數(shù)據(jù)庫生成投影數(shù)據(jù)庫，得到的投影數(shù)據(jù)庫為，并以此生成長度為3的序列模式，即得到結(jié)果為:2。掃描投影數(shù)據(jù)庫生成投影數(shù)據(jù)庫為，沒有發(fā)現(xiàn)任何長度為4的序列模式。共一百二十九頁 處理:2序列(xli)模式：掃描投影數(shù)據(jù)庫生成投影數(shù)據(jù)庫，得到的投影數(shù)據(jù)庫為，并以此生成長度為3的序列模式，即得到結(jié)果為:2。該頻繁模式前面已考慮，不再繼續(xù)。 處理:2序列模式：掃描投影

58、數(shù)據(jù)庫生成投影數(shù)據(jù)庫，得到的投影數(shù)據(jù)庫為，沒有發(fā)現(xiàn)任何長度為3的序列模式。這樣，挖掘包含b但不包含cf的序列模式時，共產(chǎn)生4個頻繁模式:4，:2，:2，:2。共一百二十九頁（3）挖掘包含c但不包含df的序列模式即挖掘投影(tuyng)數(shù)據(jù)庫即，其過程如下： 掃描投影數(shù)據(jù)庫，挖掘出長度為2的頻繁(pnfn)序列，結(jié)果為:4，2，:3，:3,:2，:3（前面已求過的頻繁模式不再考慮）。共一百二十九頁 處理:4序列模式：掃貓投影數(shù)據(jù)庫生成(shn chn)投影數(shù)據(jù)庫，得到的投影數(shù)據(jù)庫為，并以此生成長度為3的序列模式，即得到結(jié)果為:3，:3，:2，:2，:2。 處理:3序列模式：掃描投影數(shù)據(jù)庫得到投影

59、數(shù)據(jù)庫，得到的結(jié)果為，此時發(fā)現(xiàn)找不到長度為4的序列模式，這一過程結(jié)束。類似的，其他3-序列的投影數(shù)據(jù)庫中也沒有長度為4的序列模式。這樣投影數(shù)據(jù)庫的挖掘過程結(jié)束。其他頻繁模式的挖掘過程與此類似。共一百二十九頁FreeSpan算法分析：它將頻繁序列和頻繁模式(msh)的挖掘統(tǒng)一起來，把挖掘工作限制在投影數(shù)據(jù)庫中，還能限制序列分片的增長。它能有效地發(fā)現(xiàn)完整的序列模式(msh)，同時大大減少產(chǎn)生候選序列所需的開銷，比GSP算法快很多。不足之處是可能會產(chǎn)生許多投影數(shù)據(jù)庫，如果一個模式在數(shù)據(jù)庫中的每個序列中出現(xiàn)，該模式的投影數(shù)據(jù)庫將不會縮減；另外，一個長度為k的序列可能在任何位置增長，那么長度為k+1的候

60、選序列必須對每個可能的組合情況進(jìn)行考察，這樣所需的開銷是比較大的。共一百二十九頁6.3.2 PrefixSpan算法(sun f)PrefixSpan算法(sun f)和FreeSpan算法(sun f)一樣，也是采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘。但PrefixSpan算法克服FreeSpan算法中序列模式在任何位置增長問題，它只基于頻繁前綴投影，確保序列向后增長，同時也縮減投影數(shù)據(jù)庫的大小。共一百二十九頁定義6.8 設(shè)序列中每個事件中的項按字典順序排列。給定(i dn)序列=（其中ei對應(yīng)序列數(shù)據(jù)庫S中的一個頻繁事件），=（mn