序列模式

约 1497 字大约 5 分钟

2024-06-05

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

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

预备知识

对象	时间戳	事件
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

表 7.1 序列数据举例

序列
一般地, 序列是元素(事务)的有序列表, 记作 $s = <e_1e_2e_3\dots e_n>$ , 其中每个 $e_j$ 是一个或多个事件的集族.
例子
1. web 站点访问者访问 web 页面序列:
<{首页} {电子产品} {相机和摄像机} {数码项集} {购物车} {订购确认}{ 返回购物}>
1. 计算机专业学生在不同的学期参加课程的序列:
<{算法与数据结构, 操作系统导论} {数据库系统, 计算机体系结构} {计算机网络, 软件工程} {计算机图形学, 并行程序设计}>
序列的长度对应序列中的元素个数, 包含 k 个事件的序列被称为 k-序列.
子序列
若通过删去 $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}> 是
表 7.2 子序列概念例子

序列数据 $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}>	是

序列模式发现

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

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

序列模式发现

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

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

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

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

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

候选生成

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

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

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