频繁时序模式挖掘方法综述

doi:10.3778/j.issn.1002-8331.2403-0114

摘要/Abstract

摘要： 频繁时序模式挖掘是指从时间序列数据中发现频繁出现的模式或规律的过程，其目的是可以帮助理解时间序列数据中的重要特征，例如周期性、趋势和异常等，有助于预测未来的发展趋势和识别异常情况等。根据近年来的频繁时序模式挖掘方法的相关文献调研，按照关键技术和代表性算法将其分为三类，即基于结构约束的频繁时序模式挖掘方法、基于参数约束的频繁时序模式挖掘方法和基于窗口的频繁时序模式挖掘方法。陈述了频繁时序模式挖掘方法的背景以及各方法的特点；分别介绍了三类挖掘方法的发展以及分类，并从优缺点和性能等方面对各类改进方法进行了详细的对比分析；对频繁时序模式挖掘方法进行归纳和总结，并对频繁时序模式挖掘方法的未来研究方向进行了展望。

关键词: 时序数据, 频繁时序模式, 结构约束, 参数约束, 窗口, 数据挖掘

Abstract: Frequent temporal pattern mining refers to the process of discovering frequently occurring patterns or patterns from time series data. Its purpose is to help understand important features in time series data, such as periodicity, trends, and anomalies, which can help predict future development trends and identify abnormal situations. Based on literature research on frequent temporal pattern mining methods in recent years, they are divided into three categories according to key technologies and representative algorithms, namely structural constraint based frequent temporal pattern mining methods, parameter constraint based frequent temporal pattern mining methods, and window based frequent temporal pattern mining methods. Firstly, the background of frequent temporal pattern mining methods and the characteristics of each method are described. Secondly, the development and classification of three mining methods are introduced, and a detailed comparative analysis is conducted on the advantages, disadvantages, and performance of each improved method. Finally, the frequent temporal pattern mining methods are summarized and summarized, and the future research directions of frequent temporal pattern mining methods are discussed.

Key words: time series data, frequent temporal patterns, structural constraints, parameter constraints, window, data mining

唐增金, 徐贞顺, 苏梦瑶, 刘纳, 王振彪, 张文豪. 频繁时序模式挖掘方法综述[J]. 计算机工程与应用, 2024, 60(17): 48-61.

TANG Zengjin, XU Zhenshun, SU Mengyao, LIU Na, WANG Zhenbiao, ZHANG Wenhao. Review of Frequent Temporal Pattern Mining Methods[J]. Computer Engineering and Applications, 2024, 60(17): 48-61.

参考文献

