序列模式挖掘算法幻灯片.ppt

《序列模式挖掘算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《序列模式挖掘算法幻灯片.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、序列模式挖掘算法2023/4/101第1页，共92页，编辑于2022年，星期六主要内容n序列模式挖掘简介n序列模式挖掘的应用背景n序列模式挖掘算法概述nGSP算法nPrefixSpan算法nDisc-all算法n支持约束的序列模式挖掘2023/4/102第2页，共92页，编辑于2022年，星期六一、序列模式挖掘简介n序列模式的概念最早是由Agrawal和Srikant 提出的。n动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有针对性的营销措施。202

2、3/4/103第3页，共92页，编辑于2022年，星期六 事务数据库实例n例：一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID2023/4/104第4页，共92页，编辑于2022年，星期六 序列数据库n一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。2023/4/105第5页，共92页，编辑于2022年，星期六 问题定义n项集(Itemset)是所有在序列数据库出现过的单项组成的集合n例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就

3、是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID。2023/4/106第6页，共92页，编辑于2022年，星期六 问题定义n元素(Element)可表示为(x1x2xm)，xk(1=k=m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列在用户事务数据库里，一个事务就是一个元素。2023/4/107第7页，共92页，编辑于2022年，星期六 问题定义序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s=，sj(1=j=l)为序列s的元素 一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列2023/4/

4、108第8页，共92页，编辑于2022年，星期六 n例：一条序列有3个元素，分别是（10 20），30，（40 60 70）；n3个事务的发生时间是由前到后。这条 序列是一个6-序列。2023/4/109第9页，共92页，编辑于2022年，星期六 问题定义设序列=，序列=，ai 和bi都是元素。如果存在整数1=j1 j2 jn=m，使得a1 bj1，a2 bj2，an bjn，则称序列为序列的子序列，又称序列包含序列，记为 。2023/4/1010第10页，共92页，编辑于2022年，星期六 问题定义序列在序列数据库S中的支持度为序列数据库S中包含序列的序列个数，记为Support()给定支持

5、度阈值，如果序列在序列数据库中的支持数不低于，则称序列为序列模式长度为l的序列模式记为l-模式2023/4/1011第11页，共92页，编辑于2022年，星期六 n例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support=2。SidSequence10203040n序列是序列的子序列n序列是长度为3的序列模式2023/4/1012第12页，共92页，编辑于2022年，星期六序列模式 VS 关联规则 问题序列模式挖掘关联规则挖掘数据集序列数据库事务数据库关注点单项间在同一事务内以及事务间的关系单项间在同一事务内的关系2023/4/1013第13页，共92页，编辑于2022年，

6、星期六二、序列模式挖掘的应用背景n应用领域：客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析2023/4/1014第14页，共92页，编辑于2022年，星期六应用案例1：客户购买行为模式分析nB2C电子商务网站可以根据客户购买纪录来分析客户购买行为模式，从而进行有针对性的营销策略。IDUser transaction sequence1.23.4.图书交易网站将用户购物纪录整合成用户购物序列集合得到用户购物行为序列模式相关商品推荐：如果用户购买了书籍“UML语言”,则推荐“Visio2003实用技巧”2023/4/1015第15页，共92页，编辑于2022年，星期六应用

7、案例2：Web访问模式分析n大型网站的网站地图(site map)往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助于改进网站地图的拓扑结构。比如用户经常访问网页web1然后访问web2,而在网站地图中二者距离较远，就有必要调整网站地图，缩短它们的距离，甚至直接增加一条链接。Index 网站入口web1web22023/4/1016第16页，共92页，编辑于2022年，星期六应用案例3：疾病诊断n医疗领域的专家系统可以作为疾病诊断的辅助决策手段。对应特定的疾病，众多该类病人的症状按时间顺序被记录。自动分析该纪录可以发现对应此类疾病普适的症状模式。每种疾病和对应的一系列症状模式被加入到知识库后，

8、专家系统就可以依此来辅助人类专家进行疾病诊断。2023/4/1017第17页，共92页，编辑于2022年，星期六应用案例3：疾病诊断n例:通过分析大量曾患A类疾病的病人发病纪录，发现以下症状发生的序列模式：n如果病人具有以上症状，则有可能患A类疾病2023/4/1018第18页，共92页，编辑于2022年，星期六应用案例4：查询扩展n查询扩展是搜索领域一个重要的问题。用户提交的查询往往不能完全反映其信息需求。一些研究工作尝试用用户的查询序列模式来辅助原始查询，其主要思想是：n1）挖掘用户的查询序列模式n2）用这些序列模式构造查询词关系图n3）找到每个极大全连通图作为一个”概念”n4)对于一个查

