序列模式挖掘算法简介 报告人：邓爱林 2001-8-15.

Presentation on theme: "序列模式挖掘算法简介 报告人：邓爱林 2001-8-15."— Presentation transcript:

1 序列模式挖掘算法简介 报告人：邓爱林

2 报告的主要内容 序列模式简介 GSP算法 PrefixSpan算法

3 一、序列模式简介 序列模式的概念最早是由Agrawal和Srikant 提出的
序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值

4 一、序列模式简介 例子1：在两年前购买了Ford 牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动
例子2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒

5 一、序列模式简介 应用领域： 客户购买行为模式预测 Web访问模式预测 疾病诊断 自然灾害预测 DNA序列分析

6 一、序列模式简介 符号化表示： 项目集(Itemset)是各种项目组成的集合
序列(Sequence)是不同项目集(ItemSet)的有序排列，序列s可以表示为s = <s1s2…sl>，sj(1 <= j <= l)为项目集(Itemset)，也称为序列s的元素 序列的元素(Element)可表示为(x1x2…xm)， xk(1 <= k <= m)为不同的项目，如果一个序列只有一个项目，则括号可以省略 一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列

7 一、序列模式简介 符号化表示： 设 = <a1a2…an>， = <b1b2…bm>，如果存在整数1 <= j1 < j2 <…< jn <= m，使得a1  bj1，a2  bj2，…， an  bjn，则称序列为序列的子序列，又称序列包含序列，记为   序列在序列数据库S中的支持数为序列数据库S中包含序列的序列个数，记为Support() 给定支持度阈值，如果序列在序列数据库中的支持数不低于，则称序列为序列模式 长度为l的序列模式记为l-模式

8 <a(abc)(ac)d(cf)> <(ad)c(bc)(ae)> <(ef)(ab)(df)cb>
一、序列模式简介 例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2。 Sequence_id Sequence 10 <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的序列模式

9 一、序列模式简介 问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式
系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列

10 一、序列模式简介 序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法：类似于Apriori算法 PrefixSpan(Prefix-project Sequential Pattern mining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘

11 一、序列模式简介 上述算法存在的主要问题：
缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向 事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务 缺少分类层次：只能在项目的原始级别上进行挖掘

12 二、GSP算法 L1 C2  L2  C3  L3  C4  L4  …… GSP算法描述：
根据长度为i 的种子集Li 通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集 重复第二步，直到没有新的序列模式或新的候选序列模式产生为止 L1 C2  L2  C3  L3  C4  L4  ……

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

14 二、GSP算法 例子：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式 Sequential patterns
With length 3 Candidate 4-Sequences After Join After Pruning <(1,2) 3> <(1,2) (3,4)> <(1,2) 4> <(1,2) 3 5> <1 (3,4)> <(1,3) 5> <2 (3,4)> <2 3 5>

15 二、GSP算法 候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d,找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数 L1 C2  L2  C3  L3  ……

16 二、GSP算法 GSP算法存在的主要问题： 如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式 需要对序列数据库进行循环扫描
对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理

17 三、PrefixSpan算法 相关定义 前缀：设每个元素中的所有项目按照字典序排列。给定序列 = <e1e2…en>， = <e1’ e2’… em’>(mn) ，如果ei’ = ei (i  m - 1)， em’  em，并且(em - em’)中的项目均在em’中项目的后面， 则称是的前缀 投影：给定序列和 ，如果是的子序列，则关于的投影’必须满足： 是’的前缀，’是的满足上述条件的最大子序列 后缀： 序列关于子序列 = <e1e2… em-1em’>的投影为’ = <e1e2… en> (n >= m)，则序列关于子序列的后缀为<em”em+1… en>， 其中em” = (em - em’)

18 三、PrefixSpan算法 例子： <a(abc)(ac)d(cf)> <a>

19 三、PrefixSpan算法 算法描述： 扫描序列数据库，生成所有长度为1的序列模式 根据长度为1的序列模式，生成相应的投影数据库
在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止 S11 …… … S1 … S S1n …… Sm Sm1 …… … Smp ……

20 <a(abc)(ac)d(cf)> <(ad)c(bc)(ae)> <(ef)(ab)(df)cb>
三、PrefixSpan算法 扫描序列数据库S，产生长度为1的序列模式有：<a> : 4, <b>:4, <c> : 4, <d> : 3, <e> : 3, <f> : 3 序列模式的全集必然可以分为分别以<a>，<b>，<c>，<d>，<e>和<f>为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结果如下页图所示 分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止 Sequence_id Sequence 10 <a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <eg(af)cbc>

21 三、PrefixSpan算法 Prefix Project Database <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_id Sequence 10 <a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <eg(af)cbc>

22 三、PrefixSpan算法 定义1. 投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S| 定义2. 投影数据库中的支持数：设为序列数据库S中的一个序列模式，序列以为前缀，则在的投影数据库S|中的支持数为S|中满足条件  .的序列的个数

23 三、PrefixSpan算法 PrefixSpan算法 输入：序列数据库S及最小支持度阈值min_sup 输出：所有的序列模式

24 三、PrefixSpan算法 子程序PrefixSpan(, L, S|)
参数： . 一个序列模式 L. 序列模式的长度 S| . 如果为空，则为S，否则为的投影数据库 扫描S|，找到满足下述要求的长度为1的序列模式b： b可以添加到的最后一个元素中并为序列模式 <b>可以作为的最后一个元素并为序列模式 对每个生成的序列模式b，将b添加到形成序列模式’，并输出’ 对每个’,构造’的投影数据库S|’ ,并调用子程序PrefixSpan(’, L + 1, S|’)

25 三、PrefixSpan算法 PrefixSpan算法分析： PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间
相对于原始的序列数据库而言，投影数据库的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的构造

26 三、PrefixSpan算法 PrefixSpan算法的主要改进： 逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数
伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销

27 <a(abc)(ac)d(cf)> <(ad)c(bc)(ae)> <(ef)(ab)(df)cb>
Sequence_id Sequence 10 <a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <eg(af)cbc> 三、PrefixSpan算法 隔层投影的例子： 扫描序列数据库，产生所有长度为1的序列模式 再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有长度为2的序列模式 构造长度为2的序列模式所对应的扫描数据库，然后对每个投影数据库，重复上面的操作，直到没有新的序列模式产生为止 a 2 b (4,2,2) 1 c (4,2,1) (3,3,2) 3 d (2,1,1) (2,2,0) (1,3,0) e (1,2,1) (1,2,0) (1,1,0) f (1,1,1) (2,0,1)

28 三、PrefixSpan算法 伪投影：当数据库可以直接放入内层时，并不需要构造所有的序列模式对应的投影数据库，我们可以使用指向数据库中序列的指针及其偏移量作为伪投影 例子：假设上述序列数据库可以放入内层，在构造a投影数据库时，序列 S1 = <a(abc)(ac)d(cf)>所对应的伪投影为：一个指向S1的指针，指针偏移设定为2。同样的，序列S1的<ab>投影数据库对应的伪投影为：一个指向S1的指针，指针偏移设定为4