Computer Science ›› 2023, Vol. 50 ›› Issue (3): 147-154.doi: 10.11896/jsjkx.211200248

• Database & Big Data & Data Science • Previous Articles     Next Articles

Mining Negative Sequential Patterns with Periodic Gap Constraints

WANG Zhulin1, WU Youxi1,2, WANG Yuehua3, LIU Jingyu1,2   

  1. 1 School of Artificial Intelligence,Hebei University of Technology,Tianjin 300401,China
    2 Hebei Key Laboratory of Big Data Computing,Tianjin 300401,China
    3 School of Economics and Management,Hebei University of Technology,Tianjin 300401,China
  • Received:2021-12-23 Revised:2022-06-21 Online:2023-03-15 Published:2023-03-15
  • About author:WANG Zhulin,born in 1997,postgra-duate,is a member of China Computer Federation.His main research interests include data mining and so on.
    WU Youxi,born in 1974,Ph.D,professor,Ph.D supervisor,is a distinguished member of China Computer Federation.His main research interests include data mining and machine learning.
  • Supported by:
    National Natural Science Foundation of China(61976240).

Abstract: Sequential pattern mining with gap constraints is a special form of sequential pattern mining,which can reveal frequent subsequences in a certain gap.However,the current sequential pattern mining methods with gap constraints only focus on positive sequential pattern mining,and ignore the missing behavior in a series of events.To solve this problem,a negative sequential pattern method with periodic gap constraints(NSPG) mining is explored,which can reflect the relationship between elements more flexibly.To solve the problem of NSPG mining,this paper proposes an NSPG-INtree(incomplete nettrees) algorithm,which includes two key steps:candidate pattern generation and support calculation.For candidate pattern generation,to reduce the number of candidate patterns,the algorithm uses a pattern join strategy.For support calculation,to improve the efficiency and reduce space consumption,the algorithm employs an incomplete nettree structure to calculate the supports of patterns.Experimental results show that NSPG-INtree not only has high mining efficiency,but also can mine positive and negative sequential patterns with gap constraints.NSPG-INtree can find 209% ~ 352% more patterns than other gap-constrained sequential pattern mining algorithms.Moreover,NSPG-INtree can reduce the running time by 6%~38% than other competitive algorithms with different stra-tegies.

Key words: Sequential pattern mining, Negative sequential pattern, Frequent pattern, Gap constraint, Incomplete nettree

CLC Number: 

  • TP311
