The International Arab Journal of Information Technology (IAJIT)

..............................
..............................
..............................


An Efficient Approach for Mining Frequent Item

Deletion of transactions in databases is common in real-world applications. Developing an efficient and effective mining algorithm to maintain discovered information is thus quite important in data mining fields. A lot of algorithms have been proposed in recent years, and the best of them is the pre-large-tree-based algorithm. However, this algorithm only rebuilds the final pre-large tree every deleted transactions. After that, the FP-growth algorithm is applied for mining all frequent item sets. The pre-large-tree-based approach requires twice the computation time needed for a single procedure. In this paper, we present an incremental mining algorithm to solve above issues. An itemset tidset-tree structure will be used to maintain large and pre-large item sets. The proposed algorithm only processes deleted transactions for updating some nodes in this tree, and all frequent item sets are directly derived from the tree traversal process. Experimental results show that the proposed algorithm has good performance.


[1] Agrawal R. and Srikant R., Fast Algorithm for Mining Association Rules, In VLDB 94 Proceedings of the 20th International Conference on Very Large Data Bases, Santiago de Chile, Chile, pp. 487-499, 1994.

[2] Bodon F. and Ronyai L., Trie: An Alternative Data Structure for Data Mining Algorithms, Mathematical and Computer Modelling, vol. 38, no. 7, pp. 739-751, 2003.

[3] Cheung D., Han J., Ng V., and Wong C., Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Approach, in Proceedings of the 12th IEEE International Conference on Data Engineering, New Orleans, USA, pp. 106-114, 1996.

[4] Han J., Pei J., and Yin Y., Mining Frequent Patterns without Candidate Generation, in Proceedings of ACM SIGMOD International Conference on Management of Data, Dallas, Taxas, USA, pp. 1-12, 2000.

[5] Hong T., Wang C., and Tao Y., A New Incremental Data Mining Algorithm using Pre- Large Itemsets, Intelligent Data Analysis, vol. 5, no. 2, pp. 111-129, 2001.

[6] Hong T., Lin C., and Wu Y., Incrementally Fast Updated Frequent Pattern Trees, Expert Systems with Applications, vol. 34, no. 4, pp. 2424-2435, 2008.

[7] Hong T., Lin C., and Wu Y., Maintenance of Fast Updated Frequent Pattern Trees for Record Deletion, Computational Statistics and Data Analysis, vol. 53, no. 7, pp. 2485-2499, 2009.

[8] Hong T. and Wang C., An Efficient and Effective Association-Rule Maintenance Algorithm for Record Modification, Expert Systems with Applications, vol. 37, no. 1, pp. 618-626, 2010.

[9] Hong T., Wang C., and Tseng S., An Incremental Mining Algorithm for Maintaining Sequential Patterns using Pre-Large Sequences, Expert Systems with Applications, vol. 53, no. 6, pp. 7051-7058, 2011.

[10] Koh J. and Shied S., An Efficient Approach for Maintaining Association Rules based on Adjusting FP-Tree Structures, available at: http://www.csie.ntnu.edu.tw/~jlkoh/publications/ dasfaa04.pdf, last visited 2004.

[11] Le T., Hong T., Vo B., Le B., and Hwang D., Improving Efficiency of Incremental Mining by Trie Structure and Pre-Large Itemsets, Computing and Informatics, vol. 33, no. 3, pp. 609-632, 2014.

[12] Le T., Vo B., Hong T., and Le B., An Efficient Incremental Mining Approach based on IT- An Efficient Approach for Mining Frequent Item sets with Transaction Deletion Operation 601 Tree, in Proceedings of tIEEE International Conference on Computing and Communication Technologies, Research, Innovation, and Vision for the Future, Ho Chi Minh, VietNam, pp. 57- 61, 2012.

[13] Lin X., Deng Z., and Tang S., A Fast Algorithm for Maintenance of Associations Rules in Incremental Databases, in Proceedings of the 2nd International Conference on Advanced Data Mining and Applications, XiAn, China, pp. 56- 63, 2006.

