For the purpose of efficiency improvement, Eclat algorithm was optimized in three aspects-pruning, itemsets connection and intersection. Firstly, the equivalence classes were divided in the suffix-based way to make the best of pruning in which a double layer hash table was utilized to accelerate the search process of subsets of candidate itemsets. Secondly, a partition list of the set of itemsets was presented to eliminate the connection judgment of itemsets. Finally, a transaction id (Tid) lost threshold was introduced to speed up intersection. Based on the above three improvement strategies an Eclat_opt algorithm was proposed. The performance comparison between the Eclat_opt algorithm, the original Eclat algorithm (ZAKI) and two other improved Eclat algorithms Diffset(ZAKI), hEclat (XIONG Zhong-yang) showed that the efficiency of the Eclat_opt algorithm ranked the first among the four algorithms on sparse datasets, and its overall time performance was the best.
[1] AGRAWAL R, SRIKANT R. Fast Algorithms for mining association rules [C]∥ Proceedings of 20th International Conference on Very Large Data Bases. Santiago, Chile: Morgankaufman, 1994: 487-499.
[2] HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation [C]∥ Proceedings of the 2000 ACM Data. Dallas, United States: ACM, 2000: 1-12.
[3] FENG Pei-en, ZHANG Hui, QIU Qing-ying, et al. PCAR: an efficient approach for mining association rules [C]∥ Proceedings of the ICNC-FSKD 2008 International Conference on Fussy Systems and Knowledge Discovery. Jinan: IEEE, 2008: 605-609.
[4] ZAKI M J. Scalable algorithms for association mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2000,12(3): 372-390.
[5] 宋长新, 马克. 改进的Eclat数据挖掘算法的研究[J]. 微计算机信息, 2008, 24(8): 92-94
SONG Chang-xin, MA Ke. Research on the improved eclat data mining algorithm [J]. Control & Automation, 2008, 24(8): 92-94.
[6] ZAKI M J. Fast vertical mining using diffsets [R].Technical Report 01-1, Troy, New York: Rensselaer Polytechnic Institute. 2001.
[7] 熊忠阳, 陈培恩, 张玉芳. 基于散列布尔矩阵的关联规则Eclat改进算法[J]. 计算机应用研究, 2010, 27(4): 1323-1325.
XIONG Zhong-yang, CHEN Pei-en, ZHANG Yu-fang. Improvement of Eclat algorithm for association rules based on hash Boolean matrix [J]. Application Research of Computers, 2010, 27(4): 1323-1325.
[8] 李敏, 李春平. 频繁模式挖掘算法分析和比较[J]. 计算机应用, 2005, 25: 166-171.
LI Min, LI Chun-ping. Analysis and Comparison of frequent patterns mining algorithms [J]. Journal of Computer Applications, 2005, 25: 166-171.
[9] HAN J, KAMBE M. Data mining: concepts and Techniques [M]. San Francisco, United States: Morgan Kaufmann Publishers Inc, 2001: 231.
[10] 刘井莲. Eclat与Eclat+算法的比较分析[J]. 绥化学院学报, 2010, 30(2): 189-190.
LIU Jing-lian. Comparative Analysis of Eclat Algorithm and Eclat+ Algorithm [J]. Journal of Suihua University, 2010, 30(2): 189-190.
[11] GOETHALS B. Frequent itemset mining dataset repository [EB/OL]. [2004-12-2]. http:∥fimi.ua.ac.be/data/