Abstract
Skyline frequent-utility itemsets (SFUIs) can provide more actionable information for decision-making with both frequency and utility considered. In this paper, the problem of mining SFUIs by filtering utilities from different perspectives is studied. First, filtering by frequency is considered. The max utility array (MUA) structure is designed, which is proved to have a size no larger than the size of arrays in state-of-the-art algorithms. Using the MUA, the utility-list is verified to prune unpromising itemsets and their extensions. Second, filtering using transaction-weighted utilization is applied. The minimum utility of SFUIs is proposed and the proof that this concept can be used as a pruning strategy in the early stage of search space traversal is provided. Finally, filtering using utility itself is also considered. The minimum utility of extension is presented, and its use as a pruning strategy during the extension stage of search space traversal is validated. Based on these filtering methods, a novel algorithm called SFUIs mining based on utility filtering (SFUI-UF) is proposed. Extensive experimental results show that the SFUI-UF algorithm can discover all correct SFUIs with high efficiency and low memory usage.
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
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
Goyal, V., Sureka, A., Patel, D.: Efficient skyline itemsets mining. In: Proceedings of the Eighth International C* Conference on Computer Science & Software Engineering, pp.119–124 (2015)
Lin, J.C.-W., Yang, L., Fournier-Viger, P., Hong, T.-P.: Mining of skyline patterns by considering both frequent and utility constraints. Eng. Appl. Artif. Intell. 77, 229–238 (2019)
Liu, M., Qu, J.: Mining high utility itemsets without candidate generation. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp.55–64 (2012)
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.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 689–695. Springer, Heidelberg (2005). https://doi.org/10.1007/11430919_79
Luna, J.M., Fournier-Viger, P., Ventura, S.: Frequent itemset mining: a 25 years review. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 9(6) (2019)
Nguyen, H.M., Phan, A.V., Pham, L.V.: FSKYMINE: a faster algorithm for mining skyline frequent utility itemsets. In: Proceedings of the 6th NAFOSTED Conference on Information and Computer Science, pp.251–255 (2019)
Pan, J.-S., Lin, J.C.-W., Yang, L., Fournier-Viger, P., Hong, T.-P.: Efficiently mining of skyline frequent-utility patterns. Intell. Data Anal. 21(6), 1407–1423 (2017)
Podpecan, V., Lavrac, N., Kononenko, I.: A fast algorithm for mining utility-frequent itemsets. In: Proceedings of International Workshop on Constraint-Based Mining and Learning, pp. 9–20 (2007)
Song, W., Jiang, B., Qiao, Y.: Mining multi-relational high utility itemsets from star schemas. Intell. Data Anal. 22(1), 143–165 (2018)
Song, W., Zhang, Z., Li, J.: A high utility itemset mining algorithm based on subsume index. Knowl. Inf. Syst. 49(1), 315–340 (2015). https://doi.org/10.1007/s10115-015-0900-1
Yeh, J.-S., Li, Y.-C., Chang, C.-C.: Two-phase algorithms for a novel utility-frequent mining model. In: Proceedings of the International Workshops on Emerging Technologies in Knowledge Discovery and Data Mining, pp.433–444 (2007)
Acknowledgments
We would like to thank Prof. Jerry Chun-Wei Lin for providing the source codes of the SKYFUP-D and SKYFUP-B algorithms. This work was partially supported by the National Natural Science Foundation of China (61977001), and Great Wall Scholar Program (CIT&TCD20190305).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Song, W., Zheng, C., Fournier-Viger, P. (2021). Mining Skyline Frequent-Utility Itemsets with Utility Filtering. In: Pham, D.N., Theeramunkong, T., Governatori, G., Liu, F. (eds) PRICAI 2021: Trends in Artificial Intelligence. PRICAI 2021. Lecture Notes in Computer Science(), vol 13031. Springer, Cham. https://doi.org/10.1007/978-3-030-89188-6_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-89188-6_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89187-9
Online ISBN: 978-3-030-89188-6
eBook Packages: Computer ScienceComputer Science (R0)