Abstract
High utility pattern/itemset mining is a hotspot of data mining. Different from the traditional frequent pattern, high utility pattern takes into consideration not only the number of items in the transaction, but also the weight of these items, such as profit and price. Hence the computational complexity of this mining algorithm is higher than the traditional frequent pattern mining. Thus, one essential topic of this field is to reduce the search space and improve the mining efficiency. Constraint on pattern length can effectively reduce algorithm search space while fulfill a certain kind of actual requirement. Addressing fixed length high utility pattern mining, we propose a novel algorithm, called HUIK (High Utility Itemsets with K-length Miner), that first compresses transaction data into a tree, then recursively searches high utility patterns with designated length using a pattern growth approach. An effective pruning strategy is also proposed to reduce the number of candidate items on the compressed tree, to further reduce the search space and improve algorithm efficiency. The performance of the algorithm HUIK is verified on six classical datasets. Experimental results verify that the proposed algorithm has a significant improvement in time efficiency, especially for long datasets and dense datasets.
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
Lin, C., Lan, G., Hong, T.: Mining high utility itemsets for transaction deletion in a dynamic database. Intell. Data Anal. 19(1), 43–55 (2015)
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
Zida, S., et al.: EFIM: a fast and memory efficient algorithm for high-utility itemset mining. Knowl. Inf. Syst. 51(2), 595–625 (2017)
Han, X., Liu, X., Li, J., Gao, H.: Efficient top-k high utility itemset mining on massive data. Inf. Sci. 557, 382–406 (2021)
Verma, A., Dawar, S., Kumar, R., Navathe, S., Goyal, V.: High-utility and diverse itemset mining. Appl. Intell. 51(7), 4649–4663 (2021). https://doi.org/10.1007/s10489-020-02063-x
Agrawal, R., Imielinski, T., Swami, A.. Mining association rules between sets of items in large databases. In: ACM SIGMOD International Conference on Management of Data, Washington, DC, United States. ACM (1993)
Li, H., et al.: Fast and memory efficient mining of high utility itemsets in data streams. In: 2008 Eighth IEEE International Conference on Data Mining. IEEE (2008)
Ahmed, C.F., et al.: Efficient tree structures for high utility pattern mining in incremental databases. IEEE Trans. Knowl. Data Eng. 21(12), 1708–1721 (2009)
Shie, B.-E., Hsiao, H.-F., Tseng, V.S.: Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments. Knowl. Inf. Syst. 37(2), 363–387 (2012). https://doi.org/10.1007/s10115-012-0483-z
Li, Y., Yeh, J., Chang, C.: Isolated items discarding strategy for discovering high utility itemsets. Data Knowl. Eng. 64(1), 198–217 (2008)
Zihayat, M., Davoudi, H., An, A.: Mining significant high utility gene regulation sequential patterns. BMC Syst. Biol. 11(6), 109 (2017)
Yao, H., Hamilton, H.J., Butz, G.J.: A foundational approach to mining itemset utilities from databases. In: 4th SIAM International Conference on Data Mining (ICDM 2004), Lake Buena Vista, FL, United States (2004)
Liu, Y., Liao, W.K., Choudhary, A.: A two-phase algorithm for fast discovery of high utility itemsets. In: Ho, T.B., Cheung, D., Liu, H. (eds.) Advances in Knowledge Discovery and Data Mining, pp. 689–695. Springer, Heidelberg (2005). https://doi.org/10.1007/11430919_79
Liu, M., Qu, J.: Mining high utility itemsets without candidate generation. In: 21st ACM International Conference on Information and Knowledge Management (CIKM 2012), Maui, HI, United States. Association for Computing Machinery (2012)
Lan, G., et al.: Applying the maximum utility measure in high utility sequential pattern mining. Expert Syst. Appl. 41(11), 5071–5081 (2014)
Yun, U., Ryang, H., Ryu, K.H.: High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates. Expert Syst. Appl. 41(8), 3861–3878 (2014)
Krishnamoorthy, S.: Pruning strategies for mining high utility itemsets. Expert Syst. Appl. 2015(42), 2371–2381 (2015)
Fournier-Viger, P., Lin, J.-W., Duong, Q.-H., Dam, T.-L.: FHM$+$: faster high-utility itemset mining using length upper-bound reduction. In: Fujita, H., Ali, M., Selamat, A., Sasaki, J., Kurematsu, M. (eds.) IEA/AIE 2016. LNCS (LNAI), vol. 9799, pp. 115–127. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42007-3_11
Tseng, V.S., et al.: Efficient algorithms for mining high utility itemsets from transactional databases. IEEE Trans. Knowl. Data Eng. 25(8), 1772–1786 (2013)
Duong, Q.-H., Fournier-Viger, P., Ramampiaro, H., Nørvåg, K., Dam, T.-L.: Efficient high utility itemset mining using buffered utility-lists. Appl. Intell. 48(7), 1859–1877 (2017). https://doi.org/10.1007/s10489-017-1057-2
Liu, J., Wang, K., Fung, B.C.: Direct discovery of high utility itemsets without candidate generation. In: 2012 IEEE 12th International Conference on Data Mining. IEEE (2012)
Kim, J., et al.: One scan based high average-utility pattern mining in static and dynamic databases. Futur. Gener. Comput. Syst. 111, 143–158 (2020)
Truong, T., et al.: Efficient high average-utility itemset mining using novel vertical weak upper-bounds. Knowl.-Based Syst. 183, 104847 (2019)
Krishnamoorthy, S.: Mining top-k high utility itemsets with effective threshold raising strategies. Expert Syst. Appl. 117, 148–165 (2019)
Nam, H., et al.: Efficient approach of recent high utility stream pattern mining with indexed list structure and pruning strategy considering arrival times of transactions. Inf. Sci. 529, 1–27 (2020)
Fournier-Viger, P., et al.: The SPMF open-source data mining library version 2. In: Berendt, B., Bringmann, B., Fromont, É., Garriga, G., Miettinen, P., Tatti, N., Tresp, V. (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
Acknowledgement
This work is partially supported by the Zhejiang Philosophy and Social Science Project (19GXSZ49YB).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, L. (2022). An Algorithm for Mining Fixed-Length High Utility Itemsets. In: Rage, U.K., Goyal, V., Reddy, P.K. (eds) Database Systems for Advanced Applications. DASFAA 2022 International Workshops. DASFAA 2022. Lecture Notes in Computer Science, vol 13248. Springer, Cham. https://doi.org/10.1007/978-3-031-11217-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-11217-1_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-11216-4
Online ISBN: 978-3-031-11217-1
eBook Packages: Computer ScienceComputer Science (R0)