第6章 序列模式挖掘

1、第6章 序列(xli)模式挖掘序列數(shù)據(jù)(shj)是由有序元素或事件的序列組成的，可以不包括具體的時(shí)間概念，序列數(shù)據(jù)的例子有客戶購(gòu)物序列、Web點(diǎn)擊流和生物學(xué)序列等。這類數(shù)據(jù)處理的不是一個(gè)時(shí)間點(diǎn)上的數(shù)據(jù)，而是大量時(shí)間點(diǎn)上的數(shù)據(jù)，因而具有自身的特殊性。 共一百二十九頁(yè)6.1 序列(xli)模式挖掘概述6.1.1 序列(xli)數(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è)客戶在特定商店的一次購(gòu)物，一次購(gòu)物可以購(gòu)買多種商品，所以事件表示為（x1，x2，xq），其

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

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

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

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

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

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

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

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

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

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

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

13、k-1生成候選k-序列Ck的過(guò)程(guchng)說(shuō)明如下：（1）連接(linji)對(duì)于Lk-1中任意兩個(gè)序列s1和s2，如果s1與s2的前k-2項(xiàng)相同，即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共一百二十九頁(yè)（2）剪枝(jin

14、zh)剪枝的原則：一個(gè)候選k-序列，如果它的(k-1)-序列有一個(gè)是非頻繁的，則刪除它。由Ck剪枝產(chǎn)生Lk的過(guò)程(guchng)如下：for (所有cCk的序列)for (所有c的(k-1)-序列s)if (s不屬于Lk-1) 從Ck中刪除c;Ck Lk;/由Ck剪枝后得到Lk共一百二十九頁(yè)【例6.3】以表6.6所示的序列數(shù)據(jù)庫(kù)S1為例，給出ApriorAll算法的執(zhí)行過(guò)程，這里I=1，2，3，4，5，每個(gè)數(shù)字表示(biosh)一個(gè)項(xiàng)。假設(shè)min_sup=2?？蛻籼?hào)客戶序列s1s2s3s4s5一個(gè)(y )序列數(shù)據(jù)庫(kù)S1 共一百二十九頁(yè) 先求出L1，由其產(chǎn)生L2的過(guò)程如圖6.2所示，實(shí)際上這個(gè)過(guò)

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

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

17、)它的2-子序列、和1-子序列，剩下的2-序列是最大序列。到此，L中已沒(méi)有可以再刪除的子序列了，得到的序列模式如下表所示。序列模式計(jì)數(shù)222共一百二十九頁(yè)當(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方法：其過(guò)程描述如下：R=;for (對(duì)于L中每個(gè)頻繁序列)for (對(duì)于的每個(gè)子序列)conf=.sup_count/.sup_count;if (confmin_conf)R=R;/產(chǎn)生一條新規(guī)則r

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

19、二十九頁(yè)AprioriSome算法(sun f)描述如下：輸入：找頻繁項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)S，最小支持度閾值min_sup輸出：序列模式集合(jh)L方法：其過(guò)程描述如下：/前推階段（前半階段）L1=頻繁1-序列; C1=L1;last=1;/計(jì)數(shù)的序列長(zhǎng)度f(wàn)or (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 (對(duì)于序列數(shù)據(jù)庫(kù)S中的每一個(gè)客戶序列c) 所有在Ck中包含在c中的候選者的計(jì)數(shù)增1;Lk=

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

21、的序列則在回溯階段中計(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)=100k時(shí)，這時(shí)幾乎所有的子序列都不被計(jì)算，但候選序列數(shù)卻大大增加。共一百二十九頁(yè)下面給出按經(jīng)驗(yàn)(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;在掃描開(kāi)始階段，hitk較大，也就是說(shuō)候選序列較少，將k設(shè)置(shzh)為較大的值，可以減少對(duì)子序列的計(jì)數(shù)。在以后掃描過(guò)程中，hitk越來(lái)越小，將k設(shè)置為較小的值，可以減少候選序列數(shù)。共一百二十九頁(yè)【例6.5】以表6.6的序列數(shù)據(jù)庫(kù)S1為例，給出AprioriSome算法的執(zhí)行過(guò)程(guchng)，設(shè)定min_sup=2。假設(shè)前推階段只計(jì)算長(zhǎng)度k為1、2、4、6、的序列(xli)（即n

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

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

25、一百二十九頁(yè) 當(dāng)k=2循環(huán)時(shí)，L2已求出，刪除L2中包含(bohn)在L3和L4中的子序列， 只剩下。 當(dāng)k=1循環(huán)時(shí)，L1中的所作序列都已被刪除。最后得到的序列模式(msh)如表6.6相同。序列模式計(jì)數(shù)222共一百二十九頁(yè)AprioriSome和AprioriAll比較(bjio)有以下幾個(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)存滿了，

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

27、rioriAll、AprioriSome 那樣計(jì)數(shù)后就進(jìn)行剪枝，因此在支持度較小時(shí)，會(huì)產(chǎn)生大量的候選序列。 共一百二十九頁(yè)DynamicSome算法(sun f)主要特點(diǎn)如下： 由變量step來(lái)決定要計(jì)數(shù)的候選序列。在初始化階段(jidun)，所有達(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ù)。共一百二十九頁(yè)DynamicSome算法(sun f)描述如下：輸入：找頻繁項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)S，

28、最小支持度閾值min_sup輸出：序列模式(msh)集合L方法：其過(guò)程描述如下：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)生所有序列模式共一百二十九頁(yè)對(duì)于DynamicSome算法，若step設(shè)為3，在初始化階段對(duì)長(zhǎng)度為1、2、3的序列(xli)計(jì)數(shù)。然后在前半部分對(duì)長(zhǎng)度為6、9、12、的序列計(jì)數(shù)。若只想對(duì)長(zhǎng)度為6、9、12、的序

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

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

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

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

