research-article

SN-RNSP: : Mining self-adaptive nonoverlapping repetitive negative sequential patterns in transaction sequences

Authors:

Xiangjun DongAuthors Info & Claims

Volume 287, Issue C

https://doi.org/10.1016/j.knosys.2024.111449

Published: 05 March 2024 Publication History

Abstract

Negative sequential patterns (NSP) focus on non-occurring events and play a role that cannot be replaced by positive sequential patterns (PSP). Considering the repetitive occurrence of sequential patterns in a sequence, repetitive NSP (RNSP) mining captures frequent NSP across different sequences from a database. Those patterns benefit many tasks of transaction services, e.g., fraud detection and medical diagnosis. However, limited studies focusing on mining RNSP are proposed, e.g., e-RNSP and ONP-Miner, and they are devised under strict constraints and are inefficient in practice. To address these issues, this paper proposes a Self-adaptive Nonoverlapping RNSP mining method SN-RNSP to mine nonoverlapping RNSP with the self-adaptive gap between successive elements from transaction sequences, which requires that each element cannot be reused at the same position in occurrences, and the gap value does not need to be specified in advance. First, this paper develops a method that maintains occurrences of pattern candidates via the bitmap structure to capture all repetitive PSP (RPSP), which utilizes the bitmap-based operation to calculate support efficiently. Second, SN-RNSP leverages bitmaps to record the locations of RPSP and RNSP in the database and query the repetition times of corresponding RPSP for the support calculation of RNSP. Conducted on real-world and synthetic datasets, extensive experiments demonstrate that SN-RNSP can discover more patterns with better mining performance than the state-of-the-art RNSP mining algorithms in transaction sequence databases.

References

[1]

Srikant R., Agrawal R., Mining sequential patterns: Generalizations and performance improvements, International Conference on Extending Database Technology, Springer, 1996, pp. 1–17.

[2]

J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, M.-C. Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, pp. 355–359.

[3]

Han J., Pei J., Mortazavi-Asl B., Pinto H., Chen Q., Dayal U., Hsu M., Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth, Proceedings of the 17th International Conference on Data Engineering, IEEE, 2001, pp. 215–224.

[4]

Zaki M.J., SPADE: An efficient algorithm for mining frequent sequences, Mach. Learn. 42 (2001) 31–60.

[5]

J. Ayres, J. Flannick, J. Gehrke, T. Yiu, Sequential pattern mining using a bitmap representation, in: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, pp. 429–435.

[6]

Cao L., Dong X., Zheng Z., E-NSP: Efficient negative sequential pattern mining, Artificial Intelligence 235 (2016) 156–182.

[7]

Guyet T., Quiniou R., NegPSpan: efficient extraction of negative sequential patterns with embedding constraints, Data Min. Knowl. Discov. 34 (2) (2020) 563–609.

[8]

Hsueh S.-C., Lin M.-Y., Chen C.-L., Mining negative sequential patterns for e-commerce recommendations, 2008 IEEE Asia-Pacific Services Computing Conference, IEEE, 2008, pp. 1213–1218.

[9]

Zheng Z., Zhao Y., Zuo Z., Cao L., An efficient GA-based algorithm for mining negative sequential patterns, Advances in Knowledge Discovery and Data Mining: 14th Pacific-Asia Conference, PAKDD 2010, Hyderabad, India, June 21-24, 2010. Proceedings. Part I 14, Springer, 2010, pp. 262–273.

[10]

Yadav P., Hybridized optimization oriented fast negative sequential patterns mining, Multimedia Tools Appl. 81 (4) (2022) 5279–5303.

[11]

Gao X., Gong Y., Xu T., Lü J., Zhao Y., Dong X., Toward to better structure and constraint to mine negative sequential patterns, IEEE Trans. Neural Netw. Learn. Syst. (2020).

[12]

Cao L., Ou Y., Philip S.Y., Coupled behavior analysis with applications, IEEE Trans. Knowl. Data Eng. 24 (8) (2011) 1378–1392.

[13]

L. Cao, Y. Ou, P.S. Yu, G. Wei, Detecting abnormal coupled sequences and sequence changes in group-based manipulative trading behaviors, in: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010, pp. 85–94.

