随着计算机和因特网技术的迅猛发展，从各种各样应用中收集到的数据量越来越庞大，若不采用有效工具挖掘需要信息，这些海量数据信息将超出人类的理解范畴。长此以往将演变为数据量大而有效信息却贫乏的形势。因此，从海量数据中挖掘出有价值的信息和所需要的知识已经成为数据挖掘研究领域中的重要任务之一。数据的多样性和丰富性已经形成不同的数据种类，其中包括事务数据、序列数据、流数据、时间序列数据等。序列数据是数据的一种重要类型，其被广泛运用在科学与工程学、商业、客户行为分析、股票趋势预测、DNA序列分析、web使用行为分析及其他的一些实际应用中。它由具有有序元素或事件的序列组成，并且列出或没有列出特定时间概念。尽管对于其他种类的数据已经存在大量通用的数据挖掘方法，但对于序列数据，这些方法不能被应用。因为在所有类型的数据中，序列数据有其自身独特的序列特征，并且可以应用于许多有趣的应用程序中，这使得发现了许多新的有趣种类的知识，包括序列模式、相似生物序列模式、部分有序模式、周期性的模式、模体等；这些种类的模式将有助于开发新的分类、聚类和异常值分析方法，这需要新的不同种类应用程序的发展。序列模式挖掘是数据挖掘研究的重要任务之一，并且被普遍使用到序列数据挖掘应用程序中。它在挖掘关联，相关分析和许多其他有趣的数据之间的关系起着根本性的作用。此外，它提供数据分类，聚类，和其他的数据挖掘任务。序列模式挖掘的过程即在序列数据库中提取频繁子序列。这项工作也更加吸引数据挖掘研究的研究人员的注意，并有许多关于挖掘序列模式的研究作品被审查。然而，面临的主要挑战仍然以大的搜索空间和无效处理稠密数据集的方式存在。例如，当挖掘包含组合数的频繁序列的长频繁序列，长模式挖掘过程中会产生大量频繁子序列，或当使用非常低的支持度阈值来挖掘序列模式时，这在时间和空间成本上都是十分昂贵的。因此，序列模式挖掘算法的性能通常会出乎意料地被降低。要解决上述挑战，挖掘序列规则，闭序列模式，以及顺序生成模式的问题已经被提出。前缀树是一个有序的树数据结构，用于存储序列的快速查找，其中父节点的所有孩子节点都有一个与该节点相关的序列的共同的前缀，而根节点与空序列有关联。其最简单的形式中通常可以使用的关键字的列表或字典。构建前缀树的过程是,建立序列之间父节点与孩子节点间直接关系,共同帮助开采过程中采取更快、更直观的方法,其中前缀树从根节点具有空序列的0层开始。每个子节点在1层存储一个序列模式,每个节点在k层都是一个单一的项目集；每个节点设置一个k模式序列。递归地,继一个k模式序列后还有下一级(k+1)以单个项目延深。有两种方法可以扩展一个k-模式序列,即序列扩展项集延伸。在序列扩展中,表示为◇s,I是在最终以字典顺序排序的项目集中大于其中所有其他项目的项目,其中单一的项目被添加到k-模式序列最后的项目集作为一个新的项集,增加序列的大小。一个序列α是α所有序列扩展序列的一个前缀, α是α中扩展序列节点的所有子节点的前缀。在项集扩展表示◇s,扩展的项集序列的大小没有改变。 α是α中扩展项集节点的所有子节点的一个不完全前缀。项目集扩展表示为◇i,扩展的项目集序列的大小不会改变, α是一个在α中扩展项目集节点的所有子节点的不完整前缀。关于前缀树的节点序列常以字典字母顺序出现,所以他们采用深度优先搜索方式。基于前缀树,我们遵守的规则基于深度优先搜索如下：ⅰ.如果序列β′=β◇θ,那么β<β′,所以我们需要首先搜索前缀,然后搜索序列。例如,给出序列<(AB)>,我们首先搜索<A>,然后搜索<(AB)>。如果序列β=α◇Sθ和β′=α◇iθ,然后β<β′,所以我们需要首先搜索序列扩展,然后搜索项集扩展。例如,给出序列<(A)(B)> and<(AB)>,首先搜索<(A)(B)>,然后搜索<(AB)>。ⅱ.如果β=α◇θ并且β′=α◇θ′,θ<θ’意味着β<β′,然后两个序列β和β′有相同的前缀,所以基于后缀的字母顺序搜索他们。例如,给出一个序列<(A)(A)>和<(A)(B)>,我们首先搜索<(A)(A)>然后搜索<(A)(B)>。在本文中,我们提出了新的算法以如下两个主要目标来解决这些问题。●二级信息如基于相应前缀树结构的序列模式,闭序列模式,序列生成模式的开发●在前缀树结构中,基于二级信息生成多种序列规则。在这篇论文中,我们做出的四项主要贡献可以简要描述如下第一,我们也提出一个有效的算法,采用从存储了整个序列模式的前缀树获得的以上趣味性措施来生成所有相关顺序的规则,序列模式的每个子节点存储序列模式及其相应的支持值。通过遍历前缀树,该算法可以很容易地识别一个规则的组成部分,并且可以计算出测量值的规则。本文中我们提到了像Lift, Conviction, Piatetsky-Shapiro, Cosine, Jaccard等几个兴趣度,这些规则的提出是为了挖掘关联规则和分类规则,但他们并没有被应用到序列数据库挖掘序列规则,除了传统措施的规则如支持度和置信度。在数据挖掘研究中挖掘序列规则是一个重要问题。已经提出了通过应用规则的兴趣度度量决策相关的知识和去除虚假模式。兴趣度规则在挖掘数据研究中是重要的规则挖掘指标。它们可以用来减少搜索空间的大小,从而提高了挖掘效率,或根据它们的兴趣度值的安排的排列模式。此外,在从发现规则集中选择有用或有趣的规则的过程中,他们起着至关重要的作用。经常用来计算规则X(?)Y的测量值的术语,是序列数据库中的序列的总数(n),包含X的序列数(nX)，含Y的序列数(nY),包含X和Y的序列数(nXY),包含X但不包含Y的序列数(nXY),包含Y序列但不包含X的序列(nXY)。如果我们知道n, nX, nY和nXY。在这些方程中计算评估值得其他项目可以很容易被表示为nXY=nX-nXU, nXT=nY-nXY, nX=n-nX和nY=n-nY。o形成了一种序列规则X(?) Y (q, imv),其中X和Y是序列模式,X∩Y=(?),q是规则(q=Sup(X, Y))的支撑,imv是规则的兴趣度值。在传统的序列规则,imv是一个规则的自信度,并且imv=Sup(X,Y)/Sup(X)。一个序列规则可通过将序列分成两部分来创建：前缀(pre)和后缀(post)的顺序模式。如果pre与post串联,表示为pre++post,那么结果是初始的序列模式。序列规则r由此可以形成pre(?)post (Sup, imv)。r的支持Sup(r)因此为Sup(pre++post)。r值的趣味性措施imv, r的传统测量值是r的置信度Conf(r)。也就是说,Conf(r)=Sup(pre++post)/Sup (pre) o以前缀树兴趣度度量挖掘序列规则的算法可被详细描述如下：它首先调用PRISM算法生成前缀树结构中所有的序列模式,这些模式和存储。对于每个节点SP在1级的前缀树,它调用GENERATE SR FROM TREE ROOT程序生成序列规则,从每个子树与SP作为根节点。当过程GENERATE SR FROM TREE ROOT中被处理时,有两种类型的节点：序列扩展节点和项集扩展节点。由于项集扩展的节点集的大小不改变,根节点的大小是基于扩展项集的定义,那么序列规则不是从这个项目集扩展的节点集形成的。子树的节点是根节点的序列扩展节点,子树序列的序列规则是调用程序GENERATE SR FROM SUBTREE而形成的,因为上面的根序列记为pre会形成从根的序列扩展节点扩展的所有序列的前缀。因此,对于每个子树中,子树序列的序列规则根据前缀pre而形成。现有的根节点的所有扩展节点由此成为下一级子树的前缀,这个过程被每个根节点的扩展节点递归地调用。此递归过程反复进行,直至达到最后一级的前缀树此外,在程序GENERATE SR FROM SUBTREE中,输入是序列pre预和子树,因而pre是子树所有序列的一个共有前缀。子树中的每个序列SP,规则“pre post”形成，由此post是SP的一个关于pre前缀的前缀。一个规则的大多数有趣的方法依赖于Post的支持，为了获得Post的支持，程序FIND_SUP_POST(RNode,Post)被调用，RNode是Post的前缀树中的第一个根节点并且为非空。FIND_SUP_POST程序(RNode,Post)产生Post的支持通过遍历以RNode为根节点的前缀树的所有分支，Rnode为Post的前缀。实验结果表明，使用这种基于前缀树并结合趣味性标准的序列规则挖掘算法，比使用其他现有的改进算法更快，特别是用最小支持度去挖掘大型序列数据库时，从序列数据库中产生序列模型的数量是非常巨大。并且该算法比那些只通过前缀树立即去确定一个序列是左边还是右边规则的算法，并且他们的支持度值从序列模式集中计算兴趣度值的规则。第二，本文中，序列生成器模式的特征是结合前缀树的扩展序列提出了两种高效的算法，命名为MSGPs和MSGP_PreTre，这两种算法在产生序列模式的同时挖掘出所有的序列生成器模式。使用前缀树，通过附加到最后位置的一个父节点作为项集合的扩展或通过序列扩展，作为子节点集的新序列可以很容易的创建。该方法使用了主模块编码方法来表示候选序列，并且通过在主模块使用联合操作来判断每个候选序列的频率。在MSGPs算法中，为了能快速检查，它使用了一个带有哈希秘钥的哈希表来存储序列生成模式作为模式的支持度。MSGPs算法中输入参数是一个序列数据库(SD)和最小支持度，输出是一组序列生成器模式(SGPs)。为了能快速检索，使用哈希表存储模式。首先，该算法遍历序列数据库一次，找到所有频率为1的模式并存储到dbpat。每个出现频率为1模式序列作为一个序列生成器模式增加到SGPs，对于每个在数据集dbpat中的模式,EXTEND_TREE通过在前缀树中使用深度优先搜素去扩充对应的前缀树。算法然后返回SGPs中所有的序列生成器模式。扩充树种每个根节点有两个扩充类型，项目集扩展和序列扩展，EXTEND_ITEMSET和EXTEND_SEQUENCE各自扩充了树。基于性质4.3，算法然后调用EXTEND_TREE通过扩充根节点集继续扩充树，这样可以减少搜索空间，算法仅扩充序列生成器中的节点。EXTEND_ITEMSET通过在数据集dbpat中附加没一项来增加新节点集，其中每一项必须大于最后一个项目在最近项目集的扩展节点和到最后的项目集的扩展节点。使用基于棱柱分解的块编码来创建一个新的模式和计算其支持度。如果新模式Pnew是序列模式并且Pnew的支持度和扩充节点相等，则Pnew不是生成模式。否则，调用CHECK_GENERATOR检查Pnew是否是生成器，然后将Pnew添加到扩充节点的项扩充集里。EXTEND_SEQUENCE通过增加dbpat中每一项到扩充节点的最后位置来创建新模式Pnew。每一个添加的项目新节点Pnew最近的项集。如果Pnew的支持度与扩展节点相同，则Pnew是一个非生成模式。否则，调用CHECK_GENERATOR去确认Pnew是否是一个生成器模式，然后增加Pnew到扩充节点的扩充序列。在CHECK_GENERATOR中，如果Pnew是P的子序列，P是非生成模式，则P可以被Pnew取代，如果Pnew是P的超序列，并且Pnew是一个非生成模式，如果Pnew不存在SGPs中，则它可以被插入到生成模式集合中。在生成序列生成器模式的算法中，MSGP_PreTree算法是另一个改进了MSGPs算法的有效算法。改进算法的思想是通过修改前缀树，前缀树的每个节点将被添加字段，确实存储在这个节点上的序列是否是一个序列生成器。整个序列的信息存储在前缀树，所以MSGP_PreTree算法不需要使用哈希表来存储序列生成器模式。基于频率的超序列和前缀树的非生成树的删减应用在MSGP_PreTree算法来减少搜索空间。为了生成所有的序列生成模式，MSGP_PreTree算法在MSGPs算法的基础上进行了改进。改进算法的想法是通过修改前缀树执行的，例如前缀树中的每个顶点将会添加字段来检查储存在这个点中的这个序列是否是一个序列生成模式。这个序列的所有信息都被储存在前缀树中，所以MSGP_PreTree算法不需要跟哈希表来储存序列生成模式，这样会大大减少内存的使用。超层序在前缀树中基于频繁的剪支和基于非生成器的剪支被应用在MSGP_PreTree算法中来减少所有空间。扩展前缀树和在MSGP_PreTree算法中决策序列模式的过程，与MSGP算法是相似的。MSGP_PreTree算法也初始化pretree树，把根节点设为空，遍历SD一次找出所有频率为1的模式并且将其存储在SPs中。每个SPs中的频率模式作为一个根节点被插入到pretree。对于每一个频率为1的模式序列是一个序列生成模式，所以在pretree中所有序列为1的模式序列被设置作为一个生成器。对于Pretree的每个节点，算法通过调用EXTEND_TREE去扩展相应的前缀树。算法返回的pretree包含所有的SGPs。在EXTEND_TREE,每根节点有两个扩展类型，项目集扩展和序列扩展，对应的扩展过程分别是EXTEND_ITEMSET和EXTEND_SEQUENCE。对于根节点的每个扩充节点集，算法调用EXTEND_TREE继续扩展树。对于扩充节点中的项目集中的每个节点，删减搜索空间保证算法仅遍历生成模式的节点。EXTEND_ITEMSET通过在SPs中增加项来创建新节点,其中增加的项必须大于扩从节点最后一个项集的最后一项。算法使用基于棱镜分解的块编码来创建一个新的模式并计算支持度。如果Pnew的支持度等于扩充节点，则Pnew是非扩充集，否则调用CHECK_GENERATOR确认Pnew是否是生成器，然后Pnew作为扩充节点的孩子节点的扩充项增加到pretree。EXTEND_SEQUENCE通过在dbpat增加每一项到扩充节点的最后位置来创建新模式Pnew。每一个添加的项目新节点Pnew最近的项集。如果Pnew的支持度与扩展节点相同,则Pnew是一个非生成模式。否则,调用CHECK_GENERATOR去确认Pnew是否是一个生成器模式，然后增加Pnew到扩充节点的扩充序列。在CHECK_GENERATOR中，遍历pretree确认是否存在Pnew的子序列或者超序列是生成器。对于在pretree中有和Pnew一样支持度的模体，如果Pnew是P的子序列，P是非生成模式集，Pnew是生成模式集；如果Pnew是P的超序列，则Pnew是非生成器模式。对于合成的和真实的数据库，所有的实验结果表明序列生成器模式的数量总是小于序列模式的数量，并且在所有情况中这种算法就运行时间来说是胜过其他算法的。第三，我们提出了一种高效的算法，在生成序列模式的过程中，直接来发现闭合序列模式和他们的序列生成器模式，称为CloGen算法（Closedsequential pattern-sequential Generator pattern），该算法是基于结合前缀树结构的父子节点关系和闭合序列模式以及序列生成器模式的定义。 CSGM（闭合序列和序列生成器挖掘）算法是2010年Zang等人首先提出的，算法同时挖掘频繁闭合序列和序列生成器模式。使用CSGM算法，通过遍历序列数据库一次就能产生序列生成器和闭合序列生成器模式，减少了时间复杂度。但是，集合构建对象数据库的时间复杂度很高。论文提出了一个高效的算法能直接发现闭合序列和序列生成器模式，在生成序列模式的过程中调用CloGen算法，该算法是基于结合前缀树中的父子节点关系和闭合序列模式及序列生成器模式。在我们的方法中，前缀树上的每个节点存储了一个序列模式和它相对应的支持度值。此外，它会被添加一个字段（IsmSGP）来决策该节点是否是最小的序列生成模式，并且另一个字段(IsCSP)用来决策该节点是否是一个闭合序列模式。根据添加到节点上的这些字段，算法很容易判断每个节点上的序列是最小生成器序列还是闭合序列模式，所以算法的时间复杂度明显减少了。算法同时也在素因子分解的主模块编码方法上使用了联合操作来代表候选序列并且判定每个候选序列的频率。算法描述如下：首先，初始化前缀树pretree，根节点是空节点设置为空，孩子节点序列模式为1设置IsmSGP和IsCSP为true。每个前缀树的孩子节点作为根节点，使用EXTEND_TREE算法创建孩子节点并且扩充前缀树。在函数中，每个根节点P的孩子节点是由项扩充或序列扩充创建的。为找出候选序列和决定每个序列的频率，使用主模块编码方法和合并主模块。因为每一个新创建的子节点Pnew被分配{IsmSGP,IsCSP}={true,true}，如果Sup(Pnew)=Sup(P)，Pnew.IsmSGP和P.IsCSP将被设置为false。调用UPDATE_PRETREE (Pnew, pretree)更新闭序列模式和前缀树的序列生成器模式。最后，算法返回对应的前缀树。实验结果表明挖掘闭序列模式的运行时间和它们使用CloGen算法的最小序列生成器模型提高了一个数量级。CloGen算法可以同时生成所有的序列模式，序列生成器模式，和闭合序列模式。此外，对于挖掘非冗余序列规则以及挖掘所有序列规则，我们方法中构建的前缀树将会在未来成为最有效前缀树方法之一。第四，本论文提出了一个高效的MNSR-Pretree算法来挖掘非冗余序列规则。这个算法分为两个阶段。第一阶段，它从一个给定的序列数据库中构建了一个前缀树，存储所有的序列模式。在第二阶段，它从这个前缀树中挖掘非冗余序列规则。在前缀树的构建过程中，前缀树中的每个节点都有有一个字段（IsmSGP）来表示该节点是否是最小的序列生成模式，另外一字段（IsCSP）来表示该节点是否是一个闭序列模式。通过遍历这个前缀树，非冗余序列规则可以很容易从最小序列生成器模式X到闭序列Y中挖掘到，因为X是Y的前缀树，这样可以很大程度地减少挖掘所需的时间。基于IsmSGP和IsCSP值，当父节点的IsmSGP值对于子节点IsCSP为真是正确的时，算法才挖掘该规则。因此父节点的序列被认为是先验规则，从闭序列模体中移除前缀部分，挖掘规则就会产生。MNSR-Pretree算法的输入是前缀树pretree和minConf。对于前缀树深入为1的每个节点SP，算法调用GENERATE_NSR_FROM_ROOT(SP)从每个以SP作为根节点的子图中产生非冗余序列规则。最终返回非冗余序列规则集NSR。有两种不同类型的节点：序列扩种节点和项扩充节点。根据项扩充定义，项扩充类型的孩子节点集的大小不会改变根节点的规模。所以GENERATE_NSR_FROM_ROOT(SP)不会在项扩充节点集中产生规则。在序列根节点的扩充集中会产生规则。当子集SP的根节点是最小序列生成器模式（IsSGP为true）。生成树的非冗余序列准则通过函数GENERATE_NSR(SP, Subtree)。生成函数GENERATE_NSR(SP, Subtree)的输入包括子树SP的根节点和子树，其中子树为最小序列生成器模式。子树SP的根序列，和所有字数中的序列有相同的前缀。因此，Pre从根的序列扩充节点构成了所有扩充序列的前缀。非冗余序列准则从前缀树的序列中产生。对于子树种每个节点n，都是序列模式（n的IsCSP为true）。如果Conf≥minConf，则序列准则SR：“Pre Post”成立，其中post是节点n的后缀序列。所有本阶段的根的扩充节点将在下个节点变成字数的前缀，每个根的扩充节点递归调用这个函数。这个过程重复执行直到前缀树的最后一层到达。合成数据和真实的数据库的实验结果表明，序列生成器模式的数量远小于序列模式，而且本文提出的算法在运行时间方面优于其他算法。同时，结果也表明对于挖掘非冗余序列规则本文提出的算法在时间复杂度上是优于现有算法的。综上所述，在本文中我们已经提出了有效的算法并且完成了最开始提出的目标——提高挖掘次级信息算法，如基于前缀树结构的序列模式、闭序列模式和序列生成器模式的有效性。主要的贡献是前缀树的使用，为了从次级信息中生成有效的各种序列规则，如具有兴趣度方法和非冗余序列规则的序列规则。这篇文章的目标已经达到了，通过在前缀结构中使用父子关系和使用序列的扩展，提出新的算法来挖掘有关序列模式的工作，在序列数据库中包括挖掘具有兴趣度方法的序列规则，挖掘生成器模式，挖掘闭合序列模式和它们的序列生成器模式，以及挖掘非冗余的序列规则。上述提出的方法可以被合成和真实的数据进行评估。实验结果显示了算法有效性的显著提高。