如果t是s的子序列，则称t包含在s中。
例如序列<{2}，{1，3}>是序列<{1，2}，{5}，{1，3，4}> 的子序列，因为{2}包含在{1，2}中，{1，3}包含在{1，3，4}中。
而<{2，5}，{3}>不是序列<{1，2}，{5}，{1，3，4}>的子 序列，因为前者中项2和项5是一次购买的，而后者中项2和项5 是先后购买的，这就是区别所在。
定义6.5 如果一个序列s不包含在序列数据库S中的任何其 他序列中，则称序列s为最大序列。
定义6.6 一个序列α的支持度计数是指在整个序列数据 库S中包含α的序列个数。即：
supportS(α)=|{(SID，s)| (SID，s)∈S ∧α是s的子序列}|
其中，|·|表示集合中·出现的次数。若序列α的支持度计数 不小于最小支持度阈值min_sup，则称之为频繁序列，频繁 序列也称为序列模式。
定义6.1 事件（events）是一个项集，在购物篮例子中， 一个事件表示一个客户在特定商店的一次购物，一次购物 可以购买多种商品，所以事件表示为（x1，x2，…，xq）， 其中xk（1≤k≤q）是I中的一个项，一个事件中所有项均不 相同，每个事件可以有一个事件时间标识TID，也可以表 示事件的顺序。
6月10日 6月15日 6月20日
6月25日
6月25日 6月30日 7月25日
30 80
10，20 30
40，60，70
30，50，70
30 40，70
80
s5
6月12日
80
序
客户号
客户序列
列
s1
<{30}，{80}>
数
s2
<{10，20}，{30}，{40，60，70}>
S
据 库
s3
<{30，50，70}>
（2）模式增长框架的序列挖掘算法
模式增长框架挖掘算法的最大特点：
在挖掘过程中不产生候选序列，通过分而治之的思想， 迭代的将原始数据库进行划分，同时在划分的过程中动态的 挖掘序列模式，并将新发现的序列模式作为新的划分元，进 行下一次的挖掘过程，从而获得长度不断增长的序列模式。
主要有FreeSpan和PrefixSpan算法。
定义6.2 序列（sequence）是事件的有序列表，序列s记 作<e1，e2，…，el>，其中ej（1≤j≤l）表示事件，也称为s的元 素。
通常一个序列中的事件有时间先后关系，也就是说，ej （1≤j≤l）出现在ej+1之前。序列中的事件个数称为序列的长度， 长度为k的序列称为k-序列。在有些算法中，将含有k个项的 序列称为k-序列。
第6章 序列模式挖掘
序列数据是由有序元素或事件的序列组成的，可以 不包括具体的时间概念，序列数据的例子有客户购物序 列、Web点击流和生物学序列等。
这类数据处理的不是一个时间点上的数据，而是大 量时间点上的数据，因而具有自身的特殊性。
6.1 序列模式挖掘概述
6.1.1 序列数据库
设I={i1，i2，…，in}是所有项的集合，在购物篮例子 中，每种商品就是一个项。项集是由项组成的一个非空集 合。
长度为k的频繁序列称为频繁k-序列。
6.1.2 序列模式挖掘算法
1. 什么是序列模式挖掘
序列模式挖掘的问题定义为：给定一个客户交易数据 库D以及最小支持度阈值min_sup，从中找出所有支持度 计数不小于min_sup的序列，这些频繁序列也称为序列模 式。
有的算法还可以找出最大序列，即这些最大序列构成 序列模式。
3. 经典算法比较分析
算法
是否产生候选 存储结构 数据库是否缩 原数据库扫描
序列
减
次数
AprioriAll
是
Hash树
否
最长模式长度
GSP
是
Hash树
否ቤተ መጻሕፍቲ ባይዱ
最长模式长度
SPADE
是
序列格
是
3
PrefixSpan
否
前缀树
是
2
算法 执行 循环 循环 递归 递归
6.2 Apriori类算法
6.2.1 AprioriAll算法
根据数据集的不同分布方式，Aprior类算法又可以分为 水平格式算法和垂直格式算法。
水平分布的数据集是由一系列序列标识符和序列组成， 对应的算法有AprioriAll、AprioriSome、DynamicSome 和GSP，其中AprioriSome和DynamicSome只求最大序 列模式。 垂直分布的数据集是由一系列序列标识符（SID）、项 集和事件标识符（TID）组成，对应的算法有SPADE等。
定义6.3 序列数据库（sequence databases）S是元组<SID， s>的集合，其中SID是序列编号，s是一个序列，每个序列由若 干事件构成。
在序列数据库中每个序列的事件在时间或空间上是有序排 列的。
客户号SID
交易时间TID
商品列表（事件）
交
s1
易
数
据
s2
库
D
s3
s4
6月25日 6月30日
基于水平格式的Apriori类算法将序列模式挖掘过程分为 5个具体阶段，即排序阶段、找频繁项集阶段、转换阶段、 产生频繁序列阶段以及最大化阶段。
对于含有n个事件的序列数据库S，其中k-序列总数 为 Cnk，因此，具有9个事件的序列包含 C91 + C92+…+ C99 =29-1=511个不同的序列。
序列模式挖掘可以采用蛮立法枚举所有可能的序列， 并统计它们的支持度计数。但计算量非常大。
AprioriAll本质上是Apriori思想的扩张，只是在产生候 选序列和频繁序列方面考虑序列元素有序的特点，将项集的 处理改为序列的处理。
2. 经典的序列模式挖掘算法
（1）候选码生成—测试框架的序列挖掘算法
候选码生成—测试框架基于Apriori理论，即序列模 式的任一子序列也是序列模式，这类算法统称为Aprior 类算法。
主要包括AprioriAll、AprioriSome、DynamicSome、 GSP和SPADE算法等。
这类算法通过多次扫描数据库，根据较短的序列模 式生成较长的候选序列模式，然后计算候选序列模式的 支持度，从而获得所有序列模式。
s4
<{30}，{40，70}，{80}>
s5
<{80}>
定义6.4 对于序列t和s，如果t中每个有序元素都是s中一 个有序元素的子集，则称t是s的子序列。
形式化表述为，序列t=<t1，t2，…，tm>是序列s=<s1， s2，…，sn>的子序列，如果存在整数1≤j1<j2<…<jm≤n，使得
t1 s j1 ，t2 s j2 ，…，tm s jm 。