JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (05): 23-29.doi: 10.6040/j.issn.1671-9352.0.2014.306

Previous Articles     Next Articles

An efficient bittable based frequent itemsets mining algorithm

ZHAO Guan-bao, LIU Yun   

  1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, Yunnan, China
  • Received:2014-07-04 Online:2015-05-20 Published:2015-05-29

PDF (PC)

877

Abstract: Fast and accurate mining frequent item set is the key of mining association rules in data mining techniques. The traditional Apriori-like algorithms need to scan the entire transaction database many times and spend too long time for mining frequent itemsets. Based on the efficient bittable, an based frequent itemsets mining algorithm BITXOR was proposed, which uses the bit table and represents item sets with binary sequence. BITXOR judges whether two items can be connected by the sequence of binary XOR. After the connection of item set, BITXOR also carries out pruning operation on the initial candidate sets. The simulation results show, compared with the traditional Apriori algorithm and FP-growth algorithm under the same conditions, BITXOR algorithm scans the entire transaction database only once and significantly reduces the time of mining frequent itemsets. The performances of BITXOR are more significant in conditions of intensive database.

Key words: association rules, frequent itemsets, XOR, pruning, bittable

CLC Number: 

  • TP274
[1] HAN Jiawei, PEI Jian, YIN Yiwen. Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. New York: ACM, 2000: 1-12.
[2] DONG Jie, HAN Min. BitTableFI: an efficient mining frequent itemsets algorithm[J]. Knowledge-Based Systems, 2007, 20:329-335.
[3] ZHANG Yan, ZHANG Fan, BAKOS J. Frequent itemset mining on large scale shared memory machines[C]//Proceedings of IEEE International Conference on Cluster Computing.Washington: IEEE Computer Society, 2011: 585-589.
[4] 张志刚,黄刘生,金宗安,等. 基于父子等价剪枝策略的最大频繁项集挖掘[J].计算机工程,2013,39(4):219-221,225. ZHANG Zhigang, HUANG Liusheng, JIN Zongan, et al. Maximal frequent itemset mining based on parent-child equivalency pruning strategy[J]. Computer Engineering, 2013, 39(4):219-221,225.
[5] TRAN A N, DUONG H V, TRUONG T C, et al. Efficient algorithms for mining frequent itemsets with constraint[C]//Proceedings of the 3rd International Conference on Knowledge and Systems Engineering (KSE). Washington: IEEE Computer Society, 2011: 19- 25.
[6] 刘彩苹,毛建频,毛建旭,等.基于格的快速频繁项集挖掘算法[J]. 湖南大学学报:自然科学版,2013,40(10):52-57. LIU Caiping, MAO Jianpin, MAO Jianxu, et al. Lattice-based algorithm for fast mining frequent itemsets[J]. Journal of Hunan University: Natural Sciences, 2013, 40(10):52-57.
[7] TRAN A T, NGO T P, NGUYEN K A. An efficient algorithm for discovering maximum length frequent itemsets[C]//Proceedings of the 3rd International Conference on Knowledge and Systems Engineering (KSE). Washington: IEEE Computer Society, 2011: 62-69.
[8] SURIYA S, SHANTHARAJAH S P. A hybrid k-DCI and Apriori algorithm for mining frequent itemsets[C]//Proceedings of 2013 International Conference on Circuits, Power and Computing Technologies (ICCPCT). Washington: IEEE Computer Society, 2013: 1059-1064.
[9] 张步忠,程玉胜,王则林.基于片上多核的频繁项集并行挖掘算法[J].计算机科学,2014,41(3):55-58. ZHANG Buzhong, CHENG Yusheng, WANG Zelin. Frequent itemset mining parallel algorithm based on chip multi-core[J]. Computer Science, 2014, 41(3):55-58.
[10] VO B, COENEN F, LE T, et al. A hybrid Approach for mining frequent itemsets[C]//Proceedings of 2013 IEEE International Conference on Systems, Man, and Cybernetics. Washington: IEEE Computer Society, 2013: 4647-4651.
[1] WANG Kai-rong, MA Lin. An accelerating algorithm for solving global solution of  generalized geometric programming [J]. J4, 2013, 48(1): 72-77.
[2] CAO Lin-lin1,2, ZHANG Hua-xiang1,2*, WANG Zhi-chao1,2. EB-SVM: support vector machine based data pruning with informatior entropy [J]. J4, 2012, 47(5): 59-62.
[3] LI Gui, HAN Zi-yang, ZHENG Xin-lu, LI Zheng-yu. Study on Deep Web pages mining based on Apriori algorithm [J]. J4, 2011, 46(5): 67-70.
[4] ZHANG Wen-dong1, YIN Jin-huan1, JIA Xiao-fei2, HUANG Chao1, YUAN Yan-mei1. Research of a frequent itemsets mining algorithm based on vector [J]. J4, 2011, 46(3): 31-34.
[5] LOU Lan-fang,PAN Qing-xian . An improved algorithm based on sets operation for mining frequent itemsets [J]. J4, 2008, 43(11): 54-57 .
[6] GUO Yue-bin,ZHAI Yan-fu,DONG Xiang-jun,YANG Yue-yue,LI Gang . Positive and negative association rules based on sequential patterns [J]. J4, 2007, 42(9): 88-90 .
[7] SONG Chun-fang,SHI Bing . An algorithm to cluster the search results basedon the association rules [J]. J4, 2006, 41(3): 61-65 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd