对比保序模式挖掘算法

doi:10.11772/j.issn.1001-9081.2022121828

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (12): 3740-3746.DOI: 10.11772/j.issn.1001-9081.2022121828

对比保序模式挖掘算法

孟玉飞¹, 武优西¹(), 王珍¹, 李艳²

^1.河北工业大学人工智能与数据科学学院，天津 300401
^2.河北工业大学经济管理学院，天津 300401

收稿日期:2022-12-09 修回日期:2023-02-24 接受日期:2023-02-28 发布日期:2023-03-06 出版日期:2023-12-10
通讯作者: 武优西
作者简介:孟玉飞（1995—），女，河北石家庄人，硕士研究生，主要研究方向：数据挖掘
王珍（1997—），女，河南周口人，硕士研究生，主要研究方向：数据挖掘
李艳（1975—），女，天津人，副教授，博士，主要研究方向：数据挖掘、供应链管理。
基金资助:
河北省自然科学基金资助项目(F2020202013)

Contrast order-preserving pattern mining algorithm

Yufei MENG¹, Youxi WU¹(), Zhen WANG¹, Yan LI²

^1.School of Artificial Intelligence，Hebei University of Technology，Tianjin 300401，China
^2.School of Economics and Management，Hebei University of Technology，Tianjin 300401，China

Received:2022-12-09 Revised:2023-02-24 Accepted:2023-02-28 Online:2023-03-06 Published:2023-12-10
Contact: Youxi WU
About author:MENG Yufei， born in 1995， M. S. candidate. Her research interests include data mining.
WANG Zhen， born in 1997， M. S. candidate. Her research interests include data mining.
LI Yan， born in 1975， Ph. D.， associate professor. Her research interests include data mining， supply chain management.
Supported by:
Natural Science Foundation of Hebei Province(F20202013)

摘要/Abstract

摘要：

针对现有的对比序列模式挖掘方法主要针对字符序列数据集且难以应用于时间序列数据集的问题，提出一种对比保序模式挖掘（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算法可以有效挖掘对比保序模式，发现不同类别的时间序列数据集间的差异。

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

Abstract:

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.

Key words: pattern mining, sequential pattern mining, time series, contrast pattern, order-preserving pattern

中图分类号:

TP311.13

孟玉飞, 武优西, 王珍, 李艳. 对比保序模式挖掘算法[J]. 计算机应用, 2023, 43(12): 3740-3746.

Yufei MENG, Youxi WU, Zhen WANG, Yan LI. Contrast order-preserving pattern mining algorithm[J]. Journal of Computer Applications, 2023, 43(12): 3740-3746.

图/表 6

参考文献 39

1	LIN Y， LIN Z X， LIAO Y， et al. Forecasting the realized volatility of stock price index： a hybrid model integrating CEEMDAN and LSTM ［J］. Expert Systems with Applications， 2022， 206： 117736. 10.1016/j.eswa.2022.117736
2	MAN J， DONG H H， GAO J Y， et al. GA-GRGAT： a novel deep learning model for high-speed train axle temperature long term forecasting ［J］. Expert Systems with Applications， 2022， 202： 117033. 10.1016/j.eswa.2022.117033
3	DAI C L， WU J， PI D C， et al. Brain EEG time-series clustering using maximum-weight clique ［J］. IEEE Transactions on Cybernetics， 2022， 52（1）： 357-371. 10.1109/tcyb.2020.2974776
4	CHAKRABARTI K， KEOGH E， MEHROTRA S， et al. Locally adaptive dimensionality reduction for indexing large time series databases ［J］. ACM Transactions on Database Systems， 2002， 27（2）： 188-228. 10.1145/568518.568520
5	LIN J， KEOGH E， WEI L， et al. Experiencing SAX： a novel symbolic representation of time series ［J］. Data Mining and Knowledge Discovery. 2007， 15（2）： 107-144. 10.1007/s10618-007-0064-z
6	KIM J， EADES P， FLEISCHER R， et al. Order-preserving matching ［J］. Theoretical Computer Science， 2014， 525（13）： 68-79. 10.1016/j.tcs.2013.10.006
7	武优西，刘茜，闫文杰，等. 无重叠条件严格模式匹配的高效求解算法［J］. 软件学报， 2021， 32（11）： 3331-3350. 10.13328/j.cnki.jos.006054
	WU Y X， LIU X， YAN W J， et al. Efficient algorithm for solving strict pattern matching under nonoverlapping condition ［J］. Journal of Software， 2021， 32（11）： 3331-3350. 10.13328/j.cnki.jos.006054
