序列模式发现
给定序列数据集 和用户指定的最小支持度阈值 minsup,则序列模式发现的任务是找出支持度大于或等于 minsup 的所有序列。
约 1469 字大约 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=<e1e2e3…en>,其中每个 ej 是一个或多个事件的集族。
<{算法与数据结构, 操作系统导论} {数据库系统, 计算机体系结构} {计算机网络, 软件工程} {计算机图形学, 并行程序设计}>
序列的长度对应序列中的元素个数,包含 k 个事件的序列被称为 k-序列。
子序列。
若通过删去 s 中的一些事件或者删除 s 中的一些元素能推导出 t,则称 t 为 s 的 子序列(subsequence)。形式上讲,如果存在整数 1≤j1<j2<⋯<jm≤n,使得 t1⊆sj1,t2⊆sj2,…,tm⊆sjm,则序列 t=<t1t2…tm> 是序列 s=<s1s2…sn> 的子序列。如果 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 的所有序列。
由于以下的三个原因,相较于候选项集,候选序列的数量是远远多于候选项集的。
下面给出类 Apriori 算法从序列数据集中提取序列模式。
该算法的结构几乎和前面提到的用于频繁项集发现的 Apriori 算法完全一样。该算法迭代产生新的候选 k-序列,剪掉那些子集中有非频繁 (k-1)-序列的候选,然后对留下的候选计数,识别序列模式。
序列的生成和候选项集不同。前面我们通过项集内部的元素使用字典序排序来避免重复产生候选,但是序列本身可能并不符合字典序。合并序列的标准可以用以下过程的形式来表示:
序列 s(1) 与另一个序列 s(2) 合并,仅当从 s(1) 中去掉第一个事件得到的子序列与从 s(2) 中去掉最后一个事件得到的子序列相同。通过如下方式扩展序列 s(1) 来得到候选集:
步骤可见下图:
如果候选 k-序列的 (k-1)-序列至少有一个是非频繁的,那么将它剪掉。
在计算支持度计数期间,算法将识别属于特定数据序列的所有候选 k-序列,并增加其支持度。在对每个数据序列执行该步骤后,算法将识别出频繁 k-序列,并可以丢弃支持度小于最小支持度阈值 minsup 的候选。