Skip to main content
SpringerLink
Log in

Efficient Algorithms for High Utility Itemset Mining Without Candidate Generation

  • Chapter
  • First Online:
High-Utility Pattern Mining

Part of the book series: Studies in Big Data ((SBD,volume 51))

Abstract

High utility itemsets are sets of items having a high utility or profit in a database. Efficiently discovering high utility itemsets plays a crucial role in real-life applications such as market analysis. Traditional high utility itemset mining algorithms generate candidate itemsets and subsequently compute the exact utilities of these candidates. These algorithms have the drawback of generating numerous candidates most of which are discarded for having a low utility. In this paper, we propose two algorithms, called HUI-Miner (High Utility Itemset Miner) and HUI-Miner*, for high utility itemset mining. HUI-Miner uses a novel utility-list structure to store both utility information about itemsets and heuristic information for search space pruning. The utility-list of items allows to directly derives the utility-lists of other itemsets and calculate their utilities without scanning the database. By avoiding candidate generation, HUI-Miner can efficiently mine high utility itemsets. To further speed up the construction of utility-lists, HUI-Miner* introduces an improved structure called utility-list* and an horizontal method to construct utility-lists*. Experimental results show that the proposed algorithms are several orders of magnitude faster than the state-of-the-art algorithms, reduce memory consumption, and that HUI-Miner* outperforms HUI-Miner especially for sparse databases.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    This is an extension of the conference paper “Mining high utility itemsets without candidate generation” published in the proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM 2012).

