高效的一次性弱间隙序列模式挖掘算法

doi:10.19678/j.issn.1000-3428.0067255

摘要/Abstract

摘要：

间隙约束序列模式挖掘作为序列模式挖掘的一个重要分支，可以发现模式在序列中的重复出现。然而，当前研究主要针对单项序列进行挖掘，并且序列中每一项都被认为具有相同意义。为解决该问题，提出一次性弱间隙序列模式挖掘（OWP）算法，该算法由准备阶段、支持度计算和候选模式生成3个步骤组成。在准备阶段，建立倒排索引，并对不频繁的项进行剪枝；在支持度计算方面，利用倒排索引结构记录出现位置，避免对原始数据集的重复扫描；在候选模式生成方面，采用模式连接策略，减少冗余候选模式的生成。在项集序列和单项序列共6个真实数据集上的实验结果表明，OWP算法相比OWP-p、Ows-OWP和OWP-e算法在运行时间上分别提升了2.653、1.348、3.592倍，在内存消耗上分别减少了3.51%、0.07%、5%，说明OWP算法可以更高效地挖掘出用户感兴趣的模式。此外，OWP算法在以D1数据集为基础的6倍大小的数据集上的运行时间比D1数据集增长了3.763倍，内存消耗增长了2.310倍，运行时间和内存消耗的增加倍数均小于数据集大小的增加倍数，说明OWP算法具有良好的可扩展性。

关键词: 序列模式挖掘, 项集挖掘, 间隙约束, 一次性条件, 弱间隙约束

Abstract:

Sequential Pattern Mining(SPM) with gap constraint, as an important branch of sequential pattern mining, can discover the repetitive occurrences of patterns in sequences. However, the current studies mainly focus on datasets with items, and each item in the sequence is considered to have the same effects. To address this problem, the One-off Weak gap sequential Pattern mining(OWP) algorithm is proposed, which includes three steps: preparation stage, support calculation, and candidate pattern generation. In the preparation stage, an inverted index is constructed and infrequent items are pruned. For support calculation, the occurrence positions are recorded using an inverted index, which avoids repeated scanning of the original dataset. For candidate pattern generation, a pattern- join strategy is used to reduce the generation of redundant candidate patterns. Finally, from the experimental results on six real datasets comprising datasets with items and itemsets, it is observed that the OWP algorithm improves the runtime by 2.653, 1.348, and 3.592 times compared with the OWP-p, Ows-OWP, and OWP-e algorithms, respectively, and as concerns memory usage, it reduces by 3.51%, 0.07%, and 5%, respectively. This indicates that the OWP algorithm can mine the patterns of user interest more efficiently. In addition, the OWP algorithm on the dataset with six times the size based on D1 increases by 3.763 times and memory usage increases by 2.310 times compared to that of D1. Clearly, both the increases in runtime and memory usage are smaller than those in dataset size, implying that the OWP algorithm has good scalability.

Key words: Sequential Pattern Mining(SPM), mining with itemset, gap constraint, one-off condition, weak-gap constraint

杨鸿茜, 武优西, 耿萌, 刘靖宇, 李艳. 高效的一次性弱间隙序列模式挖掘算法[J]. 计算机工程, 2024, 50(3): 60-67.

Hongxi YANG, Youxi WU, Meng GENG, Jingyu LIU, Yan LI. Efficient One-off Weak Gap Sequential Pattern Mining Algorithm[J]. Computer Engineering, 2024, 50(3): 60-67.

http://www.ecice06.com/CN/Y2024/V50/I3/60

图/表 8

图1 模式p在序列s₁中的所有出现

Fig.1 The supports pattern p in sequence s₁

图2 D1~D6运行时间对比

Fig.2 Comparison of D1~D6 running time

图3 D1~D6内存消耗对比

Fig.3 Comparison of D1~ D6 memory consumption

图4 不同大小数据集上的运行时间对比

Fig.4 Comparison of running time on different size datasets

图5 在不同大小数据集上的内存消耗对比

Fig.5 Comparison of memory consumption on different sizes datasets

参考文献 30

1	张光兰, 杨秋辉, 程雪梅, 等. 序列模式挖掘在通信网络告警预测中的应用. 计算机科学, 2018, 45 (S2): 535-538, 563. URL
	ZHANG G L, YANG Q H, CHENG X M, et al. Application of sequential pattern mining in communication network alarm prediction. Computer Science, 2018, 45 (S2): 535-538, 563. URL
2	刘新斌, 王丽珍, 周丽华. MLCPM-UC: 一种基于模式实例分布均匀系数的多级co-location模式挖掘算法. 计算机科学, 2021, 48 (11): 208- 218. doi: 10.11896/jsjkx.201000097
	LIU X B, WANG L Z, ZHOU L H. MLCPM-UC: a multi-level co-location pattern mining algorithm based on uniform coefficient of pattern instance distribution. Computer Science, 2021, 48 (11): 208- 218. doi: 10.11896/jsjkx.201000097
