The International Arab Journal of Information Technology (IAJIT)

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


Effective and Efficient Utility Mining Technique for

Traditional association rule mining, which is based on frequency values of items, cannot meet the demands of different factors in real world applications. Thus utility mining is presented to consider additional measures, such as profit or price according to user preference. Although several algorithms were proposed for mining high utility itemsets, they incur the problem of producing large number of candidate itemsets, results in performance degradation in terms of execution time and space requirement. On the other hand when the data come intermittently, the incremental and interactive data mining approach needs to be processed to reduce unnecessary calculations by using previous data structures and mining results. In this paper, an incremental mining algorithm for efficiently mining high utility itemsets is proposed to handle the above situation. It is based on the concept of Utility Pattern Growth (UP-Growth) for mining high utility itemsets with a set of effective strategies for pruning candidate itemsets and Fast Update (FUP) approach, which first partitions itemsets into four parts according to whether they are high-transaction weighted utilization items in the original and newly inserted transactions. Experimental results show that the proposed Fast Update Utility Pattern Tree (FUUP) approach can thus achieve a good trade between execution time and tree complexity.


[1] Agrawal R., Imielinksi T., and Swami A., Mining Association Rules Between Sets of Items in Large Database, in Proceedings of ACM International Conference on Management of Data, Washington, pp. 207-216, 1993.

[2] Agrawal R. and Srikant R., Fast Algorithm for Mining Association Rules, in Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, pp. 487-499, 1994.

[3] Agrawal R., Srikant R., and Vu Q., Mining Association Rules with Item Constraints, in Proceedings of The Third International Conference on Knowledge Discovery in Databases and Data Mining, New Port Beach, pp. 67-73, 1997

[4] Ahmed C., Tanbeer S., Jeong B., and Lee Y., Efficient tree Structures for High Utility Pattern Mining in Incremental Databases, IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 12, pp. 1708-1721, 2009.

[5] Chan R., Yang Q., and Shen Y., Mining High Utility Itemsets, in Proceedings of The 3rd IEEE International Conference on Data Mining, Melbourne, pp. 19-26,2003.

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

[7] Cheung D., Lee S., and Kao B., A General Incremental Technique for Maintaining Discovered Association Rules, in Proceedings of the 5th International Conference on Database System for Advanced Applications, Melbourn, pp. 185-194, 1997.

[8] Das A. and Bhattacharyya D., Rule Mining for Dynamic Databases, Australasian Journal of Information Systems, vol. 13, no. 1, Kolkata, pp. 19-39, 2004.

[9] Erwin A., Gopalan R., and Achuthan N., Efficient mining of High Utility Itemises from Large Datasets, in Proceedings of Advances in Knowledge Discovery and Data Mining, Osaka, pp. 554-561, 2008

[10] Ezeife C. and Su Y., Mining Incremental Association Rules with Generalized FP Tree, in Proceedings of 15th Canadian Conference on Artificial Intelligence, Calgary, pp. 147-160, 2002.

[11] Feldman R., Aumann Y., Manilla H., and Lipshtat O., Borders: An Efficient Algorithm for Association Generation in Dynamic Databases, Journal of Intelligent Information System, vol. 12, no. 1, pp. 61-73, 1999.

[12] Fukuda T., Morimoto Y., Morishita S., and Tokuyama T., Mining Optimized Association Rules for Numeric Attributes, in Proceedings of the 5th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Montreal, pp. 182-191, 1996.

[13] Han J. and Fu Y., Discovery of Multiple-level Association Rules from Large Database, in Proceedings of the 21th International Conference on Very Large Data Bases, San Francisco, pp. 420-431, 1995.

[14] Han J., Pei J., Yin Y., and Mao R., Mining Frequent Patterns without Candidate Generation: a Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, vol. 8, no. 1, pp 53-87, 2004.

[15] 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. 166 The International Arab Journal of Information Technology, Vol. 15, No. 1, January 2018

