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

Mining Negative Sequential Patterns with Periodic Gap Constraints

作　　者：王珠林 武优西 王月华 刘靖宇 WANG Zhulin;WU Youxi;WANG Yuehua;LIU Jingyu(School of Artificial Intelligence,Hebei University of Technology,Tianjin 300401,China;Hebei Key Laboratory of Big Data Computing,Tianjin 300401,China;School of Economics and Management,Hebei University of Technology,Tianjin 300401,China)

机构地区：[1]河北工业大学人工智能与数据科学学院,天津300401 [2]河北省大数据计算重点实验室,天津300401 [3]河北工业大学经济管理学院,天津300401

出　　处：《计算机科学》2023年第3期147-154,共8页Computer Science

基　　金：国家自然科学基金(61976240)。

摘　　要：间隙约束的序列模式挖掘是一种特殊形式的序列模式挖掘方法,该方法能够揭示一定间隔下的频繁出现(发生)的子序列。但当前间隙约束的序列模式挖掘方法只关注正序列模式的挖掘,忽略了事件中的缺失行为。为解决该问题,探索了周期间隙约束的负序列模式(Negative Sequential Pattern with Periodic Gap Constraints,NSPG)挖掘方法,该方法能够更灵活地反映元素与元素之间的关系。为高效求解NSPG挖掘问题,提出了NSPG-INtree(Incomplete Nettrees)算法,该算法主要包括两个步骤:候选模式生成和支持度计算。在候选模式生成方面,为了减少候选模式的数量,该算法采用模式连接策略;在支持度计算方面,为了提高模式支持度计算效率并减少空间消耗,该算法采用不完整网树结构计算模式支持度。实验结果表明,NSPG-INtree算法不仅具有较高的挖掘效率,而且能同时挖掘间隙约束的正序列模式和负序列模式。与其他间隙约束的序列模式挖掘算法相比,NSPG-INtree能够多发现209%~352%的模式;与不同策略的对比算法相比,NSPG-INtree能够缩短6%~38%的运行时间。Sequential pattern mining with gap constraints is a special form of sequential pattern mining,which can reveal frequent subsequences in a certain gap.However,the current sequential pattern mining methods with gap constraints only focus on positive sequential pattern mining,and ignore the missing behavior in a series of events.To solve this problem,a negative sequential pattern method with periodic gap constraints(NSPG)mining is explored,which can reflect the relationship between elements more flexibly.To solve the problem of NSPG mining,this paper proposes an NSPG-INtree(incomplete nettrees)algorithm,which includes two key steps:candidate pattern generation and support calculation.For candidate pattern generation,to reduce the number of candidate patterns,the algorithm uses a pattern join strategy.For support calculation,to improve the efficiency and reduce space consumption,the algorithm employs an incomplete nettree structure to calculate the supports of patterns.Experimental results show that NSPG-INtree not only has high mining efficiency,but also can mine positive and negative sequential patterns with gap constraints.NSPG-INtree can find 209%~352%more patterns than other gap-constrained sequential pattern mining algorithms.Moreover,NSPG-INtree can reduce the running time by 6%~38%than other competitive algorithms with different stra-tegies.

关 键 词：序列模式挖掘 负序列模式 频繁模式 间隙约束 不完整网树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]