Abstract
In high-utility itemset mining (HUIM), the utility of a set of items is calculated as the sum of the utilities of the individual items. In this paper, we describe scenarios where utility may be less than this sum for multi-item itemsets. To overcome the limitation of the current itemset mining algorithms for such scenarios, we introduce the SMIM framework for itemset mining in which utilities are constrained to be non-negative subadditive and monotone functions over itemsets. SMIM generalizes HUIM, can be used to analyse transaction databases with multi-item discount schemes, and can further be used to mine interesting patterns in a social network dataset. Finally, we explain how to design algorithms for SMIM with any general subadditive monotone utility function.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahmed, C.F., Tanbeer, S.K., Jeong, B., Lee, Y.: Efficient tree structures for high utility pattern mining in incremental databases. IEEE Trans. Knowl. Data Eng. 21(12), 1708–1721 (2009)
Bansal, R., Dawar, S., Goyal, V.: An efficient algorithm for mining high-utility itemsets with discount notion. In: Kumar, N., Bhatnagar, V. (eds.) BDA 2015. LNCS, vol. 9498, pp. 84–98. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27057-9_6
Cerf, L., Meira, W.: Complete discovery of high-quality patterns in large numerical tensors. In: 2014 IEEE 30th International Conference on Data Engineering (2014)
Coussat, A., Nadisic, N., Cerf, L.: Mining high-utility patterns in uncertain tensors. Procedia Comput. Sci. 126, 404–412 (2018)
Dawar, S., Goyal, V., Bera, D.: A hybrid framework for mining high-utility itemsets in a sparse transaction database. Appl. Intell. 47(3), 809–827 (2017). https://doi.org/10.1007/s10489-017-0932-1
Fournier-Viger, P., Wu, C.-W., Zida, S., Tseng, V.S.: FHM: faster high-utility itemset mining using estimated utility co-occurrence pruning. In: Andreasen, T., Christiansen, H., Cubero, J.-C., Raś, Z.W. (eds.) ISMIS 2014. LNCS (LNAI), vol. 8502, pp. 83–92. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08326-1_9
Fournier-Viger, P., Chun-Wei Lin, J., Truong-Chi, T., Nkambou, R.: A survey of high utility itemset mining. In: Fournier-Viger, P., Lin, J.C.-W., Nkambou, R., Vo, B., Tseng, V.S. (eds.) High-Utility Pattern Mining. SBD, vol. 51, pp. 1–45. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-04921-8_1
Fournier-Viger, P., et al.: The SPMF open-source data mining library version 2. In: Berendt, B., et al. (eds.) ECML PKDD 2016. LNCS (LNAI), vol. 9853, pp. 36–40. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46131-1_8
Guns, T., Dries, A., Nijssen, S., Tack, G., Raedt, L.D.: MiningZinc: a declarative framework for constraint-based mining. Artif. Intell. 244, 6–29 (2017)
Jaysawal, B.P., Huang, J.W.: DMHUPS: discovering multiple high utility patterns simultaneously. Knowl. Inf. Syst. 59(2), 337–359 (2019). https://doi.org/10.1007/s10115-018-1207-9
Lin, J.C., Gan, W., Fournier-Viger, P., Hong, T., Tseng, V.S.: Mining high-utility itemsets with various discount strategies. In: 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA) (2015)
Liu, J., Wang, K., Fung, B.C.M.: Mining high utility patterns in one phase without generating candidates. IEEE Trans. Knowl. Data Eng. 28(5), 1245–1257 (2016)
Liu, M., Qu, J.: Mining high utility itemsets without candidate generation. In: Proceedings of the \(21^{st}\) ACM International Conference on Information and Knowledge Management (2012)
Liu, Y., Liao, W.k., Choudhary, A.: A fast high utility itemsets mining algorithm. In: Proceedings of the 1st International Workshop on Utility-based Data Mining (2005)
Liu, Y., Liao, W., Choudhary, A.: A two-phase algorithm for fast discovery of high utility itemsets. In: Ho, T.B., Cheung, D., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 689–695. Springer, Heidelberg (2005). https://doi.org/10.1007/11430919_79
Silva, A., Antunes, C.: Constrained pattern mining in the new era. Knowl. Inf. Syst. 47(3), 489–516 (2015). https://doi.org/10.1007/s10115-015-0860-5
Sohrabi, M.K.: An efficient projection-based method for high utility itemset mining using a novel pruning approach on the utility matrix. Knowl. Inf. Syst. 62(11), 4141–4167 (2020). https://doi.org/10.1007/s10115-020-01485-w
Tschiatschek, S., Singla, A., Krause, A.: Selecting sequences of items via submodular maximization. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (2017)
Tseng, V.S., Shie, B., Wu, C., Yu, P.S.: Efficient algorithms for mining high utility itemsets from transactional databases. IEEE Trans. Knowl. Data Eng. 25(8), 1772–1786 (2013)
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 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2010)
Yao, H., Hamilton, H., Geng, L.: A unified framework for utility based measures for mining itemsets. In: 2nd International Workshop on Utility-Based Data Mining (2006)
Zhang, C., Han, M., Sun, R., Du, S., Shen, M.: A survey of key technologies for high utility patterns mining. IEEE Access 8, 55798–55814 (2020)
Zida, S., Fournier-Viger, P., Lin, J.C.-W., Wu, C.-W., Tseng, V.S.: EFIM: a fast and memory efficient algorithm for high-utility itemset mining. Knowl. Inf. Syst. 51(2), 595–625 (2016). https://doi.org/10.1007/s10115-016-0986-0
Acknowledgements
This work was supported in part by Infosys Centre for Artificial Intelligence, Indraprastha Institute of Information Technology, Delhi (IIIT-Delhi), and Visvesvaraya Ph.D. scheme for Electronics and IT.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Dawar, S., Goyal, V., Bera, D. (2022). SMIM Framework to Generalize High-Utility Itemset Mining. In: Li, B., et al. Advanced Data Mining and Applications. ADMA 2022. Lecture Notes in Computer Science(), vol 13088. Springer, Cham. https://doi.org/10.1007/978-3-030-95408-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-95408-6_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95407-9
Online ISBN: 978-3-030-95408-6
eBook Packages: Computer ScienceComputer Science (R0)