序列模式挖掘綜述

1、序 列,報告人：熊 赟,,內(nèi)容概要,基本概念,其他,類Apriori生成候選算法,相似性搜索,FreeSpan算法,PrefixSpan算法,,第6章 序 列,6.1 基本概念6.2 原 理6.3 核心算法6.4 其 他,,序列是不同項集的有序排列。 定義1(序列)：I=｛i1i2…im｝是項集，ik（1，其中sj（1<=j<=n）為項集（也稱序列S的元素），即sj?I

2、。每個元素由不同項組成。序列的元素可表示為（i1i2…ik），若一個序列只有一個項，則括號可以省略。 序列包含的所有項的個數(shù)稱為序列的長度。長度為l 的序列記為l -序列。,序 列,,定義2(子序列)：序列T＝是另一個序列S＝的子序列，滿足下面條件：對于每一個j，1<=j<=m-1，有ij<ij+1 且 對于每一個j，1<=j<=m，存在1<=k<=n，使得tij?sk。即序列S包含序

3、列T。用符號“?”表示“被包含于”，序列T是序列S的子序列可記為T?S。稱T為S的子序列，S為T的超序列。若一個序列S不包含在任何其他的序列之中，則稱序列S是最大的。,子 序 列,,定義3（支持度）：序列數(shù)據(jù)庫D是元組的集合，sid為序列標識號，如果序列T是S的子序列（即T?S）稱元組包含序列T；則序列T在序列數(shù)據(jù)庫D中的支持度是數(shù)據(jù)庫中包含T的元組數(shù)，即supportD(T)＝|{|?D?T?S }|記作support（T）。,

4、序列支持度,,定義4（頻繁序列模式）：給定正整數(shù)?為支持度閾值，如果數(shù)據(jù)庫中最少有?個元組包含序列S，即support（S）>=?，則稱序列S為序列數(shù)據(jù)庫D中的一個（頻繁）序列模式。長度為l 的序列模式稱為l –模式。 序列模式挖掘的任務就是找出數(shù)據(jù)庫中所有的序列模式，即那些在序列集合中出現(xiàn)頻率超過最小支持度（用戶指定最小支持度閾值）的子序列。,頻繁序列模式,,定義5: （序列關(guān)聯(lián)規(guī)則）對于給定的項集I=｛i1i2…im｝以

5、及序列S,T，形如S?T的表達式稱為序列關(guān)聯(lián)規(guī)則。,序列關(guān)聯(lián)規(guī)則,,置信度,支持度,序列關(guān)聯(lián)規(guī)則,序列關(guān)聯(lián)規(guī)則S?T的支持度是支持序列S和T的顧客數(shù)占總顧客數(shù)之比。,序列關(guān)聯(lián)規(guī)則S?T的置信度記為（?），是支持序列S和T的顧客數(shù)與僅支持S的顧客數(shù)之比。,,,,,序列模式挖掘階段,排序階段 發(fā)現(xiàn)頻繁項集階段 轉(zhuǎn)換階段 序列階段 最大階段,由客戶標識及交易發(fā)生的時間為關(guān)鍵字所排序的數(shù)據(jù)庫,排序階段,客戶序列描述數(shù)據(jù)庫,頻繁

6、項集分別是(C)、(D)、(G)、(D,G)和(H),發(fā)現(xiàn)頻繁項集階段,轉(zhuǎn)換后的數(shù)據(jù)庫（客戶序列）,轉(zhuǎn)換階段,核心算法,,AprioriAll, AprioriSome算法 FreeSpan，PrefixSpan算法,序列階段 最大階段,,,AprioriAll算法,基本思想,,,AprioriAll算法,AprioriAll算法,,L1,L2,AprioriAll算法,,L3,L4,AprioriAll算法,,最大的頻繁序列

7、,AprioriSome算法,,基本思想： 算法分為兩個階段： 前階段：只對一定長度的序列計數(shù) －－next（k）函數(shù) 即Ck生成Lk 后階段： 對前階段已確定的Lk確定為最大序列 對前階段沒有生成Lk，先刪除所有在Ck中包含在Li中的序列，再對Ck計數(shù)生成Lk。,AprioriSome算法,,L1,L2,next(last)=2k,AprioriSome算法,,C3,C4,修剪,AprioriSome算法,,C

