第4章序列模式挖掘算法 2021/8/25
2021/8/25 1 第4章 序列模式挖掘算法
主要内容 序列模式挖掘简介 序列模式挖掘的应用背景 序列模式挖掘算法概述 ■GSP算法 PrefiX Span算法 Disc-a算法 ■支持约束的序列模式挖掘 2021/8/25
2021/8/25 2 主要内容 ◼ 序列模式挖掘简介 ◼ 序列模式挖掘的应用背景 ◼ 序列模式挖掘算法概述 ◼ GSP算法 ◼ PrefixSpan算法 ◼ Disc-all算法 ◼ 支持约束的序列模式挖掘
序列模式挖掘简介 序列模式的概念最早是由 Agrawal和 Srikant提出 的。 ■动机:大型连锁超市的交易数据有一系列的用户事 务数据库,每一条记录包括用户的ID,事务发生的 时间和事务涉及的项目。如果能在其中挖掘涉及事 务间关联关系的模式,即用户几次购买行为间的联 系,可以采取更有针对性的营销措施。 2021/8/25
2021/8/25 3 一、序列模式挖掘简介 ◼ 序列模式的概念最早是由Agrawal和Srikant 提出 的。 ◼ 动机：大型连锁超市的交易数据有一系列的用户事 务数据库，每一条记录包括用户的ID，事务发生的 时间和事务涉及的项目。如果能在其中挖掘涉及事 务间关联关系的模式，即用户几次购买行为间的联 系，可以采取更有针对性的营销措施
事务数据库实例 例:一个事务数据库,一个事务代表一笔交易,一个 单项代表交易的商品,单项属性中的数字记录的是商 品ID Customer Id I Transaction Time T Items Bought June 25 93 June 30 93 90 June 10 93 10,20 June 15 93 30 June 20 93 40,60,70 3 June 25 93 30.50 June 25 93 30 June 30 93 40,70 Jul25"93 90 5 June 12 93 90 2021/8/25
2021/8/25 4 事务数据库实例 ◼ 例：一个事务数据库，一个事务代表一笔交易，一个 单项代表交易的商品，单项属性中的数字记录的是商 品ID
序列数据库 一般为了方便处理,需要把数据库转化为序列 数据库。方法是把用户ID相同的记录合并,有 时每个事务的发生时间可以忽略,仅保持事务 间的偏序关系 C'ustomer Id Customer Sequence ((30)(90) 2345 (1020)(30)(406070) (305070) ((30)(4070)(90)) ((90) 2021/8/25 5
2021/8/25 5 序列数据库 ◼ 一般为了方便处理，需要把数据库转化为序列 数据库。方法是把用户ID相同的记录合并，有 时每个事务的发生时间可以忽略，仅保持事务 间的偏序关系
问题定义 项集 teaset)是所有在序列数据库出现过的单 项组成的集合 例:对一个用户购买记录的序列数据库来说, 项集包含用户购买的所有商品,一种商品就是 一个单项。通常每个单项有一个唯一的I,在 数据库中记录的是单项的ID 2021/8/25 6
2021/8/25 6 问题定义 ◼ 项集(Itemset)是所有在序列数据库出现过的单 项组成的集合 ◼ 例：对一个用户购买记录的序列数据库来说， 项集包含用户购买的所有商品，一种商品就是 一个单项。通常每个单项有一个唯一的ID，在 数据库中记录的是单项的ID
问题定义 元素( Element)可表示为x1x2xn),x(1<=k <=m)为不同的单项。元素内的单项不考虑顺 序关系,一般默认按照D的字典序排列 在用户事务数据库里,一个事务就是一个元素。 2021/8/25
2021/8/25 7 问题定义 ▪ 元素(Element)可表示为(x1x2…xm)， xk (1 <= k <= m)为不同的单项。元素内的单项不考虑顺 序关系，一般默认按照ID的字典序排列． ▪ 在用户事务数据库里，一个事务就是一个元素
问题定义 序列 Sequence)是不同元素 Element)的有序排 列,序列s可以表示为s=<>,s(1<=j <=1)为序列s的元素 一个序列包含的所有单项的个数称为序列的长 度。长度为-序列记为l序列 2021/8/25
2021/8/25 8 问题定义 ▪ 序列(Sequence)是不同元素(Element)的有序排 列，序列s可以表示为s = ，sj (1 <= j <= l)为序列s的元素 ▪ 一个序列包含的所有单项的个数称为序列的长 度。长度为l的序列记为l-序列
例:一条序列有3个元 素,分别是(1020),30,(406070) 3个事务的发生时间是由前到后。这条 序列是一个6-序列 2021/8/25
2021/8/25 9 ◼ 例：一条序列有3个元 素，分别是（10 20），30，（40 60 70 ）； ◼ 3个事务的发生时间是由前到后。这条 序列是一个6-序列
问题定义 设序列=,序列β=<bb 和b都是元素。如果存在整数1<=j<j2<.<jn m,使得a1sba2sb2,…, anc bin,则 称序列为序列β的子序列,又称序列β包含序 列a,记为a≤β 2021/8/25
2021/8/25 10 问题定义 ▪ 设序列 = ，序列 = ，ai 和bi都是元素。如果存在整数1 <= j1 < j2 <…< jn <= m，使得a1 bj1，a2 bj2，…， an bjn，则 称序列为序列的子序列，又称序列包含序 列，记为