序列模式挖掘

1、,知识背景：,序列模式是神马？,1.顾客购买产品X，很可能在一段时间内购买购买产品Y；（时间序列模型） 2.在某个点发现了现象X，很可能在下一个点发现现象Y；（空间序列模型）,知识背景：序列模型VS关联规则,关联规则,序列模型,序列模型=关联规则+时间（空间）维度,知识背景：序列模型VS时间序列模型,时间序列模型,序列模型,序 列 模 型：一系列研究对象在某段时间内的行为模式 分析，如顾客购买序列模式的发现； 时间序列模型：一个特定对象（变量）在某段时间内的变化 趋势，具有时间自相关性，如股票分析；,知识框架：,1.1 概念,定性： 序列模式挖掘是挖掘频繁出现的有序事件或子序列； 定量： 给定

2、一个正整数min_sup，表示最小支持度阈值，如 果序列在序列数据库S中存在support（S）（ ）min_sup， 则序列是频繁序列，也叫做序列模式。,1.2：定义,序列：将与对象A有关的所有事务按时间戳增序排序，就得到 对象A的一个序列s； 事务：序列是事务的有序列表，可以记作s=； 项 ：事务e是一个项集，可以记作e=（x1,x2,x3,xn），当 只有1项时直接记作x1；序列包含的项的数量记作序列的长度，长度为L的序列记作L序列； 序列数据库：包含一个或多个序列数据的数据集； 子序列：设序列 = ，序列 = ，ai 和bi都是元素。如果存在整数1 = j1 j2 jn = m，使得a

3、1 bj1，a2 bj2， an bjn则称序列为序列的子序列，又称序列包含序列，记为 ；,包含3个序列： S1= S2= S3= （假设有S4=）,S1包含3个事务，8个项，长度即为8，成为8序列； S2以及S3都为S1的子序列； S4则不是S1的子序列；,2.1 GSP算法和SPADE算法,算法介绍： 属于类Apriori算法，基于原理“序列模式的每个非空子集都是序列模式”，基于“候选产生-测试”模式进行挖掘。 主要步骤： 1、扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集； 2、根据长度为i 的种子集Li ，通过连接操作和修剪操作 生成长度为i+1的候选序列模式Ci+1；然

4、后扫描序列数据 库，计算每个候选序列模式的支持度，产生长度为i+1的 序列模式Li+1，并将Li+1作为新的种子集； 3、重复第二步，直到没有新的序列模式或新的候选序列模式产生为止；,L1 C2 L2 C3 L3 C4 L4 ,2.1 GSP算法和SPADE算法,连接操作：如果去掉序列模式S1的第一个项与去掉序列模式S2的最后一个项所得到的序列相同，则可以将S1于S2进行连接，即将S2的最后一个项目添加到S1中。 其中： （1）若S2的最后两个项本来属于同一个事务，则合并后与S1序列的最后一个项合并为同一个同一个事务； （2）否则，S2最后一项则单独成为一个事务。 剪切阶段：若某候选序列模式的

5、某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。,频繁3序列： ,候选产生： ,候选剪枝： ,2.1 GSP算法和SPADE算法,GSPVSSPADE,区别在于数据库中存储数据的结构不一样，因此扫描数据库的效率不一样。,2.1 GSP算法和SPADE算法,如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式 需要对序列数据库进行循环扫描 对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理,类Apriori算法存在的问题,2.2 PrefixSpan算法,算法介绍：基于FP增长算法采用分治的思想，不断产生序列数据库的多个更

6、小的投影数据库，然后在各个投影数据库上进行序列模式挖掘; 前缀与后缀： 假定序列S = ，则序列、等都是S的前缀。S关于的后缀为; S关于的后缀为; S关于的后缀为 ,2.2 PrefixSpan算法,投影数据库： 设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S| 例：序列模式的投影数据库为： , ,2.2 PrefixSpan算法,主要步骤： (1)得到长度为1的序列模型； （2）划分搜索空间； （3）找出序列模式的子集； （a）找出序列数据库D关于的投影数据库； （b）扫描投影数据库，得到局部频繁项； （c）递归过程； （4）汇集,S,S1 ,

7、Sm,S11 ,S1n ,Sm1 ,Smp ,2.2 PrefixSpan算法,（1）1序列模型为： ：4次， ：4次， ：4次， ：3次， ：3次， ：3次； （2）划分搜索空间： 根据（1）中的结果划分 前缀为的子集； 前缀为的子集； 前缀为的子集等,2.2 PrefixSpan算法,（3）找出序列模型的子集： (a)建立的投影数据库； (b)扫描上述投影数据库，找出局部频繁项， 分别为：,; (c)递归地寻找以, 为前缀的序列模型; （4）汇总以上挖掘的序列模型子集；, ,2.2 PrefixSpan算法,PrefixSpan算法分析,PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间 相对于原始的序列数据库而言，投影数据库的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的构造,3.1 多维、多层次的序列模式挖掘,“购买数码相机的退休顾客很可能在一个月内购买彩色打印机”、 “购买笔记本的年轻人很可能在两周内购买打印机” 这些例子的序列模式挖掘都是多维、多层次的。 多维体现在：“年轻人”与“老人”； 多层次体现在：“彩色打印机”与“打印机”,3.2 基于约束的序列模式挖掘,1.序列的长度 例：顾客在1周内购买的商品序列； 2.序列间事务的最大间隔 例：用户的Web页面浏览序