9、询，和它同处于一个”概念”的查询可以作为查询扩展的选项2023/4/1019第19页，共92页，编辑于2022年，星期六应用案例4：查询扩展n给定一组查询模式：,查询关系图如上图：丰田雷诺宝马汽车概念1：汽车品牌概念2：汽车2023/4/1020第20页，共92页，编辑于2022年，星期六三、序列模式挖掘算法概述nAgrawal和Srikant在提出这个问题时提出了三个算法，AprioriAll，AprioriSome 和DynamicSome，它们都基于Apriori框架。构成了序列模式挖掘问题的基石。随后，这个领域 的研究工作取得了大量的成果。2023/4/1021第21页，共92页，编辑

10、于2022年，星期六 序列模式挖掘算法概述n类Apriori算法n基于划分的模式生长算法n基于序列比较的算法2023/4/1022第22页，共92页，编辑于2022年，星期六 类Apriori算法该类算法基于Apriori理论，即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式，然后计算候选序列模式的支持度。典型的代表有GSP算法,spade算法等。2023/4/1023第23页，共92页，编辑于2022年，星期六基于划分的模式生长算法n该类算法基于分治的思想，迭代的将原始数据集进行划分，减少数据规模，同时在划分的过程中动态的挖掘序列模式，并将新发现

11、的序列模式作为新的划分元。典型的代表有FreeSpan算法和prefixSpan算法。2023/4/1024第24页，共92页，编辑于2022年，星期六基于序列比较的算法n该类算法首先定义序列的大小度量，接着从小到大的枚举原始序列数据库中包含的所有k-序列，理论上所有的k-序列模式都能被找到。算法制定特定的规则加快这种枚举过程。典型的代表为Disc-all算法。2023/4/1025第25页，共92页，编辑于2022年，星期六 四、GSP算法算法思想：类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的数据结构-哈希树来实现候选模式的快速访存。2023/4/1026第26页，共92页，

12、编辑于2022年，星期六 GSP算法描述n扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集n根据长度为i 的种子集Li，通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集n重复第二步，直到没有新的序列模式或新的候选序列模式产生为止L1 C2 L2 C3 L3 C4 L4 2023/4/1027第27页，共92页，编辑于2022年，星期六 n产生候选序列模式主要分两步：n连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，

13、则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中n修切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除L1 C2 L2 C3 L3 C4 L4 2023/4/1028第28页，共92页，编辑于2022年，星期六 n候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数L1 C2 L2 C3 L3 2023/4/1029第29页，共92页，编辑于2022年，星期六哈希树nGSP采用哈希树存储候选序列模式。哈希树的节点分为三类

14、：1、根节点；2、内部节点；3、叶子节点。2023/4/1030第30页，共92页，编辑于2022年，星期六 哈希树n根节点和内部节点中存放的是一个哈希表，每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。n例：2023/4/1031第31页，共92页，编辑于2022年，星期六 添加候选序列模式n从根节点开始，用哈希函数对序列的第一个项目做映射来决定从哪个分支向下，依次在第n层对序列的第n个项目作映射来决定从哪个分支向下，直到到达一个叶子节点。将序列储存在此叶子节点。n初始时所有节点都是叶子节点，当一个叶子节点所存放的序列数目达到一个阈值，它将转化为一个内部节点。2023/4/

15、1032第32页，共92页，编辑于2022年，星期六 计算候选序列模式的支持度n给定一个序列s是序列数据库的一个记录：1）对于根节点，用哈希函数对序列s的每一个单项做映射来并从相应的表项向下迭代的进行操作 2）。2023/4/1033第33页，共92页，编辑于2022年，星期六 计算候选序列模式的支持度 2）对于内部节点，如果s是通过对单项x做哈希映射来到此节点的，则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射，然后从相应的表项向下迭代做操作 2）或 3）。2023/4/1034第34页，共92页，编辑于2022年，星期六 计算候选序列模式的支持度n（

