research-article

Mining actionable repetitive positive and negative sequential patterns

Authors:

Chengqi ZhangAuthors Info & Claims

Volume 302, Issue C

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

Published: 25 October 2024 Publication History

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 PNSPs. However, existing repetitive PNSP mining methods produce numerous conflict patterns that do not benefit decision-making. To address this issue, we propose an actionable repetitive PNSP mining method, namely ARPNSP, for transaction databases. First, we propose the definition of negative occurrence under the self-adaptive gap and nonoverlapping conditions, which makes it possible to identify whether a pattern is actionable via correlation analysis. Second, we propose an offset sequence definition by adding a dummy character at the head of the sequences, which determines the population of repetitive PNSP. Finally, we utilize the bitmap structure to represent databases and occurrences of patterns, which avoids rescanning data sequences to calculate support. To the best of our knowledge, this study is the first attempt at actionable repetitive PNSP mining. Extensive experiments on real-world datasets show that ARPNSP can efficiently discover more actionable PNSPs with high correlation than the considered methods.

References

[1]

Srikant R., Agrawal R., Mining sequential patterns: Generalizations and performance improvements, in: 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]

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.

[4]

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

Digital Library

[5]

Zheng Z., Zhao Y., Zuo Z., Cao L., An efficient GA-based algorithm for mining negative sequential patterns, in: 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.

[6]

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

[7]

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.

[8]

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.

[9]

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.

[10]

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

[11]

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

[12]

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.

[13]

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.

[14]

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

[15]

Wang Y., Wu Y., Li Y., Yao F., Fournier-Viger P., Wu X., Self-adaptive nonoverlapping sequential pattern mining, Appl. Intell. 52 (6) (2022) 6646–6661.

[16]

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. (TMIS) 13 (3) (2022) 1–23.

[17]

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

[18]

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

[19]

Gong Y., Dong X., Han X., Hou R., Mining non-overlapping repetitive sequential patterns by improving GSP algorithm, Open Cybern. Syst. J. 9 (1) (2015).

[20]

Cao L., Actionable knowledge discovery and delivery, Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 2 (2) (2012) 149–163.

[21]

Goh Y., Tan B.Y., Bhartendu C., Ong J.J., Sharma V.K., The face mask: How a real protection becomes a psychological symbol during Covid-19?, Brain Behav. Immun. 88 (2020) 1–5.

[22]

Wu X., Zhang C., Zhang S., Efficient mining of both positive and negative association rules, ACM Trans. Inf. Syst. (TOIS) 22 (3) (2004) 381–405.

[23]

Dong X., Liu C., Xu T., Wang D., Select actionable positive or negative sequential patterns, J. Intell. Fuzzy Systems 29 (6) (2015) 2759–2767.

[24]

Liu C., Dong X., Li C., Li Y., SAPNSP: Select actionable positive and negative sequential patterns based on a contribution metric, in: 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD, IEEE, 2015, pp. 811–815.

[25]

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

[26]

Sun C., Gong Y., Guo Y., Zhao L., Guan H., Liu X., Dong X., SN-RNSP: Mining self-adaptive nonoverlapping repetitive negative sequential patterns in transaction sequences, Knowl.-Based Syst. 287 (2024).

[27]

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

[28]

Cao L., Zhang C., Domain driven data mining, in: Data Mining and Knowledge Discovery Technologies, IGI Global, 2008, pp. 196–223.

[29]

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

[30]

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

[31]

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.

[32]

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.

[33]

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

[34]

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.

[35]

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) (2021) 1864–1878.

[36]

Wang W., Cao L., VM-NSP: Vertical negative sequential pattern mining with loose negative element constraints, ACM Trans. Inf. Syst. (TOIS) 39 (2) (2021) 1–27.

[37]

S. Brin, R. Motwani, C. Silverstein, Beyond market baskets: Generalizing association rules to correlations, in: Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, 1997, pp. 265–276.

[38]

B. Liu, W. Hsu, Y. Ma, Pruning and summarizing the discovered associations, in: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999, pp. 125–134.

[39]

Zhao Y., Zhang H., Cao L., Zhang C., Bohlscheid H., Mining both positive and negative impact-oriented sequential rules from transactional data, in: Advances in Knowledge Discovery and Data Mining: 13th Pacific-Asia Conference, PAKDD 2009 Bangkok, Thailand, April 27-30, 2009 Proceedings 13, Springer, 2009, pp. 656–663.

[40]

Wang W., Cao L., Explicit and implicit pattern relation analysis for discovering actionable negative sequences, IEEE Trans. Neural Netw. Learn. Syst. (2022).

[41]

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

[42]

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).

[43]

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

[44]

Wu Y., Luo L., Li Y., Guo L., Fournier-Viger P., Zhu X., Wu X., NTP-Miner: Nonoverlapping three-way sequential pattern mining, ACM Trans. Knowl. Discov. Data (TKDD) 16 (3) (2021) 1–21.

[45]

Wu Y., Yuan Z., Li Y., Guo L., Fournier-Viger P., Wu X., NWP-Miner: Nonoverlapping weak-gap sequential pattern mining, Inform. Sci. 588 (2022) 124–141.

[46]

Geng M., Wu Y., Li Y., Liu J., Fournier-Viger P., Zhu X., Wu X., RNP-Miner: Repetitive nonoverlapping sequential pattern mining, IEEE Trans. Knowl. Data Eng. (2023).

[47]

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, in: Proceedings of the 17th International Conference on Data Engineering, IEEE, 2001, pp. 215–224.

[48]

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

[49]

Aseervatham S., Osmani A., Viennet E., Bitspade: A lattice-based sequential pattern mining algorithm using bitmap representation, in: Sixth International Conference on Data Mining, ICDM’06, IEEE, 2006, pp. 792–797.

[50]

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

[51]

Tan P.-N., Kumar V., Interestingness measures for association patterns: A perspective, 2000.

[52]

Antonie M.-L., Zaïane O.R., Mining positive and negative association rules: An approach for confined rules, in: European Conference on Principles of Data Mining and Knowledge Discovery, Springer, 2004, pp. 27–38.

[53]

Cohen J., Statistical Power Analysis for the Behavioral Sciences, Routledge, 2013.

Index Terms

Mining actionable repetitive positive and negative sequential patterns
1. Computing methodologies
  1. Machine learning
2. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database transaction processing
      2. Triggers and rules
  2. Information systems applications
    1. Data mining
      1. Association rules

Index terms have been assigned to the content through auto-classification.

Recommendations

SN-RNSP: Mining self-adaptive nonoverlapping repetitive negative sequential patterns in transaction sequences
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 strong positive and negative sequential patterns

In data mining field, sequential pattern mining can be applied in divers applications such as basket analysis, web access patterns analysis, and quality control in manufactory engineering, etc. Many methods have been proposed for mining sequential ...
Mining negative sequential patterns
ACOS'07: Proceedings of the 6th Conference on WSEAS International Conference on Applied Computer Science - Volume 6

Sequential pattern mining is to discover all frequent sequences from a sequence database and has been an important issue in data mining. A lot of methods have been proposed for mining sequential pattern. However, conventional methods consider only 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 302, Issue C

Oct 2024

670 pages

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 25 October 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total 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

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

Xiaoqiang Ren

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

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

Ping Qiu

School of Internet of Things, Nanjing University of Posts and Telecommunications, Nanjing, China

Xiaoming Wu

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

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

Yongshun Gong

School of Software, Shandong University, Jinan, China

Chengqi Zhang

Centre for Artificial Intelligence, Faculty of Engineering and Information Technology, University of Technology Sydney, NSW 2007, Australia

View Issue’s Table of Contents