Mining Closed Repetitive Gapped Sequential Patterns Based on Repetition Linked WAP-Tree

Abstract:

Closed repetitive gapped sequential pattern mining has been gained more and more attention in recent years, in this paper, we propose a novel method MRCGP(mining closed repetitive gapped sequential pattern based on repetition linked WAP-Tree). In the first step of MRCGP, the given sequential database is transformed into a new database in which every item is expressed by its landmark; then a positional information table(PIT) which includes all of the position information of 1-frequent items is constructed, all of the repetitive gapped 2-sequential patterns of different items (RPDI) can be obtained through searching the positional information table; following, a repetitive linked web access pattern tree (RLWAP-Tree) is built, in RLWAP-Tree, the 1-frequent items are stored as header table, the items in header table will be linked to their same items which appear earliest in each sequence corresponding to RLWAP-Tree with solid line, all of the items in RLWAP-Tree are linked to their same items in the same sequences with broken line; through mining projection tree of the existing repetitive gapped pattern recursively, we can obtain the repetitive gapped sequential pattern; at the end, we get the closed repetitive gapped sequential pattern by checking inclusion relation of any two patterns. The experiment result shows MRCGP has better time efficiency.

• Periodical: Applied Mechanics and Materials (Volume 197)
• Pages: 283-291
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.197.283
• Online since: September 2012
• Authors: Jun Dong, Yu Jie Xie, Jia Dong Ren, Wei Wei Zhou
• Keywords: Positional Information Table, Projection Tree, Repetitive Gapped Sequential Pattern, RLWAP-Tree

References

[1] L. EunJu, K. WonYoung, R. JoonSuk and  K. Ung-Mo: Efficient weighted mining of repetitive subsequences, Web Society( 2009). SWS' 09, 1st IEEE Symposium(Aug 2009), pp.66-70.

DOI: 10.1109/sws.2009.5271708

[2] J. Ayres, J. Gehrke, T. Yiu, and J. Flannick: Sequential Pattern Mining Using A Bitmap Representation, Proc of the eighth ACM SIGKDD international conference on Knowledge Discovery and Data Mining. New York: ACM(2002), pp.429-435.

DOI: 10.1145/775047.775109

[3] Yan X, J. Han, R. Afshar. CloSpan: Mining Closed Sequential Patterns in Large Datasets, Proc of SIAM International Conference on Data Mining. Chicago: SDM( May 2003): pp.166-177.

DOI: 10.1137/1.9781611972733.15

[4] D. Yuan, K. Lee, H. Cheng, G. Krishna, Z. Li and X. Ma, CISpan: Comprehensive Incremental Mining Algorithms of Closed Sequential Patterns for Multi-Versional Software Mining, Proc of the 2008 SIAM International Conference on Data Mining (SDM08), Georgia: SDM(April 2008), pp.84-95.

DOI: 10.1137/1.9781611972788.8

[5] J. Pei, J. Han, B. Mortazavi-asl and Zhu: Mining access patterns efficiently from web logs, Proc of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'00), Kyoto Japan( 2000), pp.390-407.

DOI: 10.1007/3-540-45571-x_47

[6] C. I. Ezeife and Y. Lu: Mining web log sequential patterns with position coded pre-order linked wap-tree, International Journal of Data Mining and Knowledge Discovery (DMKD) Kluwer Publishers10(1)(2005), p.5–38.

DOI: 10.1007/s10618-005-0248-3

[7] C. I. Ezeife, K. Saeed and D. Zhang: Mining very long sequences in large databases with PLWAPLong, Proc of the 2009 International Database Engineering & Applications Symposium, Cetraro - Calabria Italy(2009), pp.234-241.

DOI: 10.1145/1620432.1620457

[8] C. I. Ezdife and Y. Liu: Fast incremental mining of web sequential patterns with PLWAP tree, Data Mining and Knowledge Discovery (2009), pp.376-416.

DOI: 10.1007/s10618-009-0133-6

[9] B. Ding, D. Lo, J. Han, and S-C. Khoo: Efficient mining of closed repetitive gapped sequential patterns from a sequence database, Proc of the 25th International Conference on Data Engineering (ICDE'09), Shanghai China (Mar 2009), pp.1024-1035.

DOI: 10.1109/icde.2009.104

[10] Y. Tong, L. Zhao, and D. Yu: Mining Compressed Repetitive Gapped Sequential Patterns Efficiently, The 5th International Conference on Advanced Data Mining and Applications (ADMA2009) (2009), pp.652-660.

DOI: 10.1007/978-3-642-03348-3_68