[14]

Y. Song, L. Cao, X. Wu, G. Wei, W. Ye, W. Ding, Coupled behavior analysis for capturing coupling relationships in group-based market manipulations, in: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012, pp. 976–984.

[15]

Cao L., Zhao Y., Zhang C., Mining impact-targeted activity patterns in imbalanced data, IEEE Trans. Knowl. Data Eng. 20 (8) (2008) 1053–1066.

[16]

Zhao Y., Zhang H., Wu S., Pei J., Cao L., Zhang C., Bohlscheid H., Debt detection in social security by sequence classification using both positive and negative patterns, Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2009, Bled, Slovenia, September 7-11, 2009, Proceedings, Part II 20, Springer, 2009, pp. 648–663.

[17]

Dong X., Gong Y., Cao L., E-RNSP: An efficient method for mining repetition negative sequential patterns, IEEE Trans. Cybern. 50 (5) (2018) 2084–2096.

[18]

Wu Y., Chen M., Li Y., Liu J., Li Z., Li J., Wu X., ONP-Miner: One-off negative sequential pattern mining, ACM Trans. Knowl. Discov. Data 17 (3) (2023) 1–24.

[19]

Wu Y., Wang X., Li Y., Guo L., Li Z., Zhang J., Wu X., OWSP-Miner: Self-adaptive one-off weak-gap strong pattern mining, ACM Trans. Manag. Inf. Syst. 13 (3) (2022) 1–23.

[20]

Wang Y., Wu Y., Li Y., Yao F., Fournier-Viger P., Wu X., Self-adaptive nonoverlapping sequential pattern mining, Appl. Intell. (2021) 1–16.

[21]

Cao L., Philip S.Y., Kumar V., Nonoccurring behavior analytics: A new area, IEEE Intell. Syst. 30 (6) (2015) 4–11.

[22]

Cekinel R.F., Karagoz P., Event prediction from news text using subgraph embedding and graph sequence mining, World Wide Web 25 (6) (2022) 2403–2428.

[23]

Y.J.M. Pokou, P. Fournier-Viger, C. Moghrabi, Authorship attribution using small sets of frequent part-of-speech skip-grams, in: Flairs Conference, 2016, pp. 86–91.

[24]

Wang J., Jia R., Zhou J., Zhou M., Mining sequential alarm pattern based on the incremental causality prefixSpan algorithm, IEEE Trans. Artif. Intell. (2022).

[25]

Yu X., Ma N., Yang T., Zhang Y., Miao Q., Tao J., Li H., Li Y., Yang Y., A multi-level hypoglycemia early alarm system based on sequence pattern mining, BMC Medical Informatics Decis. Mak. 21 (1) (2021) 1–11.

[26]

Cao L., In-depth behavior understanding and use: the behavior informatics approach, Inform. Sci. 180 (17) (2010) 3067–3085.

[27]

Cao L., Health and medical behavior informatics, in: Biomedical Information Technology, Elsevier, 2020, pp. 735–761.

[28]

Huynh H.M., Nguyen L.T., Vo B., Oplatková Z.K., Fournier-Viger P., Yun U., An efficient parallel algorithm for mining weighted clickstream patterns, Inform. Sci. 582 (2022) 349–368.

[29]

Song W., Ye W., Fournier-Viger P., Mining sequential patterns with flexible constraints from MOOC data, Appl. Intell. 52 (14) (2022) 16458–16474.

[30]

Ahmed S.A., Nath B., Identification of adverse disease agents and risk analysis using frequent pattern mining, Inform. Sci. 576 (2021) 609–641.

[31]

Chen M.-S., Park J.S., Yu P.S., Efficient data mining for path traversal patterns, IEEE Trans. Knowl. Data Eng. 10 (2) (1998) 209–221.

[32]

Ji X., Bailey J., Dong G., Mining minimal distinguishing subsequence patterns with gap constraints, Knowl. Inf. Syst. 11 (3) (2007) 259–286.

[33]

Wu X., Zhu X., He Y., Arslan A.N., PMBC: Pattern mining from biological sequences with wildcard constraints, Comput. Biol. Med. 43 (5) (2013) 481–492.

[34]