8、5為空結(jié)束前階段進入回溯階段,刪除了L4的子序列后的C3再計數(shù)發(fā)現(xiàn)是最大3序列,L4,AprioriSome算法,,最大的頻繁序列,除以外L2中所有的序列都被刪除 L1中所有的序列都被刪除,類Apriori算法有以下缺點：有可能生成龐大眾多的候選序列。多遍掃描數(shù)據(jù)庫。 不易發(fā)生長度較大的序列模式。序列模式越長，所需要生成的序列就越多。,FreeSpan算法頻繁模式投影的序列模式挖掘 Frequent pattern-pro

9、jected Sequential pattern mining,,基本思想（基于數(shù)據(jù)庫投影和分片技術(shù)）利用頻繁項遞歸地將序列數(shù)據(jù)庫投影到更小的投影數(shù)據(jù)庫集中，在每個投影數(shù)據(jù)庫中生成子序列片段。,FreeSpan算法,,序列數(shù)據(jù)庫 最小支持度設為2,,,FreeSpan算法,1.找到頻繁項集L1頻繁項按支持度降序排列形成頻繁項列表，f_list=根據(jù)f_list，序列模式集

10、被分為不相交的六個子集：1）只包含項f； ……分而自治策略,,,FreeSpan算法,2.A.構(gòu)造頻繁項矩陣F用于生成長度為2的序列模式，投影數(shù)據(jù)庫集用于生成長度為3及更長的序列模式F是一個三角矩陣F[j,k]（1≤j≤m，1≤k≤j）。其中F[j,j]（1≤j≤m）僅有一個計數(shù)值，而其他每個F[j,k]（1≤j≤m，1≤k≤j）有三個計數(shù)值：（A,B,C）,序列模式α的投影數(shù)據(jù)庫是含有α的序列集的子序列，非頻繁項及α后的項也被刪

11、除。,F矩陣圖,1b,2c,3a,4d,5e,6f,1b,2c,3a,4d,5e,6f,F[j,j] 僅有一個計數(shù)值，F(xiàn)[j,k] 有三個計數(shù)值：（A,B,C） ,序列,,,FreeSpan算法,2.B.生成長度為2的序列模式 標記循環(huán)項模式和投影數(shù)據(jù)庫；,循環(huán)項模式標記形如$αiγαjγ$，其中$…$表示兩種形式，｛…｝。 投影數(shù)據(jù)庫標記形如$αiαj$：｛bp,…,bq｝，｛bp

12、,…,bq｝表示在子序列挖掘過程中與$αiαj$合在一起生成長度更長的序列模式的頻繁項集。,,,FreeSpan算法,,,FreeSpan算法,2.C.再次掃描數(shù)據(jù)庫S，生成循環(huán)項模式和投影數(shù)據(jù)庫；｛b+ f+ ｝ ｛b+ d ｝ {:2,:2,:2,:2, :2,:2,:2,:2,:2,:2,:2} 四個投影數(shù)據(jù)庫如下圖：,,FreeSpan算法,2.D.對生成的投影數(shù)據(jù)庫遞歸調(diào)用矩陣投影挖掘算法挖掘更長的候選模式。,

13、,FreeSpan算法：給定序列數(shù)據(jù)庫S及最小支持度閾值ζ。1. 掃描序列數(shù)據(jù)庫S，找到S中的頻繁項集，并以降序排列生成f_list列表。2. 執(zhí)行下面步驟：a.    第一遍掃描數(shù)據(jù)庫S，構(gòu)造頻繁項矩陣；b.    生成長度為2的序列模式及標記循環(huán)項模式和投影數(shù)據(jù)庫；c.    再次掃描數(shù)據(jù)庫S，生成循環(huán)項模式和投影數(shù)據(jù)庫；d.

