当前的大数据中许多数据都是具有固有的序列特征, 即事件之间是基于时间或空间的先后次序. 例如购物篮数据通常包含商品何时被顾客购买的时间信息. 迄今为止, 我们在前面的章节中所讨论的关联模式概念都只强调同时出现关系, 而忽略数据中的序列信息. 对于识别动态系统的重现特征, 或者预测特定时间的未来发生, 序列信息可能是非常有价值的.

本章将给出序列模式的基本概念和发现序列模式的算法.

预备知识

对象	时间戳	事件
A	10	2,3,5
A	20	1,6
A	23	1
B	11	4,5,6
B	17	2
B	21	1,2,7,8
C	14	1,6
C	28	1,7,8

表1 序列数据举例

1. 序列

   一般地, 序列是元素(事务)的有序列表, 记作$s=<e_1e_2e_3\dots e_n>$, 其中每个$e_j$是一个或多个事件的集族.

例子

1. web站点访问者访问web页面序列:

<{首页}{电子产品}{相机和摄像机}{数码项集}{购物车}{订购确认}{返回购物}>

---

2. 计算机专业学生在不同的学期参加课程的序列:

<{算法与数据结构, 操作系统导论}{数据库系统, 计算机体系结构}{计算机网络, 软件工程}{计算机图形学, 并行程序设计}>

序列的长度对应序列中的元素个数, 包含k个事件的序列被称为 k-序列.

2. 子序列

   若通过删去$s$中的一些事件或者删除$s$中的一些元素能推导出$t$, 则称$t$为$s$的 子序列(subsequence). 形式上讲, 如果存在整数$1 \le j_1<j_2<\dots <j_m \le n$, 使得$t_1 \subseteq s_{j1}, t_2 \subseteq s_{j2}, \dots , t_m \subseteq s_{jm}$, 则序列$t=<t_1t_2\dots t_m>$是序列$s=<s_1s_2\dots s_n>$的子序列. 如果$t$是$s$的子序列, 则称$t$包含在$s$中.

   序列数据$s$	序列数据$t$	$t$是否为$s$的子序列
   <{2,4}{3,5,6}{8}>	<{2}{3,6}{8}>	是
   <{2,4}{3,5,6}{8}>	<{2}{8}>	是
   <{1,2}{3,4}>	<{1}{2}>	否
   <{2,4}{2,4}{2,5}>	<{2}{4}>	是

   表2 子序列概念例子

序列模式发现

设$D$是包含一个或多个 数据序列(data sequence) 的数据集. 数据序列是指与单个数据对象相关联的事件的有序列表. 例如表1中共有3个数据序列, 对象A、B、C各一个.

序列$s$的支持度是包含$s$的所有数据序列所占的比例. 如果序列$s$的支持度大于或等于用户指定的最小支持度阈值, 则称$s$是一个序列模式(或频繁序列).

序列模式发现

给定序列数据集$D$和用户指定的最小支持度阈值minsup, 则序列模式发现的任务是找出支持度大于或等于minsup的所有序列

由于以下的三个原因, 相较于候选项集, 候选序列的数量是远远多于候选项集的.

1. 一个项在项集中只会出现一次, 但是在序列中可能会多次出现.
2. 次序在序列中是重要的, 项集和序列的区别相当于组合变排序.
3. 对于序列数据, n个不同的项的候选项集数量上限为$2^{n-1}$, 但是仅仅2个不同事件产生的序列可能数量都相当多.

下面给出类Apriori算法从序列数据集中提取序列模式.

序列模式发现的类Apriori算法

该算法的结构几乎和前面提到的用于频繁项集发现的Apriori算法完全一样. 该算法迭代产生新的候选k-序列, 剪掉那些子集中有非频繁(k-1)-序列的候选, 然后对留下的候选计数, 识别序列模式.

候选生成

序列的生成和候选项集不同. 前面我们通过项集内部的元素使用字典序排序来避免重复产生候选, 但是序列本身可能并不符合字典序. 合并序列的标准可以用以下过程的形式来表示:

序列$s^{(1)}$与另一个序列$s^{(2)}$合并, 仅当从$s^{(1)}$中去掉第一个事件得到的子序列与从$s^{(2)}$中去掉最后一个事件得到的子序列相同. 通过如下方式扩展序列$s^{(1)}$来得到候选集:

1. 如果$s^{(2)}$的最后一个元素只有一个事件, 则将$s^{(2)}$的最后一个元素合并到$s^{(1)}$的末尾, 得到合并后的序列
2. 如果$s^{(2)}$的最后一个元素多于一个事件, 则将$s^{(2)}$的最后一个元素的最后一个事件(不被包含在$s^{(1)}$的最后一个元素)合并到$s^{(1)}$的最后一个元素, 得到合并后的序列

步骤可见下图:

序列模式挖掘算法候选生成和剪枝步骤示例

候选剪枝

如果候选k-序列的(k-1)-序列至少有一个是非频繁的, 那么将它剪掉.

支持度计数

在计算支持度计数期间, 算法将识别属于特定数据序列的所有候选k-序列, 并增加其支持度. 在对每个数据序列执行该步骤后, 算法将识别出频繁k-序列, 并可以丢弃支持度小于最小支持度阈值minsup的候选.