Please wait a minute...
浙江大学学报(工学版)
J4
    
An incremental algorithm for mining frequent closed patterns
SHI Huai-dong1, CAI Ming1, WU Hong-sen2, DONG Jin-xiang1, FU Hao1
1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;
2. Zhejiang Police College, Hangzhou 310053, China
Download:   PDF(795KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

While mining frequent closed patterns (FCP), the input sequence database dynamically increases in many situations. By analyzing Bide algorithm, the theorem of backward-extension event (BEE) detection was proposed and proved. It shows that the BEE set of any prefix item is non-increasing with the extension of the prefix. Based on the theorem, the accumulation performance of the BEE set was optimized by 4.8% averagely. The FCP tree was defined to represent the final result of FCP mining and its three characteristics were demonstrated. When the frequent item and the prefix are not coexistent in the new input sequence, the results of contiguous FCP mining are equal. And the corresponding theorem was proved. The BideInc algorithm was proposed to incrementally mine FCPs. The experiments validated the algorithm, and the performance was improved by 47% averagely.

Published: 28 September 2009
CLC:  TP 311  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

DAN Fu-Dong, CA Ming, TUN Hong-Sen, DONG Jin-Xiang, FU Gao. An incremental algorithm for mining frequent closed patterns. J4, 2009, 43(8): 1389-1395.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2009.     OR     http://www.zjujournals.com/eng/Y2009/V43/I8/1389


增量式频繁闭合序列挖掘算法

在许多场合挖掘频繁闭合序列时,输入串数据库呈现实时动态增长的特点.分析Bide算法,给出并证明了闭合序列前缀中任意一个项目的后向扩展事件（BEE）项目交集随前缀的生长单调不增的定理,据此对BEE累计操作进行了优化,使其性能平均提高了48%.定义了闭合序列树作为频繁闭合序列的表示形式,并阐述了它的3个性质.分析发现,当新增输入串不同时包含前缀串和频繁项目时,两次连续挖掘的结果是相同的,给出了相应的定理和证明,据此实现了增量式频繁闭合序列挖掘算法BideInc.实验验证了BideInc算法的正确性,使用该算法后挖掘性能平均提高了47%.


[1] WEISER M. The computer for the twenty-first century
[J]. Scientific American, 1991, 265(3): 94-104.


[2] NORMAN D. The invisible computer
[M]. Cambridge: MIT Press, 1999.


[3] AGRAWAL R, SRIKANT R. Mining sequential patterns
[C]∥ Proceedings of the 11th International Conference on Data Engineering. Taipei: IEEE, 1995: 3-14.


[4] SRIKANT R, AGRAWAL R. Mining sequential patterns: generalizations and performance improvements
[C]∥ Proceedings of the 5th International Conference on Extending Database Technology. Avignon: Springer, 1996: 3-17.


[5] ZAKI M J. SPADE: an efficient algorithm for mining frequent sequences
[J]. Machine Learning, 2001, 42(1): 31-60.


[6] PEI J, HAN J, MORTAZAVI-ASL B, et al. Prefix- Span: mining sequential patterns efficiently by prefix-projected pattern growth
[C]∥ Proceedings of the 17th International Conference on Data Engineering. Heidelberg: IEEE, 2001: 215-224.


[7] AYRES J, GEHRKE J, YIU T, et al. Sequential pattern mining using a bitmap representation
[C]∥ Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining. Edmonton: ACM, 2002: 429-435.


[8] PASQUIER N, BASTIDE Y, TAOUIL R, et al. Discovering frequent closed itemsets for association rules
[C]∥ Proceedings of the 7th International Conference on Database Theory. Jerusalem: Springer, 1999: 398-416.


[9] PEI J, HAN J, MAO R. CLOSET: an efficient algorithm for mining frequent closed itemsets
[C]∥ Proceedings of the 2000 ACM SIGMOD International Workshop Data Mining and Knowledge Discovery. Dallas: ACM, 2001: 11-20.


[10] WANG J, HAN J, PEI J. CLOSET+: searching for the best strategies for mining frequent closed itemsets
[C]∥ Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM, 2003: 236-245.


[11] ZAKI M J, HSIAO C. CHARM: an efficient algorithm for closed itemset mining
[C]∥ Proceedings of the Second SIAM International Conference on Data Mining. Arlington: SIAM, 2002: 457-473.


[12] HAN J, WANG J, LU Y, et al. Mining Top-K frequent closed patterns without minimum support
[C]∥ Proceedings of the 2002 IEEE International Conference on Data Mining. Maebashi: IEEE, 2002: 211-218.


[13] YAN X, HAN J, AFSHAR R, CloSpan: mining closed sequential patterns in large databases
[C]∥ Proceedings of the 3th SIAM International Conference on Data Mining. San Francisco: SIAM, 2003: 166-177.


[14] WANG J, HAN J. BIDE: efficient mining of frequent closed sequences
[C]∥ Proceedings of the 20th International Conference on Data Engineering. Boston: IEEE, 2004: 79-90.


[15] TZVETKOV P, YAN X, HAN J. TSP: mining top-k closed sequential patterns
[C]∥ Proceedings of the Third IEEE International Conference on Data Mining. Melbourne: IEEE, 2003: 347-354.


[16] 刘君强,孙晓莹,庄越挺,等. 挖掘闭合模式的高性能算法
[J]. 软件学报, 2004, 15(1): 94-102.

LIU Jun-qiang, SUN Xiao-ying, ZHUANG Yue-ting, et al. Mining frequent closed patterns by adaptive pruning
[J]. Journal of Software, 2004, 15(1): 94-102.


[17] MUNGUIA E T, STEPHEN S. Activity recognition in the home using simple and ubiquitous sensors
[C]∥ Proceedings of Pervasive Computing: Second International Conference. Vienna: Springer, 2004: 158-175. 
[1] KE Hai-feng, YING Jing. Real-time license character recognition technology based on R-ELM[J]. J4, 2014, 48(2): 0-0.
[2] JIN Cang-hong, WU Ming-hui, YING Jing. A context-aware index based text extraction framework[J]. J4, 2013, 47(9): 1537-1546.
[3] ZHU Fan-wei, WU Ming-hui, YING Jing. Faceted Web search approach for large scale unstructured data[J]. J4, 2013, 47(6): 990-999.
[4] FENG Pei-en, LIU Yu, QIU Qing-ying, LI Li-xin. Strategies of efficiency improvement for Eclat algorithm[J]. J4, 2013, 47(2): 223-230.
[5] LIU Ying, CHEN Ling, CHEN Gen-cai, ZHAO Jiang-qi, WANG Jing-chang. Approach for collection selection based on click-through data[J]. J4, 2013, 47(1): 23-28.
[6] YIN Ting, XIAO Min, CHEN Ling, ZHAO Jiang-qi, WANG Jing-chang. CQPM based OLAP query log mining and recommendation[J]. J4, 2012, 46(11): 2052-2060.
[7] XIAO Min, CHEN Iing, XIA Hai-yuan, CHEN Gen-cai. Data warehouse native feature based OLAP querying with keywords[J]. J4, 2012, 46(6): 974-979.
[8] ZHANG Li-ping, LI Song, HAO Xiao-hong, HAO Zhong-xiao. Jrv  rough Vague region relation[J]. J4, 2012, 46(1): 105-111.
[9] CHEN Ling, XU Xiao-long, YANG Qing, CHEN Gen-cai. Wireless signal strength propagation model
 base on cubic spline interpolation[J]. J4, 2011, 45(9): 1521-1527.
[10] WU Ming-hui, YING Jing. Business process modeling and formal verification[J]. J4, 2011, 45(2): 280-287.
[11] FU Chao-yang, GAO Ji, ZHOU You-ming. Service discovery based on integrating lexical multi-level hashing
with subsumption semantics[J]. J4, 2010, 44(12): 2274-2283.
[12] YANG Qing, CHEN Ling, CHEN Gen-Cai. Estimating walking distance based on single accelerometer[J]. J4, 2010, 44(9): 1681-1686.
[13] XIONG Wei, WANG Xiao-Tun. Method for mapping software dependability requirements
based on quality function deployment[J]. J4, 2010, 44(5): 881-886.
[14] ZHANG Yin, HE Gao, DIAO Li-Na, ZHANG San-Yuan. Abstract state machine design of Internetware model[J]. J4, 2010, 44(5): 923-929.
[15] JIANG Chao, YING Jing, TUN Meng-Hui, et al. Feature increment oriented  approach for software product line analysis[J]. J4, 2009, 43(12): 2142-2148.