序列模式挖掘概述

序列模式最早来源于零售业，购物篮数据常常包含关于商品何时被顾客购买的时间信息，可以使用这种信息，将顾客在一段时间内的购物拼接成事务序列，这些事务通常基于时间或空间的先后次序。

序列模式(sequential pattern)的概念最早是由Agrawal和Srikant提出的，最初的动机是针对带有交易时间属性的交易数据库，通过找出频繁序列以发现某一时间段内客户的购买活动规律。

序列模式分析旨在寻找事件间在顺序上的相关性。

例子：ü凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒 。

   ü两年前购买了Ford 牌轿车的顾客，很可能在今年采取贴旧换新的购车行动。

   ü购买了自行车的客户中，70%的客户会在两个月后购买打气筒。

序列数据是由有序元素或事件的序列组成的，可以不包括具体的时间概念，序列数据的例子有客户购物序列、Web点击流和生物学序列等。

这类数据处理的不是一个时间点上的数据，而是大量时间点上的数据，因而具有自身的特殊性。

一、序列数据库

设I={i1，i2，…，in}是所有项的集合，在购物篮例子中，每种商品就是一个项。项集是由项组成的一个非空集合，是多个物品组成的集合，内部元素不分排列顺序，比如“枕头和枕头套”就可以看作是由两个项(item)组成的项集 。

定义6.1  事件（events）是一个项集，在购物篮例子中，一个事件表示一个客户在特定商店的一次购物，一次购物可以购买多种商品，所以事件表示为（x1，x2，…，xq），其中xk（1≤k≤q）是I中的一个项，一个事件中所有项均不相同，每个事件可以有一个事件时间标识TID，也可以表示事件的顺序。

定义6.2  序列（sequence）是事件的有序列表，序列s记作<e1，e2，…，el>，其中ej（1≤j≤l）表示事件，也称为s的元素。如

 lweb站点访问者访问的web页面序列：<{主页} {电子产品} {照相机和摄像机} {数码相机} {购物车} {订购确认} {返回购物}>

 l计算机科学主修课程序列：<{算法与数据结构， 操作系统引论} {数据库系统， 计算机体系结构} {计算机网络， 软件工程} {计算机图形学， 并行程序设计}>

通常一个序列中的事件有时间先后关系，也就是说，ej（1≤j≤l）出现在ej+1之前。

此外，序列可以用它的长度和出现时间个数刻画，序列的长度对应于出现序列中的元素个数，k-序列是包含k个事件的序列。上面例子中web序列包含7个元素和7个事件，课程序列包含4个元素和8个事件。

定义6.3  序列数据库（sequence databases）S是元组<SID，s>的集合，其中SID是序列编号，s是一个序列，每个序列由若干事件构成。

　　在序列数据库中每个序列的事件在时间或空间上是有序排列的。

定义6.4   对于序列t和s，如果t中每个有序元素都是s中一个有序元素的子集，则称t是s的子序列。

　　形式化表述为，序列t=<t1，t2，…，tm>是序列s=<s1，s2，…，sn>的子序列，如果存在整数1≤j1<j2<…<jm≤n，使得t1Í，t2Í，…，tmÍ。

　　如果t是s的子序列，则称t包含在s中。

   n例：序列<{2},{1.3} >是序列<{1,2},{5}, {1,3,4} >的子序列，因为{2}包含在{1,2}中, {1.3}包含在{1,3,4}中，而<{2,5},{3} >不是<{1,2},{5}, {1,3,4} >的子序列，因为前者中项2和项5是一次性购买，后者中项2和项5是先后购买的，这就是区别。

定义6.5   如果一个序列s不包含在序列数据库S中的任何其他序列中，则称序列s为最大序列。

定义6.6   给定序列数据库SD，序列模式α。一个序列α的支持度计数是指在整个序列数据库SD中包含α的序列个数，记为Count(α)。Count(α)所占的百分比称为α的支持度，记为sup(α)。即：sup(α)= Count(α) /|SD|

      其中，|·|表示集合中·出现的次数。若序列α的支持度计数不小于最小支持度阈值min_sup，则称之为频繁序列，频繁序列也称为序列模式。

　　长度为k的频繁序列称为频繁k-序列。

二、序列模式挖掘

序列模式的挖掘任务是：给定序列数据库SD和最小支持度阙值minsup，找出SD中所有的频繁序列模式，这些频繁序列模式的支持度不小于min_sup。

  n序列模式挖掘问题描述ü输入–对于序列数据库D:•I={i1, i2,…,in}是所有项目的集合•每个序列都是按时间排列的一组交易•每个交易包含以下字段:sequence-id, transaction-id, transaction-timeand a set of items.ü问题–找到满足最小支持度的所有序列模式

n主要算法

  n类Apriori算法:GSP(Generalized Sequential Patterns)：

  n基于模式增长（Pattern-Growth-based ）的算法:PrefixSpan&FreeSpan