Efficient Mining of Concise Patterns for Fre- quent High-Utility Occupancy Itemsets Using Extended Pruning Strategies
Abstract
Concise representations of frequent high utility occupancy itemsets (FHUOIs), including maximal FHUOIs, closed FHUOIs, and generators of FHUOIs, are essential in utility-driven pattern mining. These representations offer several advantages over the complete set of FHUOIs, such as reduced size, improved efficiency, lower storage costs, and eas- ier analysis. Notably, maximal FHUOIs allow for the recovery of all FHUOIs, while closed FHUOIs and generators enable the generation of non-redundant high utility occupancy rules and the efficient reconstruction of all FHUOIs along with their key information. Despite their significance, existing methods either mine closed FHUOIs and generators separately or lack a solution for mining all maximal FHUOIs. To bridge this gap, this paper introduces two novel algorithms MaxFHUOI- Miner and CGFHUOI-Miner. The former efficiently extracts only maximal FHUOIs using extended pruning strategies that eliminate non-maximal itemsets early, while the latter simul- taneously mines closed FHUOIs and generators by employing innovative pruning techniques to eliminate non-closed and non-generator itemsets at three levels of the prefix tree without performing subset checks. Extensive experiments on real- world and synthetic datasets demonstrate that the proposed algorithms outperform existing and baseline methods in both speed and memory efficiency, particularly for low minimum support and utility occupancy thresholds in dense databases.
References
Z. H. Deng, “Mining high occupancy itemsets,” Future Gen- eration Computer Systems, vol. 102, pp. 222–229, 2020.
K. Zhang, Y. Zhang, and Z. Wang, “Frequent pattern mining based on occupation and correlation,” in Proc. IEEE 3rd Int. Conf. Electronic Information and Communication Technology (ICEICT), pp. 161–166, 2020.
H. Kim et al., “Mining high occupancy patterns to analyze incremental data in intelligent systems,” ISA Transactions, vol. 131, pp. 460–475, 2022.
L. T. T. Nguyen, T. Mai, G. H. Pham, U. Yun, and B. Vo, “An efficient method for mining high occupancy itemsets based on equivalence class and early pruning,” Knowledge-Based Systems, vol. 267, Art. no. 110441, 2023.
B. Shen, Z. Wen, Y. Zhao, D. Zhou, and W. Zheng, “OCEAN: Fast discovery of high utility occupancy itemsets,” in Lecture Notes in Computer Science, pp. 354–365, 2016.
J. He, X. Han, J. Wang, and K. Zhang, “Efficient high-utility occupancy itemset mining algorithm on massive data,” Expert Systems with Applications, vol. 210, Art. no. 118329, 2022.
H. Duong, H. Pham, T. Truong, and P. Fournier-Viger, “Effi- cient algorithms to mine concise representations of frequent high utility occupancy patterns,” Applied Intelligence, 2024.
D. Hai and T. Tin, “An efficient algorithm for mining frequent high utility occupancy generators,” in Proc. 9th Int. Conf. Cloud Computing and Internet of Things (CCIOT), pp. 101– 109, 2025.
D. Hai, H. Tien, and T. Tin, “Mining concise representations of frequent high utility occupancy itemsets using generator patterns,” Dalat University Journal of Science, to be pub- lished, 2025.
J. Li, H. Li, L. Wong, J. Pei, and G. Dong, “Minimum de- scription length principle: Generators are preferable to closed patterns,” in Proc. 21st AAAI Conf. Artificial Intelligence, pp. 409–414, 2006.
H. Yao, H. J. Hamilton, and C. J. Butz, “A foundational approach to mining itemset utilities from databases,” in Proc. SIAM Int. Conf. Data Mining, pp. 482–486, 2004.
Y. Liu, W. Liao, and A. Choudhary, “A fast high utility itemsets mining algorithm,” in Proc. Int. Workshop Utility- Based Data Mining, pp. 90–99, 2005.
M. Liu and J. Qu, “Mining high utility itemsets without candidate generation,” in Proc. ACM Int. Conf. Information and Knowledge Management, pp. 55–64, 2012.
V. S. Tseng, C. Wu, B. Shie, and P. S. Yu, “UP-Growth: An efficient algorithm for high utility itemset mining,” in Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, pp. 253–262, 2010.
S. Zida et al., “EFIM: A highly efficient algorithm for high- utility itemset mining,” in Proc. Mexican Int. Conf. Artificial Intelligence (MICAI), pp. 530–546, 2015.
S. Krishnamoorthy, “HMiner: Efficiently mining high utility itemsets,” Expert Systems with Applications, vol. 90, pp. 168– 183, 2017.
J.-F. Qu et al., “Mining high utility itemsets using prefix trees and utility vectors,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, pp. 10224–10236, 2023.
V. S. Tseng, C. Wu, P. Fournier-Viger, and P. S. Yu, “Efficient algorithms for mining the concise and lossless representation of high utility itemsets,” IEEE Transactions on Knowledge and Data Engineering, vol. 27, pp. 726–739, 2015.
W. Gan et al., “HUOPM: High-utility occupancy pattern mining,” IEEE Transactions on Cybernetics, vol. 50, pp. 1195–1208, 2020.
C. M. Chen et al., “Discovering high utility-occupancy patterns from uncertain data,” Information Sciences, vol. 546, pp. 1208–1229, 2021.
S. Vemulapalli and S. Mogalla, “High utility-occupancy se- quential pattern mining algorithm based on utility-occupancy framework,” Int. J. Engineering Trends and Technology, vol. 69, pp. 228–235, 2021.
C.-W. Wu, P. Fournier-Viger, J. Gu, and V. S. Tseng, “Mining compact high utility itemsets without candidate generation,” in High-Utility Pattern Mining, Studies in Big Data, pp. 283–307, 2019.
H. Duong et al., “Efficient algorithms for mining closed and maximal high utility itemsets,” Knowledge-Based Systems, vol. 257, Art. no. 109921, 2022.
C.-W. Wu, P. Fournier-Viger, J.-Y. Gu, and V. S. Tseng, “Mining closed high utility itemsets without candidate gen- eration,” in Proc. Conf. Technologies and Applications of Artificial Intelligence, pp. 187–194, 2015.
P. Fournier-Viger et al., “EFIM-Closed: Fast and memory- efficient discovery of closed high-utility itemsets,” in Proc. Int. Conf. Machine Learning and Data Mining in Pattern Recognition, pp. 199–213, 2016.
L. T. T. Nguyen et al., “An efficient method for mining high utility closed itemsets,” Information Sciences, vol. 495, pp. 78–99, 2019.
P. Fournier-Viger, C.-W. Wu, and V. S. Tseng, “Novel concise representations of high utility itemsets using generator patterns,” in Proc. Int. Conf. Advanced Data Mining and Applications, pp. 30–43, 2014.
C.-W. Lin, T.-P. Hong, and W.-H. Lu, “An effective tree structure for mining high utility itemsets,” Expert Systems with Applications, vol. 38, 2011.
H. Duong, T. Truong, B. Le, and P. Fournier-Viger, “CG- FHAUI: An efficient algorithm for mining succinct pattern sets of frequent high average utility itemsets,” Knowledge and Information Systems, 2024.
P. Fournier-Viger et al., “SPMF: A Java open-source pattern mining library,” Journal of Machine Learning Research, vol. 15, pp. 3569–3573, 2014.