[1] QI H, ZHOU Z, YUAN J, et al. Accident pattern recognition in subway construction for the provision of customized safety measures[J]. Tunnelling and Underground Space Technology, 2023, 137: 105157.
[2] SHU X, YE Y. Knowledge discovery: methods from data mining and machine learning[J]. Social Science Research, 2023, 110: 102817.
[3] REHMAN S U, ALNAZZAWI N, ASHRAF J, et al. Efficient top-k identical frequent itemsets mining without support threshold parameter from transactional datasets produced by IoT-based smart shopping carts[J]. Sensors, 2022, 22(20): 8063.
[4] PRAVEEN KUMAR B, PAULRAJ D. Frequent mining analysis using pattern mining utility incremental algorithm based on relational query process[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12: 4745-4755.
[5] ZHOU Y, HAO J K, DUVAL B. Frequent pattern-based search: a case study on the quadratic assignment problem[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 52(3): 1503-1515.
[6] ZHANG Z, HUANG J. Fast frequent patterns mining by multiple sampling with tight guarantee under Bayesian statistics[J]. IEEE Transactions on Cybernetics, 2023, 53(5): 2993-3006.
[7] MEI?NER K, RIECK J. Strategic planning support for road safety measures based on accident data mining[J]. IATSS Research, 2022, 46(3): 427-440.
[8] JAZAYERI A, YANG C C, CAPAN M. Frequent temporal patterns of physiological and biological biomarkers and their evolution in sepsis[J]. Artificial Intelligence in Medicine, 2023, 143: 102576.
[9] ARI N S B, MOSKOVITCH R. Predictive temporal patterns discovery[J]. Expert Systems with Applications, 2023, 226: 119974.
[10] JAMSHEELA O, RAJU G. An improved frequent pattern tree: the child structured frequent pattern tree CSFP-tree[J]. Pattern Analysis and Applications, 2023, 26(2): 437-454.
[11] NGUYEN H, LE N, BUI H, et al. A new approach for efficiently mining frequent weighted utility patterns[J]. Applied Intelligence, 2023, 53(1): 121-140.
[12] 韩萌, 丁剑. 数据流频繁模式挖掘综述[J]. 计算机应用, 2019, 39(3): 719-727.
HAN M, DING J. Survey of frequent pattern mining over data streams[J]. Computer Applications, 2019, 39(3): 719-727.
[13] 王少峰, 韩萌, 贾涛, 等. 数据流高效用模式挖掘综述[J]. 计算机应用研究, 2020, 37(9): 2571-2578.
WANG S F, HAN M, JIA T, et al. A review of efficient pattern mining in data streams[J]. Application Research of Computers, 2020, 37(9): 2571-2578.
[14] WU Y, ZHAO X, LI Y, et al. OPR-Miner: order-preserving rule mining for time series[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(11): 11722-11735.
[15] WANG L, MENG J, XU P, et al. Mining temporal association rules with frequent itemsets tree[J]. Applied Soft Computing, 2018, 62: 817-829.
[16] GULZAR K, MEMON M, MOHSIN S M, et al. An efficient healthcare data mining approach using apriori algorithm: a case study of eye disorders in young adults[J]. Information, 2023, 14: 203.
[17] CHEN Y, YUAN P, QIU M, et al. An indoor trajectory frequent pattern mining algorithm based on vague grid sequence[J]. Expert Systems with Applications, 2019, 118: 614-624.
[18] PEI J, HAN J, WANG W. Mining sequential patterns with constraints in large databases[C]//Proceedings of the 11th International Conference on Information and Knowledge Management, 2002: 18-25.
[19] VANAMALA S, SREE P L, BHAVANI S. Eclat_RPGrowth: finding rare patterns using vertical mining and rare pattern tree[C]//Proceedings of the Computer Networks, Big Data and IoT, 2021: 161-176.
[20] AMARANATHA REDDY P, KRISHNA PRASAD M H M. High utility item-set mining from retail market data stream with various discount strategies using EGUI-tree[J]. International Journal of Software Innovation, 2021, 10(1): 1-15.
[21] AHMED S A, NATH B. ISSP-tree: an improved fast algorithm for constructing a complete prefix tree using single database scan[J]. Expert Systems with Applications, 2021, 185(3): 115603.
[22] AHMED S A, NATH B. Identification of adverse disease agents and risk analysis using frequent pattern mining[J]. Information Sciences, 2021, 576(2): 609-641.
[23] WANG Y, WU Y, LI Y, et al. Self-adaptive nonoverlapping sequential pattern mining[J]. Applied Intelligence, 2022, 52(6): 6646-6661.
[24] WU Y, YUAN Z, LI Y, et al. NWP-Miner: nonoverlapping weak-gap sequential pattern mining[J]. Information Sciences: an International Journal, 2022, 588: 124-141.
[25] WU Y, HU Q, LI Y, et al. OPP-Miner: order-preserving sequential pattern mining for time series[J]. IEEE Transactions on Cybernetics, 2023, 53(5): 3288-3300.
[26] LV Z, WANG X, CHENG Z, et al. A new approach to COVID-19 data mining: a deep spatial-temporal prediction model based on tree structure for traffic revitalization index[J]. Data & Knowledge Engineering, 2023, 146: 102193.
[27] SINGH K, BISWAS B. Efficient algorithm for mining high utility pattern considering length constraints[J]. International Journal of Data Warehousing and Mining, 2019, 15(3): 1-27.
[28] AGRAWAL R, SRIKANT R. Mining sequential patterns[C]//Proceedings of the 11th International Conference on Data Engineering, 1995: 3-14.
[29] TRUONG T, DUONG H, LE B, et al. Frequent high minimum average utility sequence mining with constraints in dynamic databases using efficient pruning strategies[J]. Applied Intelligence, 2022, 52(6): 6106-6128.
[30] FEREMANS L, CULE B, GOETHALS B. Efficient pattern-based anomaly detection in a network of multivariate devices[J]. arXiv:2305.05538, 2023.
[31] HU W, WANG Z, WANG J. A priority-aware sequential pattern mining method for detection of compact patterns from alarm floods[J]. Journal of Process Control, 2023, 129: 103041.
[32] WANG J, JIA R, ZHOU J, et al. Mining sequential alarm pattern based on the incremental causality PrefixSpan algorithm[J]. IEEE Transactions on Artificial Intelligence, 2023, 4(4): 612-623.
[33] 袁泉, 唐成亮, 徐雲鹏. 基于长度约束的蝙蝠高效用项集挖掘算法[J]. 计算机应用, 2023, 43(5): 1473-1480.
YUAN Q, TANG C L, XU Y P. Bat algorithm for high untility itemset mining based on length constraint[J]. Journal of Computer Applications, 2023, 43 (5): 1473-1480.
[34] ZHAO L, LI Y, LI S, et al. A frequency item mining based embedded feature selection algorithm and its application in energy consumption prediction of electric bus[J]. Energy, 2023, 271: 126999.
[35] HAN J, PEI J, MORTAZAVI-ASL B, et al. PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth[C]//Proceedings of the 17th International Conference on Data Engineering, 2001: 215-224.
[36] LE T, NGUYEN A, HUYNH B, et al. Mining constrained inter-sequence patterns: a novel approach to cope with item constraints[J]. Applied Intelligence, 2018, 48(5): 1327-1343.
[37] VAN T, LE B. Mining sequential rules with itemset constraints[J]. Applied Intelligence, 2021, 51(10): 7208-7220.
[38] WANG W, TIAN J, LV F, et al. Mining frequent pyramid patterns from time series transaction data with custom constraints[J]. Computers & Security, 2021, 100: 102088.
[39] 陈平, 王利钢. 基于项约束的关联规则频繁项集挖掘方法研究[J]. 信息化研究, 2021, 47(5): 18-22.
CHEN P, WANG L G. Research constraints frequent item sets mining algorithm based on transaction binary[J]. Informatization Research, 2021, 47(5): 18-22.
[40] DUONG H, TRUONG T, TRAN A, et al. Fast generation of sequential patterns with item constraints from concise representations[J]. Knowledge and Information Systems, 2020, 62(6): 2191-2223.
[41] NGUYEN A, NGUYEN N T, NGUYEN L T T, et al. Mining inter-sequence patterns with itemset constraints[J]. Applied Intelligence, 2023, 53: 19827-19842.
[42] CHEN C H, CHOU H, HONG T P, et al. Cluster-based membership function acquisition approaches for mining fuzzy temporal association rules[J]. IEEE Access, 2020, 8: 123996-124006.
[43] RAHMAN M M, AHMED C F, LEUNG C K S. Mining weighted frequent sequences in uncertain databases[J]. Information Sciences, 2019, 479: 76-100.
[44] MOU N, WANG H, ZHANG H, et al. Association rule mining method based on the similarity metric of tuple-relation in indoor environment[J]. IEEE Access, 2020, 8: 52041-52051.
[45] DU X, YU F. A fast algorithm for mining temporal association rules in a multi-attributed graph sequence[J]. Expert Systems with Applications, 2022, 192: 116390.
[46] 姜建武, 王博. 高维数据组合关联关系挖掘方法[J]. 科学技术与工程, 2023, 23(4): 1615-1624.
JIANG J W, WANG B. Combinatorial association mining method for high-dimensional data[J]. Science Technology and Engineering, 2023, 23 (4): 1615-1624.
[47] WEI L, GUO D, CHEN Z, et al. Forecasting short-term passenger flow of subway stations based on the temporal pattern attention mechanism and the long short-term memory network[J]. ISPRS International Journal of Geo-Information, 2023, 12(1): 25.
[48] DUONG T H, JANOS D, THI V D, et al. An algorithm for mining high utility sequential patterns with time interval[J]. Cybernetics and Information Technologies, 2019, 19(4): 3-16.
[49] RITIKA, GUPTA S K. HUFTI-SPM: high-utility and frequent time-interval sequential pattern mining from transactional databases[J]. International Journal of Data Science and Analytics, 2022, 13: 239-250.
[50] WANG C, ZHENG X. Application of improved time series Apriori algorithm by frequent itemsets in association rule data mining based on temporal constraint[J]. Evolutionary Intelligence, 2020, 13: 39-49.
[51] 梁天恺, 曾碧, 刘建圻. 基于FP-Growth的智能家居用户时序关联操控习惯挖掘方法[J]. 计算机应用研究, 2020, 37(2): 385-389.
LIANG T K, ZENG B, LIU J Q. FP-Growth-based users temporal association control habits mining method for smart home[J]. Application Research of Computers, 2020, 37(2): 385-389.
[52] BUSTIO-MARTíNEZ L, CUMPLIDO R, LETRAS M, et al. FPGA/GPU-based acceleration for frequent itemsets mining: a comprehensive review[J]. ACM Computing Surveys (CSUR), 2021, 54(9): 1-35.
[53] M?RCHEN F. Unsupervised pattern mining from symbolic temporal data[J]. ACM SIGKDD Explorations Newsletter, 2007, 9(1): 41-55.
[54] 张广路, 雷景生, 吴兴惠. 界标窗口中数据流频繁模式挖掘算法研究[J]. 计算机工程, 2012, 38(1): 55-58.
ZHANG G L, LEI J S, WU X H. Research on data stream frequent pattern mining algorithms in landmark window[J]. Computer Engineering, 2012, 38(1): 55-58.
[55] 吴媚, 高玲. 基于界标窗口的数据流频繁项集挖掘算法的改进[J]. 山东师范大学学报 (自然科学版), 2014(3): 21-25.
WU M, GAO L. Improved algorithms for mining frequent itemsets in data stream based on landmark window[J]. Journal of Shandong Normal University(Natural Science), 2014(3): 21-25.
[56] 闻英友, 王少鹏, 赵宏. 界标窗口下数据流最大规范模式挖掘算法研究[J]. 计算机研究与发展, 2017, 54(1): 94-110.
WEN Y Y, WANG S P, ZHAO H. The maximal regular patterns mining algorithm based on landmark window over data stream[J]. Journal of Computer Research and Development, 2017, 54(1): 94-110.
[57] LI D, WANG C, LI L, et al. Collaborative filtering algorithm with social information and dynamic time windows[J]. Applied Intelligence, 2022, 52(5): 5261-5272.
[58] HAN M, DING J, LI J. TDMCS: an efficient method formining closed frequent patterns over data streams based on time decay model[J]. International Arab Journal of Information Technology, 2017, 14(6): 851-860.
[59] YUN U, KIM D, YOON E, et al. Damped window basedhigh average utility pattern mining over data streams[J]. Knowledge-Based Systems, 2017, 144: 188-205.
[60] KIM H, YUN U, BAEK Y, et al. Damped sliding basedutility oriented pattern mining over stream data[J]. Knowledge-Based Systems, 2021, 213: 106653.
[61] LU X, JIN S, WANG X, et al. A mining frequent itemsets algorithm in stream data based on sliding time decay window[C]//Proceedings of the 2020 3rd International Conference on Artificial Intelligence and Pattern Recognition, 2020: 18-24.
[62] AN Y, TANG K, WANG J. Time-aware multi-type data fusion representation learning framework for risk prediction of cardiovascular diseases[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2021, 19(6): 3725-3734.
[63] BUI H, NGUYEN-HOANG T A, VO B, et al. A sliding window-based approach for mining frequent weighted patterns over data streams[J]. IEEE Access, 2021, 99: 56318-56329.
[64] CHEN J, LI P, FANG W, et al. Fuzzy frequent pattern mining algorithm based on weighted sliding window and type-2 fuzzy sets over medical data stream[J]. Wireless Communications and Mobile Computing, 2021, 2021: 1-17.
[65] 陈玉, 戴华, 李博涵, 等. 面向移动对象的松散型传染模式挖掘方法[J]. 浙江大学学报 (工学版), 2022, 56(2): 280-287.
CHEN Y, DAI H, LI B H, et al. Loose infection pattern mining algorithms over moving objects[J]. Journal of Zhejiang University (Engineering Science), 2022, 56(2): 280-287.
[66] YIN Y, LI P, CHEN J. A variable sliding window algorithm based on concept drift for frequent pattern mining over data streams[C]//Proceedings of the 2022 IEEE 28th International Conference on Parallel and Distributed Systems, 2023: 818-825.
[67] SI J, YANG J, XIANG Y, et al. TrajBERT: BERT-based trajectory recovery with spatial-temporal refinement for implicit sparse trajectories[J]. IEEE Transactions on Mobile Computing, 2023, 23(5): 4849-4860.
[68] ZHANG C, ZHANG J, ZHAO Y, et al. Automated data mining framework for building energy conservation aided by generative pre-trained transformers (GPT)[J]. Energy and Buildings, 2024, 305: 113877.