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

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