8	CHO S， NA J C， PARK K， et al. A fast algorithm for order-preserving pattern matching ［J］. Information Processing Letters， 2015， 115（2）： 397-402. 10.1016/j.ipl.2014.10.018
9	LI Y， YU L， LIU J， et al. NetDPO：（delta， gamma）-approximate pattern matching with gap constraints under one-off condition ［J］. Applied Intelligence， 2022， 52（11）： 12155-12174. 10.1007/s10489-021-03000-2
10	CHHABRA T， TARHIO J. A filtration method for order-preserving matching ［J］. Information Processing Letters， 2016， 116（2）： 71-74. 10.1016/j.ipl.2015.10.005
11	KIM Y， KANG M， NA J C， et al. Order-preserving pattern matching with scaling ［J］. Information Processing Letters， 2023， 180： 106333. 10.1016/j.ipl.2022.106333
12	WU Y X， HU Q， LI Y， et al. OPP-Miner： order-preserving sequential pattern mining for time series ［EB/OL］. ［2022-02-09］. . 10.1109/tcyb.2022.3169327
13	WU Y X， ZHAO X Q， LI Y， et al. OPR-Miner： order-preserving rule mining for time series ［EB/OL］. ［2022-12-04］. . 10.1109/tkde.2022.3224963
14	WU Y X， WANG Y H， LI Y， et al. Top-k self-adaptive contrast sequential pattern mining ［J］. IEEE Transactions on Cybernetics， 2022， 52（11）： 11819-11833. 10.1109/tcyb.2021.3082114
15	GAN W S， LIN J C， FOURNIER-VIGER P， et al. A survey of parallel sequential pattern mining ［J］. ACM Transactions on Knowledge Discovery from Data， 2019， 13（3）： 1-34. 10.1145/3314107
16	OKOLICA J S， PETERSON G L， MILLS R F， et al. Sequence pattern mining with variables ［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（1）： 177-187. 10.1109/tkde.2018.2881675
17	SAMARIYA D， MA J. A new dimensionality-unbiased score for efficient and effective outlying aspect mining［J］. Data Science and Engineering， 2022， 7（2）： 120-135. 10.1007/s41019-022-00185-5
18	李艳辉，刘浩，袁野，等. 基于差分隐私的频繁序列模式挖掘算法［J］. 计算机应用， 2017， 37（2）： 316-321. 10.11772/j.issn.1001-9081.2017.02.0316
	LI Y H， LIU H， YUAN Y， et al. Frequent sequence pattern mining with differential privacy ［J］. Journal of Computer Applications， 2017， 37（2）： 316-321. 10.11772/j.issn.1001-9081.2017.02.0316
19	WU Y X， TONG Y， ZHU X Q， et al. NOSEP： nonoverlapping sequence pattern mining with gap constraints ［J］. IEEE Transactions on Cybernetics， 2018， 48（10）： 2809-2822. 10.1109/tcyb.2017.2750691
20	武优西，周坤，刘靖宇，等. 周期性一般间隙约束的序列模式挖掘［J］. 计算机学报， 2017， 40（6）： 1338-1352. 10.11897/SP.J.1016.2017.01338
	WU Y X， ZHOU K， LIU J Y， et al. Mining sequential patterns with periodic general gap constraints ［J］. Chinese Journal of Computers， 2017， 40（6）： 1338-1352. 10.11897/SP.J.1016.2017.01338
21	LI Y， ZHANG S， GUO L， et al. NetNMSP： nonoverlapping maximal sequential pattern mining ［J］. Applied Intelligence. 2022， 52（9）： 9861-9884. 10.1007/s10489-021-02912-3
22	WU Y X， ZHU C R， LI Y， et al. NetNCSP： nonoverlapping closed sequential pattern mining ［J］. Knowledge-Based Systems， 2020， 196： 105812. 10.1016/j.knosys.2020.105812
23	WANG L Z， BAO X G， ZHOU L H. Redundancy reduction for prevalent co-location patterns ［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（1）： 142-155. 10.1109/tkde.2017.2759110
24	王晓璇，王丽珍，陈红梅，等. 基于特征效用参与率的空间高效用co-location模式挖掘方法［J］. 计算机学报， 2019， 42（8）： 1721-1738. 10.11897/SP.J.1016.2019.01721
	WANG X X， WANG L Z， CHEN H M， et al. Mining spatial high utility co-location patterns based on feature utility ratio ［J］. Chinese Journal of Computers， 2019， 42（8）： 1721-1738. 10.11897/SP.J.1016.2019.01721
