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

序列模式挖掘

序列模式挖掘(sequence pattern mining)是数据挖掘的内容之一，指挖掘相对时间或其他模式出现频率高的模式，典型的应用还是限于离散型的序列。。

其涉及在数据示例之间找到统计上相关的模式，其中数据值以序列被递送。通常假设这些值是离散的，因此与时间序列挖掘是密切相关的，但时间通常被认为是不同的活动。序列模式挖掘是结构化数据挖掘的一种特殊情况。

基础概念

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

例如，一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID

一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。

序列(Sequence)

通常以SID表示，一个序列即是一个完整的信息流。每个序列由不同的元素按顺序有序排列，每个元素由不同项目（或者也可以称之为事件）组成，

让我们将其符号化

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

3个事务的发生时间是由前到后。其中项目10和项目20是同时发生的，所以处在同一个元素中。这条序列是一个6-序列。

子序列(Subsequence)

设序列
α=<a1a2…an>
，序列
β=<b1b2…bm>
，
ai
和
bi
都是元素。如果存在整数序列
J
有
1≤j1<j2<…<jn≤m
，使得
a1?bj1
，
a2?bj2
，
…
，
an?bjn
，则称序列
α
为序列
β
的子序列，又称序列
β
包含序列
α
，记为
α?β
。

支持度

序列
α
在序列数据库S中的支持度为序列数据库S中包含序列支持度的序列个数，记为Support(
α
)。

给定最小支持度阈值
ξ
，如果序列
α
在序列数据库中的支持数不低于
ξ
，则称序列
α
为序列模式。

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

序列模式挖掘：找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于最小支持度阈值。

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

序列
<a(bc)df>
是序列
<a(abc)(ac)d(cf)>
的子序列。

序列
<(ab)c>
是长度为3的序列模式，
<a(abc)(ac)d(cf)>
中出现了2次，
<(ad)c(bc)(ae)>
出现了一次。