对比保序模式挖掘算法  

Contrast order-preserving pattern mining algorithm

作　　者：孟玉飞 武优西 王珍 李艳[2] MENG Yufei;WU Youxi;WANG Zhen;LI Yan(School of Artificial Intelligence,Hebei University of Technology,Tianjin 300401,China;School of Economics and Management,Hebei University of Technology,Tianjin 300401,China)

机构地区：[1]河北工业大学人工智能与数据科学学院,天津300401 [2]河北工业大学经济管理学院,天津300401

出　　处：《计算机应用》2023年第12期3740-3746,共7页journal of Computer Applications

基　　金：河北省自然科学基金资助项目(F2020202013)。

摘　　要：针对现有的对比序列模式挖掘方法主要针对字符序列数据集且难以应用于时间序列数据集的问题,提出一种对比保序模式挖掘(COPM)算法。首先,在候选模式生成阶段,采用模式融合策略减少候选模式数;其次在模式支持度计算阶段,利用子模式的匹配结果计算超模式的支持度;最后,设计了动态最小支持度阈值的剪枝策略,以进一步有效地剪枝候选模式。实验结果表明,在6个真实的时间序列数据集上,在内存消耗方面,COPM算法至少比COPM-o(COPM-original)算法降低52.1%,比COPM-e(COPM-enumeration)算法低36.8%,比COPM-p(COPM-prune)算法降低63.6%;同时在运行时间方面,COPM算法至少比COPM-o算法降低30.3%,比COPM-e算法降低8.8%,比COPM-p算法降低41.2%。因此,在算法性能方面,COPM算法优于COPM-o、COPM-e和COPM-p算法。实验结果验证了COPM算法可以有效挖掘对比保序模式,发现不同类别的时间序列数据集间的差异。Aiming at the problem that the existing contrast sequential pattern mining methods mainly focus on character sequence datasets and are difficult to be applied to time series datasets,a new Contrast Order-preserving Pattern Mining(COPM)algorithm was proposed.Firstly,in the candidate pattern generation stage,a pattern fusion strategy was used to reduce the number of candidate patterns.Then,in the pattern support calculation stage,the support of super-pattern was calculated by using the matching results of sub-patterns.Finally,a dynamic pruning strategy of minimum support threshold was designed to further effectively prune the candidate patterns.Experimental results show that on six real time series datasets,the memory consumption of COPM algorithm is at least 52.1%lower than that of COPM-o(COPM-original)algorithm,36.8%lower than that of COPM-e(COPM-enumeration)algorithm,and 63.6%lower than that of COPM-p(COPM-prune)algorithm.At the same time,the running time of COPM algorithm is at least 30.3%lower than that of COPM-o algorithm,8.8%lower than that of COPM-e algorithm and 41.2%lower than that of COPM-p algorithm.Therefore,in terms of algorithm performance,COPM algorithm is superior to COPM-o,COPM-e and COPM-p algorithms.The experimental results verify that COPM algorithm can effectively mine the contrast order-preserving patterns to find the differences between different classes of time series datasets.

关 键 词：模式挖掘 序列模式挖掘 时间序列 对比模式 保序模式 

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