25	马董，陈红梅，王丽珍，等. 空间亚频繁co-location模式的主导特征挖掘［J］. 计算机应用， 2020， 40（2）： 465-472.
	MA D， CHEN H M， WANG L Z， et al. Dominant feature mining of spatial sub-prevalent co-location patterns ［J］. Journal of Computer Applications， 2020， 40（2）： 465-472.
26	LIU C H， GUO C H. Mining top-N high-utility operation patterns for taxi drivers ［J］. Expert Systems with Applications， 2021， 170： 114546. 10.1016/j.eswa.2020.114546
27	WU Y X， GENG M， LI Y， et al. HANP-Miner： high average utility nonoverlapping sequential pattern mining ［J］. Knowledge-Based Systems， 2021， 229： 107361. 10.1016/j.knosys.2021.107361
28	GAN W S， LIN J C， FOURNIER-VIGER P， et al. HUOPM： high-utility occupancy pattern mining ［J］. IEEE Transactions on Cybernetics， 2020， 50（3）： 1195-1208. 10.1109/tcyb.2019.2896267
29	WU Y X， CHEN M J， LI Y， et al. ONP-Miner： one-off negative sequential pattern mining ［EB/OL］. ［2022-07-25］. . 10.1145/3549940
30	DONG X J， GONG Y S， CAO L B. e-RNSP： an efficient method for mining repetition negative sequential patterns ［J］. IEEE Transactions on Cybernetics， 2020， 50（5）： 2084-2096. 10.1109/tcyb.2018.2869907
31	WU Y X， LUO L F， LI Y， et al. NTP-Miner： nonoverlapping three-way sequential pattern mining ［J］. ACM Transaction on Knowledge Discovery from Data， 2022， 16（3）： 51. 10.1145/3480245
32	JI X N， BAILEY J， DONG G Z. Mining minimal distinguishing subsequence patterns with gap constraints ［J］. Knowledge and Information Systems， 2007， 11（3）： 259-286. 10.1007/s10115-006-0038-2
33	WANG X M， DUAN L， DONG G Z， et al. Efficient mining of density-aware distinguishing sequential patterns with gap constraints ［J］. Database Systems for Advanced Applications， 2014， 8421： 372-387. 10.1007/978-3-319-05810-8_25
34	段磊，唐常杰，杨宁，等. 基于显露模式的对比挖掘研究及应用进展［J］. 计算机应用， 2012， 32（2）： 304-308. 10.3724/sp.j.1087.2012.00304
	DUAN L， TANG C J， YANG N， et al. Survey on emerging pattern based contrast mining and applications ［J］. Journal of Computer Applications， 2012， 32（2）： 304-308. 10.3724/sp.j.1087.2012.00304
35	WU Y X， WANG Y H， LIU J Y， et al. Mining distinguishing subsequence patterns with nonoverlapping condition ［J］. Cluster Computing， 2019， 22： 5905-5907. 10.1007/s10586-017-1671-0
36	HE Z Y， ZHANG S M， GU F Y， et al. Mining conditional discriminative sequential patterns ［J］. Information Sciences， 2019， 478： 524-539. 10.1016/j.ins.2018.11.043
37	武优西，户倩，郭媛，等.保序序列模式挖掘方法： CN202010544303.5 ［P］. 2020-06-15.
	WU Y X， H Q， GUO Y， et al. Order-preserving sequential pattern mining algorithm： CN202010544303.5 ［P］. 2020-06-15.
38	武优西，赵晓倩，李艳，等.保序序列规则挖掘方法： CN202210294476.5 ［P］. 2022-03-23. 10.1109/tkde.2022.3224963
	WU Y X， ZHAO X Q， LI Y， et al. Order-preserving sequential rule mining algorithm： CN202210294476.5 ［P］. 2022-03-23. 10.1109/tkde.2022.3224963
39	武优西，刘锦，耿萌，等.近似保序序列模式挖掘方法： CN202210295950.6 ［P］. 2022-03-23. 10.1109/tcyb.2022.3169327
	WU Y X， LIU J， GENG M， et al. Approximate order-preserving sequential pattern mining algorithm： CN202210295950.6 ［P］. 2022-03-23. 10.1109/tcyb.2022.3169327

序号	时间序列	类别标签
1	15，10，18，12，19，14	D₊
2	13，19，16，22，18
3	15，20，17，22，20
4	12，13，11，10	D_-
5	15，16，13，14
6	12，15，19，11

