数据仓库与数据挖掘PPT第6章 序列模式挖掘

序列数据是由有序元素或事件的序列组成的，可以 不包括具体的时间概念，序列数据的例子有客户购物序 列、Web点击流和生物学序列等。
大型连锁超市的交易数据有一系列的用户事务数据 库，每一条记录包括用户的ID，事务发生的时间和事务 涉及的项目。如果能在其中挖掘涉及事务间关联关系的 模式，即用户几次购买行为间的联系，可以采取更有针 对性的营销措施。
定义6.1 事件（events）是一个项集，在购物篮例子中，一个事件表示 一个客户在特定商店的一次购物，一次购物可以购买多种商品，所以事件表示 为（x1，x2，…，xq），其中xk（1≤k≤q）是I中的一个项，一个事件中所有项 均不相同，每个事件可以有一个事件时间标识TID，也可以表示事件的顺序。
定义6.2 序列（sequence）是事件的有序列表，序列s记作<e1，e2，…，el>， 其中ej（1≤j≤l）表示事件，也称为s的元素。
序列<{a}，{b,c}, {d}, {f}>是序列 <{a},{a,b,c}, {a,c},{d},{c,f}>的
子序列
Sid
Sequence
10
<a(abc)(ac)d(cf)>
20
<(ad)c(bc)(ae)>
30
<(ef)(ab)(df)cb>
40
<(af)cbc>
定义6.5 如果一个序列s不包含在序列数据库S中的任何 其他序列中，则称序列s为最大序列。
大型网站的网站地图(site map) 往往具有复杂的拓扑结构。用 户访问序列模式的挖掘有助于 改进网站地图的拓扑结构。比 如用户经常访问网页web1然后 访问web2,而在网站地图中二者 距离较远，就有必要调整网站 地图，缩短它们的距离，甚至 直接增加一条链接。
应用案例3：疾病诊断
医疗领域的专家系统可以作为疾病诊断的辅助决策手段。 对应特定的疾病，众多该类病人的症状按时间顺序被记录。 自动分析该纪录可以发现对应此类疾病普适的症状模式。 每种疾病和对应的一系列症状模式被加入到知识库后，专 家系统就可以依此来辅助人类专家进行疾病诊断。
2
………………………………………… ……
3
………………………………………… …………..
4 ………………………………….
图书交易网站将用户 购物纪录整合成用户
购物序列集合
得到用户购物行 为序列模式
相关商品推荐：如 果用户购买了书籍
应用案例2：Web访问模式分析
Index 网站入口
web1 web2
在序列数据库中每个序列的事件在时间或空间上是有序 排列的。
客户号SID
交易时间TID
商品列表（事件）
交 易
s1
数
据
s2
库
D
s3
s4
6月25日 6月30日
6月10日 6月Hale Waihona Puke 5日 6月20日6月25日
6月25日 6月30日 7月25日
30 80
10，20 30
40，60，70
30，50，70
30 40，70
2. 经典的序列模式挖掘算法
（1）候选码生成—测试框架的序列挖掘算法
候选码生成—测试框架基于Apriori理论，即序列模 式的任一子序列也是序列模式，这类算法统称为Aprior 类算法。
例: 通过分析大量曾患A类疾病的病人发病纪录，发 现以下症状发生的序列模式：<(眩晕) (两天后低烧3738度) >
如果病人具有以上症状，则有可能患A类疾病
6.1.1 序列数据库
设I={i1，i2，…，in}是所有项的集合，在购物篮例子 中，每种商品就是一个项。项集是由项组成的一个非空集 合。
第6章 序列模式挖掘
6.1 序列模式挖掘概述 6.2 Apriori类算法 6.3 模式增长框架的序列挖掘算法
• 与关联规则挖掘的区别
• 序列模式是在一组有序的数据列组成的数据集中，经常出现 的那些序列组合构成的模式。
• 序列模式挖掘的对象以及结果都是有序的，即数据集中的每 个序列的条目在时间或空间上是有序排列的，输出的结果也 是有序的。
通常一个序列中的事件有时间先后关系，也就是说，ej（1≤j≤l）出现在ej+1 之前。序列中的事件个数称为序列的长度，长度为k的序列称为k-序列。在有些算 法中，将含有k个项的序列称为k-序列。
定义6.3 序列数据库（sequence databases）S是元组 <SID，s>的集合，其中SID是序列编号，s是一个序列，每个 序列由若干事件构成。
定义6.6 一个序列α的支持度计数是指在整个序列数 据库S中包含α的序列个数。即：
supportS(α)=|{(SID，s)| (SID，s)∈S ∧α是s的子序列}|
其中，|·|表示集合中·出现的次数。若序列α的支持度计数不 小于最小支持度阈值min_sup，则称之为频繁序列，频繁序 列也称为序列模式。
这类数据处理的不是一个时间点上的数据，而是大 量时间点上的数据，因而具有自身的特殊性。
应用案例1：客户购买行为模式分析
B2C电子商务网站可以根据客户购买纪录来分析客 户购买行为模式，从而进行有针对性的营销策略。
ID User transaction sequence
1
………………………………………… ………………..
形式化表述为，序列t=<t1，t2，…，tm>是序列s=<s1，s2，…，sn>的子序列，如 果存在整数1≤j1<j2<…<jm≤n，使得t1 ，t2 ，…，tm 。
如果t是s的子序列，则称t包含在s中。
s j1
s j2
s jm
例子：设序列数据库如下图 所示，并设用户指定的最小 支持度： min-support = 2。
80
s5
6月12日
80
序
客户号 客户序列
列
s1
<{30}，{80}>
数 据 库
s2
<{10，20}，{30}，{40，60，70}>
s3
<{30，50，70}>
S
s4
<{30}，{40，70}，{80}>
s5
<{80}>
定义6.4 对于序列t和s，如果t中每个有序元素都是s中一个有序元素的子集， 则称t是s的子序列。
长度为k的频繁序列称为频繁k-序列。
6.1.2 序列模式挖掘算法
1. 什么是序列模式挖掘
序列模式挖掘的问题定义为：给定一个客户交易数据 库D以及最小支持度阈值min_sup，从中找出所有支持度 计数不小于min_sup的序列，这些频繁序列也称为序列模 式。
有的算法还可以找出最大序列，即这些最大序列构成 序列模式。