无重叠条件严格模式匹配的高效求解算法

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法，与同类挖掘方法相比，该方法更容易发现有价值的频繁模式，其核心问题是计算给定模式在序列中的支持度或出现数，进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现，然后剪枝无用结点的方式计算模式的支持度，其计算时间复杂度为O （m×m×n×W），其中，m，n和W分别为模式长度、序列长度及最大间隙.为了进一步提高无重叠条件模式匹配计算速度，从而有效地降低无重叠条件序列模式挖掘时间，提出了一种高效的算法，该算法将模式匹配问题转换为一棵网树，然后从网树的最小树根结点出发，采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现，在网树上剪枝该出现后，无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备性，并将该算法的时间复杂度降低为O （m×n×W）.在此基础上，继续指明该问题还存在另外3种相似的求解策略，分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式.实验结果验证了该算法的性能，特别是在序列模式挖掘中，应用该方法的挖掘算法可以降低挖掘时间.     

无重叠条件模式匹配的在线求解算法

无重叠条件模式匹配是众多间隙约束的模式匹配算法中的一种,尽管当前证明了无重叠条件模式匹配是一个多项式时间复杂度问题,并提出了有效的求解算法,但是当前求解算法采用离线计算方式,具有空间复杂度较高的缺点。为了解决该问题,设计了一种在线求解算法,该算法一边读入序列串,一边在流网树中寻找符合约束条件的树根-树叶路径,以快速剪枝无用节点,从而加快了匹配速度。与离线算法的空间复杂度相比,在线算法的空间复杂度为O(m×maxlen×W),这里m,maxlen和W分别表示模式串长度、模式最大长度约束和最大间隙约束。实验结果不仅验证了算法的完备性,与现有算法相比,在内存占用上均有较大性能的提升。     

子网树求解一般间隙和长度约束严格模式匹配

具有通配符间隙约束的模式匹配问题在信息检索、计算生物学和序列模式挖掘等研究领域有重要的应用.提出了更一般性的模式匹配问题,即一般间隙和长度约束的严格模式匹配(strict pattern matching with generalgaps and length constraints,简称SPANGLO).该问题具有如下4 个特点:它是一种严格的精确模式匹配;允许序列中任意位置的字符被多次使用;模式串中可以包含多个一般间隙;对出现的总体长度进行了约束.最坏情况下,一个SPANGLO 实例将转换出指数个非负间隙的严格模式匹配实例.为了有效地解决该问题,提出了子网树及其相关概念和性质.在此基础上提出了求解算法Subnettree Spanglo(SETS),并给出算法的正确性和完备性证明,同时指出该算法的空间复杂度与时间复杂度分别为O(m×MaxLen×W)和O(MaxLen×W×m²×n),其中,m,n,MaxLen和W分别是模式和序列的长度、出现的最大长度约束和模式的最大间距.实验结果既验证了SPANGLO 问题转换方法的正确性,又验证了该算法的正确性和有效性.     

一般间隙与One-Off条件的序列模式匹配

带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前大多数的研究都为非负间隙,对字符串中的每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题,该问题为NP-Hard问题.为了有效的求解该问题,提出了MSAING(Maximum Sequential pattern mAtching wIth oNe-off and General gaps condition)算法,首先利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度的降低,同时利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制,判断模式串是否会产生内部重复现象,进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性,以及在时间和空间方面的高效性.     

一般间隙近似无重叠模式匹配

具有间隙约束条件模式匹配问题是序列模式挖掘问题的基础与核心.无重叠模式匹配是其中的一种方法,当前研究是在间隙为正的精确模式匹配,为了进一步增加匹配的灵活性,本文探索了一般间隙近似无重叠模式匹配问题.本文提出一种有效的求解算法,该算法首先将问题转化为网树;然后为了有效地避免可行解丢失,提出近似监测机制以解决该问题;采用迭代搜索最左孩子策略的方式寻找无重叠出现;之后在网树上剪枝找到的无重叠出现,并迭代上述过程直至没有新的无重叠出现产生.最后本文理论分析了算法的空间复杂度和时间复杂度.大量实验结果验证了本文算法具有较好的求解质量及求解效率.     

具有周期间隙约束的负序列模式挖掘

