序列模式挖掘綜述

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

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

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

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

5、及序列S,T，形如S?T的表達(dá)式稱為序列關(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)頻繁項(xiàng)集階段 轉(zhuǎn)換階段 序列階段 最大階段,由客戶標(biāo)識(shí)及交易發(fā)生的時(shí)間為關(guān)鍵字所排序的數(shù)據(jù)庫(kù),排序階段,客戶序列描述數(shù)據(jù)庫(kù),頻繁

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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