Article Details

Abstract

High-Utility Itemset Mining (HUIM) aims to discover high-value patterns whose utilities meet a user-specified threshold in transaction databases. In many practical scenarios, however, users are mainly interested in itemsets that contain a given target item (or target itemset), while conventional HUIM often produces a large number of irrelevant results and incurs unnecessary computational overhead. To address this issue, we propose TIP-MINER, a targeted HUIM method that integrates an IndexSet-based propagation mechanism. It organizes transactional information with an encoded IndexSet representation and performs both candidate expansion and utility accumulation through propagation in a join-free manner. In addition, it adopts target-driven strategies by retaining only target-containing transactions during reconstruction to reduce the initial workload, and by introducing a target boundary to terminate target-irrelevant propagation paths early, thereby shrinking the search space and intermediate structures. Experiments on multiple real-world and synthetic datasets show that the proposed method achieves better runtime and memory efficiency than representative targeted querying approaches while preserving completeness and accuracy, especially on dense or long-transaction databases.

Keywords

High-Utility Itemset Mining; targeted pattern; IndexSet; propagation mechanism; mining

References

1. [1] Yao H，Hamilton H J，Butz C J. A Foundational Approach to Mining Itemset Utilities from Databases [C]//Proceedings of the 2004 SIAM International Conference on Data Mining，2004：482-486.
2. [2] Liu Y，Liao W K，Choudhary A. A Two-phase Algorithm for Fast Discovery of High Utility Itemsets [C]//PAKDD'05: Proceedings of the 9th Pacific-Asia conference on Advances in Knowledge Discovery and Data Mining，2005：689-695.
3. [3] Tseng V S，Shie B E，Wu C W，et al. Efficient Algorithms for Mining High Utility Itemsets from Transactional Databases [J].IEEE Transactions on Knowledge and Data Engineering，2013，25（8）：1772-1786.
4. [4] Liu M C，Qu J F. Mining High Utility Itemsets without Candidate Generation [C]//CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management，2012：55-64.
5. [5] Liu J Q，Wang K，Fung B C M. Direct Discovery of High Utility Itemsets without Candidate Generation [C]//2012 IEEE 12th International Conference on Data Mining，2012：984-989.
6. [6] Zida S，Fournier-Viger P，Lin J C W，et al. EFIM：A Highly Efficient Algorithm for High-utility Itemset Mining [C]//Advances in Artificial Intelligence and Soft Computing，2015：530-546.
7. [7] Fournier-Viger P，Wu C W，Zida S，et al. FHM: Faster High-Utility Itemset Mining Using Estimated Utility Co-occurrence Pruning [C]//Foundations of Intelligent Systems，2014：83-92.
8. [8] Lin J C，Fournier-Viger P，Gan W. FHN: An Efficient Algorithm for Mining High-utility Itemsets with Negative Unit Profits [J].Knowledge-Based Systems，2016，111：283-298.
9. [9] Krishnamoorthy S. Pruning Strategies for Mining High Utility Itemsets [J].Expert Systems with Applications，2015，42（5）：2371-2381.
10. [10] Krishnamoorthy S. HMiner: Efficiently Mining High Utility Itemsets [J].Expert Systems with Applications，2017，90：168-183.
11. [11] Ryang H，Yun U. Indexed List-based High Utility Pattern Mining with Utility Upper-bound Reduction and Pattern Combination Techniques [J].Knowledge and Information Systems，2017，51（2）：627-659.
12. [12] Peng A Y，Koh Y S，Riddle P. mHUIMiner: A fast high utility itemset mining algorithm for sparse datasets [C]//Advances in Knowledge Discovery and Data Mining，2017：196-207.
13. [13] Qu J F，Liu M，Fournier-Viger P. Efficient Algorithms for High Utility Itemset Mining Without Candidate Generation [C]//High-Utility Pattern Mining: Theory, Algorithms and Applications，2019：131-160.
14. [14] Wu P，Niu X Z，Fournier-Viger P，et al. UBP-Miner: An Efficient Bit-based High Utility Itemset Mining Algorithm [J/OL].Knowledge-Based Systems，2022，248：108865.https://doi.org/10.1016/j.knosys.2022.108865.
15. [15] Tseng V S，Wu C W，Fournier-Viger P，et al. Efficient Algorithms for Mining Top-K High Utility Itemsets [J]. IEEE Transactions on Knowledge and Data Engineering，2016，28（1）：54-67.
16. [16] Duong Q H，Liao B，Fournier-Viger P，et al. An Efficient Algorithm for Mining the Top-k High Utility Itemsets, Using Novel Threshold Raising and Pruning Strategies [J].Knowledge-Based Systems，2016，104：106-122.
17. [17] Song W，Zhang Z，Li J H. A High Utility Itemset Mining Algorithm Based on Subsume Index [J].Knowledge and Information Systems，2016，49（1）：315-340.
18. [18] Miao J，Wan S，Gan W S，et al. Targeted High-Utility Itemset Querying [J].IEEE Transactions on Artificial Intelligence，2023：4（4）：871-883.
19. [19] Yan Y H，Niu X Z，Zhang Z H，et al. Efficient High Utility Itemset Mining without the Join Operation [J/OL].Information Sciences，2024，681：121218.https://s100.copyright.com/AppDispatchServlet?publisherName = ELS&contentID = S0020025524011320&orderBeanReset = true.
20. [20] Kubat M，Hafez A，Raghavan V，et al. Itemset trees for targeted association querying [J].IEEE Transactions on Knowledge and Data Engineering，2003，15（6）：1522-1534.
21. [21] Fournier-Viger P，Mwamikazi E，Gueniche T，et al. MEIT: Memory Efficient Itemset Tree for Targeted Association Rule Mining [C]//Advanced Data Mining and Applications – ADMA 2013. Lecture Notes in Computer Science，2013，8347：95-106.
22. [22] Chueh H E. Mining Target-oriented Sequential Patterns with Time-intervals [J].International Journal of Computer Science and Information Technology，2010，2（4）：113-123.
23. [23] Zhang C，Du Z，Dai Q，et al. TUSQ: Targeted High-utility Sequence Querying [J].IEEE Transactions on Big Data，2022，9（2）：512-527.
24. [24] Agrawal R，Imieliński T，Swami A. Mining Association Rules Between Sets of Items in Large Databases [J].SIGMOD Record，1993，22（2）：207-216.
25. Wu Jun, Wei Dandan, Ouyang Aijia, etc Efficient itemset mining algorithm based on statistical significance test [J]. Computer Application Research, 2024, 41 (10): 2970-2977
26. [26] Gao Zhizhi, Han Meng, Li Ang, etc HHUIM: A New Heuristic and Efficient Method for Mining itemsets [J]. Computer Application Research, 2024, 41 (1): 94-101

Funding

National Natural Science Foundation of China (62566016); Guangxi Natural Science Foundation (2025GXNSFAA069551); College Student Innovation and Entrepreneurship Training Program (202410595063)

About the authors

Gong Guojian (2002-), male, Han ethnicity, from Mingshui, Heilongjiang Province, undergraduate studies, research direction: data mining; Bao Xuguang (1985-), male, Han nationality, from Yantai, Shandong, professor, doctoral student, research direction: data mining, machine learning.