Efficient Mining of Frequent Itemsets using Improved FP-Growth Algorithm
Abdulkader M Al-Badani and Basheer M Al-Maqaleh. Efficient Mining of Frequent Itemsets using Improved FP-Growth Algorithm. International Journal of Applied Information Systems 12(14):15-20, July 2018. URL, DOI BibTeX
@article{10.5120/ijais2018451766, author = "Abdulkader M. Al-Badani and Basheer M. Al-Maqaleh", title = "Efficient Mining of Frequent Itemsets using Improved FP-Growth Algorithm", journal = "International Journal of Applied Information Systems", issue_date = "July 2018", volume = 12, number = 14, month = "July", year = 2018, issn = "2249-0868", pages = "15-20", url = "http://www.ijais.org/archives/volume12/number14/1036-2018451766", doi = "10.5120/ijais2018451766", publisher = "Foundation of Computer Science (FCS), NY, USA", address = "New York, USA" }
Abstract
Frequent itemsets are itemsets that appear frequently in a dataset. Finding frequent itemsets plays an important role in association rules mining, correlations, and many other interesting relationships among data. Frequent itemset mining has been an active research area and a large number of algorithms have been developed. FP- Growth algorithm is currently one of the best approaches to frequent itemsets mining. It constructs a tree structure from transaction dataset and recursively traverse this tree to extract frequent itemsets in a depth first search manner. Also, it takes time to build an FP-tree, suffers from the increasing size of FP-tree and generating large number of frequent itemsets. In this paper, an improved frequent itemsets mining algorithm based on FP-Growth algorithm is proposed. The proposed algorithm uses a two dimensional array structure called Ordered Frequent Itemsets Matrix (OFIM) to construct a highly compact FP-tree. It greatly circumvents repeated scanning of datasets and it reduces the computational time, and reduces the number of frequent items that are generated obtaining significantly improved performance for FP-tree based algorithms.
Reference
- Han, J., Pei, J., and Kamber, M. 2011. Data Mining: Concepts and Techniques. Morgan Kaufmann, San Francisco, California, USA.
- Shridhar, M., and Parmar, M. 2017. Survey on association rule mining and its approaches.? International Journal of Computer Sciences and Engineering (IJCSE), 5(3), pp.129-135.
- Agrawal, R., and Srikant, R. 1994. Fast algorithms for mining association rules. In Proceeding of 20th International Conference on Very Large Databases (VLDB), pp. 487-499.?
- Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation. ACM. pp, 1-12.
- Wei, F., and Xiang, L. 2015. Improved frequent pattern mining algorithm based on FP-Tree. In Proceedings of The Fourth International Conference on Information Science and Cloud Computing (ISCC2015), pp.18-19.
- Krupali, R., Garg, D., and Kotecha, K. 2017. An improved approach of FP-Growth tree for frequent itemset mining using partition projection and parallel projection techniques. International Recent and Innovation Trends in Computing and Communication, 5(5), pp. 929-934.
- Khanali, H., and Vaziri, B. (2017). A survey on improved algorithms for mining association rules. International Journal of Computer Applications(IJCA), 165(9), pp. 6-11.
- Gruca, A. 2014. Improvement of FP-Growth algorithm for mining description-oriented rules. In Man-Machine Interactions, Part of Advances in Intelligent Systems and Computing, (AISC), Springer, vol. 242, pp. 183-192.
- Sohrabi, M. K., and Marzooni, H. H. 2016. Association rule mining using new FP-Linked list algorithm. Journal of Advances in Computer Research (JACR), 7(1), pp. 23-34.?
- Dange, A. S., and Patil, S. J. 2016. A combined approach of frequent pattern growth and decision tree for infrequent weighted itemset mining.? International Research Journal of Engineering and Technology ( IRJET), 3(7), pp. 2070- 2075.
- Sagar, B. P., and Kale, S. 2017. Efficient algorithms to find frequent itemsets using data mining. International Research Journal of Engineering and Technology ( IRJET), 4(6), pp. 2645- 2648.
- Hao, J., and Xu, H. 2017. An improved algorithm for frequent itemsets mining. In 5th International Conference on Advanced Cloud and Big Data (CBD), IEEE Computer Society , pp. 314-317?.
- Devi, R. S., and Shanthi, D. 2016. A new hybrid frequent Pattern-Apriori (FP-AP) algorithm for high utility item set mining. Middle East Journal of Scientific Research (MEJSR), 24(3), pp. 986-991.
- Princy. S, Ankita, H., Babita, P., and Shiv, K. 2017. A survey on FP (Growth) tree using association rule mining. International Research Journal of Engineering and Technology( IRJET), vol. 4, Issue 7, pp. 1637-1640.
- Jiten, G., Ashish, P., Swapnit, M., and Christi, L. 2017. Compressed frequent pattern tree. International Journal of Engineering Sciences and Research Technology ( IJESRT), 6(4), pp. 652-657.
- Saxena, P. and Jain, R. 2016. An improved FP-Tree algorithm with relationship technique for refined result of association rule mining.? International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), vol. 2, pp. 525-529.
- Usman, A., Zhang, P., and Theel, O. 2017. An efficient and updatable item-to-item frequency matrix for frequent itemset generation. ICC'17, Cambridge, United Kingdom, ACM, pp. 978 -983.
- Blake, C. L., and Merz., M. J, UCI Repository of Machine Learning Databases [http://www. ics. uci. edu/~ mlearn/ MLRepository. html]. Irvine, CA: University of California?, Department of Information and Computer Science.
Keywords
FP-Growth Algorithm, Aprioiri Algorithm, FP-tree, Support Count, Ordered Frequent Itemset Matrix