Fournier-Viger P., Gan W., Wu Y., Nouioua M., Song W., Truong T., Duong H., Pattern mining: Current challenges and opportunities, International Conference on Database Systems for Advanced Applications, Springer, 2022, pp. 34–49.

[35]

Wu Y., Wang L., Ren J., Ding W., Wu X., Mining sequential patterns with periodic wildcard gaps, Appl. Intell. 41 (1) (2014) 99–116.

Digital Library

[36]

Ding B., Lo D., Han J., Khoo S.-C., Efficient mining of closed repetitive gapped subsequences from a sequence database, 2009 IEEE 25th International Conference on Data Engineering, IEEE, 2009, pp. 1024–1035.

[37]

Han X.Q., Gong Y.S., Dong X.J., Hou R.L., Mining repetitive sequential patterns without overlapping from sequence database, Applied Mechanics and Materials 644 (2014) 2097–2100.

[38]

Zhang M., Kao B., Cheung D.W., Yip K.Y., Mining periodic patterns with gap requirement from sequences, ACM Trans. Knowl. Discov. Data 1 (2) (2007) 7–es.

[39]

Min F., Wu Y., Wu X., The Apriori property of sequence pattern mining with wildcard gaps, Int. J. Funct. Informatics Pers. Medicine 4 (1) (2012) 15–31.

[40]

Xie F., Wu X., Zhu X., Efficient sequential pattern mining with wildcards for keyphrase extraction, Knowl.-Based Syst. 115 (2017) 27–39.

[41]

Wu Y., Tong Y., Zhu X., Wu X., NOSEP: Nonoverlapping sequence pattern mining with gap constraints, IEEE Trans. Cybern. 48 (10) (2017) 2809–2822.

[42]

Wu Y., Zhu C., Li Y., Guo L., Wu X., NetNCSP: Nonoverlapping closed sequential pattern mining, Knowl.-Based Syst. 196 (2020).

[43]

Wu Y., Geng M., Li Y., Guo L., Li Z., Fournier-Viger P., Zhu X., Wu X., HANP-Miner: High average utility nonoverlapping sequential pattern mining, Knowl.-Based Syst. 229 (2021).

[44]

Wu Y., Wang Y., Li Y., Zhu X., Wu X., Top-k self-adaptive contrast sequential pattern mining, IEEE Trans. Cybern. 52 (11) (2021) 11819–11833.

[45]

Li Y., Zhang S., Guo L., Liu J., Wu Y., Wu X., NetNMSP: Nonoverlapping maximal sequential pattern mining, Appl. Intell. (2022) 1–24.

[46]

Wang W., Cao L., Negative sequence analysis: A review, ACM Comput. Surv. 52 (2) (2019) 1–39.

[47]

Dong X., Gong Y., Cao L., F-NSP+: A fast negative sequential patterns mining method with self-adaptive data storage, Pattern Recognit. 84 (2018) 13–27.

[48]

Dong X., Qiu P., Lü J., Cao L., Xu T., Mining top-k useful negative sequential patterns via learning, IEEE Trans. Neural Netw. Learn. Syst. 30 (9) (2019) 2764–2778.

[49]

Qiu P., Gong Y., Zhao Y., Cao L., Zhang C., Dong X., An efficient method for modeling nonoccurring behaviors by negative sequential patterns with loose constraints, IEEE Trans. Neural Netw. Learn. Syst. 34 (4) (2023) 1864–1878.

[50]

Z. Zheng, Y. Zhao, Z. Zuo, L. Cao, Negative-GSP: An efficient method for mining negative sequential patterns, in: Conferences in Research and Practice in Information Technology Series, 2009.

[51]

Mitchell M., An Introduction to Genetic Algorithms, MIT Press, 1998.

[52]

Ezugwu A.E., Agushaka J.O., Abualigah L., Mirjalili S., Gandomi A.H., Prairie dog optimization algorithm, Neural Comput. Appl. 34 (22) (2022) 20017–20065.

Digital Library

[53]

Agushaka J.O., Ezugwu A.E., Abualigah L., Dwarf mongoose optimization algorithm, Comput. Methods Appl. Mech. Engrg. 391 (2022).

[54]

