序列及Apriori生成候选算法.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/2/8,#,序 列,报告人：熊 赟,内容概要,基本概念,其他,类Apriori生成候选算法,相似性搜索,FreeSpan算法,PrefixSpan算法,第6章 序 列,6.1 基本概念,6.2 原 理,6.3 核心算法,6.4 其 他,序列是不同项集的有序排列。,定义1(序列)：I=i,1,i,2,i,m,是项集，i,k,（1=k=m）是一个项，序列S记为S，其中s,j,（1=j=n）为项集（也称序列S的元素），即s,j,I。每个元素由不同项组成。序列的元素可表示为（i,1,i,2,i,k,），若一个序列只有一个项，则括号可以省略。,序列包含的所有项的个数称为,序列的长度。,长度为,l,的序列记为,l,-序列。,序 列,定义2(子序列)：序列T是另一个序列S的子序列，满足下面条件：对于每一个j，1=j=m-1，有i,j,i,j+1,且 对于每一个j，1=j=m，存在1=k=,，则称序列S为序列数据库D中的一个（频繁）序列模式。,长度为,l,的序列模式称为,l,模式。,序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度（用户指定最小支持度阈值）的子序列。,频繁序列模式,定义5:（序列关联规则）对于给定的项集,I=,i,1,i,2,i,m,以及序列S,T形如,S,T,的表达式称为序列关联规则。,序列关联规则,置信度,支持度,序列关联规则,序列关联规则,S,T,的支持度,是支持序列,S,和,T,的顾客数占,总顾客数之比。,序列关联规则S,T的置信度,记为（,），是支持序列S和T,的顾客数与仅支持S的顾客数,之比。,序列模式挖掘阶段,排序阶段,发现频繁项集阶段,转换阶段,序列阶段,最大阶段,交易发生的时间,客户标识,购买项,June 1004,June 1204,June 1504,June 2004,June 2504,June 2504,June 2504,June 3004,June 3004,July 2504,2,5,2,2,4,3,1,1,4,4,A，B,H,C,D，F，G,C,C，E，G,C,H,D，G,H,客户标识,交易时间,购买项,1,1,June 2504,June 3004,C,H,2,2,2,June 1004,June 1504,June 2004,A,B,C,D,F,G,3,June 2504,C,E,G,4,4,4,June 2504,June 3004,July 2504,C,D,G,H,5,June 1204,H,由客户标识及交易发生的时间为关键字所排序的数据库,排序阶段,客户号,客户序列,1,2,3,4,5,客户序列描述数据库,频繁项集,映射,(C),(D),(G),(DG),(H),1,2,3,4,5,频繁项集分别是,(C),、,(D),、,(G),、,(D,G),和,(H),发现频繁项集阶段,客户标识,原始客户序列,转换后客户序列,映射后序列,1,2,3,4,5,转换后的数据库（客户序列）,转换阶段,核心算法,AprioriAll,AprioriSome算法,FreeSpan，PrefixSpan算法,序列阶段,最大阶段,AprioriAll算法,基本思想,客户号,客户序列,1,2,3,4,5,AprioriAll算法,AprioriAll算法,1-,序列,支持度,4,2,4,4,4,L,1,2-,序列,支持度,2,4,3,3,2,2,3,2,2,L,2,3-,序列,支持度,2,23,2,2,AprioriAll算法,4-,序列,支持度,2,L,3,L,4,序列,支持度,2,2,2,AprioriAll算法,最大的频繁序列,AprioriSome算法,基本思想：,算法分为两个阶段：,前阶段：只对一定长度的序列计数,next（k）函数 即C,k,生成L,k,后阶段：,对前阶段已确定的L,k,确定为最大序列,对前阶段没有生成L,k,，先删除所有在C,k,中包含在L,i,中的序列，再对C,k,计数生成L,k,。,AprioriSome算法,1-,序列,支持度,4,2,4,4,4,L,1,2-,序列,支持度,2,4,3,3,2,2,3,2,2,L,2,next(last)=2k,不计数,AprioriSome算法,C,3,C,4,修剪,AprioriSome算法,C,5,为空结束前阶段进入回溯阶段,删除了L,4,的子序列后的C,3,再计数发现,是最大3序列,L,4,4-,序列,支持度,2,序列,支持度,2,2,2,AprioriSome算法,最大的频繁序列,除,以外,L,2,中所有的序列都被删除,L,1,中所有的序列都被删除,类,Apriori,算法有以下缺点：,有可能生成庞大众多的候选序列。,多遍扫描数据库。,不易发生长度较大的序列模式。序列模式越长，所需要生成的序列就越多。,FreeSpan算法,频繁模式投影的序列模式挖掘,Fre,qu,e,nt pattern-projected,S,equential,p,atter,n,mining,基本思想（基于数据库投影和分片技术）,利用频繁项递归地将序列数据库投影到更小,的投影数据库集中，在每个投影数据库中生,成子序列片段。,FreeSpan算法,序列,id,序列,项,10,a,b,c,d,20,b,c,e,f,g,30,a,b,f,h,40,b,c,d,e,50,a,b,c,d,e,序列数据库,最小支持度设为2,FreeSpan算法,1.找到频繁项集L,1,频繁项按支持度降序排列形成频繁项列表，,f_list=,根据f_list，序列模式集被分为不相交的六个子集：1）只包含项f；,分而自治策略,FreeSpan算法,2.A.,构造,频繁项矩阵F,用于生成长度为2的序列模式，,投影数据库,集用于生成长度为3及更长的序列模式,F是一个三角矩阵Fj,k（1jm，1kj）。其中Fj,j（1jm）仅有一个计数值，而其他每个Fj,k（1jm，,1kj,）有三个计数值：（A,B,C）,序列模式,的投影数据库,是含有的序列集的子序列，非频繁项及后的项也被删除。,F矩阵图,4,(4,3,0),1,(3,2,0),(2,1,1),2,(2,2,2),(2,2,0),(1,2,1),1,(3,1,1),(1,1,2),(1,0,1),(1,1,1),1,(2,2,2),(1,1,0),(1,1,0),(0,0,0),(1,1,0),2,1b,2c,3a,4d,5e,6f,1b,2c,3a,4d,5e,6f,Fj,j 仅有一个计数值，,Fj,k 有三个计数值：（A,B,C）,序列,FreeSpan算法,2.B.,生成长度为2的序列模式,标记循环项模式和投影数据库；,循环项模式标记形如$,i,j,$，其中$表示两种形式,，,。,投影数据库标记形如$,i,j,$：b,p,b,q,，b,p,b,q,表示在子序列挖掘过程中与$,i,j,$合在一起生成长度更长的序列模式的频繁项集。,FreeSpan算法,项,长度为2的序列模式,循环项标记,投影数据库标记,f,:2,:2,:2,b,+,f,+,e,:3,:2,:b,d,:2,:2,:2,:2,:2,:2,b,+,d ,:bc,cd:b,a,c,b,:4,FreeSpan算法,2.C.,再次扫描数据库S，生成循环项模式和投影数据库；,b,+,f,+,b,+,d ,:2,:2,:2,:2,:2,:2,:2,:2,:2,:2,:2,四个投影数据库如下图：,FreeSpan算法,2.D.,对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。,标记,:b,:bc,cd:b,:b,投影数据库,序列模式,:2,:2,:2,:2,:2,:2,:2,:2,FreeSpan算法：给定序列数据库S及最小支持度阈值。,1.扫描序列数据库S，找到S中的频繁项集，并以降序排列生成f_list列表。,2.执行下面步骤：,a.,第一遍扫描数据库S，构造频繁项矩阵；,b.,生成长度为2的序列模式及标记循环项模式和投影数据库；,c.,再次扫描数据库S，生成循环项模式和投影数据库；,d.,对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式,。,PrefixSpan,算法,（通过前缀投影挖掘序列模式）,Prefix,-projected,S,equential,p,atter,n,mining,基本思想：序列数据库投影时，并不考虑所有可能出现的频繁子序列，而,只检验,前缀,序列,，,然后把相应的后缀序列投影成投影数据库。每个投影数据库中，只检查局部频繁模式,不需要生成候选序列。,例：,前缀：给定序列,=,，,=,(m,n)，如果e,i,=e,i,(i,m-1,)，e,m,e,m,，并且(,e,m,-e,m,)中的项目均在,e,m,中项目的后面，则称是的前缀.,投影：,给定序列和，其中是的子序列，即。的子序列（），被称为关于前缀的投影，当且仅当1）是的前缀2）不存在的超集,/,（即 ,/,，,/,），使得,/,是的子序列并且是,/,的前缀。,后缀：序列关于子序列=,的投影为=,(n=m)，则序列,关于子序列的后缀为,，其中e,m,”=(e,m,-e,m,),算法描述：,扫描序列数据库，生成所有长度为1的序列模式,根据长度为1的序列模式，生成相应的投影数据库,在相应的投影数据库上重复上述步骤，直到在相应,的投影数据库上不能产生序列模式为止,S,S,1,S,m,S,11 ,S,1n,S,m1 ,S,mp,PrefixSpan,算法,PrefixSpan算法,序列号,序列,10,20,30,40,定义1.投影数据库：设,为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|,例：,投影数据库，由4个后缀序列组成：，。,投影数据库,PrefixSpan,算法,PrefixSpan算法,查找长度为1的序列模式,:4,:4,:4,:3,:3,:3,分割搜索空间,序列模式集可按6个前缀被划分为六个子集：1）包含前缀的子集；6）包含前缀的子集。,寻找序列模式的子集。构建并递归挖掘投影数据库。,PrefixSpan算法,寻找具有前缀的序列模式。,投影数据库，由4个后缀序列组成：，。,扫描投影数据库一遍，找到含有前缀的长度为2的序列模式，包括：2，：4，：2，：4，：2，：2。,递归，所有具有前缀的序列划分为6个子集：1）包含前缀的子集；6）包含前缀的子集,投影数据库：。不产生任何频繁子序列，结束。,投影数据库：，包含前缀的序列模式有：，。,即，,投影数据库：，。序列模式：，（即，）。,，投影数据库，投影数据库,投影数据库：，,包含前缀的序列模式有：,找到含有前缀的序列模式，包括：,子程序,PrefixSpan(,L,S|,),参数：,：一个序列模式；L：序列模式的长度,S|,：如果不为空时，为投影数据库，否则为投影数据库S，,1,扫描S|,，找到频繁项b，b满足：,a)b可以作为,的最后一个元素，形成一个序列模式；或者,b),可以追加到,上，形成一个序列模式。,2）对于每个频繁项b，追加到,上，形成一个序列模式,，输出,；,3）对于每个,，构建,投影数据库S|,，调用PrefixSpan(,l+1,S|,)。,前缀,投影（后缀）数据库,序列模式,PrefixSpan算法分析：,PrefixSpan算法不需要产生候选序列模式，从,而大大缩减了检索空间,相对于原始的序列数据库而言，投影数据库,的规模不断减小,PrefixSpan算法的主要开销在于投影数据库的,构造,PrefixSpan算法,谢 谢！,