33、計(jì)數(shù)得到L3。共一百二十九頁(yè)執(zhí)行k-，得到k=2，L2已確定，從中刪除包含(bohn)在L3、L4中的序列。執(zhí)行k-，得到k=1，L1已確定，從中刪除包含在L2、L3、L4中的子序列。 最后得到的序列模式(msh)如表6.6相同。序列模式計(jì)數(shù)222共一百二十九頁(yè)6.2.4 GSP算法(sun f)1. GSP算法(sun f)描述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

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

35、o)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=，s2=，則項(xiàng)y既再成為s1的最后一個(gè)項(xiàng)，又可成為s1的最后一個(gè)元素的最后一項(xiàng)，即產(chǎn)生候選2-序列x，y、。共一百二十九頁(yè) 剪枝階段：若某候選序列模式(msh)的某個(gè)子序列不是序列模式(msh)，則此候選序列模式(msh)不可能是序列模式(msh)，將它從候選序列模式(msh)中刪

36、除。頻繁3-序列候選4-序列連接后剪枝后 例如(lr) ：共一百二十九頁(yè)GSP算法(sun f)如下：輸入：找頻繁項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)S， 最小支持度閾值(y zh)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è)客戶序列c) /掃描序列數(shù)據(jù)庫(kù)S被包含于c中的Ck內(nèi)的所有候選者的計(jì)數(shù)增1; Lk=cCk | c.sup_co

37、untmin_sup ; /生成頻繁k-序列集合LkL=kLk; /求Lk的并集產(chǎn)生所有序列模式共一百二十九頁(yè)2. 利用哈希樹(shù)計(jì)算(j sun)候選序列的支持度計(jì)數(shù)對(duì)于(duy)一組候選序列模式，構(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)。共一百二十九頁(yè)假如，有如圖6.8所示的哈希樹(shù)，哈希函數(shù)為“模5”，哈希表的尺寸為5。一個(gè)葉子結(jié)點(diǎn)轉(zhuǎn)換為內(nèi)部結(jié)點(diǎn)的閾值為