References

  1. Ceglar, A., Roddick, J.F.: Association mining. ACM Comput. Surv. 38(2), 55–86 (2006)

    Article  Google Scholar 

  2. Han, J., Cheng, H., Xin, D., Yan, X.: Frequent pattern mining: current status and future directions. Data Min. Knowl. Discov. 15(1), 55–86 (2007)

    Article  MathSciNet  Google Scholar 

  3. Fournier-Viger, P., Lin, J.C.-W., Vo, B., Chi, T.T., Zhang, J., Le, H.B.: A survey of itemset mining. WIREs Data Min. Knowl. Discov., e1207 (2017). Wiley. https://doi.org/10.1002/widm.1207

    Google Scholar 

  4. Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: Proceedings of the International Conference on Very Large Data Bases (VLDB), pp. 487–499 (1994)

    Google Scholar 

  5. Yao, H., Hamilton, H.J., Butz, C.J.: A foundational approach to mining itemset utilities from databases. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp. 482–486 (2004)

    Google Scholar 

  6. Liu, Y., Liao, W.-K., Choudhary, A.N.: A two-phase algorithm for fast discovery of high utility itemsets. In: Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp. 689–695 (2005)

    Chapter  Google Scholar 

  7. Li, Y.-C., Yeh, J.-S., Chang, C.-C.: Isolated items discarding strategy for discovering high utility itemsets. Data Knowl. Eng. 64(1), 198–217 (2008)

    Article  Google Scholar 

  8. Ahmed, C.F., Tanbeer, S.K., Jeong, B.-S., Lee, Y.-K.: Efficient tree structures for high utility pattern mining in incremental databases. IEEE Trans. Knowl. Data Eng. 21(12), 1708–1721 (2009)

    Article  Google Scholar 

  9. Tseng, V.S., Wu, C.-W., Shie, B.-E., Yu, P.S.: UP-Growth: an efficient algorithm for high utility itemset mining. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 253–262 (2010)

    Google Scholar 

  10. Tseng, V.S., Shie, B.-E., Wu, C.-W., Yu, P.S.: Efficient algorithms for mining high utility itemsets from transactional databases. IEEE Trans. Knowl. Data Eng. 25(8), 1772–1786 (2013)

    Article  Google Scholar 

  11. Liu, M., Qu, J.: Mining high utility itemsets without candidate generation. In: Proceedings of the ACM 21st International Conference on Information and Knowledge Management (CIKM), pp. 55–64 (2012)

    Google Scholar 

  12. Rymon, R.: Search through systematic set enumeration. In: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, pp. 539–550 (1992)

    Google Scholar 

  13. Barber, B., Hamilton, H.J.: Extracting share frequent itemsets with infrequent subsets. Data Min. Knowl. Discov. 7(2), 153–185 (2003)

    Article  MathSciNet  Google Scholar 

  14. Li, Y.-C., Yeh, J.-S., Chang, C.-C.: A fast algorithm for mining share-frequent itemsets. In: Proceedings Asia-Pacific Web Conference (APWeb), pp. 417–428 (2005)

    Chapter  Google Scholar 

  15. Li, Y.-C., Yeh, J.-S., Chang, C.-C.: Efficient algorithms for mining share-frequent itemsets. In: Proceedings of the 11th World Congress of International Fuzzy Systems Association, pp. 534–539 (2005)

    Google Scholar 

  16. Li, Y.-C., Yeh, J.-S., Chang, C.-C.: Direct candidates generation: a novel algorithm for discovering complete share-frequent itemsets. In: Proceedings of the Fuzzy Systems and Knowledge Discovery, pp. 551–560 (2005)

    Chapter  Google Scholar 

  17. Liu, Y., Liao, W.-K., Choudhary, A.: A fast high utility itemsets mining algorithm. In: Proceedings of the Utility-Based Data Mining Workshop (UBDM), pp. 90–99 (2005)

    Google Scholar 

  18. Han, J., Pei, J., Yin, Y., Mao, R.: Mining frequent patterns without candidate generation: a frequent-pattern tree approach*. Data Min. Knowl. Discov. 8(1), 53–87 (2004)

    Article  MathSciNet  Google Scholar 

  19. Hu, J., Mojsilovic, A.: High-utility pattern mining: a method for discovery of high-utility item sets. Pattern Recognit. 40(11), 3317–3324 (2007)

    Article  Google Scholar 

  20. Wu, C.W., Fournier-Viger, P., Yu, P., Tseng, V.: Efficient mining of a concise and lossless representation of high utility itemsets. In: Procedings of the IEEE International Conference Data Mining (ICDM), pp. 824–833 (2011)

    Google Scholar 

  21. Soulet, A., Crémilleux, B.: Adequate condensed representations of patterns. Data Min. Knowl. Discov. 17, 94–110 (2008)

    Article  MathSciNet  Google Scholar 

  22. Soulet, A., Raïssi, C., Plantevit, M., Crémilleux, B.: Mining dominant patterns in the sky. In: Proceedings of the IEEE International Conference on Data Mining (ICDM), pp. 655–664 (2011)

    Google Scholar 

  23. Wu, C.W., Shie, B.-E., Tseng, V.S., Yu, P.S.: Mining top-k high utility itemsets. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 78–86 (2012)

    Google Scholar 

  24. Zaki, M.J.: Scalable algorithms for association mining. IEEE Trans. Knowl. Data Eng. 12(3), 372–390 (2000)

    Article  Google Scholar 

  25. KDD Cup Center (2012). http://www.sigkdd.org/kddcup/index.php?section =2000&method=data

  26. Zheng, Z., Kohavi, R., Mason, L.: Real world performance of association rule algorithms. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 401–406 (2001)

    Google Scholar 

  27. Pisharath, J., Liu, Y., et al.: NU-Minebench: a data mining benchmark suite (2012)

    Google Scholar 

  28. Frequent itemset mining dataset repository (2012). http://fimi.ua.ac.be/

  29. Armour Brown, C., Armour-Brown, C., et al.: Valgrind: a GPL’d system for debugging and profiling linux programs (2012). http://valgrind.org/

  30. Palmerini, P.: Paolo Palmerini’s Website (2012). http://miles.cnuce.cnr.it/~palmeri/datam/DCI/datasets.php

  31. Liu, G., Lu, H., Lou, W., Xu, Y., Yu, J.X.: Efficient mining of frequent patterns using ascending frequency ordered prefix-tree. Data Min. Knowl. Discov. 9(3), 249–274 (2004)

    Article  MathSciNet  Google Scholar 

  32. Liu, G., Lu, H., Yu, J.X., Wang, W., Xiao, X.: AFOPT: an efficient implementation of pattern growth approach. In: Proceedings of the IEEE International Conference on Data Mining Workshop Frequent Itemset Mining Implementations (ICDM FIMI) (2003)

    Google Scholar 

  33. Fournier-Viger, P., Wu, C.-W., Zida, S., Tseng, V.S.: FHM: faster high-utility itemset mining using estimated utility co-occurrence pruning. In: Proceedings of the 21st International Symposium on Methodologies for Intelligent Systems (ISMIS 2014), pp. 83–92. Springer, LNAI (2014)

    Google Scholar 

  34. Krishnamoorthy, S.: Pruning strategies for mining high utility itemsets. Expert Syst. Appl. 42(5), 2371–2381 (2015)

    Article  Google Scholar 

  35. Krishnamoorthy, S.: HMiner: efficiently mining high utility itemsets. Expert Syst. Appl. 90, 168–183 (2017)

    Article  Google Scholar 

  36. Duong, Q.-H., Liao, B., Fournier-Viger, P., Dam, T.-L.: An efficient algorithm for mining the top-k high utility itemsets, using novel threshold raising and pruning strategies. Knowl. Based Syst. 104, 106–122 (2016)

    Article  Google Scholar 

  37. Lin, J.C.-W., Gan, W., Fournier-Viger, P., Hong, T.-P., Tseng, V.S.: Efficiently mining uncertain high-utility itemsets. Soft Comput. 21, 2801–2820 (2016)

    Article  Google Scholar 

  38. Lin., J.C.W., Gan, W., Fournier-Viger, P., Tseng, V.S.: Efficient algorithms for mining high-utility itemsets in uncertain databases. Knowl. Based Syst. (KBS) 96, 171–187 (2016)

    Article  Google Scholar 

  39. Krishnamoorthy, S.: Efficient mining of high utility itemsets with multiple minimum utility thresholds. Eng. Appl. AI 69, 112–126 (2018)

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported by Natural Science Foundation of HuBei Province of China (Grant No. 2017CFB723).

