删除或更新信息,请邮件至freekaoyan#163.com(#换成@)

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

本站小编 Free考研考试/2022-01-02

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



Abstract:Nonoverlapping conditional sequence pattern mining is a method of gap constrained sequence pattern mining. Compared with similar mining methods, this method is easier to find valuable frequent patterns. The core of the problem is to calculate the support (or the number of occurrences) of a pattern in the sequence, and then determine whether the pattern is frequent. The essence of calculating the support is the pattern matching under nonoverlapping condition. The current studies employ the iterative search to find a nonoverlapping occurrence, and then prune the useless nodes to calculate the support of the pattern. The computational time complexity of these algorithms is O(m×m×n×W), where m, n, and W are the pattern length, sequence length, and maximum gap, respectively. In order to improve the calculation speed of pattern matching under nonoverlapping condition, and effectively reduce sequence pattern mining time, this study proposes an efficient and effective algorithm, which converts the pattern matching problem into a NetTree, then starts from the minroot node of the NetTree, and adopts the backtracking strategy to iteratively search the leftmost child to calculate the nonoverlapping minimum occurrence. After pruning the occurrence on the NetTree, the problem can be solved without further searching and pruning invalid nodes. This study proves the completeness of the algorithm and reduces the time complexity to O(m×n×W). On this basis, the study continues to indicate that there are other three similar solving strategies for this problem, iteratively finds the leftmost parent path from the leftmost leaf, the rightmost child path from the rightmost root, and the rightmost parent path from the rightmost leaf. Extensively experimental results verify the efficiency of the proposed algorithm in this study, especially, the mining algorithm adopting this method can reduce the mining time.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6054
相关话题/计算 序列 实验 模式 算法

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19
  • 噪音数据的属性选择算法
    摘要:正则化属性选择算法减小噪音数据影响的效果不佳,而且样本空间的局部结构几乎没有被考虑,在将样本映射到属性子空间后,样本之间的联系与原空间不一致,导致数据挖掘算法的效果不能令人满意.提出一个抗噪音属性选择方法,可以有效地解决传统算法的这两个缺陷.该方法首先采用自步学习的训练方式,这不仅能大幅度降低 ...
    本站小编 Free考研考试 2022-01-02
  • 改进的元启发式优化算法及其在图像分割中的应用
    摘要:元启发式算法自20世纪60年代提出以后,由于其具有可以有效地减少计算量、提高优化效率等优点而得到了广泛应用.该类算法以模仿自然界中各类运行机制为特点,具有自我调节的特征,解决了诸如梯度法、牛顿法和共轭下降法等这些传统优化算法计算效率低、收敛性差等缺点,在组合优化、生产调度、图像处理等方面均有很 ...
    本站小编 Free考研考试 2022-01-02
  • 优化简单表缩减算法求解因子分解编码实例
    摘要:表约束在约束程序(constraintprogramming,简称CP)中被广泛研究.目前,求解表约束问题效率最高的算法是CT(compact-table)和STRbit(simpletabularreductionbit).它们在搜索过程中维持广义弧相容(generalizedarccons ...
    本站小编 Free考研考试 2022-01-02
  • 一种基于进化策略和注意力机制的黑盒对抗攻击算法
    摘要:深度神经网络在许多计算机视觉任务中都取得了优异的结果,并在不同领域中得到了广泛应用.然而研究发现,在面临对抗样本攻击时,深度神经网络表现得较为脆弱,严重威胁着各类系统的安全性.在现有的对抗样本攻击中,由于黑盒攻击具有模型不可知性质和查询限制等约束,更接近实际的攻击场景.但现有的黑盒攻击方法存在 ...
    本站小编 Free考研考试 2022-01-02
  • 基于贝叶斯网络的时间序列因果关系学习
    摘要:贝叶斯网络是研究变量之间因果关系的有力工具,基于贝叶斯网络的因果关系学习包括结构学习与参数学习两部分,其中,结构学习是核心.目前,贝叶斯网络主要用于发现非时间序列数据中所蕴含的因果关系(非时间序列因果关系),从数据中学习得到的也均是一般变量之间的因果关系.针对这些情况,结合时间序列预处理、时间 ...
    本站小编 Free考研考试 2022-01-02
  • 一种采用新型聚类方法的最佳类簇数确定算法
    摘要:聚类分析是统计学、模式识别和机器学习等领域的研究热点.通过有效的聚类分析,数据集的内在结构与特征可以被很好地发掘出来.然而,无监督学习的特性使得当前已有的聚类方法依旧面临着聚类效果不稳定、无法对多种结构的数据集进行正确聚类等问题.针对这些问题,首先将K-means算法和层次聚类算法的聚类思想相 ...
    本站小编 Free考研考试 2022-01-02
  • 基于多策略的改进花授粉算法
    摘要:花授粉算法是近年来提出的一种新型的、简单高效的优化算法,已在各个领域得到广泛应用,但其搜索策略存在的不足,制约着其应用范围.为此,提出一种改进的基于多策略的花授粉算法.首先,新全局搜索策略通过利用两组随机个体差异矢量和莱维飞行机制来增加种群多样性并扩大搜索范围,使算法更易跳出局部最优,提升其开 ...
    本站小编 Free考研考试 2022-01-02
  • 领域驱动设计模式的收益与挑战:系统综述
    摘要:背景:近年来,领域驱动设计(domaindrivendesign,简称DDD)作为一种软件设计方法在业界中逐渐流行起来,并形成了若干应用的固有范式,即领域驱动设计模式(domaindrivendesignpattern,简称DDDP).然而,目前软件开发社区却仍然对DDDP在软件项目中的作用缺 ...
    本站小编 Free考研考试 2022-01-02
  • 基于多核CPU的表约束并行传播模式研究
    摘要:并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容(generalizedarcconsistency,简称GAC)的串行传播模式,提出了维持表约束网络临时广义弧相容(temporarygeneralizedarcconsist ...
    本站小编 Free考研考试 2022-01-02
  • 概率积分及其在PUFFIN算法中的应用
    摘要:积分分析是一种针对分组密码十分有效的分析方法,其通常利用密文某些位置的零和性质构造积分区分器.基于高阶差分理论,可通过研究密文与明文之间多项式的代数次数来确定密文某些位置是否平衡.从传统的积分分析出发,首次考虑常数对多项式首项系数的影响,提出了概率积分分析方法,并将其应用于PUFFIN算法的安 ...
    本站小编 Free考研考试 2022-01-02