Mining High Utility Pattern in One Phase without Candidate Generation using up Growth+ Algorithm

Mining High Utility Pattern in One Phase without Candidate Generation using up Growth+ Algorithm

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
  
© 2017 by IJETT Journal
Volume-45 Number-4
Year of Publication : 2017
Authors : P.Sri Varshini, N.Saranya.N, Uma Maheswari, Prof.R.Sujatha
DOI :  10.14445/22315381/IJETT-V45P239

Citation 

P.Sri Varshini, N.Saranya.N, Uma Maheswari, Prof.R.Sujatha "Mining High Utility Pattern in One Phase without Candidate Generation using up Growth+ Algorithm", International Journal of Engineering Trends and Technology (IJETT), V45(4),183-189 March 2017. ISSN:2231-5381. www.ijettjournal.org. published by seventh sense research group

Abstract
Utility mining developed to address the limitation of frequent itemset mining by introducing interestingness measures that satisfies both the statistical significance and the user’s expectation. Existing high utility itemsets mining algorithms two steps: first, generate a large number of candidate itemsets and second, identify high utility itemsets from the candidates by an additional scan of the original transaction database. The performance holdup of these algorithms is the generate more no of candidates itemsets and increasing of the number of long transaction itemsets it cannot work minimum utility threshold, the situation may become worse and also creating more no tree. To overcome these problems, propose an efficient algorithm, namely UP-Growth (Utility Pattern Growth), for mining high utility itemsets with pruning techniques for pruning candidate itemsets. The information of high utility itemsets is stored in a special data structure named UP-Tree (Utility Pattern Tree) such that the candidate itemsets can be generated with only two scans of the database. The performance of UP growth+ was evaluated in comparison with the state-of-the-art algorithms on different types of datasets. The experimental results show that UP growth+ outperforms other algorithms in terms of both execution time and memory space under minimum utility threshold is, the more observable its advantage will be it can achieve the level of about two orders of magnitude faster than the state-of-theart algorithms on dense dataset, and more than one order of magnitude on sparse datasets.

 References

[1] R.Agrawal, T. Imielinski, and A. Swami, “Mining association rules between sets of items in large databases,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 1993, pp. 207– 216.
[2] C. F. Ahmed, S. K. Tanbeer, B.-S. Jeong, and Y.-K. Lee, “Efficient tree structures for high utility pattern mining in incremental databases,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 12, pp. 1708– 1721, Dec. 2009.
[3] F. Bonchi, F. Giannotti, A. Mazzanti, and D. Pedreschi, “ExAnte: A preprocessing method for frequent-pattern mining,” IEEE Intell. Syst., vol. 20, no. 3, pp. 25–31, May/Jun. 2005.
[4] C. Bucila, J. Gehrke, D. Kifer, and W. M. White, “Dualminer: A dual-pruning algorithm for itemsetswith constraints,” DataMining Knowl. Discovery, vol. 7, no. 3, pp. 241–272, 2003.
[5] R. Chan, Q. Yang, and Y. Shen, “Mining high utility itemsets,” in Proc. Int. Conf. Data Mining, 2003, pp. 19–26.
[6] S. Dawar and V. Goyal, “UP-Hist tree: An efficient data structure for mining high utility patterns from transaction databases,” in Proc. 19th Int. Database Eng. Appl. Symp., 2015, pp. 56–61.
[7] P. Fournier-Viger, C.-W. Wu, S. Zida, and V. S. Tseng, “FHM: Faster high-utility itemset mining using estimated utility cooccurrence pruning,” in Proc. 21st Int. Symp. Found. Intell. Syst., 2014, pp. 83–92.
[8] S. Krishnamoorthy, “Pruning strategies for mining high utility itemsets,” Expert Syst. Appl., vol. 42, no. 5, pp. 2371–2381, 2015.
[9] Y.-C. Li, J.-S.Yeh, and C.-C. Chang, “Isolated items discarding strategy for discovering high utility itemsets,” Data Knowl.Eng., vol. 64, no. 1, pp. 198–217, 2008.
[10] M. Liu and J. Qu, “Mining high utility itemsets without candidate generation,” in Proc. ACMConf. Inf. Knowl.Manage., 2012, pp. 55–64.
[11] Y. Shen, Q. Yang, and Z. Zhang, “Objective-oriented utilitybased association mining,” in Proc. IEEE Int. Conf. Data Mining, 2002, pp. 426–433.
[12] U. Yun, H. Ryang, and K. H. Ryu, “High utility itemsetmining with techniques for reducing overestimated utilities and pruning candidates,” Expert Syst. Appl., vol. 41, no. 8, pp. 3861–3878, 2014.

Keywords
Utility Pattern Growth, UP Tree, High Utility mining, reducing search space, Pruning.