16、3）对一个叶子节点，检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。n这种计算候选序列的支持度的方法避免了大量无用的扫描，对于一条序列，仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量，m表示候选序列模式的数量，t代表哈希树叶子节点的最大容量2023/4/1035第35页，共92页，编辑于2022年，星期六 n例：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式Sequential patternsWith length 3Candidate 4-SequencesAfter JoinAft

17、er Pruning2023/4/1036第36页，共92页，编辑于2022年，星期六 GSP算法存在的主要问题n如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式n需要对序列数据库进行循环扫描n对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理2023/4/1037第37页，共92页，编辑于2022年，星期六五、PrefixSpan算法算法思想：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘2023/4/1038第38页，共92页，编辑于2022年，星期六 相关定义前缀：设每个元素中的所有项目按照字典序

18、排列。给定序列=，=(m n)，如果ei=ei(i m-1)，em em，并且(em-em)中的项目均在em中项目的后面，则称是的前缀例：序列 是序列 的一个前缀；序列则不是。2023/4/1039第39页，共92页，编辑于2022年，星期六相关定义投影：给定序列和，如果是的子序列，则关于的投影必须满足：是的前缀，是的满足上述条件的最大子序列例：对于 序列=，其子序列 =的投影是=;的投影是原序列。2023/4/1040第40页，共92页，编辑于2022年，星期六相关定义后缀：序列关于子序列=的投影为=(n=m)，则序列关于子序列的后缀为，其中em”=(em-em)例：对于 序列，其子序列的投

19、影是，则对于的后缀为。2023/4/1041第41页，共92页，编辑于2022年，星期六 n例：a(ab)a(abc)2023/4/1042第42页，共92页，编辑于2022年，星期六相关定义n投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|n投影数据库中的支持度：设为序列数据库S中的一个序列，序列以为前缀，则在的投影数据库S|中的支持度为S|中满足条件 .的序列的个数2023/4/1043第43页，共92页，编辑于2022年，星期六算法描述n扫描序列数据库，生成所有长度为1的序列模式n根据长度为1的序列模式，生成相应的投影数据库n在相

20、应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止n分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止SS1SmS11 S1n Sm1 Smp 2023/4/1044第44页，共92页，编辑于2022年，星期六 n例：对于如下的序列数据库生成一系列的投影数据库SidSequence102030402023/4/1045第45页，共92页，编辑于2022年，星期六 n扫描序列数据库S，产生长度为1的序列模式有：:4,:4,:4,:3,:3,:3n序列模式的全集必然可以分为分别以，和为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结

21、果如下页图所示2023/4/1046第46页，共92页，编辑于2022年，星期六 PrefixProject Database 2023/4/1047第47页，共92页，编辑于2022年，星期六算法伪码nPrefixSpan算法输入：序列数据库S及最小支持度阈值min_sup输出：所有的序列模式方法：去除所有非频繁的项目，然后调用子程序PrefixSpan(,0,S)2023/4/1048第48页，共92页，编辑于2022年，星期六 算法伪码n子程序PrefixSpan(,L,S|)参数：.一个序列模式 L.序列模式的长度 S|.如果为空，则为S，否则为的投影数据库扫描S|，找到满足下述要求的

22、长度为1的序列模式b：b可以添加到的最后一个元素中并为序列模式可以作为的最后一个元素并为序列模式对每个生成的序列模式b，将b添加到形成序列模式，并输出对每个,构造的投影数据库S|,并调用子程序PrefixSpan(,L+1,S|)2023/4/1049第49页，共92页，编辑于2022年，星期六 Sid sequence 1 2 3 4 给定如下的序列数据库：2023/4/1050第50页，共92页，编辑于2022年，星期六 n找出频繁单项：1，3，7，8；然后除去非频繁的单项：Sid sequence 1 2 3 4 2023/4/1051第51页，共92页，编辑于2022年，星期六 n为频

