【正文】 列： itemset(T1), itemset(T2),…, itemset(Tn) 。73 挖掘序列模式? 如果一個(gè)序列 s包含于一個(gè)客戶序列中，則我們稱該客戶支持（ support）序列 s。? 一個(gè)具體序列的支持（ support）定義為那一部分支持該序列的客戶總數(shù)。? 給定一個(gè)客戶交易組成的數(shù)據(jù)庫 D，挖掘序列模式的問題就是在那些具有客戶指定最小支持度（ minimum support）的序列中找出最大序列。而每個(gè)這樣的最大序列就代表了一個(gè)序列模式（ sequence pattern）。74 挖掘序列模式? 實(shí)現(xiàn)算法可以分五個(gè)具體階段來找出所有的序列模式，分別是排序階段、大項(xiàng)集階段、轉(zhuǎn)換階段、序列階段以及最大值階段。? 序列模式分析規(guī)則挖掘的重點(diǎn)在于分析數(shù)據(jù)間的前后（因果）關(guān)系，可以發(fā)現(xiàn)客戶潛在的購(gòu)物模式，規(guī)則是 “先購(gòu)買了商品 X的顧客后購(gòu)買產(chǎn)品 Y”，置信度和支持度由決策者輸入。? 序列模式挖掘是基于時(shí)間或者其他序列的經(jīng)常發(fā)生的模式。? 應(yīng)用領(lǐng)域：客戶購(gòu)買行為模式預(yù)測(cè)、 Web訪問模式預(yù)測(cè)、疾病診斷、自然災(zāi)害診斷、 DNA序列分析。75 挖掘序列模式? 序列模式挖掘的很多參數(shù)對(duì)挖掘的結(jié)果有很大影響。1）時(shí)間序列 T的持續(xù)時(shí)間，即這個(gè)時(shí)間序列的有效時(shí)間或者是用戶選擇的一個(gè)時(shí)間段。2）時(shí)間折疊窗口 W。在一段時(shí)間內(nèi)發(fā)生的幾件事件可以被看作是同時(shí)發(fā)生的。3）時(shí)間間隔 int，這個(gè)參數(shù)表示發(fā)現(xiàn)的模式的時(shí)間間隔。? int=0? min_inervalintmax_interval? int=c76 挖掘序列模式（ 2）序列模式挖掘的主要算法GSP算法： 類似于 Apriori算法。PrefixSpan算法： 采用分而治之的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個(gè)更小的投影數(shù)據(jù)庫，然后在各個(gè)投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘。77 挖掘序列模式? 上述算法存在的主要問題：167。 缺少時(shí)間限制 ：用戶可能需要指定序列模式的相鄰元素之間的時(shí)間間隔。例如，一個(gè)序列模式可能會(huì)發(fā)現(xiàn)客戶在購(gòu)買了物品 A后的第三年購(gòu)買物品 B。我們需要的卻是給定時(shí)間間隔內(nèi)用戶的購(gòu)買意向。167。 事務(wù)的定義過于嚴(yán)格 ：一個(gè)事務(wù)中包含在客戶的一次購(gòu)買行為中所購(gòu)買的所有物品?？赡苄枰付ㄒ粋€(gè)滑動(dòng)時(shí)間窗口，客戶在滑動(dòng)時(shí)間窗口的時(shí)間段內(nèi)的所有的購(gòu)買行為均作為一個(gè)事務(wù)。167。 缺少分類層次 ：只能在項(xiàng)目的原始級(jí)別上進(jìn)行挖掘。78 挖掘序列模式（ 2）序列模式挖掘的主要算法1） GSP算法? 掃描序列數(shù)據(jù)庫，得到長(zhǎng)度為 l的序列模式 L1，作為初始的種子集。? 掃描長(zhǎng)度為 i的種子集 Li ，通過連接操作和剪切操作生成長(zhǎng)度為 i+1的候選序列模式 Ci+1；然后掃描序列數(shù)據(jù)庫，計(jì)算每個(gè)候選序列模式的支持?jǐn)?shù)，產(chǎn)生長(zhǎng)度為 i+1的序列模式Li+1，并將 Li+1作為新的種子集。? 重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。L1? C2 ? L2 ? C3 ? L3 ? C4 ? L4 ? ……79 挖掘序列模式? 產(chǎn)生候選序列模式主要分為兩步：? 連接階段：如果去掉序列模式 s1的第一個(gè)項(xiàng)目與去掉序列模式 s2的最后一個(gè)項(xiàng)目所得到的序列相同，則可以將 s1與 s2進(jìn)行連接，即將 s2的最后一個(gè)項(xiàng)目添加到 s1中。? 剪切階段：若某候選序列模式的某個(gè)子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。80 挖掘序列模式? 例：下圖演示了如何從長(zhǎng)度為 3的序列模式產(chǎn)生長(zhǎng)度為 4的候選序列模式。Sequential patternsWith length 3Candidate 4SequencesAfter Join After Pruning(1,2) 3 (1,2) (3,4) (1,2) (3,4)(1,2) 4 (1,2) 3 51 (3,4)(1,3) 52 (3,4)2 3 581 挖掘序列模式? 候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合 C，掃描序列數(shù)據(jù)庫，對(duì)于其中的每一條序列 d，找出集合 C中被 d所包含的所有候選序列模式，并增加其支持度計(jì)數(shù)。? GSP算法存在的主要問題：? 1）如果序列數(shù)據(jù)庫的規(guī)模較大，則有可能會(huì)產(chǎn)生大量的候選序列模式；? 2）需要對(duì)序列數(shù)據(jù)庫進(jìn)行循環(huán)掃描；? 3）對(duì)于序列模式的長(zhǎng)度比較長(zhǎng)的情況，由于其對(duì)應(yīng)的短的序列模式規(guī)模太大，本算法很難處理。82 挖掘序列模式2） PrefixSpan算法（基于前綴投影的序列模式挖掘算法）? 相關(guān)定義如下：? 前綴。設(shè)每個(gè)元素中的所有項(xiàng)目按照字典序排列。給定序列 ? =(a1,a2,…,a n) ， ? (m≤n)，如果則稱 ?是 ?的前綴。83 挖掘序列模式? 投影。給定序列 ?和 ?，如果 ?是 ?的子序列，則 ?關(guān)于 ?的投影 ?’必需滿足： ?是 ?’的前綴， ?’是 ?的滿足上述條件的最大子序列。? 后綴。序列 ?關(guān)于子序列 ?的投影 ?’(n≥m)，則序列 ?關(guān)于子序列 ?的后綴為84 挖掘序列模式? 算法描述：? 掃描序列數(shù)據(jù)庫，生成所有長(zhǎng)度為 l的序列模式。? 根據(jù)長(zhǎng)度 l的序列模式，生成相應(yīng)的投影數(shù)據(jù)庫。? 在相應(yīng)的投影數(shù)據(jù)庫上重復(fù)上述步驟，直到在相應(yīng)的投影數(shù)據(jù)庫上不能產(chǎn)生長(zhǎng)度為 l的序列模式為止。? 投影數(shù)據(jù)庫：設(shè) ?為序列數(shù)據(jù)庫 S中的一個(gè)序列模式，則 ?的投影數(shù)據(jù)庫為 S中所有以 ?為前綴的序列相對(duì)于 ?的后綴，記為 S| ? 。? 投影數(shù)據(jù)庫中的支持?jǐn)?shù)：設(shè) ?為序列數(shù)據(jù)庫 S中的一個(gè)序列模式，序列 ?以 ?為前綴，則 ?在 ?投影數(shù)據(jù)庫 S中支持?jǐn)?shù)為S| ?滿足條件 ? ? ?.?的序列 ?的個(gè)數(shù)。85 挖掘序列模式? PrefixSpan算法167。 輸入：序列數(shù)據(jù)庫 S及最小支持度閾值 min_sup167。 輸出：所有的序列模式167。 方法：調(diào)用子程序 PrefixSpan(() 0, S)86 挖掘序列模式? 子程序 PrefixSpan(?, L, S|?)167。 參數(shù)： ? 為一個(gè)序列模式 ； L為序列模式 ?的長(zhǎng)度； S|?如果 ?為空，則為 S，否則為 ?的投影數(shù)據(jù)庫。216。掃描 S|?，找到滿足下述要求的長(zhǎng)度為 1的序列模式 b：?b可以添加到 ?的最后一個(gè)元素中并為序列模式?b可以作為 ?的最后一個(gè)元素并為序列模式216。對(duì)每個(gè)生成的序列模式 b，將 b添加到 ?形成序列模式 ?’，并輸出 ?’216。對(duì)每個(gè) ?’,構(gòu)造 ?’的投影數(shù)據(jù)庫 S|?’ ,并調(diào)用子程序PrefixSpan(?’, L + 1, S|?’)87 挖掘序列模式? PrefixSpan算法分析：167。 PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間167。 相對(duì)于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小167。 PrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造88 挖掘序列模式? PrefixSpan算法的主要改進(jìn)：167。 逐層投影 ：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫的個(gè)數(shù)167。 偽投影 ：當(dāng)序列數(shù)據(jù)庫可以直接放入內(nèi)存時(shí)，可以使用偽投影操作代替實(shí)際的投影數(shù)據(jù)庫，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫的