序列模式挖掘综述

序列

报告人：熊赟

内容概要基本概念其他

类Apriori生成候选算法相似性搜索

FreeSpan算法,PrefixSpan算法

第6章序列

6.1基本概念6.2原理6.3核心算法6.4其他

序列是不同项集的有序排列。定义1(序列)：I=｛i1i2…im｝是项集，ik（1<=k<=m）是一个项，序列S记为S＝<s1s2…sn>，其中sj（1<=j<=n）为项集（也称序列S的元素），即sjI。每个元素由不同项组成。序列的元素可表示为（i1i2…ik），若一个序列只有一个项，则括号可以省略。序列包含的所有项的个数称为序列的长度。长度为l的序列记为l-序列。序列定义2(子序列)：序列T＝<ti1ti2…tim>是另一个序列S＝<s1s2…sn>的子序列，满足下面条件：对于每一个j，1<=j<=m-1，有ij<ij+1且对于每一个j，1<=j<=m，存在1<=k<=n，使得tijsk。即序列S包含序列T。用符号“”表示“被包含于”，序列T是序列S的子序列可记为TS。称T为S的子序列，S为T的超序列。若一个序列S不包含在任何其他的序列之中，则称序列S是最大的。

子序列定义3（支持度）：序列数据库D是元组<sid，S>的集合，sid为序列标识号，如果序列T是S的子序列（即TS）称元组<sid,S>包含序列T；则序列T在序列数据库D中的支持度是数据库中包含T的元组数，即supportD(T)＝|{<sid,S>|<sid,S>DTS}|记作support（T）。

序列支持度定义4（频繁序列模式）：给定正整数为支持度阈值，如果数据库中最少有个元组包含序列S，即support（S）>=，则称序列S为序列数据库D中的一个（频繁）序列模式。长度为l的序列模式称为l–模式。

序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度（用户指定最小支持度阈值）的子序列。频繁序列模式定义5:（序列关联规则）对于给定的项集I=｛i1i2…im｝以及序列S,T，形如ST的表达式称为序列关联规则。

序列关联规则置信度支持度序列关联规则序列关联规则ST的支持度是支持序列S和T的顾客数占总顾客数之比。序列关联规则ST的置信度记为（），是支持序列S和T的顾客数与仅支持S的顾客数之比。

序列模式挖掘阶段

排序阶段

发现频繁项集阶段

转换阶段

序列阶段

最大阶段

交易发生的时间客户标识购买项June10’04June12’04June15’04June20’04June25’04June25’04June25’04June30’04June30’04July25’042522431144A，BHCD，F，GCC，E，GCHD，GH客户标识交易时间购买项11June25’04June30’04CH222June10’04June15’04June20’04A,BCD,F,G3June25’04C,E,G444June25’04June30’04July25’04CD,GH5June12’04H由客户标识及交易发生的时间为关键字所排序的数据库排序阶段客户号客户序列12345<(C)(H)><(A,B)(C)(D,F,G)><(C,E,G)><(C)(D,G)(H)><(H)>客户序列描述数据库频繁项集映射(C)(D)(G)(DG)(H)12345频繁项集分别是(C)、(D)、(G)、(D,G)和(H)发现频繁项集阶段客户标识原始客户序列转换后客户序列映射后序列12345<(C)(H)><(A,B)(C)(D,F,G)><(C,E,G)><(C)(D,G)(H)><(H)><{(C)}{(H)}><{(C)}{(D),(G),(D,G)}><{(C),(G)}><{(C)}{(D),(G),(D,G)}{(H)}><{(H)}><{1}{5}><{1}{2,3,4}><{1,3}><{1}{2,3,4}{5}><{5}>转换后的数据库（客户序列）转换阶段核心算法

AprioriAll,AprioriSome算法

FreeSpan，PrefixSpan算法

序列阶段

最大阶段

AprioriAll算法

基本思想

客户号客户序列12345<{15}{2}{3}{4}><{1}{3}{4}{35}><{1}{2}{3}{4}><{1}{3}{5}><{4}{5}>

AprioriAll算法AprioriAll算法

1-序列支持度<1>4<2>2<3>4<4>4<5>4L12-序列支持度<12>2<13>4<14>3<15>3<23>2<24>2<34>3<35>2<45>2L23-序列支持度<123>2<124>2<134>3<135>2<234>2AprioriAll算法

4-序列支持度<1234>2L3L4序列支持度<1234>2<135>2<45>2AprioriAll算法

最大的频繁序列AprioriSome算法

基本思想：算法分为两个阶段：前阶段：只对一定长度的序列计数－－next（k）函数即Ck生成Lk