Author information

Authors and Affiliations

  1. School of Computer Engineering, Hubei University of Arts and Science, Xiangyang, 441053, China

    Jun-Feng Qu

  2. School of Computer Science, Carleton University, Ottawa, ON, K1S 5B6, Canada

    Mengchi Liu

  3. School of Humanities and Social Sciences, Harbin Institute of Technology (Shenzhen), Shenzhen, 518055, China

    Philippe Fournier-Viger

Authors
  1. Jun-Feng Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mengchi Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Philippe Fournier-Viger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jun-Feng Qu .

Editor information

Editors and Affiliations

  1. Harbin Institute of Technology (Shenzhen), Shenzhen, China

    Philippe Fournier-Viger

  2. Western Norway University of Applied Sciences, Bergen, Norway

    Jerry Chun-Wei Lin

  3. Université du Québec à Montréal, Montreal, QC, Canada

    Roger Nkambou

  4. Ho Chi Minh City University of Technology, Ho Chi Minh City, Vietnam

    Bay Vo

  5. National Chiao Tung University, Hsinchu, Taiwan

    Vincent S. Tseng

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Qu, JF., Liu, M., Fournier-Viger, P. (2019). Efficient Algorithms for High Utility Itemset Mining Without Candidate Generation. In: Fournier-Viger, P., Lin, JW., Nkambou, R., Vo, B., Tseng, V. (eds) High-Utility Pattern Mining. Studies in Big Data, vol 51. Springer, Cham. https://doi.org/10.1007/978-3-030-04921-8_5

Download citation

Publish with us

Policies and ethics

Search

Navigation