序列模式挖掘算法

《序列模式挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章序列模式挖掘算法9/17/20211主要内容序列模式挖掘简介序列模式挖掘的应用背景序列模式挖掘算法概述GSP算法PrefixSpan算法Disc-all算法支持约束的序列模式挖掘9/17/20212一、序列模式挖掘简介序列模式的概念最早是由Agrawal和Srikant提出的。动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有针对性的营销措施。9/17/20213事务数据库实例例：一个事务数

2、据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID9/17/20214序列数据库一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。9/17/20215问题定义项集(Itemset)是所有在序列数据库出现过的单项组成的集合例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID。9/17/20216问题定义元素(Element)可表

3、示为(x1x2…xm)，xk(1<=k<=m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列．在用户事务数据库里，一个事务就是一个元素。9/17/20217问题定义序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s=，sj(1<=j<=l)为序列s的元素一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列9/17/20218例：一条序列<(10,20)30(40,60,70)>有3个元素，分别是（1020），30，（406070）；3个事务的发生时

4、间是由前到后。这条序列是一个6-序列。9/17/20219问题定义设序列=，序列=，ai和bi都是元素。如果存在整数1<=j1

5、202111例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support=2。SidSequence1020<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>序列是序列的子序列序列<(ab)c>是长度为3的序列模式9/17/202112序列模式VS关联规则问题序列模式挖掘关联规则挖掘数据集序列数据库事务数据库关注点单项间在同一事务内以及事务间的关系单项间在同一事务内的关系9/17/202113二、序列

6、模式挖掘的应用背景应用领域：客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析9/17/202114应用案例1：客户购买行为模式分析B2C电子商务网站可以根据客户购买纪录来分析客户购买行为模式，从而进行有针对性的营销策略。IDUsertransactionsequence1…………………………………………………………..2………………………………………………3……………………………………………………..4………………………………….图书交易网站将用户购物纪录整合成用户购物序列集合得到用户购物行为序列模式<(“UML语

7、言”)(“Visio2003实用技巧”)>相关商品推荐：如果用户购买了书籍“UML语言”,则推荐“Visio2003实用技巧”9/17/202115应用案例2：Web访问模式分析大型网站的网站地图(sitemap)往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助于改进网站地图的拓扑结构。比如用户经常访问网页web1然后访问web2,而在网站地图中二者距离较远，就有必要调整网站地图，缩短它们的距离，甚至直接增加一条链接。Index网站入口web1web29/17/202116应用案例3：疾病诊断医疗领域的专家系统可以作为疾病诊断的辅助决策

8、手段。对应特定的疾病，众多该类病人的症状按时间顺序被记录。自动分析该纪录可以发现对应此类疾病普适的症状模式。每种疾病和对应的一系列症状模式被加入到知识库后，专家系统就可以依此来辅助人类专家进行