序号	时间序列	类别标签
1	15，10，18，12，19，14	D₊
2	13，19，16，22，18
3	15，20，17，22，20
4	12，13，11，10	D_-
5	15，16，13，14
6	12，15，19，11

数据集	名称	单条时间序列长度	数据库中序列数	总长度
D1	Chinatown	24	345	8 280
D2	BeetleFly	512	20	10 240
D3	GunPoint	150	150	22 500
D4	ItalyPowerDemand	24	1 029	24 696
D5	PowerCons	144	180	25 920
D6	ShapeletSim	500	180	90 000

数据集	名称	单条时间序列长度	数据库中序列数	总长度
D1	Chinatown	24	345	8 280
D2	BeetleFly	512	20	10 240
D3	GunPoint	150	150	22 500
D4	ItalyPowerDemand	24	1 029	24 696
D5	PowerCons	144	180	25 920
D6	ShapeletSim	500	180	90 000

指标	算法	D1	D2	D3	D4	D5	D6
内存/ MB	COPM-o	67.451	52.318	63.812	72.269	55.952	52.763
	COPM-e	29.905	80.707	121.784	45.925	35.103	34.782
	COPM-p	189.235	66.103	236.548	151.224	76.025	60.419
	COPM	16.284	22.194	30.575	10.074	20.217	21.973
运行时间/ s	COPM-o	0.607	0.261	0.501	1.302	0.313	0.479
	COPM-e	0.221	0.809	0.431	0.341	0.217	0.293
	COPM-p	336.734	0.391	1.038	185.176	0.398	0.369
	COPM	0.165	0.182	0.271	0.148	0.198	0.217
候选模式数	COPM-o	161	202	275	142	171	190
	COPM-e	235	2 208	1 359	333	431	494
	COPM-p	29 925	375	2 159	25 167	978	894
	COPM	161	202	275	142	171	190

对比保序模式挖掘算法

Contrast order-preserving pattern mining algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 39

相关文章 15

编辑推荐

Metrics

算法	内存消耗/MB						运行时间/s
算法	D6_1	D6_2	D6_3	D6_4	D6_5	D6_6	D6_1	D6_2	D6_3	D6_4	D6_5	D6_6
COPM-o	52.763	80.916	130.892	172.057	248.719	296.423	0.479	0.833	1.464	1.923	2.641	3.074
COPM-e	34.782	54.824	105.923	143.471	223.286	280.066	0.293	0.431	0.736	0.978	1.155	1.459
COPM-p	60.419	102.129	142.494	184.845	255.101	303.965	0.369	0.455	0.788	1.139	1.364	1.646
COPM	21.973	32.733	48.299	66.712	83.856	94.395	0.217	0.319	0.416	0.535	0.768	0.923

[1]	徐丽, 符祥远, 李浩然. 基于门控卷积的时空交通流预测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2760-2765.
[2]	陆辉, 黄瑞章, 薛菁菁, 任丽娜, 林川. 深度动态文本聚类模型DDDC[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2370-2375.
[3]	黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.
[4]	邱莲鹏, 宋承云. 噪声鲁棒的动态时间规整算法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1855-1860.
[5]	夏进, 王正群, 朱世明. 基于时间序列分解的交通流量预测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1129-1135.
[6]	陈容均, 严宣辉, 杨超城. 面向时间序列的混合图像化循环胶囊分类网络[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 692-699.
[7]	尹春勇, 周立文. 基于再编码的无监督时间序列异常检测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 804-811.
[8]	张安勤, 王小慧. 基于时序异常检测的动力电池安全预警[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3799-3805.
[9]	罗香玉, 闫克, 卢琰, 王甜, 辛刚. 基于社区改变量估计的非均匀时间片划分方法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3457-3463.
[10]	郎祎平, 毛文涛, 罗铁军, 范黎林, 任颖莹, 刘侠. 间歇性时间序列的可预测性评估及联合预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2722-2731.
[11]	吴军, 欧阳艾嘉, 张琳. 基于影响度的统计显著序列模式挖掘算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2713-2721.
[12]	吴明晖, 张广洁, 金苍宏. 基于多模态信息融合的时间序列预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2326-2332.
[13]	玄英律, 万源, 陈嘉慧. 基于多尺度卷积和注意力机制的LSTM时间序列分类[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2343-2352.
[14]	毛群, 王微微, 尤枫, 赵瑞莲, 李征. Android应用的用户行为模式挖掘及复用方法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2155-2161.
[15]	胡鹤轩, 隋华超, 胡强, 张晔, 胡震云, 马能武. 基于图注意力网络与双阶注意力机制的径流预报模型[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1607-1615.