间隙约束的序列模式挖掘是一种特殊形式的序列模式挖掘方法，该方法能够揭示一定间隔下的频繁出现(发生)的子序列。但当前间隙约束的序列模式挖掘方法只关注正序列模式的挖掘，忽略了事件中的缺失行为。为解决该问题，探索了周期间隙约束的负序列模式(Negative Sequential Pattern with Periodic Gap Constraints, NSPG)挖掘方法，该方法能够更灵活地反映元素与元素之间的关系。为高效求解NSPG挖掘问题，提出了NSPG-INtree(Incomplete Nettrees)算法，该算法主要包括两个步骤：候选模式生成和支持度计算。在候选模式生成方面，为了减少候选模式的数量，该算法采用模式连接策略；在支持度计算方面，为了提高模式支持度计算效率并减少空间消耗，该算法采用不完整网树结构计算模式支持度。实验结果表明，NSPG-INtree算法不仅具有较高的挖掘效率，而且能同时挖掘间隙约束的正序列模式和负序列模式。与其他间隙约束的序列模式挖掘算法相比，NSPG-INtree能够多发现209%～352%的模式；与不同策略的对比算法相比，NSPG-INtree能够缩...     

网树求解有向无环图中具有长度约束的简单路径和最长路径问题

具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.     

带任意长度通配符的模式匹配

基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值.提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Pattern matching with arbitrary-length wildcards,PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大.给定序列S和带通配符的模式P,目标是从S中检索P的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置.为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW (Method of ocurrence then window)算法和MWTO (Method of window then ocurrence)算法.同时,MWTO算法进行细微改动就可以满足全局长度约束.实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能.     

一种求解MPMGOOC问题的启发式算法

具有间隙约束和一次性条件的最大模式匹配(Maximum Pattern Matching with Gaps and One-Off Condition,MPMGOOC)是一种具有通配符长度约束的模式匹配问题,其任务是寻找彼此互不相关的最多出现.文中基于一种新的非线性数据结构——网树,提出了一种解决MPMGOOC问题的...     

TDTMS:一种面向XML数据的结果子树构建算法

构建结果子树是XML关键字查询得以完成的关键步骤之一.针对已有方法求解子树效率低的问题,文中提出一种自顶向下的子树构建算法——TDTMS.TDTMS以自顶向下、深度优先的方式求解满足条件的子树根结点,避免了已有方法求解SLCA结点时存在的公共祖先重复处理问题.对于给定的子树根结点,TDTMS以自顶向下、广度优先的方式构建子树,可以在建树过程中快速裁剪无用结点,从而获得了最小的时间和空间复杂度.最后通过实验验证了TDTMS在时间和空间两方面的性能优势.     

Strict pattern matching under non-overlapping condition

