数据挖掘中的模式发现（六）挖掘序列模式

序列模式挖掘

序列模式挖掘（sequence pattern mining）作为数据挖掘的一个重要范畴，在研究基于时间或其他属性的频繁出现特定序列方面具有重要作用。其主要目标在于发现基于时间或其他属性出现频率较高的特定序列，并其典型应用仍局限于离散型数据序列中。

其涉及在数据实例之间识别具有统计学关联的模式，在这些数值按序列传递的过程中进行分析研究。为了便于分析处理，在此问题中将数值类型假定为离散型变量更为合理，并因此与基于时间序列的数据挖掘密切相关。然而，在此问题中将时间段视为独立事件更为合理的情况下，则属于另一种特定分析范畴。基于序列的数据挖掘是一种特殊的结构化数据分析方法

基础概念

为了帮助大家理解，我这里讲序列是如何产生的稍微描述一下。

该事务数据库系统中包含多个事务实例，默认情况下每个事务实例对应一次完整的交易操作。其中每个订单单元对应的商品信息由其数值字段存储该商品的唯一标识符

通常情况下，在处理复杂事务时会采用序列化的方法来简化操作流程。具体来说，在处理过程中会将数据库转换为序列数据库，并将具有相同用户ID的记录进行合并处理。通常情况下可以忽略每个事务的时间信息，并仅保留事务之间的顺序关系

序列(Sequence)

常用符号SID来表示一个序列；一个序列即代表完整的信息流；每个序列中的各个元素按照一定顺序依次排列；而其中每一个具体的位置则包含多个项目（亦可称为事件）。

让我们将其符号化

例：一条序列<(10,20)30(40,60,70)>有3个元素，分别是(10,20)，30，(40,60,70)；

3个事务按照时间顺序依次发生。在项目10和项目20同时发生的条件下，则被归入同一个元素中。这个序列是一个6-序列。

子序列(Subsequence)

设集合A = {x | x满足某种特定属性}, 令集合B = {y | y满足另一种属性}. 其中,a_i与b_i分别代表A与B中的对象. 如果存在一个整数索引集K={k₁,k₂,…,k_n}满足以下条件:对于每个i=1,2,…,n都有a_i包含于对应的b_{k_i}中，则称集合A为集合B的一个子集（即包含于），记作A ⊆ B.

支持度

在序列数据库S中定义的支持度被称为Support()（即表示）

设定一个最小的支持度阈值\xi，当序列在序列数据库中的支持数至少达到该阈值时，则该序列为序列模式。

长度为l的序列模式记为l-模式。

基于上述方法的序列数据挖掘过程：识别出所有满足最低支持度要求的关键模式

例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2。

序列\text{$id=Element-22\}$相对于\text{$id=Element-23\}$来说是一个子序列。

字符串$&lt;(ab)c&gt;$是长度为3的序列模式，并且该模式在其中仅包含两次。字符串仅包含一次。字符串$&lt;(ad)c(bc)(ae)&gt;$也仅包含一次。