38、3個(gè)項(xiàng)集。對(duì)于一個(gè)事件1，4，第一層的桶1、4需要考慮(kol)，故僅有候選項(xiàng)集1，2、1，4被考察。一棵哈希樹(shù) 共一百二十九頁(yè)給定序列(xli)數(shù)據(jù)庫(kù)中的一個(gè)序列(xli)s，計(jì)算候選序列的支持度計(jì)數(shù)的過(guò)程如下：對(duì)于根結(jié)點(diǎn)，用哈希函數(shù)對(duì)序列s的每一個(gè)單項(xiàng)做映射來(lái)并從相應(yīng)(xingyng)的表項(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。共一百

39、二十九頁(yè)3. 有時(shí)間約束(yush)的序列模式挖掘基于時(shí)間約束(yush)的序列模式挖掘?yàn)橛脩籼峁┝送诰蚨ㄖ颇Ｊ降姆椒ā?用戶可以通過(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)。共一百二十九頁(yè)在考察某個(gè)數(shù)據(jù)(shj)序列S是否包含某個(gè)候選k-序列s時(shí)，需分成兩個(gè)階段：（1）向前階段在S中尋找從s的首項(xiàng)開(kāi)始(kish)的連續(xù)子序列xixj（im

40、axgap（這里time(x)表示事件x的交易時(shí)間），此時(shí)轉(zhuǎn)入向后階段，否則，如在S中不能找到s的某個(gè)元素，則s不是S的子序列。共一百二十九頁(yè)（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位置不變，直至某位置元素(yun s)xj-i滿足條件或x1不能保持位置不變，此時(shí)，返回向前階段。 當(dāng)xj-i滿足time(xj-i)

41、-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ù)元素。共一百二十九頁(yè)【例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，考察(koch)候選數(shù)據(jù)序列s=是否包含在該數(shù)據(jù)序列中。事件時(shí)間事件項(xiàng)集101，2254，6453501，2653902，4956共一百二十九頁(yè)事務(wù)(shw)項(xiàng)的事務(wù)(shw)時(shí)間鏈表 事務(wù)項(xiàng)事務(wù)時(shí)間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 = 。共一百二十九頁(yè)GSP算法(sun f)的特點(diǎn)如下：如果序列數(shù)據(jù)庫(kù)的規(guī)模比較大，則有可能會(huì)產(chǎn)生大量的候選序列模式(msh)。需要對(duì)序列數(shù)據(jù)庫(kù)進(jìn)行循環(huán)掃描。對(duì)于序列模式的長(zhǎng)度比較長(zhǎng)的情況，由于其對(duì)應(yīng)的短的序列模式規(guī)模太大，算法很難處理。共一百二十九頁(yè)6.2.5 SPADE算法(sun f)1. SPADE算法(sun f)的相關(guān)概念SPADE是一種基于數(shù)據(jù)垂直數(shù)據(jù)格式的Aprior類算法，垂直數(shù)據(jù)分布的數(shù)據(jù)集由一系列序列標(biāo)識(shí)符、

43、事件標(biāo)識(shí)符和項(xiàng)集組成。 共一百二十九頁(yè)例如，表6.13所示是一個(gè)客戶交易(jioy)的垂直數(shù)據(jù)庫(kù)D，它是由相應(yīng)客戶交易數(shù)據(jù)庫(kù)轉(zhuǎn)換而來(lái)的?？蛻籼?hào)SID交易時(shí)間TID項(xiàng)集（事件） 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共一百二十九頁(yè)所有的頻繁序列都可以通過(guò)(tnggu)搜索序列格的方式被挖掘出來(lái)，其基本運(yùn)算是兩個(gè)序列的組合。兩個(gè)k-序列組合的結(jié)果為(k+1)-序列的集合，它們?cè)谛蛄懈裰星『锰幱谶@兩個(gè)k-序列的上一層，該運(yùn)算用“”表示。共一百二十九頁(yè)

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