Pattern matching (or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support (or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints (or flexible wildcards) uses the number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.     

Mining Web Log Sequential Patterns with Position Coded Pre-Order Linked WAP-Tree

Sequential mining is the process of applying data mining techniques to a sequential database for the purposes of discovering the correlation relationships that exist among an ordered list of events. An important application of sequential mining techniques is web usage mining, for mining web log accesses, where the sequences of web page accesses made by different web users over a period of time, through a server, are recorded. Web access pattern tree (WAP-tree) mining is a sequential pattern mining technique for web log access sequences, which first stores the original web access sequence database on a prefix tree, similar to the frequent pattern tree (FP-tree) for storing non-sequential data. WAP-tree algorithm then, mines the frequent sequences from the WAP-tree by recursively re-constructing intermediate trees, starting with suffix sequences and ending with prefix sequences.This paper proposes a more efficient approach for using the WAP-tree to mine frequent sequences, which totally eliminates the need to engage in numerous re-construction of intermediate WAP-trees during mining. The proposed algorithm builds the frequent header node links of the original WAP-tree in a pre-order fashion and uses the position code of each node to identify the ancestor/descendant relationships between nodes of the tree. It then, finds each frequent sequential pattern, through progressive prefix sequence search, starting with its first prefix subsequence event. Experiments show huge performance gain over the WAP-tree technique.     

带通配符和One-Off条件的序列模式挖掘

很多应用领域产生大量的序列数据。如何从这些序列数据中挖掘具有重要价值的模式,已成为序列模式挖掘研究的主要任务。研究这样一个问题：给定序列S、支持度阈值和间隔约束,从序列S中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束。设计了一种有效的带有通配符的模式挖掘算法One-Off Mining,模式在序列中的出现满足One-Off条件,即模式的任意两次出现都不共享序列中同一位置的字符。在生物DNA序列上的实验结果表明,One-Off Mining比相关的序列模式挖掘算法具有更好的时间性能和完备性。     

Mining weighted sequential patterns in a sequence database with a time-interval weight

Sequential pattern mining, including weighted sequential pattern mining, has been attracting much attention since it is one of the essential data mining tasks with broad applications. The weighted sequential pattern mining aims to find more interesting sequential patterns, considering the different significance of each data element in a sequence database. In the conventional weighted sequential pattern mining, usually pre-assigned weights of data elements are used to get the importance, which are derived from their quantitative information and their importance in real world application domains. In general sequential pattern mining, the generation order of data elements is considered to find sequential patterns. However, their generation times and time-intervals are also important in real world application domains. Therefore, time-interval information of data elements can be helpful in finding more interesting sequential patterns. This paper presents a new framework for finding time-interval weighted sequential (TiWS) patterns in a sequence database and time-interval weighted support (TiW-support) to find the TiWS patterns. In addition, a new method of mining TiWS patterns in a sequence database is also presented. In the proposed framework of TiWS pattern mining, the weight of each sequence in a sequence database is first obtained from the time-intervals of elements in the sequence, and subsequently TiWS patterns are found considering the weight. A series of evaluation results shows that TIWS pattern mining is efficient and helpful in finding more interesting sequential patterns.     

一种基于MFSP-DG的个性化推荐算法

提出一种基于最大频繁序列模式有向图的页面个性化推荐技术,由于考虑了用户会话的页面访问顺序,比一些不考虑页面访问顺序的推荐技术有更高的准确率。有向图结构压缩存储了所有最大频繁序列模式,推荐引擎依据截取的用户最近访问页面子序列,与有向图的部分路径进行匹配并进行横向推荐和纵向推荐,无需在整个模式库中搜索相同或相似的模式,从而加快了模式匹配的速度,更好地满足了页面推荐的特性和实时要求。实验证明,方法是有效的。     

一种序列模式发现的新方法*

针对序列模式挖掘,提出频繁2序列图(F2SG)来表示数据库中的序列信息,通过扫描一次数据库,将与挖掘任务相关的信息映射到F2SG中,并在此基础上提出一种新的序列模式发现算法——GBSP。GBSP算法充分利用F2SG中表示的项目之间的次序关系进行频繁序列挖掘,提高了其生成效率。理论分析与实验表明,该算法较传统的序列模式发现算法在时间和空间性能上具有优越性。     

Mining sequential patterns across multiple sequence databases

In this paper, given a set of sequence databases across multiple domains, we aim at mining multi-domain sequential patterns, where a multi-domain sequential pattern is a sequence of events whose occurrence time is within a pre-defined time window. We first propose algorithm Naive in which multiple sequence databases are joined as one sequence database for utilizing traditional sequential pattern mining algorithms (e.g., PrefixSpan). Due to the nature of join operations, algorithm Naive is costly and is developed for comparison purposes. Thus, we propose two algorithms without any join operations for mining multi-domain sequential patterns. Explicitly, algorithm IndividualMine derives sequential patterns in each domain and then iteratively combines sequential patterns among sequence databases of multiple domains to derive candidate multi-domain sequential patterns. However, not all sequential patterns mined in the sequence database of each domain are able to form multi-domain sequential patterns. To avoid the mining cost incurred in algorithm IndividualMine, algorithm PropagatedMine is developed. Algorithm PropagatedMine first performs one sequential pattern mining from one sequence database. In light of sequential patterns mined, algorithm PropagatedMine propagates sequential patterns mined to other sequence databases. Furthermore, sequential patterns mined are represented as a lattice structure for further reducing the number of sequential patterns to be propagated. In addition, we develop some mechanisms to allow some empty sets in multi-domain sequential patterns. Performance of the proposed algorithms is comparatively analyzed and sensitivity analysis is conducted. Experimental results show that by exploring propagation and lattice structures, algorithm PropagatedMine outperforms algorithm IndividualMine in terms of efficiency (i.e., the execution time).