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

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. 

• Elsayeda M. Elgaml
• Dina M. Ibrahim
• Elsayed A. Sallam

• Association Rules
• FP-growth
• Multiple minimum supports
• Weka Tool

[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.