No Access

Department of Computer Engineering, St. Francis Institute of Technology, Mumbai 400103, India

Department of Informatics, Sanata Dharma University, Yogyakarta 55281, Indonesia

E-mail Address: eduardus@student.sfit.ac.in

Corresponding author.

Search for more papers by this author

and

Kavita Sonawane

https://orcid.org/0000-0003-0865-6760

Department of Computer Engineering, St. Francis Institute of Technology, Mumbai 400103, India

E-mail Address: kavitasonawane@sfit.ac.in

Search for more papers by this author

https://doi.org/10.1142/S146902682450024XCited by:0 (Source: Crossref)

Abstract

In pattern mining, high-utility itemset mining (HUIM) is useful for discovering high-utility patterns. The study of HUIM using heuristic techniques reflects issues in producing better offspring. It is ineffective in terms of search space organization, population diversity, and utility calculation, which impact runtime and accuracy. It is observed that very few researchers have experimented with genetic algorithm (GA) and are still facing the same issues as mentioned before. To overcome these problems, a novel approach is proposed for HUIM using modified GA and optimized local search (HUIM-MGALS) with six potential contributions. First is linking the utility with the Bitmap dataset to reduce utility access time, leading to effective search space organization. Second, HUIM-MGALS employs a fitness scaling strategy to avoid redundancy. Third, a high-utility itemset (HUI) revision strategy is employed to explore significant HUIs. Modified population diversity maintenance strategy and iterative crossover help to preserve significant HUIs and improve search capability as fourth and fifth contributions. Sixth, the use of multiple mutations refines the wasted individuals to boost accuracy. Extensive experimentation showed that HUIM-MGALS significantly outperforms the presented algorithms, up to 8.6 times faster. It also demonstrates superior HUI discovery capabilities for both sparse and dense datasets. This is supported by the modified population diversity maintenance strategy, which is proved to be the most impactful modification for HUI discovery in HUIM-MGALS.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