3	周忠玉, 皮德常. 面向购物篮数据的稀有序列模式挖掘算法. 小型微型计算机系统, 2019, 40 (3): 683- 688. doi: 10.3969/j.issn.1000-1220.2019.03.040
	ZHOU Z Y, PI D C. Rare sequence pattern mining algorithm for shopping basket data. Journal of Chinese Computer Systems, 2019, 40 (3): 683- 688. doi: 10.3969/j.issn.1000-1220.2019.03.040
4	CUI Y L, GAN W S, LIN H, et al. FRI-miner: fuzzy rare itemset mining. Applied Intelligence, 2022, 52 (3): 3387- 3402. doi: 10.1007/s10489-021-02574-1
5	WU Y X, WANG L L, REN J D, et al. Mining sequential patterns with periodic wildcard gaps. Applied Intelligence, 2014, 41 (1): 99- 116. doi: 10.1007/s10489-013-0499-4
6	吴军, 欧阳艾嘉, 张琳. 面向对比序列模式发现的独立精确置换检验算法. 计算机工程, 2021, 47 (8): 45-53, 61. URL
	WU J, OUYANG A J, ZHANG L. Independent exact permutation testing algorithm for distinguishing sequential pattern discovery. Computer Engineering, 2021, 47 (8): 45-53, 61. URL
7	ZHANG C K, DU Z L, GAN W S, et al. TKUS: mining top-k high utility sequential patterns. Information Sciences, 2021, 570, 342- 359. doi: 10.1016/j.ins.2021.04.035
8	朱扬勇, 熊赟. DNA序列数据挖掘技术. 软件学报, 2007, 18 (11): 2766- 2781. URL
	ZHU Y Y, XIONG Y. DNA sequence data mining technique. Journal of Software, 2007, 18 (11): 2766- 2781. URL
9	WU Y X, ZHU C R, LI Y, et al. NetNCSP: nonoverlapping closed sequential pattern mining. Knowledge-Based Systems, 2020, 196, 105812. doi: 10.1016/j.knosys.2020.105812
10	LIU H T, WANG L L, LIU Z Z, et al. Efficient pattern matching with periodical wildcards in uncertain sequences. Intelligent Data Analysis, 2018, 22 (4): 829- 842. doi: 10.3233/IDA-173435
11	PARK H, JUNG J Y. SAX-ARM: deviant event pattern discovery from multivariate time series using symbolic aggregate approximation and association rule mining. Expert Systems with Applications, 2020, 141, 112950. doi: 10.1016/j.eswa.2019.112950
12	LIN Y, LIN Z X, LIAO Y, et al. Forecasting the realized volatility of stock price index: a hybrid model integrating CEEMDAN and LSTM. Expert Systems with Applications, 2022, 206, 117736. doi: 10.1016/j.eswa.2022.117736
13	王乐, 王水, 刘胜蓝, 等. 基于索引树的带通配符序列模式挖掘算法. 计算机学报, 2019, 42 (3): 554- 565. URL
	WANG L, WANG S, LIU S L, et al. An algorithm of mining sequential pattern with wildcards based on index-tree. Chinese Journal of Computers, 2019, 42 (3): 554- 565. URL
14	LI Y, ZHANG S, GUO L, et al. NetNMSP: nonoverlapping maximal sequential pattern mining. Applied Intelligence, 2022, 52 (9): 9861- 9884. doi: 10.1007/s10489-021-02912-3
15	WU Y X, YAO T, ZHU X Q, et al. NOSEP: nonoverlapping sequence pattern mining with gap constraints. IEEE Transactions on Cybernetics, 2018, 48 (10): 2809- 2822. doi: 10.1109/TCYB.2017.2750691
16	WU Y X, GENG M, LI Y, et al. HANP-miner: high average utility nonoverlapping sequential pattern mining. Knowledge-Based Systems, 2021, 229, 107361. doi: 10.1016/j.knosys.2021.107361
17	DONG X J, GONG Y S, CAO L B. E-RNSP: an efficient method for mining repetition negative sequential patterns. IEEE Transactions on Cybernetics, 2020, 50 (5): 2084- 2096. doi: 10.1109/TCYB.2018.2869907
18	WU Y X, CHEN M J, LI Y, et al. ONP-miner: one-off negative sequential pattern mining. ACM Transactions on Knowledge Discovery from Data, 2023, 17 (3): 37. URL
19	WU Y X, LEI R, LI Y, et al. HAOP-miner: self-adaptive high-average utility one-off sequential pattern mining. Expert Systems with Applications, 2021, 184, 115449. doi: 10.1016/j.eswa.2021.115449
20	GUO D, HU X G, XIE F, et al. Pattern matching with wildcards and gap-length constraints based on a centrality-degree graph. Applied Intelligence, 2013, 39 (1): 57- 74. doi: 10.1007/s10489-012-0394-4
21	武优西, 周坤, 刘靖宇, 等. 周期性一般间隙约束的序列模式挖掘. 计算机学报, 2017, 40 (6): 1338- 1352. URL
	WU Y X, ZHOU K, LIU J Y, et al. Mining sequential patterns with periodic general gap constraints. Chinese Journal of Computers, 2017, 40 (6): 1338- 1352. URL