23、繁1序列（频繁单项）生成投影数据库：SidSuffix for prefix 13SidSuffix for prefix 1232023/4/1052第52页，共92页，编辑于2022年，星期六 SidSuffix for prefix 23SidSuffix for prefix 342023/4/1053第53页，共92页，编辑于2022年，星期六 n在上面的投影数据库中，前缀的投影数据库中还有频繁单项_3，前缀的投影数据库中还有频繁单项7.生成频繁2序列，,然后为其生成投影数据库.其中没有频繁项目，算法终止。SidSuffix for prefix 13SidSuffix for pr

24、efix 232023/4/1054第54页，共92页，编辑于2022年，星期六 PrefixSpan算法分析nPrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间n相对于原始的序列数据库而言，投影数据库的规模不断减小nPrefixSpan算法的主要开销在于投影数据库的构造2023/4/1055第55页，共92页，编辑于2022年，星期六PrefixSpan算法的主要改进隔层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销2023/4/1056第

25、56页，共92页，编辑于2022年，星期六隔层投影n扫描序列数据库，产生所有长度为1的序列模式n再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有长度为2的序列模式n构造长度为2的序列模式所对应的扫描数据库，然后对每个投影数据库，重复上面的操作，直到没有新的序列模式产生为止SidSequence102030402023/4/1057第57页，共92页，编辑于2022年，星期六a2b(4,2,2)1c(4,2,1)(3,3,2)3d(2,1,1)(2,2,0)(1,3,0)0e(1,2,1)(1,2,0)(1,2,0)(1,1,0)0f(2,1,1)(2,2,0)(1,2,1)(1,1,1

26、)(2,0,1)1abcdef2023/4/1058第58页，共92页，编辑于2022年，星期六伪投影n当数据库可以直接放入内存时，并不需要构造所有的序列模式对应的投影数据库，我们可以使用指向数据库中序列的指针及其偏移量作为伪投影n例子：假设上述序列数据库可以放入内存，在构造a投影数据库时，序列 S1=所对应的伪投影为：一个指向S1的指针，指针偏移设定为2。同样的，序列S1的投影数据库对应的伪投影为：一个指向S1的指针，指针偏移设定为42023/4/1059第59页，共92页，编辑于2022年，星期六六、Disc-all算法n算法思想：nDisc-all算法采用了Disc（Direct seq

27、uence comparing)策略。其核心思想是对于给定的k和所有k-1序列模式，通过枚举所有合适的k序列发现k-序列模式。通过引入适当的枚举策略保证算法效率。2023/4/1060第60页，共92页，编辑于2022年，星期六相关定义n给定两条l-序列和,如果 ，那么下列条件必满足其一：1）,的第m项 的第m项且与 在其第m项 之前的部分完全相同 2）,的第m项=的第m项但 的第m项和第m-1项不在同一元素中而 的第m项则相反，并且与 在其第m项 之前的部分完全相同2023/4/1061第61页，共92页，编辑于2022年，星期六 n例：小于 因为条件1),小于 因为条件2).n定义序列的大

28、小关系只是为了给序列排序，这种大小度量是相对的，没有真正的物理意义2023/4/1062第62页，共92页，编辑于2022年，星期六相关定义n一条l-序列序列所有长度为k的子序列（1 k l)中最小的一条叫做这条序列的k-最小序列.n给定k-序列c为条件序列，一条l-序列序列所有大于c的长度为k的子序列（1 k l)中最小的一条叫做这条序列的k-条件最小序列.2023/4/1063第63页，共92页，编辑于2022年，星期六 Disc-all算法概述n该算法首先划分数据库，然后在划分数据库上执行迭代的执行Disc策略，即基于序列比较的序列模式枚举过程：首先通过适当的枚举找到所有的k-序列模式，

29、然后根据k-序列模式找到所有的k+1序列模式。2023/4/1064第64页，共92页，编辑于2022年，星期六 数据库划分nDisc-all算法对原始序列数据库进行两层划分：n一层划分：首先找到所有的频繁单项并删除所有的非频繁单项，然后进行一级划分，即对于每个频繁单项i，找到所有包含它的序列组成i划分。n二层划分：找到所有的2-序列模式并删除所有的非频繁2-序列，然后进行二级划分，即对于每个2-序列模式，找到所有包含它的序列。2023/4/1065第65页，共92页，编辑于2022年，星期六 SidSequence10203040例：对如下数据库进行两层划分，给定最小支持度2，首先找到所有的