1. J. Han, M. Kamber and J. Pei, Data mining: Concepts and Techniques, 3rd edn. (Morgan Kaufmann, Waltham, 2012). Crossref, Google Scholar
2. R. Agrawal and R. Srikant, Fast algorithms for mining association rules, in Proc. 20th Int. Conf. Very Large Data Bases (Morgan Kaufmann, San Francisco, 1994), pp. 487–499. Google Scholar
3. P. Fournier-Viger, J. C. W. Lin, T. Truong-Chi and R. Nkambou, Studies in big data, in High-Utility Pattern Mining: A Survey of High Utility Itemset Mining, eds. P. Fournier-Viger, J. C. W. Lin, R. Nkambou, B. Vo and V. S. Tseng (Springer, Cham, 2019), pp. 1–45. Crossref, Google Scholar
4. Y. Liu, W. Liao and A. Choudhary, Lecture notes in computer science, in Advances in Knowledge Discovery and Data Mining: A Two-phase Algorithm for Fast Discovery of High Utility Itemsets, eds. T. B. Ho, D. Cheung and H. Liu (Springer, Berlin, 2005), pp. 689–695. Crossref, Google Scholar
5. V. S. Tseng, B. E. Shie, C. W. Wu and P. S. Yu, Efficient algorithms for mining high utility itemsets from transactional databases, IEEE Trans. Knowl. Data Eng. 25(8) (2013) 1772–1786. Crossref, Google Scholar
6. E. H. S. Atmaja and K. Sonawane, Lecture notes in networks and systems, in ICT Analysis and Applications: Parallel Algorithm to Efficiently Mine High Utility Itemset, eds. S. Fong, N. Dey and A. Joshi (Springer, Singapore, 2022), pp. 167–178. Crossref, Google Scholar
7. M. Liu and J. Qu, Mining high utility itemsets without candidate generation, in Proc. 21st ACM Int. Conf. Information and Knowledge Management (Association for Computing Machinery, New York, 2012), pp. 55–64. Crossref, Google Scholar
8. Q. H. Duong, P. Fourfnier-Viger, H. Ramampiaro, K. Norvag and T. L. Dam, Efficient high utility itemset mining using buffered utility-lists, Appl. Intell. 48 (2018) 1859–1877. Crossref, Google Scholar
9. E. H. S. Atmaja and K. Sonawane, Optimization of search space division with enhanced shared memory-based utility list buffer miner with a parallel framework (SM-PLB) for effective high utility itemset mining, Int. J. Inf. Technol. 15(3) (2023) 1597–1609. Google Scholar
10. E. H. S. Atmaja and K. Sonawane, Lecture notes in networks and systems, in Pattern Recognition and Data Analysis with Applications: A Review of High Utility Itemset Mining for Transactional Database, eds. D. Gupta, R. S. Goswami, S. Banerjee, M. Tanveer and R. B. Pachori (Springer, Singapore, 2022), pp. 15–27. Crossref, Google Scholar
11. A. Telikani, A. H. Gandomi and A. Shahbahrami, A survey of evolutionary computation for association rule mining, Inf. Sci. 524 (2020) 318–352. Crossref, Google Scholar
12. M. S. Nawaz, P. Fournier-Viger, U. Yun, Y. Wu and W. Song, Mining high utility itemsets with hill climbing and simulated annealing, ACM Trans. Manag. Inf. Syst. 13(1) (2022) 1–22. Crossref, Google Scholar
13. S. Katoch, S. S. Chauhan and V. Kumar, A review on genetic algorithm: Past, present, and future, Multimedia Tools Appl. 80 (2021) 8091–8126. Crossref, Google Scholar
14. M. S. Umam, M. Mustafid and S. Suryono, A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem, J. King Saud Univ. — Comput. Inf. Sci. 34(9) (2022) 7459–7467. Google Scholar
15. M. S. Viana, O. M. Junior and R. C. Contreras, A modified genetic algorithm with local search strategies and multi-crossover operator for job shop scheduling problem, Sensors 20(18) (2020) 5440. Crossref, Google Scholar
16. L. Asadzadeh, A local search genetic algorithm for the job shop scheduling problem with intelligent agents, Comput. Ind. Eng. 85 (2015) 376–383. Crossref, Google Scholar
17. F. Souza and D. Grimes, Combining local search and genetic algorithm for two-dimensional guillotine bin packing problems with partial sequence constraint, in Proc. 28th Irish Conf. Artificial Intelligence and Cognitive Science (Technological University Dublin, Dublin, 2020), pp. 97–108. Google Scholar
18. L. Gharsalli and Y. Guerin, A hybrid genetic algorithm with local search approach for composite structures optimization, in Proc. 8th European Conf. Aeronautics and Space Sciences (EUCASS, Madrid, 2019). Google Scholar
19. J. M. T. Wu, J. Zhan and J. C. W. Lin, An ACO-based approach to mine high-utility itemsets, Knowl.-based Syst. 2017 (2017) 102–113. Crossref, Google Scholar
20. W. Song and J. Nan, Lecture notes on data engineering and communications technologies, in Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery: Mining High Utility Itemsets Using Ant Colony Optimization, eds. H. Meng, T. Lei, M. Li, K. Li, N. Xiong and L. Wang (Springer, Cham, 2021), pp. 98–107. Crossref, Google Scholar
21. S. Kannimuthu and K. Premalatha, Discovery of high utility itemsets using genetic algorithm with ranked mutation, Appl. Artif. Intell. 28(4) (2014) 337–359. Crossref, Google Scholar
22. W. Song and C. Huang, Mining high utility itemsets using bio-inspired algorithms: A diverse optimal value framework, IEEE Access 6 (2018) 19568–19582. Crossref, Google Scholar
23. Q. Zhang, W. Fang, J. Sun and Q. Wang, Improved genetic algorithm for high-utility itemset mining, IEEE Access 7 (2019) 176799–176813. Crossref, Google Scholar
24. J. C. W. Lin, L. Yang, P. Fournier-Viger, J. M. T. Wu, T. P. Hong, T. S. L. Wang and J. Zhan, Mining high-utility itemsets based on particle swarm optimization, Eng. Appl. Artif. Intell. 55 (2016) 320–330. Crossref, Google Scholar
25. J. C. W. Lin, L. Yang, P. Fournier-Viger, T. P. Hong and M. Voznak, A binary PSO approach to mine high-utility itemsets, Soft Comput. 21 (2017) 5103–5121. Crossref, Google Scholar
26. R. Gunawan, E. Winarko and R. Pulungan, BPSO-based method for high-utility itemset mining without minimum utility threshold, Knowl.-Based Syst. 190 (2020) 105164. Crossref, Google Scholar
27. H. Yao, H. J. Hamilton and C. J. Butz, A foundational approach to mining itemset utilities from databases, in Proc. 4th SIAM Int. Conf. Data Mining (DBLP, Florida, 2004), pp. 482–486. Crossref, Google Scholar
28. B. Vo, L. V. Nguyen, V. V. Vu, M. T. H. Lam, T. T. M. Duong, L. T. Manh, T. T. T. Nguyen, L. T. T. Nguyen and T. P. Hong, Mining correlated high utility itemsets in one phase, IEEE Access 8 (2020) 90465–90477. Crossref, Google Scholar
29. T. Wei, B. Wang, Y. Zhang, K. Hu, Y. Yao and H. Liu, FCHUIM: Efficient frequent and closed high utility itemsets mining, IEEE Access 8 (2020) 109928–109939. Crossref, Google Scholar
30. C. H. Lin, C. W. Wu, J. T. Huang and V. S. Tseng, Lecture notes in computer science, in Advances in Knowledge Discovery and Data Mining: Parallel Mining of Top-k high Utility Itemsets in Spark in-memory Computing Architecture, eds. Q. Yang, Z. H. Zhou, Z. Gong, M. L. Zhang and S. J. Huang (Springer, Cham, 2019), pp. 253–265. Crossref, Google Scholar
31. D. E. Goldberg, Genetic Aalgorithms in Search, Optimization and Machine Learning (Addison-Wesley, USA, 1989). Google Scholar
32. A. J. P. Delima, A. M. Sison and R. P. Medina, A modified genetic algorithm with a new crossover mating scheme, Indonesian J. Electr. Eng. Inf. 7(2) (2019) 165–181. Google Scholar
33. S. Rimcharoen and N. Leelathakul, Ring-based crossovers in genetic algorithms: Characteristic decomposition and their generalization, IEEE Access 9 (2021) 137902–137922. Crossref, Google Scholar
34. W. Song, J. Li and C. Huang, Lecture notes in computer science, in Advances in Swarm Intelligence: Artificial Fish Swarm Algorithm for Mining High Utility Itemsets, eds. Y. Tan and Y. Shi (Springer, Cham, 2021), pp. 407–419. Crossref, Google Scholar
35. G. Liu, H. Lu, W. Lou, Y. Xu and J. X. Yu, Efficient mining of frequent patterns using ascending frequency ordered prefix-tree, Data Mining Knowl. Discov. 9 (2004) 249–274. Crossref, Google Scholar
36. P. Fournier-Viger, C. W. Lin, A. Gomariz, T. Gueniche, A. Soltani, Z. Deng and H. T. Lam, Lecture notes in computer science, in Machine Learning and Knowledge Discovery in Databases: The SPMF Open-Source Data Mining Library Version 2, eds. B. Berendt, B. Bringmann, E. Fromont, G. Garriga, P. Miettinen, N. Tatti and V. Tresp (Springer, Cham, 2016), pp. 36–40. Crossref, Google Scholar
37. Real retail dataset, https://tinyurl.com/realretail (Accessed March 2023). Google Scholar