[14] Lin C., Hong T., and Lu W., Maintenance of the Prelarge Trees for Record Deletion, in Proceedings of the 12th WSEAS International Conference on Applied Mathematics, Stevens Point, Wisconsin, USA, pp. 105-110, 2007

[15] Lin C., Hong T., and Lu W., The Pre-FUFP Algorithm for Incremental Mining, Expert Systems with Applications, vol. 36, no. 5, pp. 9498-9505, 2009.

[16] Srikant R. and Agrawal R., Mining Generalized Association Rules, available at: http://www.vldb.org/conf/1995/P407.PDF, last visited 1995.

[17] Senhadji S., Khiat S., and Belbachir H., Association Rule Mining and Load Balancing Strategy in Grid Systems, The International Arab Journal of Information Technology, vol. 11, no. 4, pp. 338-344, 2014.

[18] Srikant R. and Agrawal R., Mining Quantitative Association Rules in Large Relational Tables, in Proceedings of ACM SIGMOD International Conference on Management of Data, New York, USA, pp. 1-12, 1996.

[19] Thomas S., Bodagala S., Alsabti K., and Ranka S., An Efficient Algorithm for the Incremental Updation of Association Rules in Large Databases, available at: https://www.aaai.org/ Papers/KDD/1997/KDD97-055.pdf, last visited 1997.

[20] Toivonen H., Sampling Large Databases for Association Rules, available at: http://www.vldb.org/conf/1996/P134.PDF, last visited 1996.

[21] Vo B., Hong T., and Le B., DBV-Miner: A Dynamic Bit-Vector Approach for Fast Mining Frequent Closed Item Sets, Expert Systems with Applications, vol. 39, no. 8, pp. 7196-7206, 2012

[22] Zaki M., Scalable Algorithms for Association Mining, IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 3, pp. 372-390, 2000. Bay Vo received his PhD degrees in Computer Science from the University of Science, Vietnam National University of Ho Chi Minh, Vietnam in 2011. His research interests include association rules, classification, mining in incremental database, distributed databases and privacy preserving in data mining. Thien-Phuong Le received his MSc degrees in Information System from the University of Science, Vietnam National University of Ho Chi Minh, Vietnam in 2011. His research interests include association rules, clustering, classification, mining in incremental databases. Tzung-Pei Hong received his PhD degree in computer science and information engineering from National Chiao-Tung University in 1992. He served as the first director of the library and computer center, the Dean of Academic Affairs and the Vice President in National University of Kaohsiung. He is currently a distinguished professor at the Department of Computer Science and Information Engineering in NUK. He has published more than 400 research papers in international/national journals and conferences and has planned more than fifty information systems. He is also the board member of more than thirty journals and the program committee member of more than two hundreds conferences. His current research interests include parallel processing, machine learning, data mining, soft computing, management information systems and www applications. Bac Le received the BSc degree, in 1984, the MSc degree, in 1990, and the PhD degree in Computer Science, in 1999. He is an Associate Professor, Vice Dean of Faculty of Information Technology, Head of Department of Computer Science, University of Science, Ho Chi Minh City. His research interests are in artificial intelligent, soft computing, and knowledge discovery and data mining. 602 The International Arab Journal of Information Technology, Vol. 13, No. 5, September 2016 Jason Jung is an associate professor of Computer Engineering Department at Chung-Ang University, Korea. He was a postdoctoral researcher in INRIA Rhone-Alpes, France in 2006, and a visiting scientist in Fraunhofer Institute (FIRST) in Berlin, Germany in 2004. He received the B.Eng. in Computer Science and Mechanical Engineering from Inha University in 1999. He received M.S. and Ph.D. degrees in Computer and Information Engineering from Inha University in 2002 and 2005, respectively. His research topics are knowledge engineering on social networks by using machine learning, semantic Web mining, and ambient intelligence. He has about 25 international journal articles published in Knowledge-Based Systems, Information Retrieval, Information Processing & Management, Knowledge and Information Systems, and Expert Systems with Applications. Also, he is an editorial member of Journal of Universal Computer Science and International Journal of Intelligent Information and Database Systems. Moreover, he has been editing 10 special issues in Information Sciences, Journal of Network and Computer Applications, Computing and Informatics and so on.