30、频繁单项：a,b,c,d,e,f2023/4/1066第66页，共92页，编辑于2022年，星期六 生成一层划分数据库n下面给出了每个频繁单项的一层划分数据库：频繁单项划分数据库a b c d e f 2023/4/1067第67页，共92页，编辑于2022年，星期六 n在a-划分数据库里找到所有第一项为a的2-序列模式：，并删除非频繁的以a开头的2-序列。删除规则为：n1）如果单项i和a在同一元素内且是2-序列模式;n2）如果单项i和a不在同一元素内且是2-序列模式;当条件1),2)全都不满足时删除i.2023/4/1068第68页，共92页，编辑于2022年，星期六 生成二层划分数据库n下

31、面只给出根据a-划分找到的2-序列模式及其二层划分数据库，注意所有的非频繁2-序列已经被删除。频繁单项划分数据库 2023/4/1069第69页，共92页，编辑于2022年，星期六 Disc策略n对于每一个划分数据库，给定一组k-序列模式集合S，Disc策略通过枚举找到所有的k+1-序列模式。枚举过程如下：n1)对于每个序列s,找到s的最小的k+1-子序列s,且s的k前缀 S，将s加入k+1序列集，记录s的源序列s2023/4/1070第70页，共92页，编辑于2022年，星期六 Disc策略n2)对k+1序列集排序，设最小支持度为，排序后第个序列称为条件序列。n3)如果第一个序列和条件序列相

32、等，则输出条件序列为一个k+1-序列模式，并且将所有k+1序列替换为它们源序列的条件最小k+1-序列。否则尽可能将所有k+1序列替换为条件序列，对于源序列中不含条件序列的k+1序列则替换为条件最小k+1-序列2023/4/1071第71页，共92页，编辑于2022年，星期六 Disc策略n4）重复上述步骤直到k+1序列集包含的序列数目小于。nDisc策略迭代的根据k-序列模式集找到k+1-序列模式集，然后递增k.直到没有k+1-序列模式集为空，算法终止。Disc-all算法从从k=2时开始采用Disc策略。2023/4/1072第72页，共92页，编辑于2022年，星期六 Disc策略n由于D

33、isc-all算法是在划分数据库上采用Disc策略，对于一个的划分，Disc策略只寻找所有以为前缀的序列模式。n回忆之前讨论的prefixSpan算法，可以发现在这一点上二者非常相似。都是基于前缀生长的思想。不同的是prefixSpan采用递归而Disc-all算法采用迭代。2023/4/1073第73页，共92页，编辑于2022年，星期六 n考虑前面的序列数据库，对于右侧的一个基于二层划分，仍然给定最小支持度为2，下面的例子展示了Disc策略是如何找到以3-序列模式的n SidSequence102030402023/4/1074第74页，共92页，编辑于2022年，星期六 初始化3-序列集

34、Sid3-Sequence104020n可以看出是一条3序列模式。Sid为30的序列没有产生初始3-序列因为其不包含以为前缀的3-子序列Sid3-Sequence102040n为条件序列，将所有3-序列替换为源序列的条件3-最小序列并重新排序，又发现一条3-序列模式2023/4/1075第75页，共92页，编辑于2022年，星期六 Sid3-Sequence402010n用新的条件最小3-序列替换各3-序列并排序，3-序列数据集如右侧所示。这一次没有新的3-序列模式被发现。Sid3-Sequence104020n用新的条件序列替换各3-序列并排序，3-序列数据集如右侧所示。发现新的3-序列模式

35、.注意Sid为10的序列不含,所以用条件最小3-序列替换。2023/4/1076第76页，共92页，编辑于2022年，星期六 n重复上面的步骤，可以发现新的3-序列模式.这时只有Sid为10的序列含有比更大的3-序列，所以算法停止。Sid3-Sequence4020102023/4/1077第77页，共92页，编辑于2022年，星期六Disc-all算法分析nDisc-all算法同样不生成候选序列模式，减少了计算开销。同时采用划分技术,减少了搜索空间。应用Disc策略，解决了划分效率随划分层次增加而下降的问题。nDisc-all采用的划分技术不如prefixSpan高效，而且Disc策略较为复