后阶段：对前阶段已确定的Lk确定为最大序列对前阶段没有生成Lk，先删除所有在Ck中包含在Li中的序列，再对Ck计数生成Lk。AprioriSome算法

1-序列支持度<1>4<2>2<3>4<4>4<5>4L12-序列支持度<12>2<13>4<14>3<15>3<23>2<24>2<34>3<35>2<45>2L2next(last)=2k<123>不计数<124><134><135><234><345>AprioriSome算法

C3C4<1234><1243><1345><1354>修剪AprioriSome算法

C5为空结束前阶段进入回溯阶段<135><345>删除了L4的子序列后的C3再计数发现<135>是最大3序列L44-序列支持度<1234>2序列支持度<1234>2<135>2<45>2AprioriSome算法

最大的频繁序列除<45>以外L2中所有的序列都被删除

L1中所有的序列都被删除

类Apriori算法有以下缺点：有可能生成庞大众多的候选序列。多遍扫描数据库。不易发生长度较大的序列模式。序列模式越长，所需要生成的序列就越多。

FreeSpan算法频繁模式投影的序列模式挖掘

Frequentpattern-projectedSequentialpatternmining

基本思想（基于数据库投影和分片技术）利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片段。FreeSpan算法

序列id序列项10<(bd)cb(ac)>{a,b,c,d}20<(bf)(ce)b(fg)>{b,c,e,f,g}30<(ah)(bf)abf>{a,b,f,h}40<(be)(ce)d>{b,c,d,e}50<a(bd)bcb(ade)>{a,b,c,d,e}序列数据库最小支持度设为2

FreeSpan算法1.找到频繁项集L1频繁项按支持度降序排列形成频繁项列表，f_list=<b:5,c:4,a:3,d:3,e:3,f:3>根据f_list，序列模式集被分为不相交的六个子集：1）只包含项f；……分而自治策略

FreeSpan算法2.A.构造频繁项矩阵F用于生成长度为2的序列模式，投影数据库集用于生成长度为3及更长的序列模式F是一个三角矩阵F[j,k]（1≤j≤m，1≤k≤j）。其中F[j,j]（1≤j≤m）仅有一个计数值，而其他每个F[j,k]（1≤j≤m，1≤k≤j）有三个计数值：（A,B,C）序列模式α的投影数据库是含有α的序列集的子序列，非频繁项及α后的项也被删除。F矩阵图4(4,3,0)1(3,2,0)(2,1,1)

2(2,2,2)(2,2,0)(1,2,1)1(3,1,1)(1,1,2)(1,0,1)(1,1,1)1(2,2,2)(1,1,0)(1,1,0)(0,0,0)(1,1,0)21b2c3a4d5e6f1b2c3a4d5e6fF[j,j]仅有一个计数值，F[j,k]有三个计数值：（A,B,C）

<ijik><ikij><（ikij）>序列<(bd)cb(ac)><(bf)(ce)b(fg)><(ah)(bf)abf><(be)(ce)d><a(bd)bcb(ade)>

FreeSpan算法2.B.生成长度为2的序列模式

标记循环项模式和投影数据库；

循环项模式标记形如$αiγαjγ$，其中$…$表示两种形式<…>，｛…｝。投影数据库标记形如$αiαj$：｛bp,…,bq｝，｛bp,…,bq｝表示在子序列挖掘过程中与$αiαj$合在一起生成长度更长的序列模式的频繁项集。

FreeSpan算法项长度为2的序列模式循环项标记投影数据库标记f<bf>:2,<fb>:2,<(bf)>:2｛b+f+｝Φ

e<be>:3,<(ce)>:2<b+e><(ce)>:{b}d<bd>:2,<db>:2,<(bd)>:2<cd>:2,<dc>:2,<da>:2｛b+d｝<da+><da>:{bc}{cd}:{b}a………………c………………b<bb>:4<bb+>Φ

FreeSpan算法2.C.再次扫描数据库S，生成循环项模式和投影数据库；｛b+f+｝<b+e>｛b+d｝<da+><bb+>{<bbf>:2,<fbf>:2,<(bf)b>:2,<(bf)(bf)>:2,<(bd)b>:2,<bba>:2,<aba>:2,<aba>:2,<abb>:2,<bcb>:2,<bbc>:2}四个投影数据库如下图：