[16] IBM Quest Data Mining Project, Quest Synthetic Data Generation Code, http://www.almaden. ibm.com/cs/quest/syndata.html, Last visited 2012

[17] Li Y., Yeh J., and Chang C., Isolated Items Discarding Strategy for Discovering High Utility Itemsets, Data and Knowledge Engineering, vol. 64, no 1, pp. 198-217, 2008.

[18] Lin C., Hsieh Y., Yin K., Hung M., and Yang D., ADMiner: An Incremental Data Mining Approach Using a Compressed FP-Tree, Journal Of Software, vol. 8, no. 8, pp. 2095-2103, 2013.

[19] Liu Y., Liao W., and Choudhary A., A Fast High Utility Itemsets Mining Algorithm, in Proceedings of the 1st international Workshop on Utility-Based Data Mining, Chicago, pp. 90-99, 2005.

[20] Liu Y., Liao W., and Choudhary A., A Two Phase Algorithm for Fast Discovery of High Utility of Itemsets, in Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Hanoi pp. 689-695, 2005.

[21] Mannila H., Toivonen H., and Verkamo A., Efficient Algorithm for Discovering Association Rules, Technical Report AAAI, 1994.

[22] Park J., Chen M., and Yu P., Using a Hash- Based Method with Transaction Trimming for Mining Association Rules, IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 5, pp. 813-825, 1997.

[23] Srikant R. and Agrawal R., Mining Generalized Association Rules, in Proceedings of The Twenty-first International Conference on Very Large Data Bases, San Francisco, pp. 407-419, 1995.

[24] Srikant R. and Agrawal R., Mining Quantitative Association Rules in large Relational Tables, in Proceedings of ACM SIGMOD International Conference on Management of Data, Montreal, pp. 1-12, 1996.

[25] Shie B., Tseng V., and Yu P., Online Mining of Temporal Maximal Utility Itemsets from Data Streams, in Proceedings of the 2010 ACM Symposium on Applied Computing, Switzerland, pp. 1622-1626, 2010.

[26] Tseng V., Chu C., and Liang T., Efficient Mining of Temporal High Utility Itemsets from Data Streams, in Proceedings of Workshop on Utility-Based Data Mining Workshop, pp.18-27, Philadelphia, 2006.

[27] Tseng V., Wu C., Shie B., and Yu P., UP- Growth: An Efficient Algorithm for High Utility Itemsets Mining, in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, pp. 253-262, 2010.

[28] Yafi E., Al-Hegami A., Alam A., and Biswas R., YAMI: Incremental Mining of Interesting Association Patterns, International Arab Journal of Information technology, vol. 9, no. 6, pp.504-510, 2012.

[29] Yao H., Hamilton H., and Butz C., A Foundational Approach to Mining Itemset Utilities from Databases, in Proceedings of 4th SIAM International Conference on data Mining, florida, pp. 211-225, 2004.

[30] Yao H. and Hamilton H., Mining Itemset Utilities from Transaction Databases, Data and Knowledge Engineering, vol. 59, no. 3, pp.603- 626, 2006. Kavitha JeyaKumar, Assistant Professor. She received the M.Tech. Degree from the Department of Computer Science and Engineering at Anna University, Chennai, in 2009. She is now a Ph.D. candidate in the Department of Computer Science and Engineering at Anna University, Chennai. Her research interests include Data mining, Image Processing, Cloud Computing. Manjula Dhanabalachandran, Associate Professor. She received her B.E Electronics and Communications Engineering degree in 1983 from Thiagarajar College of Engineering, Madurai and M.E Computer Science and Engineering in 1987 and Ph.D (Computer Science and Engineering) in 2004 from Anna University Chennai. Her research interests include Data mining, Image Processing, Cloud Computing, Network security. Kasthuri JeyaKumar, Assistant Professor. She received the M.E. degree from the Department of Electronics and Communication Engineering at SRM University, Chennai, in 2008. She is now a Ph. D. candidate in the Department of Electronics and Communication Engineering at SRM University, Chennai. Her research interests include Data mining, Image Processing, VLSI.