45、s125s215s410s215s215s310s310s310s420s420s425客戶號(hào)SID交易時(shí)間TID項(xiàng)集（事件）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長(zhǎng)度(chngd)為1的序列的id-list表 共一百二十九頁(yè)定義6.7前綴形式化定義如下：定義一個(gè)函數(shù)p：(S，N)S，其中S是一個(gè)序列集合，N是一個(gè)非負(fù)整數(shù)，p(X，k)=X1:k，換句話說(shuō)，p(X，k)返回X的k長(zhǎng)度的前綴。在序列格S上定義一個(gè)等價(jià)關(guān)系如下：X，YS，當(dāng)且僅當(dāng)p(X，k)=p(Y，k

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

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

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

49、理。共一百二十九頁(yè)2. 完整(wnzhng)的SPADE算法SPADE算法(sun f)的基本過(guò)程如下：把客戶交易數(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è)類中進(jìn)行搜索，枚舉所有頻繁序列。在挖掘過(guò)程中，隨著序列模式長(zhǎng)度的增長(zhǎng)，表越來(lái)越小，表連接的次數(shù)和候選序列的產(chǎn)生大大減小，比水平格式算法效率大大提高。共一百二十九頁(yè)在生成F2時(shí)，可以由F1得到，但id-list表的連接非常耗時(shí)，可以將垂直格式轉(zhuǎn)化(zhunhu)為水平格式

50、，這樣來(lái)高效地計(jì)算F2。之后只對(duì)id-list表進(jìn)行操作，無(wú)需掃描原數(shù)據(jù)庫(kù)。因此該算法產(chǎn)生序列模式時(shí)只需要3次掃描數(shù)據(jù)庫(kù)。共一百二十九頁(yè)實(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ú)立(dl)執(zhí)行，這樣，在挖掘過(guò)程中，搜索空間逐漸變小。因此，SPADE對(duì)序列的數(shù)量呈現(xiàn)出線性可擴(kuò)展

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

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

53、以降序排列生成頻繁項(xiàng)表即f-list表，設(shè)f-list=（x1，x2，xn）。（2）將S中所有的序列模式(msh)集合可以劃分成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的序列模式集合。共一百二十九頁(yè)（3）在投影(tuyng)數(shù)據(jù)庫(kù)中通過(guò)掃描找出頻繁2-序列集合，對(duì)于其中的每個(gè)頻繁2-序列，再次掃描投影數(shù)據(jù)庫(kù)生成該頻繁2-序列的投影數(shù)據(jù)庫(kù)，從中找出頻繁

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

55、頻繁項(xiàng)表，即：f-list= f-list=（a:4，b:4，c:4，d:3，e:3，f:3）這樣生成6個(gè)長(zhǎng)度為1的頻繁序列：:4，:4，:4，:3，:3，:3，其中“:計(jì)數(shù)”表示模式和它的支持度計(jì)數(shù)。共一百二十九頁(yè)然后(rnhu)將序列數(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í)投影數(shù)據(jù)庫(kù)為空，掃描序列數(shù)據(jù)庫(kù)S，第1個(gè)序列中不含有e，不予考慮；第2個(gè)序列含有e，從中刪除所有f項(xiàng)得到，將其加入到投影數(shù)據(jù)庫(kù)中；第3個(gè)序列含有e，從中刪除所有f項(xiàng)得到，將其加入到投影數(shù)據(jù)

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

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

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

59、數(shù)據(jù)庫(kù)，得到的結(jié)果為，此時(shí)發(fā)現(xiàn)找不到長(zhǎng)度為4的序列模式，這一過(guò)程結(jié)束。類似的，其他3-序列的投影數(shù)據(jù)庫(kù)中也沒(méi)有長(zhǎng)度為4的序列模式。這樣投影數(shù)據(jù)庫(kù)的挖掘過(guò)程結(jié)束。其他頻繁模式的挖掘過(guò)程與此類似。共一百二十九頁(yè)FreeSpan算法分析：它將頻繁序列和頻繁模式(msh)的挖掘統(tǒng)一起來(lái)，把挖掘工作限制在投影數(shù)據(jù)庫(kù)中，還能限制序列分片的增長(zhǎng)。它能有效地發(fā)現(xiàn)完整的序列模式(msh)，同時(shí)大大減少產(chǎn)生候選序列所需的開(kāi)銷，比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的候

60、選序列必須對(duì)每個(gè)可能的組合情況進(jìn)行考察，這樣所需的開(kāi)銷是比較大的。共一百二十九頁(yè)6.3.2 PrefixSpan算法(sun f)PrefixSpan算法(sun f)和FreeSpan算法(sun f)一樣，也是采用分治的思想，不斷產(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ù)的大小。共一百二十九頁(yè)定義6.8 設(shè)序列中每個(gè)事件中的項(xiàng)按字典順序排列。給定(i dn)序列=（其中ei對(duì)應(yīng)序列數(shù)據(jù)庫(kù)S中的一個(gè)頻繁事件），=（mn