[1]ZHANG G L,YANG Q H,CHENG X M,et al.Application of sequence pattern mining in communication network alarm prediction[J].Computer Science,2018,45(11A):535-538.
[2]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 [J].Computer Science,2021,48(11):208-218.
[3]WU Y X,ZHU C R,LI Y,et al.NetNCSP:Nonoverlappingclosed sequential pattern mining [J].Knowledge-Based Systems,2020,196:105812.
[4]WU Y X,LUO L F,LI Y,et al.NTP-Miner:Nonoverlapping three-way sequential pattern mining [J].ACM Transactions on Knowledge Discovery from Data,2022,16(3):1-21.
[5]WU C F,CAI L,LI J,et al.Frequent pattern mining of resident'stravel based on multi-source location data [J].Computer Science,2021,48(7):155-163.
[6]HUANGT C.Mining the change of customer behavior in fuzzy time-interval sequential patterns [J].Applied Soft Computing,2012,12(3):1068-1086.
[7]WU Y X,WANG L L,REN J D,et al.Mining sequential patterns with periodic wildcard gaps [J].Applied Intelligence,2014,41(1):99-116.
[8]WU Y X,LIU X,YAN W J,et al.Efficient algorithm for solving non-overlapping strict sequential pattern matching [J].Journal of Software,2021,32(11):3331-3350.
[9]GUYET T,QUINIOU R.NegPSpan:Efficient extraction ofnegative sequential patterns with embedding constraints [J].Data Mining and Knowledge Discovery,2020,34(3):563-609.
[10]ZHENG Z G,ZHAO Y C,ZUO Z Y,et al.Negative-GSP:An efficient method for mining negative sequential patterns[C]//Eighth Australasian Data Mining Conference.2009:63-67.
[11]DING B,LO D,HAN J W,et al.Efficient mining of closed repetitive gapped subsequences from a sequence database[C]//IEEE International Conference on Data Engineering.2009:1024-1035.
[12]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.
[13]SHI Q S,SHAN J S,YAN W J,et al.NetNPG:Nonoverlapping pattern matching with general gap constraints [J].Applied Intelligence,2020,50(1):1832-1845.
[14]WANG L,WANG S,LIU S L,et al.An algorithm of mining sequential pattern with wildcards based on Index-Tree [J].Chinese Journal of Computers,2019,42(3):555-565.
[15]ZHOU Z Y,PI D C.Rare sequence pattern mining algorithm for shopping basket data [J].Journal of Chinese Computer Systems,2019,40(3):683-688.
[16]WU Y X,GENG M,LI Y,et al.HANP-Miner:High averageutility nonoverlapping sequential pattern mining[J].Knowledge-Based Systems,2021,229,107361.
[17]WU Y X,WANG Y H,LI Y,et al.Top-k self-adaptive contrast sequential pattern mining [J].IEEE Transactions on Cyberne-tics,2022,52(11):11819-11833..
[18]WU Y X,LEI R,LI Y,et al.HAOP-Miner:Self-adaptive high-average utility one-off sequential pattern mining [J].Expert Systems with Applications,2021,184,115449.
[19]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.
[20]HUANG G,GAN W,HUANG S,et al.Negative pattern discovery with individual support [J].Knowledge-Based Systems,2022,251,109194.
[21]LIN N P,CHEN H J,HAO W H.Mining negative sequential patterns [C]//Conference on Applied Computer Science.2007:654-658.
[22]OUYANG W M,HUANG Q H,LUO S H.Mining positive and negative fuzzy sequential patterns in large transaction databases[C]//Fifth International Conference on Fuzzy Systems and Knowledge Discovery.2008:18-23.
[23]HSUEH S C,LIN M Y,CHEN C L.Mining negative sequential patterns for e-commerce recommendations[C]//IEEE Asia-Pacific Services Computing Conference.2008:1213-1218.
[24]CAO L B,D X J,ZHENG Z G.E-NSP:Efficient negative se-quential pattern mining [J].Artificial Intelligence,2016,235(1):156-182.
[25]DONG X J,GONG Y S,CAO L B.F-NSP +:A fast negative sequential patterns mining method with self-adaptive data sto-rage[J].Pattern Recognition,2018,84:13-27.
[26]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,2018,50(5):2084-2096.
[27]WU Y X,WU X D,MIN F,et al.A Nettree for Pattern Ma-tching with Flexible Wildcard Constraints[C]//IEEE Interna-tional Conference on Information Reuse & Integration.2010:109-114.
[1] WU Cheng-feng, CAI Li, LI Jin, LIANG Yu. Frequent Pattern Mining of Residents’ Travel Based on Multi-source Location Data [J]. Computer Science, 2021, 48(7): 155-163.
[2] ZHANG Lei,CAI Ming. Image Annotation Based on Topic Fusion and Frequent Patterns Mining [J]. Computer Science, 2019, 46(7): 246-251.
[3] LU Xin-yun, WANG Xing-fen. Educational Administration Data Mining of Association Rules Based on Domain Association Redundancy [J]. Computer Science, 2019, 46(6A): 427-430.
[4] ZENG Qing-tian, LIU Chen-zheng, NI Wei-jian, DUAN Hua. Combined Feature Extraction Method for Ordinal Regression [J]. Computer Science, 2019, 46(6): 69-74.
[5] WANG Shu-yi and DONG Dong. Mining of API Usage Pattern Based on Clustering and Partial Order Sequences [J]. Computer Science, 2017, 44(Z6): 486-490.
[6] JIANG Jing-jing, WANG Zhi-hai and YUAN Ji-dong. Partially-lazy Learning Classification Algorithm Based on Representation of Data Stream Model [J]. Computer Science, 2017, 44(7): 167-174.
[7] LEI Dong, WANG Tao and MA Yun-fei. Frequent Pattern Mining in Bit Stream Based on AC Algorithm [J]. Computer Science, 2017, 44(1): 128-133.
[8] ZENG Xin and YANG Jian. Co-location Patterns Mining with Time Constraint [J]. Computer Science, 2016, 43(2): 293-296.
[9] DING Jian, HAN Meng and LI Juan. Review of Concept Drift Data Streams Mining Techniques [J]. Computer Science, 2016, 43(12): 24-29.
[10] WANG Wei, LIU Yuan, ZHANG Chun-rui, WEN Ping and XIE Jia-jun. Detection of Context-based Inconsistencies Bugs [J]. Computer Science, 2015, 42(Z6): 525-530.
[11] CUI Liang, GUO Jing and WU Ling-da. Algorithm for Mining Association Roles Based on Dynamic Hashing and Transaction Reduction [J]. Computer Science, 2015, 42(9): 41-44.
[12] CHENG Shu-tong, XU Cong-fu and DAN Hong-wei. Research on Efficient Privacy Preserving Frequent Pattern Mining Algorithm [J]. Computer Science, 2015, 42(4): 194-198.
[13] . Multi-relational Frequent Pattern Mining Method Relying on the ER Data Model [J]. Computer Science, 2012, 39(4): 159-163.
[14] WANG Jie,DAI Qing-hao,LI Huan. Tuning of Parallel Frequent Pattern Growth Algorithm Based on Distributed Coordination System [J]. Computer Science, 2012, 39(3): 174-182.
[15] . New Algorithm for Mining Workflow Frequent Closet Pattern [J]. Computer Science, 2012, 39(11): 153-156.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!