1、第 4章 序列模式挖掘算法* 1主要内容n 序列模式挖掘简介n 序列模式挖掘的应用背景n 序列模式挖掘算法概述n GSP算法n PrefixSpan算法n Disc-all算法n 支持约束的序列模式挖掘Date 2一、序列模式挖掘简介n 序列模式的概念最早是由 Agrawal和 Srikant 提出的。n 动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的 ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有针对性的营销措施。Date 3事务数据库实例n 例：一个事务数据库，一个事务代表一笔交易，一个单
2、项代表交易的商品，单项属性中的数字记录的是商品 IDDate 4序列数据库n 一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户 ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。Date 5问题定义n 项集 (Itemset)是所有在序列数据库出现过的单项组成的集合n 例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的 ID，在数据库中记录的是单项的 ID。Date 6问题定义 元素 (Element)可表示为 (x1x2 xm)， xk(1 ， sj(1 有 3个元素，分别是（ 10 20）， 30，（ 40 60 70 ）；n 3个事务的发生时间是由前到后。这条序列是一个 6-序列。Date 9问题定义 设序列 = ，序列 = ， ai 和 bi都是元素。如果存在整数 1 = j1 j2 jn = m， 使得 a1 bj1， a2 bj2， ， an bjn， 则称序列 为序列 的 子序列 ，又称序列 包含序列 ，记为 。Date 10