22	WU Y X, WANG X H, LI Y, et al. OWSP-miner: self-adaptive one-off weak-gap strong pattern mining. ACM Transactions on Management Information Systems, 2022, 13 (3): 1- 25. URL
23	AGGARWAL A, TOSHNIWAL D. Frequent pattern mining on time and location aware air quality data. IEEE Access, 2019, 7, 98921- 98933. doi: 10.1109/ACCESS.2019.2930004
24	赵林柳, 吕鑫, 陶飞飞. 基于Top-k的高效用模式挖掘算法. 计算机工程, 2019, 45 (5): 169-174, 181. URL
	ZHAO L L, LÜ X, TAO F F. Efficient algorithm for high utility pattern mining based on top-k. Computer Engineering, 2019, 45 (5): 169-174, 181. URL
25	LI Y, ZHANG C, LI J, et al. MCoR-miner: maximal co-occurrence nonoverlapping sequential rule mining. IEEE Transactions on Knowledge and Data Engineering, 2023, 35 (9): 9531- 9546. doi: 10.1109/TKDE.2023.3241213
26	LI C, YANG Q Y, WANG J Y, et al. Efficient mining of gap-constrained subsequences and its various applications. ACM Transactions on Knowledge Discovery from Data, 2012, 6 (1): 1- 39. doi: 10.1145/2133360.2133362
27	WU X D, ZHU X Q, HE Y, et al. PMBC: pattern mining from biological sequences with wildcard constraints. Computers in Biology and Medicine, 2013, 43 (5): 481- 492. doi: 10.1016/j.compbiomed.2013.02.006
28	LIN J C W, DJENOURI Y, SRIVASTAVA G, et al. Scalable mining of high-utility sequential patterns with three-tier MapReduce model. ACM Transactions on Knowledge Discovery from Data, 2021, 16 (3): 1- 26. URL
29	KE Y H, HUANG J W, LIN W C, et al. Finding possible promoter binding sites in DNA sequences by sequential patterns mining with specific numbers of gaps. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2021, 18 (6): 2459- 2470. doi: 10.1109/TCBB.2020.2980234
30	MIN F, ZHANG Z H, ZHAI W J, et al. Frequent pattern discovery with tri-partition alphabets. Information Sciences, 2020, 507, 715- 732. doi: 10.1016/j.ins.2018.04.013

[1]	吴军, 欧阳艾嘉, 张琳. 面向对比序列模式发现的独立精确置换检验算法[J]. 计算机工程, 2021, 47(8): 45-53,61.
[2]	马慧芳, 李苗, 童海斌, 詹子俊. 基于通配符模式与随机游走的关键词提取方法[J]. 计算机工程, 2020, 46(7): 78-83.
[3]	秦丽君, 罗雄飞. 基于动态项集计数的加权频繁项集算法[J]. 计算机工程, 2012, 38(3): 31-33.
[4]	俞东进, 郑苏杭, 李万清, 吴为. 基于BIDE的多核并行闭合序列模式挖掘[J]. 计算机工程, 2012, 38(12): 55-58.
[5]	张玉冲, 蔡皖东, 丁要军. 一种适用于应用层协议的特征提取算法[J]. 计算机工程, 2012, 38(04): 266-268.
[6]	林颖. 基于闭合序列模式的减量挖掘算法[J]. 计算机工程, 2011, 37(22): 64-66.
[7]	王翠青;陈未如. 序列模式挖掘支持度阈值的确定方法[J]. 计算机工程, 2010, 36(8): 93-95.
[8]	王丽娜;谭小彬;潘剑锋;奚宏生. 恶意代码检测中的PrefixSpan*算法应用[J]. 计算机工程, 2010, 36(7): 119-121.
[9]	朱靖君, 吴海燕, 高国柱, 程志锐. 一种基于日志分析的Web负载测试方法[J]. 计算机工程, 2010, 36(23): 25-27.
[10]	李伟;王新房;刘妮. 基于项目的非邻近序列模式推荐算法[J]. 计算机工程, 2009, 35(16): 65-67.
[11]	李春媚;蔡平良. 基于属性相关和时间约束的PrefixSpan算法[J]. 计算机工程, 2008, 34(23): 176-177,.
[12]	张坤;陈越;朱扬勇. 一种基于前缀树的增量序列挖掘算法[J]. 计算机工程, 2007, 33(19): 69-71.
[13]	朱莉;应吉康;卜忠飞. 基于SPAM-FPT的WebLog访问序列模式挖掘[J]. 计算机工程, 2007, 33(17): 80-82.

选择文件类型/文献管理软件名称

选择包含的内容