Abualigah L., Yousri D., Abd Elaziz M., Ewees A.A., Al-Qaness M.A., Gandomi A.H., Aquila optimizer: a novel meta-heuristic optimization algorithm, Comput. Ind. Eng. 157 (2021).

[55]

Abualigah L., Abd Elaziz M., Sumari P., Geem Z.W., Gandomi A.H., Reptile Search Algorithm (RSA): A nature-inspired meta-heuristic optimizer, Expert Syst. Appl. 191 (2022).

Digital Library

[56]

Oyelade O.N., Ezugwu A.E.-S., Mohamed T.I., Abualigah L., Ebola optimization search algorithm: A new nature-inspired metaheuristic optimization algorithm, IEEE Access 10 (2022) 16150–16177.

[57]

Abualigah L., Diabat A., Mirjalili S., Abd Elaziz M., Gandomi A.H., The arithmetic optimization algorithm, Comput. Methods Appl. Mech. Engrg. 376 (2021).

[58]

Agrawal R., Srikant R., Mining sequential patterns, Proceedings of the Eleventh International Conference on Data Engineering, IEEE, 1995, pp. 3–14.

Cited By

Nawaz MNawaz MJunyi ZFournier-Viger PQu J(2024)Exploiting the sequential nature of genomic data for improved analysis and identificationComputers in Biology and Medicine10.1016/j.compbiomed.2024.109307183:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.compbiomed.2024.109307

Recommendations

Mining actionable repetitive positive and negative sequential patterns
Abstract
Repetitive positive and negative sequential patterns (PNSPs) recognize the repetitive characteristics of positive (occurring) and negative (nonoccurring) sequential patterns, thereby providing more comprehensive information than traditional ...
Mining weighted sequential patterns in a sequence database with a time-interval weight

Sequential pattern mining, including weighted sequential pattern mining, has been attracting much attention since it is one of the essential data mining tasks with broad applications. The weighted sequential pattern mining aims to find more interesting ...
Mining sequential patterns by PrefixSpan algorithm with approximation
ACS'08: Proceedings of the 8th conference on Applied computer scince

We want to find sequential patterns in a long continues noisy DNA sequence. Sequential pattern mining, which discovers frequent subsequences as patterns in a sequence database, is an important data mining problem with broad applications, including the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Knowledge-Based Systems

Knowledge-Based Systems Volume 287, Issue C

Mar 2024

288 pages

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 05 March 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nawaz MNawaz MJunyi ZFournier-Viger PQu J(2024)Exploiting the sequential nature of genomic data for improved analysis and identificationComputers in Biology and Medicine10.1016/j.compbiomed.2024.109307183:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.compbiomed.2024.109307

View Options

View options

Figures

Tables

Media

Affiliations

Chuanhou Sun

Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center (National Supercomputer Center in Jinan), Qilu University of Technology (Shandong Academy of Sciences), Jinan, China

Shandong Provincial Key Laboratory of Computer Networks, Shandong Fundamental Research Center for Computer Science, Jinan, China

Yongshun Gong

School of Software, Shandong University, Jinan, China

Ying Guo

Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center (National Supercomputer Center in Jinan), Qilu University of Technology (Shandong Academy of Sciences), Jinan, China

Shandong Provincial Key Laboratory of Computer Networks, Shandong Fundamental Research Center for Computer Science, Jinan, China

Long Zhao

Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center (National Supercomputer Center in Jinan), Qilu University of Technology (Shandong Academy of Sciences), Jinan, China

Shandong Provincial Key Laboratory of Computer Networks, Shandong Fundamental Research Center for Computer Science, Jinan, China

Hongjiao Guan

Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center (National Supercomputer Center in Jinan), Qilu University of Technology (Shandong Academy of Sciences), Jinan, China

Shandong Provincial Key Laboratory of Computer Networks, Shandong Fundamental Research Center for Computer Science, Jinan, China

Xinwang Liu

School of Computer, National University of Defense Technology, Changsha, China

Xiangjun Dong

Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center (National Supercomputer Center in Jinan), Qilu University of Technology (Shandong Academy of Sciences), Jinan, China

Shandong Provincial Key Laboratory of Computer Networks, Shandong Fundamental Research Center for Computer Science, Jinan, China

View Issue’s Table of Contents