36、杂耗时，算法效率往往不及prefixSpan，但在处理长序列数据集时，因为Disc策略没有迭代开销同时投影技术效率有所下降，Disc-all表现反而更好。2023/4/1078第78页，共92页，编辑于2022年，星期六 Disc-all和prefixSpan的性能比较平均序列长度为20时，Disc-all和prefixSpan的性能比较2023/4/1079第79页，共92页，编辑于2022年，星期六Disc-all和prefixSpan的性能比较平均序列长度为80时，Disc-all和prefixSpan的性能比较2023/4/1080第80页，共92页，编辑于2022年，星期六 n用户需

37、要的往往是满足特定条件的序列模式，而传统的序列模式挖掘没有考虑用户的特殊要求，做了大量无效的挖掘。比如对于购买记录的事务数据库，用户希望得到的序列模式事务之间的时间差不能太大。七、支持约束的序列模式挖掘2023/4/1081第81页，共92页，编辑于2022年，星期六解决办法引入约束的概念。在约束条件下做符合用户要求的序列模式挖掘。一方面利用特定约束本身的性质节省了挖掘的时间和空间，另一方面避免用户陷入大量的无用信息。2023/4/1082第82页，共92页，编辑于2022年，星期六约束的分类n单调约束：如果一个序列满足，那么这个序列的所有超序列也满足的约束；n反单调约束：如果一个序列满足，那

38、么这个序列 的任意子序列也满足的约束；n简洁约束：用特定规则挖掘的约束；n还有一些无法归为以上三类的约束，一般被称为强约束（tough constraints.）比如时间性约束。2023/4/1083第83页，共92页，编辑于2022年，星期六 一些常用的约束约束分类描述单项蕴含约束单调约束目标序列模式必须包含某些单项持续时间约束反单调约束目标序列模式的第一个元素和最后一个元素间的时间间隔不大于某个阈值间隔约束强约束目标序列模式的任意连续两个元素间的时间间隔不大于某个阈值均值约束强约束如果每个单项被赋予一个表示重要性的权值，目标序列模式的平均值大于某个阈值2023/4/1084第84页，共92

39、页，编辑于2022年，星期六支持约束的序列模式挖掘算法n在支持约束的模式序列挖掘领域内产生了大量的成果。主要有两类，一类是针对特定的约束，如针对单调性约束的ExAnte,针对Gap约束的CCSM,另一类是提出一个通用的框架，可以针对不同的约束采用不同的策略，如PrefixGrowth.2023/4/1085第85页，共92页，编辑于2022年，星期六 ExAnte算法nExAnte实际上是一种数据预处理方法，它首先删除所有不满足约束条件的序列，然后删除所有在新的序列数据库中非频繁的单项。处理后的数据集可以应用任何序列模式挖掘方法。2023/4/1086第86页，共92页，编辑于2022年，星期

40、六 n例：给定最小支持度2和约束 Sum(P)4，（目标序列模式的总值大于4），考虑右侧的序列数据库,单项后的数字代表权值。SidSequence102030402023/4/1087第87页，共92页，编辑于2022年，星期六 n从表中可以看出，Sid为20，40的序列不满足给定的约束，可以被删除。删除后频繁单项为c,b,d.a被删除。得到如下的数据集：n同原数据集相比，数据规模大大减少SidSequence10302023/4/1088第88页，共92页，编辑于2022年，星期六PrefixGrowth算法nPrefixGrowth算法以prefixSpan算法为框架，将约束处理机制整合到

41、前缀增长的过程中。在为前缀构造投影数据库之前，首先启用相应的约束机制检查前缀是否有可能扩展为满足约束条件的序列模式。2023/4/1089第89页，共92页，编辑于2022年，星期六处理单调约束 n对于单调约束，PrefixGrowth算法对于每一个前缀找到其最长的投影，如果该投影满足单调约束，则为此前缀构造投影数据库，否则直接删除此前缀。2023/4/1090第90页，共92页，编辑于2022年，星期六 处理强约束n对于强约束，PrefixGrowth没有提供统一的处理策略，只是讨论了两种常见的强约束：均值约束和总值约束的处理。这是因为强约束本身不具有内在的统一性，只是一些难于处理约束的别称。2023/4/1091第91页，共92页，编辑于2022年，星期六 Thanks!2023/4/1092第92页，共92页，编辑于2022年，星期六