序列模式挖掘算法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《序列模式挖掘算法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 序列 模式 挖掘 算法 课件
- 资源描述:
-
1、第4章 序列模式挖掘算法8/12/20221第1页,共92页。主要内容n序列模式挖掘简介n序列模式挖掘的应用背景n序列模式挖掘算法概述nGSP算法nPrefixSpan算法nDisc-all算法n支持约束的序列模式挖掘8/12/20222第2页,共92页。一、序列模式挖掘简介n序列模式的概念最早是由Agrawal和Srikant 提出的。n动机:大型连锁超市的交易数据有一系列的用户事务数据库,每一条记录包括用户的ID,事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式,即用户几次购买行为间的联系,可以采取更有针对性的营销措施。8/12/20223第3页,共92页。事务数据
2、库实例n例:一个事务数据库,一个事务代表一笔交易,一个单项代表交易的商品,单项属性中的数字记录的是商品ID8/12/20224第4页,共92页。序列数据库n一般为了方便处理,需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并,有时每个事务的发生时间可以忽略,仅保持事务间的偏序关系。8/12/20225第5页,共92页。问题定义n项集(Itemset)是所有在序列数据库出现过的单项组成的集合n例:对一个用户购买记录的序列数据库来说,项集包含用户购买的所有商品,一种商品就是一个单项。通常每个单项有一个唯一的ID,在数据库中记录的是单项的ID。8/12/20226第6页,共92页。问题定义
3、元素(Element)可表示为(x1x2xm),xk(1=k=m)为不同的单项。元素内的单项不考虑顺序关系,一般默认按照ID的字典序排列在用户事务数据库里,一个事务就是一个元素。8/12/20227第7页,共92页。问题定义序列(Sequence)是不同元素(Element)的有序排列,序列s可以表示为s=,sj(1=j=l)为序列s的元素 一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列8/12/20228第8页,共92页。n例:一条序列有3个元素,分别是(10 20),30,(40 60 70);n3个事务的发生时间是由前到后。这条 序列是一个6-序列。8/12/20
4、229第9页,共92页。问题定义设序列=,序列=,ai 和bi都是元素。如果存在整数1=j1 j2 jn=m,使得a1 bj1,a2 bj2,an bjn,则称序列为序列的子序列,又称序列包含序列,记为 。8/12/202210第10页,共92页。问题定义序列在序列数据库S中的支持度为序列数据库S中包含序列的序列个数,记为Support()给定支持度阈值,如果序列在序列数据库中的支持数不低于,则称序列为序列模式长度为l的序列模式记为l-模式8/12/202211第11页,共92页。n例子:设序列数据库如下图所示,并设用户指定的最小支持度min-support=2。SidSequence1020
5、3040l序列是序列的子序列l序列是长度为3的序列模式8/12/202212第12页,共92页。序列模式 VS 关联规则 问题序列模式挖掘 关联规则挖掘数据集序列数据库事务数据库关注点单项间在同一事务内以及事务间的关系单项间在同一事务内的关系8/12/202213第13页,共92页。二、序列模式挖掘的应用背景n应用领域:客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析8/12/202214第14页,共92页。nB2C电子商务网站可以根据客户购买纪录来分析客户购买行为模式,从而进行有针对性的营销策略。IDUser transaction sequence1.23.4.图书
6、交易网站将用户购物纪录整合成用户购物序列集合得到用户购物行为序列模式相关商品推荐:如果用户购买了书籍“UML语言”,则推荐“Visio2003实用技巧”8/12/202215第15页,共92页。n大型网站的网站地图(site map)往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助于改进网站地图的拓扑结构。比如用户经常访问网页web1然后访问web2,而在网站地图中二者距离较远,就有必要调整网站地图,缩短它们的距离,甚至直接增加一条链接。Index 网站入口web1web28/12/202216第16页,共92页。n医疗领域的专家系统可以作为疾病诊断的辅助决策手段。对应特定的疾病,众多该类病
7、人的症状按时间顺序被记录。自动分析该纪录可以发现对应此类疾病普适的症状模式。每种疾病和对应的一系列症状模式被加入到知识库后,专家系统就可以依此来辅助人类专家进行疾病诊断。8/12/202217第17页,共92页。n例:通过分析大量曾患A类疾病的病人发病纪录,发现以下症状发生的序列模式:n如果病人具有以上症状,则有可能患A类疾病8/12/202218第18页,共92页。n查询扩展是搜索领域一个重要的问题。用户提交的查询往往不能完全反映其信息需求。一些研究工作尝试用用户的查询序列模式来辅助原始查询,其主要思想是:n1)挖掘用户的查询序列模式n2)用这些序列模式构造查询词关系图n3)找到每个极大全连
8、通图作为一个”概念”n4)对于一个查询,和它同处于一个”概念”的查询可以作为查询扩展的选项8/12/202219第19页,共92页。n给定一组查询模式:,查询关系图如上图:丰田雷诺宝马汽车概念1:汽车品牌概念2:汽车8/12/202220第20页,共92页。三、序列模式挖掘算法概述nAgrawal和Srikant在提出这个问题时提出了三个算法,AprioriAll,AprioriSome 和DynamicSome,它们都基于Apriori框架。构成了序列模式挖掘问题的基石。随后,这个领域 的研究工作取得了大量的成果。8/12/202221第21页,共92页。序列模式挖掘算法概述n类Aprior
9、i算法n基于划分的模式生长算法n基于序列比较的算法8/12/202222第22页,共92页。类Apriori算法该类算法基于Apriori理论,即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式,然后计算候选序列模式的支持度。典型的代表有GSP算法,spade算法等。8/12/202223第23页,共92页。基于划分的模式生长算法n该类算法基于分治的思想,迭代的将原始数据集进行划分,减少数据规模,同时在划分的过程中动态的挖掘序列模式,并将新发现的序列模式作为新的划分元。典型的代表有FreeSpan算法和prefixSpan算法。8/12/202224
10、第24页,共92页。基于序列比较的算法n该类算法首先定义序列的大小度量,接着从小到大的枚举原始序列数据库中包含的所有k-序列,理论上所有的k-序列模式都能被找到。算法制定特定的规则加快这种枚举过程。典型的代表为Disc-all算法。8/12/202225第25页,共92页。四、GSP算法算法思想:类似于Apriori算法,采用冗余候选模式的剪除策略和特殊的数据结构-哈希树来实现候选模式的快速访存。8/12/202226第26页,共92页。GSP算法描述n扫描序列数据库,得到长度为1的序列模式L1,作为初始的种子集n根据长度为i 的种子集Li,通过连接操作和修剪操作生成长度为i+1的候选序列模式
11、Ci+1;然后扫描序列数据库,计算每个候选序列模式的支持度,产生长度为i+1的序列模式Li+1,并将Li+1作为新的种子集n重复第二步,直到没有新的序列模式或新的候选序列模式产生为止L1 C2 L2 C3 L3 C4 L4 8/12/202227第27页,共92页。n产生候选序列模式主要分两步:n连接阶段:如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同,则可以将s1与s2进行连接,即将s2的最后一个项目添加到s1中n修切阶段:若某候选序列模式的某个子序列不是序列模式,则此候选序列模式不可能是序列模式,将它从候选序列模式中删除L1 C2 L2 C3 L3 C4
12、L4 8/12/202228第28页,共92页。n候选序列模式的支持度计算:对于给定的候选序列模式集合C,扫描序列数据库,对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式,并增加其支持度计数L1 C2 L2 C3 L3 8/12/202229第29页,共92页。哈希树nGSP采用哈希树存储候选序列模式。哈希树的节点分为三类:1、根节点;2、内部节点;3、叶子节点。8/12/202230第30页,共92页。哈希树n根节点和内部节点中存放的是一个哈希表,每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。n例:8/12/202231第31页,共92页。添加候选序列模式
13、n从根节点开始,用哈希函数对序列的第一个项目做映射来决定从哪个分支向下,依次在第n层对序列的第n个项目作映射来决定从哪个分支向下,直到到达一个叶子节点。将序列储存在此叶子节点。n初始时所有节点都是叶子节点,当一个叶子节点所存放的序列数目达到一个阈值,它将转化为一个内部节点。8/12/202232第32页,共92页。计算候选序列模式的支持度n给定一个序列s是序列数据库的一个记录:1)对于根节点,用哈希函数对序列s的每一个单项做映射来并从相应的表项向下迭代的进行操作 2)。8/12/202233第33页,共92页。计算候选序列模式的支持度 2)对于内部节点,如果s是通过对单项x做哈希映射来到此节点
14、的,则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射,然后从相应的表项向下迭代做操作 2)或 3)。8/12/202234第34页,共92页。计算候选序列模式的支持度n(3)对一个叶子节点,检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。n这种计算候选序列的支持度的方法避免了大量无用的扫描,对于一条序列,仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量,m表示候选序列模式的数量,t代表哈希树叶子节点的最大容量8/12/202235第35页,共92页。n例:下图演示
15、了如何从长度为3的序列模式产生长度为4的候选序列模式Sequential patternsWith length 3Candidate 4-SequencesAfter JoinAfter Pruning8/12/202236第36页,共92页。GSP算法存在的主要问题n如果序列数据库的规模比较大,则有可能会产生大量的候选序列模式n需要对序列数据库进行循环扫描n对于序列模式的长度比较长的情况,由于其对应的短的序列模式规模太大,本算法很难处理8/12/202237第37页,共92页。五、PrefixSpan算法算法思想:采用分治的思想,不断产生序列数据库的多个更小的投影数据库,然后在各个投影数据
16、库上进行序列模式挖掘8/12/202238第38页,共92页。相关定义前缀:设每个元素中的所有项目按照字典序排列。给定序列=,=(m n),如果ei=ei(i m-1),em em,并且(em-em)中的项目均在em中项目的后面,则称是的前缀例:序列 是序列 的一个前缀;序列则不是。8/12/202239第39页,共92页。相关定义投影:给定序列和,如果是的子序列,则关于的投影必须满足:是的前缀,是的满足上述条件的最大子序列例:对于 序列=,其子序列 =的投影是=;的投影是原序列。8/12/202240第40页,共92页。相关定义后缀:序列关于子序列=的投影为=(n=m),则序列关于子序列的后
17、缀为,其中em”=(em-em)n例:对于 序列,其子序列的投影是,则对于的后缀为。8/12/202241第41页,共92页。n例:a(ab)a(abc)8/12/202242第42页,共92页。相关定义n投影数据库:设为序列数据库S中的一个序列模式,则的投影数据库为S中所有以为前缀的序列相对于的后缀,记为S|n投影数据库中的支持度:设为序列数据库S中的一个序列,序列以为前缀,则在的投影数据库S|中的支持度为S|中满足条件 .的序列的个数8/12/202243第43页,共92页。算法描述n扫描序列数据库,生成所有长度为1的序列模式n根据长度为1的序列模式,生成相应的投影数据库n在相应的投影数据
18、库上重复上述步骤,直到在相应的投影数据库上不能产生长度为1的序列模式为止n分别对不同的投影数据库重复上述过程,直到没有新的长度为1的序列模式产生为止SS1SmS11 S1n Sm1 Smp 8/12/202244第44页,共92页。n例:对于如下的序列数据库生成一系列的投影数据库SidSequence102030408/12/202245第45页,共92页。n扫描序列数据库S,产生长度为1的序列模式有::4,:4,:4,:3,:3,:3n序列模式的全集必然可以分为分别以,和为前缀的序列模式的集合,构造不同前缀所对应的投影数据库,结果如下页图所示8/12/202246第46页,共92页。Pref
展开阅读全文