序列模式挖掘综述

序列报告人：熊赟内容概要基本概念其他类Apriori生成候选算法相似性搜索FreeSpan算法,PrefixSpan算法第6章序列6.1基本概念6.2原理6.3核心算法6.4其他序列是不同项集的有序排列。定义1(序列)：I=｛i1i2…im｝是项集，ik（1=k=m）是一个项，序列S记为S＝s1s2…sn，其中sj（1=j=n）为项集（也称序列S的元素），即sjI。每个元素由不同项组成。序列的元素可表示为（i1i2…ik），若一个序列只有一个项，则括号可以省略。序列包含的所有项的个数称为序列的长度。长度为l的序列记为l-序列。序列定义2(子序列)：序列T＝ti1ti2…tim是另一个序列S＝s1s2…sn的子序列，满足下面条件：对于每一个j，1=j=m-1，有ijij+1且对于每一个j，1=j=m，存在1=k=n，使得tijsk。即序列S包含序列T。用符号“”表示“被包含于”，序列T是序列S的子序列可记为TS。称T为S的子序列，S为T的超序列。若一个序列S不包含在任何其他的序列之中，则称序列S是最大的。子序列定义3（支持度）：序列数据库D是元组sid，S的集合，sid为序列标识号，如果序列T是S的子序列（即TS）称元组sid,S包含序列T；则序列T在序列数据库D中的支持度是数据库中包含T的元组数，即supportD(T)＝|{sid,S|sid,SDTS}|记作support（T）。序列支持度定义4（频繁序列模式）：给定正整数为支持度阈值，如果数据库中最少有个元组包含序列S，即support（S）=，则称序列S为序列数据库D中的一个（频繁）序列模式。长度为l的序列模式称为l–模式。序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度（用户指定最小支持度阈值）的子序列。频繁序列模式定义5:（序列关联规则）对于给定的项集I=｛i1i2…im｝以及序列S,T，形如ST的表达式称为序列关联规则。序列关联规则置信度支持度序列关联规则序列关联规则ST的支持度是支持序列S和T的顾客数占总顾客数之比。序列关联规则ST的置信度记为（），是支持序列S和T的顾客数与仅支持S的顾客数之比。序列模式挖掘阶段•排序阶段•发现频繁项集阶段•转换阶段•序列阶段•最大阶段交易发生的时间客户标识购买项June10’04June12’04June15’04June20’04June25’04June25’04June25’04June30’04June30’04July25’042522431144A，BHCD，F，GCC，E，GCHD，GH客户标识交易时间购买项11June25’04June30’04CH222June10’04June15’04June20’04A,BCD,F,G3June25’04C,E,G444June25’04June30’04July25’04CD,GH5June12’04H由客户标识及交易发生的时间为关键字所排序的数据库排序阶段客户号客户序列12345(C)(H)(A,B)(C)(D,F,G)(C,E,G)(C)(D,G)(H)(H)客户序列描述数据库频繁项集映射(C)(D)(G)(DG)(H)12345频繁项集分别是(C)、(D)、(G)、(D,G)和(H)发现频繁项集阶段客户标识原始客户序列转换后客户序列映射后序列12345(C)(H)(A,B)(C)(D,F,G)(C,E,G)(C)(D,G)(H)(H){(C)}{(H)}{(C)}{(D),(G),(D,G)}{(C),(G)}{(C)}{(D),(G),(D,G)}{(H)}{(H)}{1}{5}{1}{2,3,4}{1,3}{1}{2,3,4}{5}{5}转换后的数据库（客户序列）转换阶段核心算法•AprioriAll,AprioriSome算法•FreeSpan，PrefixSpan算法•序列阶段•最大阶段AprioriAll算法•基本思想客户号客户序列12345{15}{2}{3}{4}{1}{3}{4}{35}{1}{2}{3}{4}{1}{3}{5}{4}{5}AprioriAll算法AprioriAll算法1-序列支持度1422344454L12-序列支持度122134143153232242343352452L23-序列支持度12321242134313522342AprioriAll算法4-序列支持度12342L3L4序列支持度123421352452AprioriAll算法最大的频繁序列AprioriSome算法•基本思想：•算法分为两个阶段：•前阶段：只对一定长度的序列计数•－－next（k）函数即Ck生成Lk•后阶段：•对前阶段已确定的Lk确定为最大序列•对前阶段没有生成Lk，先删除所有在Ck中包含在Li中的序列，再对Ck计数生成Lk。AprioriSome算法1-序列支持度1422344454L12-序列支持度122134143153232242343352452L2next(last)=2k123不计数124134135234345AprioriSome算法C3C41234124313451354修剪AprioriSome算法C5为空结束前阶段进入回溯阶段135345删除了L4的子序列后的C3再计数发现135是最大3序列L44-序列支持度12342序列支持度123421352452AprioriSome算法最大的频繁序列除45以外L2中所有的序列都被删除L1中所有的序列都被删除类Apriori算法有以下缺点：有可能生成庞大众多的候选序列。多遍扫描数据库。不易发生长度较大的序列模式。序列模式越长，所需要生成的序列就越多。FreeSpan算法频繁模式投影的序列模式挖掘Frequentpattern-projectedSequentialpatternmining•基本思想（基于数据库投影和分片技术）利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片段。FreeSpan算法序列id序列项10(bd)cb(ac){a,b,c,d}20(bf)(ce)b(fg){b,c,e,f,g}30(ah)(bf)abf{a,b,f,h}40(be)(ce)d{b,c,d,e}50a(bd)bcb(ade){a,b,c,d,e}序列数据库最小支持度设为2FreeSpan算法•1.找到频繁项集L1•频繁项按支持度降序排列形成频繁项列表，•f_list=b:5,c:4,a:3,d:3,e:3,f:3•根据f_list，序列模式集被分为不相交的六个子集：1）只包含项f；……•分而自治策略FreeSpan算法•2.A.构造频繁项矩阵F用于生成长度为2的序列模式，投影数据库集用于生成长度为3及更长的序列模式•F是一个三角矩阵F[j,k]（1≤j≤m，1≤k≤j）。其中F[j,j]（1≤j≤m）仅有一个计数值，而其他每个F[j,k]（1≤j≤m，1≤k≤j）有三个计数值：（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)21b2c3a4d5e6f1b2c3a4d5e6fF[j,j]仅有一个计数值，F[j,k]有三个计数值：（A,B,C）ijikikij（ikij）序列(bd)cb(ac)(bf)(ce)b(fg)(ah)(bf)abf(be)(ce)da(bd)bcb(ade)FreeSpan算法•2.B.生成长度为2的序列模式•标记循环项模式和投影数据库；•循环项模式标记形如$αiγαjγ$，其中$…$表示两种形式…，｛…｝。•投影数据库标记形如$αiαj$：｛bp,…,bq｝，｛bp,…,bq｝表示在子序列挖掘过程中与$αiαj$合在一起生成长度更长的序列模式的频繁项集。FreeSpan算法项长度为2的序列模式循环项标记投影数据库标记fbf:2,fb:2,(bf):2｛b+f+｝Φebe:3,(ce):2b+e(ce):{b}dbd:2,db:2,(bd):2cd:2,dc:2,da:2｛b+d｝da+da:{bc}{cd}:{b}a………………c………………bbb:4bb+ΦFreeSpan算法•2.C.再次扫描数据库S，生成循环项模式和投影数据库；•｛b+f+｝b+e｛b+d｝da+bb+•{bbf:2,fbf:2,(bf)b:2,(bf)(bf):2,(bd)b:2,bba:2,aba:2,aba:2,abb:2,bcb:2,bbc:2}四个投影数据库如下图：FreeSpan算法•2.D.对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。标记(ce):{b}da:{bc}{cd}:{b}ca:{b}投影数据库b(ce)b,b(ce)(bd)cb(ac),(bd)bcba(bd)cbcbcd,(bd)bcbdbcbabbcba序列模式b(ce):2(bd)a:2dca:2dba:2(bd)ca:2…………bca:2cba:2bcba:2(bd)cb(ac)(bf)(ce)b(fg)(ah)(bf)abf(be)(ce)da(bd)bcb(ade)FreeSpan算法：给定序列数据库S及最小支持度阈值ζ。1.扫描序列数据库S，找到S中的频繁项集，并以降序排列生成f_list列表。2.执行下面步骤：a.第一遍扫描数据库S，构造频繁项矩阵；b.生成长度为2的序列模式及标记循环项模式和投影数据库；c.再次扫描数据库S，生成循环项模式和投影数据库；d.对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。PrefixSpan算法（通过前缀投影挖掘序列模式）Prefix-projectedSequentialpatternmining•基本思想：序列数据库投影时，并不考虑所有可能出现的频繁子序列，而只检验前缀序列，然后把相应的后缀序列投影成投影数据库。每个投影数据库中，只检查局部频繁模式。•不需要生成候选序列。例：a(abc)(ac)d(cf)aaaa(ab)a(abc)(abc)(ac)d(cf)(_bc)(ac)d(cf)ab(_c)(ac)d(cf)前缀：给定序列=e1e2…en，=e1’e2’…em’(mn)，如果ei’=ei(im-1)，em’em，并且(em-em’)中的项目均在em’中项目的后面，则称是的前缀.投影：给定序列和，其中是的子序列，即。的子序列’（’），’被称为关于前缀的投影，当且仅当1）是’的前缀2）不存在’的超集//（即’//，’//），使得//是的子序列并且是//的前缀。后缀：序列关于子序列=e1e2…em-1em’的投影为’=e1e2…en(n=m)，则序列关于子序列的后缀为em”em+1…en，其中em”=(em-em’)算法描述：扫描序列数