Improved FP-growth Algorithm with Multiple Minimum Supports Using Maximum Constraints

Authors: Elsayeda M. Elgaml, Dina M. Ibrahim, Elsayed A. Sallam

Abstract:

Association rule mining is one of the most important fields of data mining and knowledge discovery. In this paper, we propose an efficient multiple support frequent pattern growth algorithm which we called “MSFP-growth” that enhancing the FPgrowth algorithm by making infrequent child node pruning step with multiple minimum support using maximum constrains. The algorithm is implemented, and it is compared with other common algorithms: Apriori-multiple minimum supports using maximum constraints and FP-growth. The experimental results show that the rule mining from the proposed algorithm are interesting and our algorithm achieved better performance than other algorithms without scarifying the accuracy. 

Keywords: Association Rules, FP-growth, Multiple minimum supports, Weka Tool

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1100847

References:

[1] S. Brin, R. Motwani, J. Ullman, and S. Tsur, “Dynamic itemset counting and implication rules for market basket data,” in SIGMOD-97, 1997, pp. 255-264.
[2] C. Aggarwal, and P. Yu “Online generation of association rule,” in ICDE-98, (1998), pp. 402-411.
[3] R. Uday Kiran, P. Krishna Reddy , “An efficient approach to mine rare association rules using maximum items support constraints data Security and security data, ” Springer, vol. 6121, pp. 84-95,2010.
[4] L. Troiano, G. Scibelli and C. Birtolo, “A fast algorithm for Mining rare itemsets,” in Conf. 2009 the Ninth IEEE International Conference on Intelligent Systems Design and Applications, pp. 1149-1155.
[5] K. S. C. Sadhasivam, T. Angamuthu, “Mining rare Itemset with Automated Support Thresholds,” Computer Science J., vol. 7, pp. 394- 399, 2011.
[6] R. Agrawal, T. Imielinksi and A. Swami, “Mining association rules between sets of items in large database,” in 1993The ACM SIGMOD Conf., pp. 207–216.
[7] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” in 1994VLDB Conf., Santiago, Chile, Expanded version available as IBM Research Report RJ9839.
[8] Y. Lee, T. Hong and W. Lin, “Mining association rules with multiple minimum supports using maximum constraints,” Elsevier Inc., 2005.
[9] B. Liu, W. Hsu and Y. Ma, “Mining association rules with multiple minimum supports,” in 1999The International Conf. on Knowledge Discovery and Data Mining, pp. 337–341.
[10] J. Han, J. Pei and Y. Yin, “Mining frequent patterns without candidate generation,” in 2000International Conf. on Management of data, vol. 29, pp. 1-12.
[11] Z. Sun, “Analysis and implementation of the algorithm of fp-growth,” Guangxi Institute of Technology J., vol. 16, no. 3, pp. 64-67, 2004.
[12] R. U. Kiran, P. K. Reddy, “An improved multiple minimum support based approach to mine rare association rules,” in 2009 IEEE Int. Conf. Communications Computational Intelligence and Data Mining, pp. 340- 347.
[13] R. U. Kiran, P. K. Reddy , “An Improved Frequent Pattern growth Approach To Discover Rare Association rules,” in 2009 International Conf. on Knowledge Discovery and Information Retrieval, pp. 43-52.
[14] S. Tsang, Y. S. Koh and G. Dobbie, “Finding Interesting Rare Association Rules Using Rare Pattern Tree,” The University of Auckland, Springer-Verlag Berlin Heidelberg,2013.
[15] J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, M. Hsu, , “Mining sequential patterns by pattern-growth: the prefixspan approach,” IEEE Trans. Knowledge and Data Engineering 16, 1424– 1440, 2004.
[16] R. Srikant, Q. Vu, and R. Agrawal, “Mining association rules with item constraints,” KDD-97, pp. 67-73, 1997.
[17] Y. Hu, F. Wu, Y. Liao, “Sequential pattern mining with multiple minimum supports: a tree based approach”, in 2010, The 2nd International Conf. on Software Engineering and Data Mining, Chengdu, China.
[18] J. Pie, J. Han, and L. Lakshmanan., “Mining frequent itemsets with convertible constraints”, in 2001 IEEE ICDE Conf., p.433– 442.
[19] M. S. Saravanan, R.J. Rama, “Performance study of Association Rule Mining Algorithms for Dyeing Processing System Innovative Systems Design and Engineering”, Vol 2, No 5, 2011.
[20] http://www.cs.waikato.ac.nz/ml/weka , Last acess : 6 march 2015
[21] M. Walaa, H. Ahmed and K. Hoda, “Combined Algorithm for Data Mining using Association rules,” Ain Shams of Electrical Engineering J., Vol. 1.No. 1 ISSN: 1687-8582, 2008.
[22] P. Jyothi, V. D. Mytri, “A Fast association rule algorithm based on bitmap computing with multiple minimum supports using max constraints,” International of Comp. Sci & Electronics J.,Volume1,Issue 2, IJCSEE,2013.
[23] F.A. Hoque , N. Easmin and K. Rashed, “ Frequent pattern mining for multiple minimum supports with support tuning and tree maintenance on incremental database,” Research of Information Technology J., 3(2): 79- 90 ,2012.