14、    對生成的投影數(shù)據(jù)庫遞歸調(diào)用矩陣投影挖掘算法挖掘更長的候選模式。,,PrefixSpan算法（通過前綴投影挖掘序列模式）Prefix-projected Sequential pattern mining,基本思想：序列數(shù)據(jù)庫投影時，并不考慮所有可能出現(xiàn)的頻繁子序列，而只檢驗前綴序列，然后把相應的后綴序列投影成投影數(shù)據(jù)庫。每個投影數(shù)據(jù)庫中，只檢查局部頻繁模式。不需要生成候選序列。,例： ,,,,,

15、,,,,,,,,前綴：給定序列? = ，? = (m?n) ，如果ei’ = ei (i ? m - 1)， em’ ? em，并且(em - em’)中的項目均在em’中項目的后面， 則稱?是?的前綴.,投影：給定序列?和?，其中?是?的子序列，即???。?的子序列?’（?’??），?’被稱為?關(guān)于前綴?的投影，當且僅當1）?是?’的前綴2）不存在?’的超集?//（即?’ ? ?//， ?’ ? ?//），使得?//是?的子序列并且?

16、是?//的前綴。,后綴： 序列?關(guān)于子序列? = 的投影為?’ = (n >= m)，則序列?關(guān)于子序列?的后綴為， 其中em” = (em - em’),算法描述：掃描序列數(shù)據(jù)庫，生成所有長度為1的序列模式根據(jù)長度為1的序列模式，生成相應的投影數(shù)據(jù)庫在相應的投影數(shù)據(jù)庫上重復上述步驟，直到在相應的投影數(shù)據(jù)庫上不能產(chǎn)生序列模式為止,S,,,S1…,Sm,,,S11 ………,S1n ……,,,Sm1 ……

17、…,Smp ……,,PrefixSpan算法,,,PrefixSpan算法,定義1. 投影數(shù)據(jù)庫：設?為序列數(shù)據(jù)庫S中的一個序列模式，則?的投影數(shù)據(jù)庫為S中所有以?為前綴的序列相對于?的后綴，記為S|?例： —投影數(shù)據(jù)庫，由4個后綴序列組成：，，，。 －投影數(shù)據(jù)庫,,,PrefixSpan算法,,,PrefixSpan算法,查找長度為1的序列模式 :4,:4,:4,:3,:3,:3分割搜索空間序列模式集可按6個前綴被劃

18、分為六個子集：1）包含前綴的子集；……；6）包含前綴的子集。尋找序列模式的子集。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫。,,,PrefixSpan算法,尋找具有前綴的序列模式。 —投影數(shù)據(jù)庫，由4個后綴序列組成：，，，。 掃描—投影數(shù)據(jù)庫一遍，找到含有前綴的長度為2的序列模式，包括：：2，：4，：2，：4，：2，：2。遞歸，所有具有前綴的序列劃分為6個子集：1）包含前綴的子集；……；6）包含前綴的子集,,—投影數(shù)據(jù)庫：。不產(chǎn)生任何頻繁子序列，

19、結(jié)束?！队皵?shù)據(jù)庫：，，包含前綴的序列模式有：，，，。即， ，， —投影數(shù)據(jù)庫：，，。序列模式：，，，（即，，，）。—，—，—投影數(shù)據(jù)庫－，－，－，－，－投影數(shù)據(jù)庫 —投影數(shù)據(jù)庫：， 包含前綴的序列模式有：找到含有前綴的序列模式，包括：,子程序PrefixSpan(?, L, S|?) 參數(shù)：? ：一個序列模式 ；L：序列模式?的長度 S|? ： 如果?不為空時，為?－投影數(shù)據(jù)庫，否則為投

20、影數(shù)據(jù)庫S，1 掃描S|?，找到頻繁項b，b滿足：a)b可以作為?的最后一個元素，形成一個序列模式；或者b) 可以追加到?上，形成一個序列模式。2）對于每個頻繁項b，追加到?上，形成一個序列模式?’，輸出?’；3）對于每個?’，構(gòu)建?’—投影數(shù)據(jù)庫S|?’，調(diào)用PrefixSpan(?’,l+1,S|?’)。,,PrefixSpan算法分析：PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間