无重叠条件严格模式匹配的高效求解算法
作者:
作者单位:

作者简介:

武优西(1974-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据挖掘,机器学习.
郭磊(1968-),男,博士,教授,博士生导师,主要研究领域为模式识别,人工神经网络.
刘茜(1994-),女,硕士,主要研究领域为模式匹配.
吴信东(1963-),男,博士,教授,博士生导师,主要研究领域为数据挖掘,基于知识的系统,万维网信息探索.
闫文杰(1983-),男,博士,副教授,CCF专业会员,主要研究领域为机器学习.

通讯作者:

武优西,E-mail:wuc567@163.com

基金项目:

国家重点研发计划(2016YFB1000901);国家自然科学基金(61976240,61702157,917446209);河北省创新能力培养资助项目(CXZZSS2019023)


Efficient Algorithm for Solving Strict Pattern Matching Under Nonoverlapping Condition
Author:
Affiliation:

Fund Project:

National Key Research and Development Program of China (2016YFB1000901); National Natural Science Foundation of China (61976240, 61702157, 917446209); Graduate Student Innovation Program of Hebei Province (CXZZSS2019023)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现,然后剪枝无用结点的方式计算模式的支持度,其计算时间复杂度为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.

    参考文献
    相似文献
    引证文献
引用本文

武优西,刘茜,闫文杰,郭磊,吴信东.无重叠条件严格模式匹配的高效求解算法.软件学报,2021,32(11):3331-3350

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:2019-06-10
  • 最后修改日期:2019-12-25
  • 录用日期:
  • 在线发布日期: 2021-11-05
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号