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

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

预备知识

对象	时间戳	事件
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：序列数据举例

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}> | 是 |

   表 7.2：子序列概念例子

序列模式发现

设 $D$ 是包含一个或多个 **数据序列 ( data sequence ) ** 的数据集。数据序列是指与单个数据对象相关联的事件的有序列表。例如 表 5.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 的候选。

贡献者

dingyuqi

更新日志

2025/8/5 08:34

查看所有更新日志

• eb6eb-improve(docs): use pangu formatter于 2025/8/5
• 86b59-improve(docs): use new table grammar于 2025/8/4
• 2185e-improve(docs): use chinese punctuation于 2025/3/6
• fea7c-improve(docs): delete extra whitespace and blank lines于 2025/1/21
• c1c02-modify(docs): remanage folders and rename files于 2024/12/17
• 8b943-docs: update docs于 2024/12/2
• d201e-docs: update docs于 2024/11/22
• c5b52-docs: update docs于 2024/11/18
• b63e9-docs: update docs于 2024/11/18

版权所有

版权归属：dingyuqi

许可证：署名-非商业性-禁止演绎 4.0 国际 (CC-BY-NC-ND-4.0)