PrefixSpan

序列模式挖掘的相关定义1.项集（itemset）：由项组成的非空集合，可以表示成（x1x2…xm）这里的每一个xk表示一个项。2.序列（sequence）：项集的有序排列组成了一个序列，可以表示成s1s2…sl,这里的sj就是一个项集，同样sj也称为是序列的一个元素。3.子序列（subsequence）：设=a1a2…an，=b1b2…bm，如果存在整数1=j1j2…jn=m，使得a1bj1，a2bj2，…，anbjn，则称序列为序列的子序列，又称序列包含序列，记为。4.序列长度:一个序列中包含项的个数，称之为该序列的长度。5.支持数：序列s的支持数为在序列数据库S中包含序列s的个数。6.支持度：预先设定的一个阈值。7.序列模式：序列s的支持数support(s)如果不小于支持度，那么序列s就称作是在序列数据库中的序列模式。长度为l的序列模式称作l-模式。实例说明Sequence_idSequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40eg(af)cbc表一中给定的运行的序列数据库是S，并且支持度min_support=2.在数据库中的一组项是{a,b,c,d,e,f,g}。序列a(abc)(ac)d(cf)有五个元素，(a),(abc),(ac),(d)和(cf)。该序列的序列长度是9，因为序列中一共有9个项。序列a的支持数是1，因为在整个数据库中a只出现了一次。序列a(bc)df是a(abc)(ac)d(cf)的一个子序列。因为10号序列中包含2个(ab)c子序列，30号序列中包含了1个(ab)c子序列，所以在整个数据库中共包含了3个(ab)c子序列，所以(ab)c序列的支持数是3min_support=2,所以(ab)c是一个序列模式。序列模式挖掘介绍问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字母表顺序排列。GSP算法GSP算法是一个典型的序列模式挖掘算法，它是通过采用产生并检测一个候选序列的方法，是基于优先级原则的一个算法。这是一个典型的序列模式挖掘算法。算法描述1、扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集2、根据长度为i的种子集Li通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集3、重复第二步，直到没有新的序列模式或新的候选序列模式产生为止L1C2L2C3L3C4L4……GSP算法产生候选序列模式主要分两步：1、连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1于s2进行连接，即将s2的最后一个项目添加到s1中2、剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除L1C2L2C3L3C4L4……GSP算法一组候选序列的产生是通过在先前扫描通过的序列模式上进行自我结合产生的。在第k次扫描的时候，只要每个它的每个length-(k-1)的子序列是在第k-1次扫描的时候找到的一个序列模式，那么这个序列就是候选序列。当在一次扫描的过程中没有发现候选序列或者没有候选序列产生的时候算法就停止了。GSP算法如上图所示，在连接过程中,种子序列(1,2)3和种子序列2(3,4)连接可产生候选4序列(1,2)(3,4)；和种子序列235连接可产生候选4序列(1,2)35。其余的序列均不满足连接条件。在剪枝过程中，候选4序列(1,2)35被剪去，因为其连续子序列1,3,5不包含在3序列模式集合L3中。GSP算法GSP算法存在的问题1、如果序列数据库的规模比较大,则有可能产生大量的候选序列模式;2、需要对序列数据库进行循环扫描;3、对于序列模式的长度比较长的情况,算法很难处理。Freespan算法定义投影:给定序列A和B，如果B是A的子序列，则A关于B的投影A’必须满足B是A’的前缀，A’是A的满足上述条件的最大子序列．例如，序列A=(ab)(acd)(cdfe)，B=(b)是A的一个子序列，那么，B关于A的投影为A’=(b)(acd)(cdfe)．Freespan算法Freespan算法即是频繁模式投影的序列模式挖掘。基本思想：利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片段。这一过程对数据和待检测的频繁模式集进行了分割，并且将每一次检验限制在与其相符合的更小的投影数据库中。Freespan算法FreeSpan算法执行的过程1、首先给定序列数据库S及最小支持度阈值ζ。扫描S,找到S中的频繁项集,并以降序排列生成flist列表。2、执行下面步骤:(1)第1遍扫描S,构造频繁项矩阵;(2)生成长度为2的序列模式,循环项模式的标记和投影数据库的标记;(3)再次扫描S,生成循环项模式和投影数据;(4)对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。Freespan算法FreeSpan算法分析优点：它将频繁序列和频繁模式的挖掘统一起来,把挖掘工作限制在投影数据库中,还能限制序列分片的增长。它能有效地发现完整的序列模式,同时大大减少产生候选序列所需的开销,比基于Apriori的GSP算法快很多。Freespan算法FreeSpan算法分析不足之处：它可能会产生许多投影数据库,如果一个模式在数据库中的每个序列中出现,该模式的投影数据库将不会缩减;另外,一个长度为k的序列可能在任何位置增长,那么长度为k+1的候选序列必须对每个可能的组合情况进行考察,这样所需的开销是比较大的。PrefixSpan算法相关定义前缀：假设所有的项在一个元素中按照字母表的顺序排列出来。给定一个序列α=e1e2…en(在这里每一个e都和在S中给定的连续的元素相一致)和一个序列β=e1’e2’…em’(m≤n).只有如果：1）ei’=ei（i≤m-1），2）em’∈em，3）所有在（em—em’）的连续项在em’中都是按照字母表顺序排列的，那么我们就说β是α的一个前缀。例如，a,aa,a(ab)和a(abc)都是序列s=a(abc)(ac)d(cf)的前缀,但是如果每个项都在S中的序列s是连续的，那么ab和a(bc)都认为是a(abc)的一个前缀。PrefixSpan算法相关定义后缀：序列关于子序列=e1e2…em-1em’的投影为’=e1e2…en(n=m)，则序列关于子序列的后缀为em”em+1…en，其中em”=(em-em’)。例如，对于序列s=a(abc)(ac)d(cf)，(abc)(ac)d(cf)就被认识为是关于前缀a的后缀，(-bc)(ac)d(cf)就被认为是关于前缀aa的后缀，(-c)(ac)d(cf)就被被认为是关于前缀a(ab)的后缀。PrefixSpan算法相关定义投影数据库：令α是在序列数据库S中的一个序列模式，这个α-投影数据库表示为：S|α，它是在S中关于前缀α的序列的后缀的集合投影数据库的支持数：设α是在序列数据库S中的一个序列模式，并且β是一个带有前缀α的序列。β在α-投影数据库S|α中的支持度数表示为S|α（β）。PrefixSpan算法算法描述输入：序列数据库S和最小支持阈值min_support输出：完整的一组序列模式方法：调用PrefixSpan(,0,S)子程序：PrefixSpan(α,l,S|α)参数：α：α是一个序列模式；l：α的长度；S|α：如果α≠,S|α是α的投影数据库，否则他就是序列数据库S。PrefixSpan算法算法描述算法步骤：1）对投影数据库S|α进行一次扫描，找到一组连续的项b，其中b可以集合成为α的最后一个元素或者b可以被追加到α上，形成一个序列模式。2）对于每一个连续的项b，把他添加到α上形成一个序列α’，并且输出α’。3）对于每一个α’，创建一个α’-投影数据库S|α’,并调用PrefixSpan(α’,l+1,S|α’).PrefixSpan算法算法效率分析1)PrefixSpan算法不需要产生候选序列与相似优先级算法不同，PrefixSpan算法从较短的连续项中产生序列模式增长很少。在投影数据库中，它不用生成候选序列，也不用判断是否有候选序列的存在。2）投影数据库一直在缩小投影数据库比原始数据库更小，因为只有那些有着连续前缀的后缀子序列才能投影到投影数据库。这是因为（1）通常只有在序列数据库中只有一组很小的序列模式增长的非常快，并且当前缀增长的时候，投影数据库的数量会变得很小（2）投影仅仅发生在与前缀相关的后缀部分。PrefixSpan算法算法效率分析3）PrefixSpan算法主要消耗是构造投影数据库在最坏的情况下，PrefixSpan算法为每一个序列模式建立一个投影数据库。如果存在一些很大数量的序列模式，那么它的消耗是非平凡的。为此，提出了一个减小投影数据库个数的技术。PrefixSpan算法伪投影技术PrefixSpan算法的主要消耗是在构造投影数据库，而伪投影技术能够减少投影数据库的数量和大小。算法思想：当数据库可以存储在主存之中，我们就用一个指针指向数据库中的一个序列作为一个伪投影，而不是去通过收集所有的后缀而真实的构造物理投影。每一个投影由两部分组成：指向数据库中序列的指针和序列中后缀的后继。PrefixSpan算法伪投影的分析伪投影避免了物理的复制后缀，这样它在运行时间和运行空间上就很高效，但是它不适用于基于硬盘的存取。因为随机存取硬盘空间是十分耗时的。基于这样的原因，只要主存中可以容下一个投影数据库，那么我们就使用伪投影技术，而如果原始的序列数据库或者投影数据库太大而不适应于主存，我们就要应用物理投影。PrefixSpan算法实验结果和性能分析实验结果表明，PrefixSpan算法不论是在运行时间还是在运行空间上都大大优于其他三种算法。PrefixSpan算法不仅仅是更加的高效，而且与SPADE和GSP算法相比，他在内存使用上更加的稳定。PrefixSpan算法PrefixSpan算法的高效性原因1、不产生候选序列的模式增长PrefixSpan算法是一个基于模式增长的算法，与那些基于优先级的传统的算法不同，PrefixSpan算法没有产生任何没用的序列，而且它只是记下了本地1-项组的频率。当最小支持度减小的时候，连续的序列就会呈现指数的增长，而基于最优化的算法会花费大量呈指数增长的时间去处理一个很小的数据库。PrefixSpan算法PrefixSpan算法的高效性原因2、PrefixSpan算法采用基于投影的分治法作为减小数据的有效的方法PrefixSpan算法的搜索空间是是集中的并且是限制在一组投影数据库中。投影数据库的大小经常随着挖掘进程的序列模式的增长而快速的减小。与之相对比，基于优先级的算法经常在每次迭代的过程中搜索原始的数据库。这样就会搜索和检查很多不相干的序列，这样就增加了负担。PrefixSpan算法PrefixSpan算法的高效性原因3、PrefixSpan算法消耗相对稳定的内存因为PrefixSpan算法不产生候选序列，并且使用分治法进行搜索。另一方面，当支持度降到很小的时候，例如GSP，SPADE算法，产生和检测候选序列的方法需要大量的内存。PrefixSpan算法PrefixSpan算法的高效性原因4、PrefixSpan算法应用于基于前缀的投影模式增长，这比使用了连续的模式定位投影方法的FreeSpan算法更