文档介绍：序列模式挖掘算法简介
报告人:邓爱林
2001-8-15
1
报告的主要内容
序列模式简介
GSP算法
PrefixSpan算法
2001-8-15
2
一、序列模式简介
序列模式的概念最早是由Agrawal和Srikant 提出的
序列模式定义:给定一个由不同序列组成的集合,其中,每个序列由不同的元素按顺序有序排列,每个元素由不同项目组成,同时给定一个用户指定的最小支持度阈值,序列模式挖掘就是找出所有的频繁子序列,即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值
2001-8-15
3
一、序列模式简介
例子1:在两年前购买了Ford 牌轿车的顾客,很有可能在今年采取贴旧换新的购车行动
例子2:在购买了自行车和购物篮的所有客户中,有70%的客户会在两个月后购买打气筒
2001-8-15
4
一、序列模式简介
应用领域:
客户购买行为模式预测
Web访问模式预测
疾病诊断
自然灾害预测
DNA序列分析
2001-8-15
5
一、序列模式简介
符号化表示:
项目集(Itemset)是各种项目组成的集合
序列(Sequence)是不同项目集(ItemSet)的有序排列,序列s可以表示为s = <s1s2…sl>,sj(1 <= j <= l)为项目集(Itemset),也称为序列s的元素
序列的元素(Element)可表示为(x1x2…xm), xk(1 <= k <= m)为不同的项目,如果一个序列只有一个项目,则括号可以省略
一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列
2001-8-15
6
一、序列模式简介
符号化表示:
设= <a1a2…an>,= <b1b2…bm>,如果存在整数1 <= j1 < j2 <…< jn <= m,使得a1 bj1,a2 bj2,…, an bjn,则称序列为序列的子序列,又称序列包含序列,记为
序列在序列数据库S中的支持数为序列数据库S中包含序列的序列个数,记为Support()
给定支持度阈值,如果序列在序列数据库中的支持数不低于,则称序列为序列模式
长度为l的序列模式记为l-模式
2001-8-15
7
一、序列模式简介
例子:设序列数据库如下图所示,并设用户指定的最小支持度min-support = 2。
Sequence_id
Sequence
10
<a(abc)(ac)d(cf)>
20
<(ad)c(bc)(ae)>
30
<(ef)(ab)(df)cb>
40
<eg(af)cbc>
序列<a(bc)df>是序列<a(abc)(ac)d(cf)>的子序列
序列<(ab)c>是长度为3的序列模式
2001-8-15
8
一、序列模式简介
问题描述:给定序列数据库和最小支持度阈值,序列模式挖掘就是要找出序列数据库中所有的序列模式
系统规定:由于同一个元素中的项目之间排列没有顺序,为了表达的唯一性,我们将同一个元素内部的不同项目按照字典顺序排列
2001-8-15
9
一、序列模式简介
序列模式挖掘的主要算法
GSP(Generalized Sequential Patterns)算法:类似于Apriori算法
PrefixSpan(Prefix-project Sequential Pattern mining)算法:采用分治的思想,不断产生序列数据库的多个更小的投影数据库,然后在各个投影数据库上进行序列模式挖掘
2001-8-15
10