FreeSpan算法2.D.对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。标记<(ce)>:{b}<da>:{bc}{cd}:{b}<ca>:{b}投影数据库<b(ce)b>,<b(ce)><(bd)cb(ac)>,<(bd)bcba><(bd)cbc><bcd>,<(bd)bcbd><bcba><bbcba>序列模式<b(ce)>:2<(bd)a>:2<dca>:2<dba>:2<(bd)ca>:2…………<bca>:2<cba>:2<bcba>:2<(bd)cb(ac)><(bf)(ce)b(fg)><(ah)(bf)abf><(be)(ce)d><a(bd)bcb(ade)>FreeSpan算法：给定序列数据库S及最小支持度阈值ζ。1.扫描序列数据库S，找到S中的频繁项集，并以降序排列生成f_list列表。2.执行下面步骤：a.

第一遍扫描数据库S，构造频繁项矩阵；b.

生成长度为2的序列模式及标记循环项模式和投影数据库；c.

再次扫描数据库S，生成循环项模式和投影数据库；d.

对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。PrefixSpan算法（通过前缀投影挖掘序列模式）Prefix-projectedSequentialpatternmining

基本思想：序列数据库投影时，并不考虑所有可能出现的频繁子序列，而只检验前缀序列，然后把相应的后缀序列投影成投影数据库。每个投影数据库中，只检查局部频繁模式。不需要生成候选序列。例：<a(abc)(ac)d(cf)><a><aa><a(ab)><a(abc)><(abc)(ac)d(cf)><(_bc)(ac)d(cf)><ab><(_c)(ac)d(cf)>前缀：给定序列=<e1e2…en>，=<e1’e2’…em’>(mn)，如果ei’

=ei(im-1)，em’em，并且(em-em’)中的项目均在em’中项目的后面，则称是的前缀.投影：给定序列和，其中是的子序列，即。的子序列’（’），’被称为关于前缀的投影，当且仅当1）是’的前缀2）不存在’的超集//（即’//，’//），使得//是的子序列并且是//的前缀。

后缀：序列关于子序列=<e1e2…em-1em’>的投影为’=<e1e2…en>(n>=m)，则序列关于子序列的后缀为<em”em+1…en>，其中em”=(em-em’)算法描述：扫描序列数据库，生成所有长度为1的序列模式根据长度为1的序列模式，生成相应的投影数据库在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生序列模式为止SS1…SmS11………S1n……Sm1………Smp……PrefixSpan算法

PrefixSpan算法序列号序列10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>定义1.投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|例：<a>—投影数据库，由4个后缀序列组成：<(abc)(ac)d(cf)>，<(_d)c(bc)(ae)>，<(_b)(df)cb>，<(_f)cbc>。

<（ab）>－投影数据库<(_c)(ac)d(cf)>,<(df)cb>PrefixSpan算法

PrefixSpan算法查找长度为1的序列模式<a>:4,<b>:4,<c>:4,<d>:3,<e>:3,<f>:3分割搜索空间序列模式集可按6个前缀被划分为六个子集：1）包含前缀<a>的子集；……；6）包含前缀<f>的子集。寻找序列模式的子集。构建并递归挖掘投影数据库。

PrefixSpan算法寻找具有前缀<a>的序列模式。

<a>—投影数据库，由4个后缀序列组成：<(abc)(ac)d(cf)>，<(_d)c(bc)(ae)>，<(_b)(df)cb>，<(_f)cbc>。

扫描<a>—投影数据库一遍，找到含有前缀<a>的长度为2的序列模式，包括：<aa>：2，<ab>：4，<(ab)>：2，<ac>：4，<ad>：2，<af>：2。递归，所有具有前缀<a>的序列划分为6个子集：1）包含前缀<aa>的子集；……；6）包含前缀<af>的子集

<aa>—投影数据库：<(_bc)(ac)d(cf)>。不产生任何频繁子序列，结束。<(ab)>—投影数据库：<(_c)(ac)d(cf)>，<(df)cb>，包含前缀<(ab)>的序列模式有：<c>，<d>，<f>，<dc>。即<(ab)c>，<（ab）d>，<（ab）f>，<（ab）dc><ab>—投影数据库：<(_c)(ac)d(cf)>，<(_c)a>，<c>。序列模式：<(_c)>，<(_c)a>，<a>，<c>（即<a(bc)>，<a(bc)a>，<aba>，<abc>）。<ac>—，<ad>—，<af>—投影数据库<b>－，<c>－，<d>－，<e>－，<f>－投影数据库<(ab)d>—投影数据库：<(cf)>，<(_f)cb>包含前缀<(ab)d>的序列模式有：<c>找到含有前缀<（ab）d>的序列模式，包括：<(ab)dc>子程序PrefixSpan(,L,S|)

参数：：一个序列模式；L：序列模式的长度

S|：如果不为空时，为－投影数据库，否则为投影数