序列模式挖掘算法

序列模式挖掘算法简介报告人：邓爱林2001-8-151报告的主要内容序列模式简介GSP算法PrefixSpan算法2001-8-152一、序列模式简介序列模式的概念最早是由Agrawal和Srikant提出的序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值2001-8-153一、序列模式简介例子1：在两年前购买了Ford牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动例子2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒2001-8-154一、序列模式简介应用领域：客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析2001-8-155一、序列模式简介符号化表示：项目集(Itemset)是各种项目组成的集合序列(Sequence)是不同项目集(ItemSet)的有序排列，序列s可以表示为s=<s1s2…sl>，sj(1<=j<=l)为项目集(Itemset)，也称为序列s的元素序列的元素(Element)可表示为(x1x2…xm)，xk(1<=k<=m)为不同的项目，如果一个序列只有一个项目，则括号可以省略一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列2001-8-156一、序列模式简介符号化表示：设=<a1a2…an>，=<b1b2…bm>，如果存在整数1<=j1<j2<…<jn<=m，使得a1

bj1，a2

bj2，…，an

bjn，则称序列

为序列

的子序列，又称序列

包含序列，记为序列在序列数据库S中的支持数为序列数据库S中包含序列的序列个数，记为Support()给定支持度阈值，如果序列在序列数据库中的支持数不低于，则称序列为序列模式长度为l的序列模式记为l-模式2001-8-157一、序列模式简介例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support=2。Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>序列<a(bc)df>是序列<a(abc)(ac)d(cf)>的子序列序列<(ab)c>是长度为3的序列模式2001-8-158一、序列模式简介问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列2001-8-159一、序列模式简介序列模式挖掘的主要算法GSP(GeneralizedSequentialPatterns)算法：类似于Apriori算法PrefixSpan(Prefix-projectSequentialPatternmining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘2001-8-1510一、序列模式简介上述算法存在的主要问题：缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务缺少分类层次：只能在项目的原始级别上进行挖掘2001-8-1511二、GSP算法GSP算法描述：扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集根据长度为i的种子集Li通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集重复第二步，直到没有新的序列模式或新的候选序列模式产生为止L1

C2

L2

C3

L3

C4

L4

……2001-8-1512二、GSP算法产生候选序列模式主要分两步：连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1于s2进行连接，即将s2的最后一个项目添加到s1中剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除L1

C2

L2

C3

L3

C4

L4

……2001-8-1513二、GSP算法例子：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruning<(1,2)3><(1,2)(3,4)><(1,2)(3,4)><(1,2)4><(1,2)35><1(3,4)><(1,3)5><2(3,4)><235>2001-8-1514二、GSP算法候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d,找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数L1

C2

L2

C3

L3

……2001-8-1515二、GSP算法GSP算法存在的主要问题：如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式需要对序列数据库进行循环扫描对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理2001-8-1516三、PrefixSpan算法相关定义前缀：设每个元素中的所有项目按照字典序排列。给定序列=<e1e2…en>，=<e1’e2’…em’>(m

n)，如果ei’

=ei

(im-1)，em’

em，并且(em-em’)中的项目均在em’中项目的后面，则称

是的前缀投影：给定序列和，如果

是的子序列，则关于

的投影’必须满足：

是’的前缀，’是的满足上述条件的最大子序列后缀：序列关于子序列=<e1e2…em-1em’>的投影为’=<e1e2…en>(n>=m)，则序列

关于子序列的后缀为<em”em+1…en>，其中em”=(em-em’)2001-8-1517三、PrefixSpan算法例子：<a(abc)(ac)d(cf)><a><aa>a(ab)a(abc)<(abc)(ac)d(cf)><(_bc)(ac)d(cf)><ab><(_c)(ac)d(cf)>2001-8-1518三、PrefixSpan算法算法描述：扫描序列数据库，生成所有长度为1的序列模式根据长度为1的序列模式，生成相应的投影数据库在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止SS1…SmS11………S1n……Sm1………Smp……2001-8-1519三、PrefixSpan算法扫描序列数据库S，产生长度为1的序列模式有：<a>:4,<b>:4,<c>:4,<d>:3,<e>:3,<f>:3序列模式的全集必然可以分为分别以<a>，<b>，<c>，<d>，<e>和<f>为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结果如下页图所示分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>2001-8-1520三、PrefixSpan算法PrefixProjectDatabase<a><(abc)(ac)d(cf)><(_d)c(bc)(ae)><(_b)(df)cb><(_f)cbc><b><(_c)(ac)d(cf)><(_c)(ae)><(df)cb><c><c><(ac)d(cf)><(bc)(ae)><b><bc><d><(cf)><c(bc)(ae)><(_f)cb><e><(_f)(ab)(df)cb><(af)cbc><f><(ab)(df)cb><cbc>Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>2001-8-1521三、PrefixSpan算法定义1.投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|

定义2.投影数据库中的支持数：设为序列数据库S中的一个序列模式，序列

以为前缀，则

在的投影数据库S|

中的支持数为S|

中满足条件.的序列

的个数2001-8-1522三、PrefixSpan算法PrefixSpan算法输入：序列数据库S及最小支持度阈值min_sup输出：所有的序列模式方法：调用子程序PrefixSpan(<>,0,S)2001-8-1523三、PrefixSpan算法子程序PrefixSpan(

,L,S|

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

S|

.如果为空，则为S，否则为的投影数据库扫描S|

，找到满足下述要求的长度为1的序列模式b：b可以添加到的最后一个元素中并为序列模式<b>可以作为的最后一个元素并为序列模式对每个生成的序列模式b，将b添加到形成序列模式’，并输出’对每个’,构造’的投影数据库S|’,并调用子程序PrefixSpan(’,L+1,S|’)2001-8-1524三、PrefixSpan算法PrefixSpan算法分析：PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间相对于原始的序列数据库而言，投影数据库的规模不断减小PrefixSpan算法的主要开销在于投影数据库的构造2001-8-1525三、PrefixSpan算法PrefixSpan算法的主要改进：逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销2001-8-1526三、PrefixSpan算法隔层投影的例子：扫描序列数据库，产生所有长度为1的序列模式再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有长度为2的序列模式