数据挖掘序列模式算法

2020/3/291数据挖掘序列模式算法2020/3/292主要内容序列模式挖掘简介序列模式挖掘的应用背景序列模式挖掘算法概述GSP算法PrefixSpan算法Disc-all算法支持约束的序列模式挖掘2020/3/293一、序列模式挖掘简介序列模式的概念最早是由Agrawal和Srikant提出的。动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有针对性的营销措施。2020/3/294事务数据库实例例：一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID2020/3/295序列数据库一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。2020/3/296问题定义项集(Itemset)是所有在序列数据库出现过的单项组成的集合例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID。2020/3/297问题定义元素(Element)可表示为(x1x2…xm)，xk(1=k=m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列．在用户事务数据库里，一个事务就是一个元素。2020/3/298问题定义序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s=s1s2…sl，sj(1=j=l)为序列s的元素一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列2020/3/299例：一条序列(10,20)30(40,60,70)有3个元素，分别是（1020），30，（406070）；3个事务的发生时间是由前到后。这条序列是一个6-序列。2020/3/2910问题定义设序列=a1a2…an，序列=b1b2…bm，ai和bi都是元素。如果存在整数1=j1j2…jn=m，使得a1bj1，a2bj2，…，anbjn，则称序列为序列的子序列，又称序列包含序列，记为。2020/3/2911问题定义序列在序列数据库S中的支持度为序列数据库S中包含序列的序列个数，记为Support()给定支持度阈值，如果序列在序列数据库中的支持数不低于，则称序列为序列模式长度为l的序列模式记为l-模式2020/3/2912例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support=2。SidSequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40(af)cbc序列a(bc)df是序列a(abc)(ac)d(cf)的子序列序列(ab)c是长度为3的序列模式2020/3/2913序列模式VS关联规则问题序列模式挖掘关联规则挖掘数据集序列数据库事务数据库关注点单项间在同一事务内以及事务间的关系单项间在同一事务内的关系2020/3/2914二、序列模式挖掘的应用背景应用领域：客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析2020/3/2915应用案例1：客户购买行为模式分析B2C电子商务网站可以根据客户购买纪录来分析客户购买行为模式，从而进行有针对性的营销策略。IDUsertransactionsequence1…………………………………………………………..2………………………………………………3……………………………………………………..4………………………………….图书交易网站将用户购物纪录整合成用户购物序列集合得到用户购物行为序列模式(“UML语言”)(“Visio2003实用技巧”)相关商品推荐：如果用户购买了书籍“UML语言”,则推荐“Visio2003实用技巧”2020/3/2916应用案例2：Web访问模式分析大型网站的网站地图(sitemap)往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助于改进网站地图的拓扑结构。比如用户经常访问网页web1然后访问web2,而在网站地图中二者距离较远，就有必要调整网站地图，缩短它们的距离，甚至直接增加一条链接。Index网站入口web1web22020/3/2917应用案例3：疾病诊断医疗领域的专家系统可以作为疾病诊断的辅助决策手段。对应特定的疾病，众多该类病人的症状按时间顺序被记录。自动分析该纪录可以发现对应此类疾病普适的症状模式。每种疾病和对应的一系列症状模式被加入到知识库后，专家系统就可以依此来辅助人类专家进行疾病诊断。2020/3/2918应用案例3：疾病诊断例:通过分析大量曾患A类疾病的病人发病纪录，发现以下症状发生的序列模式：(眩晕)(两天后低烧37-38度)如果病人具有以上症状，则有可能患A类疾病2020/3/2919应用案例4：查询扩展查询扩展是搜索领域一个重要的问题。用户提交的查询往往不能完全反映其信息需求。一些研究工作尝试用用户的查询序列模式来辅助原始查询，其主要思想是：1）挖掘用户的查询序列模式2）用这些序列模式构造查询词关系图3）找到每个极大全连通图作为一个”概念”4)对于一个查询，和它同处于一个”概念”的查询可以作为查询扩展的选项2020/3/2920应用案例4：查询扩展给定一组查询模式：(丰田)(雷诺),(宝马)(丰田),(丰田)(宝马),(宝马)(雷诺),(汽车)(丰田)查询关系图如上图：丰田雷诺宝马汽车概念1：汽车品牌概念2：汽车2020/3/2921三、序列模式挖掘算法概述Agrawal和Srikant在提出这个问题时提出了三个算法，AprioriAll，AprioriSome和DynamicSome，它们都基于Apriori框架。构成了序列模式挖掘问题的基石。随后，这个领域的研究工作取得了大量的成果。2020/3/2922序列模式挖掘算法概述类Apriori算法基于划分的模式生长算法基于序列比较的算法2020/3/2923类Apriori算法该类算法基于Apriori理论，即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式，然后计算候选序列模式的支持度。典型的代表有GSP算法,spade算法等。2020/3/2924基于划分的模式生长算法该类算法基于分治的思想，迭代的将原始数据集进行划分，减少数据规模，同时在划分的过程中动态的挖掘序列模式，并将新发现的序列模式作为新的划分元。典型的代表有FreeSpan算法和prefixSpan算法。2020/3/2925基于序列比较的算法该类算法首先定义序列的大小度量，接着从小到大的枚举原始序列数据库中包含的所有k-序列，理论上所有的k-序列模式都能被找到。算法制定特定的规则加快这种枚举过程。典型的代表为Disc-all算法。2020/3/2926四、GSP算法算法思想：类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的数据结构-----哈希树来实现候选模式的快速访存。2020/3/2927GSP算法描述扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集根据长度为i的种子集Li，通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集重复第二步，直到没有新的序列模式或新的候选序列模式产生为止L1C2L2C3L3C4L4……2020/3/2928产生候选序列模式主要分两步：连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中修切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除L1C2L2C3L3C4L4……2020/3/2929候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数L1C2L2C3L3……2020/3/2930哈希树GSP采用哈希树存储候选序列模式。哈希树的节点分为三类：1、根节点；2、内部节点；3、叶子节点。2020/3/2931哈希树根节点和内部节点中存放的是一个哈希表，每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。例：2020/3/2932添加候选序列模式从根节点开始，用哈希函数对序列的第一个项目做映射来决定从哪个分支向下，依次在第n层对序列的第n个项目作映射来决定从哪个分支向下，直到到达一个叶子节点。将序列储存在此叶子节点。初始时所有节点都是叶子节点，当一个叶子节点所存放的序列数目达到一个阈值，它将转化为一个内部节点。2020/3/2933计算候选序列模式的支持度给定一个序列s是序列数据库的一个记录：1）对于根节点，用哈希函数对序列s的每一个单项做映射来并从相应的表项向下迭代的进行操作2）。2020/3/2934计算候选序列模式的支持度2）对于内部节点，如果s是通过对单项x做哈希映射来到此节点的，则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射，然后从相应的表项向下迭代做操作2）或3）。2020/3/2935计算候选序列模式的支持度（3）对一个叶子节点，检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。这种计算候选序列的支持度的方法避免了大量无用的扫描，对于一条序列，仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量，m表示候选序列模式的数量，t代表哈希树叶子节点的最大容量2020/3/2936例：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruning(1,2)3(1,2)(3,4)(1,2)(3,4)(1,2)4(1,2)351(3,4)(1,3)52(3,4)2352020/3/2937GSP算法存在的主要问题如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式需要对序列数据库进行循环扫描对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理2020/3/2938五、PrefixSpan算法算法思想：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘2020/3/2939相关定义前缀：设每个元素中的所有项目按照字典序排列。给定序列=e1e2…en，=e1’e2’…em’(mn)，如果ei’=ei(im-1)，em’em，并且(em-em’)中的项目均在em’中项目的后面，则称是的前缀例：序列(ab)是序列(abd)(acd)的一个前缀；序列(ad)则不是。2020/3/2940相关定义投影：给定序列和，如果是的子序列，则关于的投影’必须满足：是’的前缀，’是的满足上述条件的最大子序列例：对于序列=(ab)(acd)，其子序列=(b)的投影是’=(b)(acd);(ab)的投影是原序列(ab)(acd)。2020/3/2941相关定义后缀：序列关于子序