生物启发式的模式挖掘方法综述

doi:10.3778/j.issn.1002-8331.2401-0427

摘要/Abstract

摘要： 频繁项集挖掘、关联规则挖掘和高效用项集挖掘是模式挖掘中相互关联且不断发展的三个领域。近年来，由于传统算法无法应对爆炸式增长的数据环境，启发式算法已成为模式挖掘方法中的研究热点。为揭示模式挖掘领域的研究与发展现状，从粒子群、遗传、蚁群、蜂群等多个生物启发式算法角度对近年的频繁模式和高效用项集方法研究成果进行全面的分析与总结。对不同生物启发的模式挖掘方法，从使用策略、对比算法、数据集、优缺点进行概述，对相同数据集的实验结果及性能指标进行详细的对比分析。针对目前生物启发式模式挖掘方法中的不足，提出了下一步的研究方向，包括动态数据流、多目标进化、模糊计算和复杂数据类型的研究。

关键词: 生物启发式, 频繁项集, 关联规则, 高效用项集

Abstract: Frequent itemset mining, association rule mining and high utility itemset mining are three related and developing fields in pattern mining. In recent years, because traditional algorithms cannot cope with the explosive growth of data environment, heuristic algorithms have become a research hotspot in pattern mining methods. In order to reveal the research and development status in the field of pattern mining, firstly, the research results of frequent patterns and high utility pattern methods are comprehensively analyzed and summarized from the perspective of many biological heuristic algorithms, such as particle swarm optimization, genetic algorithm, ant colony optimization, and artificial bee colony and so on. Secondly, different biological heuristic pattern mining methods are summarized from strategy, comparison algorithm, datasets, advantages and disadvantages, and the experimental results and performance indicators of the same datasets are compared and analyzed in detail. Finally, in view of the shortcomings of the current biological heuristic pattern mining methods, the next research direction is put forward, including dynamic data flow, multi-objective evolution, fuzzy computing and complex data types.

Key words: biological heuristic, frequent itemset, association rule, high utility itemset

韩萌, 何菲菲, 张瑞华, 李春鹏, 孟凡兴. 生物启发式的模式挖掘方法综述[J]. 计算机工程与应用, 2024, 60(16): 19-33.

HAN Meng, HE Feifei, ZHANG Ruihua, LI Chunpeng, MENG Fanxing. Survey of Pattern Mining Methods Based on Biological Heuristic Algorithms[J]. Computer Engineering and Applications, 2024, 60(16): 19-33.

参考文献

[1] WEI Y, HUANG J, ZHANG Z, et al. SIBA: a fast frequent item sets mining algorithm based on sampling and improved bat algorithm[C]//Proceedings of the 2015 Chinese Automation Congress, 2015: 64-69.
[2] BAGUI S, STANLEY P. Mining frequent patterns from streaming transaction data using genetic algorithms[J]. Journal of Big Data, 2020, 7: 1-20.
[3] CHEN S B, WANG X F. Mining dynamical frequent itemsets based on ant colony algorithm[C]//Proceedings of the 2011 IEEE International Conference on Computer Science and Automation Engineering, 2011: 252-255.
[4] YAN D, ZHAO X, LIN R, et al. PPQAR: parallel PSO for quantitative association rule mining[J]. Peer-to-Peer Networking and Applications, 2019, 12(5): 1433-1444.
[5] JINGLE I, CELIN J. Mining optimized positive and negative association rule using advance ABC algorithm[J]. Journal of Theoretical and Applied Information Technology, 2017, 95(24): 6846-6855.
[6] KALYANI G, CHANDR SEKHARA RAO M V P, JANAKIRAMAIAH B. Particle swarm intelligence and impact factor-based privacy preserving association rule mining for balancing data utility and knowledge privacy[J]. Arabian Journal for Science and Engineering, 2018, 43: 4161-4178.
[7] KUO R J, GOSUMOLO M, ZULVIA F E. Multi-objective particle swarm optimization algorithm using adaptive archive grid for numerical association rule mining[J]. Neural Computing and Applications, 2019, 31: 3559-3572.
[8] KANNIMUTHU S, PREMALATHA K. Discovery of high utility patterns using genetic algorithm with ranked mutation[J]. Applied Artificial Intelligence, 2014, 28(4): 337-359.
[9] LIN J C W, DJENOURI Y, SRIVASTAVA G, et al. A predictive GA-based model for closed high-utility pattern mining[J]. Applied Soft Computing, 2021, 108: 107422.
[10] WU J M T, ZHAN J, LIN J C W. An ACO-based approach to mine high-utility patterns[J]. Knowledge-Based Systems, 2017, 116: 102-113.
[11] HAN M, GAO Z, LI A, et al. An overview of high utility patterns mining methods based on intelligent optimization algorithms[J]. Knowledge and Information Systems, 2022, 64(11): 2945-2984.
[12] GHAFARI S M, TJORTJIS C. A survey on association rules mining using heuristics[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2019, 9(4): e1307.
[13] CAO H, YANG S, WANG Q, et al. A closed pattern prop erty based multi-objective evolutionary approach for mining frequent and high utility patterns[C]//Proceedings of the 2019 IEEE Congress on Evolutionary Computation, 2019: 3356-3363.
[14] 高曼, 韩萌, 雷冰冰. 高效用模式产生策略综述[J]. 计算机工程与应用, 2020, 56(16): 1-12.
GAO M, HAN M, LEI B B. Survey of high utility pattern generate strategy[J]. Computer Engineering and Applications, 2020, 56(16): 1-12.
[15] 孟凡兴, 韩萌, 李春鹏, 等. 概念漂移检测与适应方法综述[J]. 计算机工程与应用, 2024, 60(4): 75-88.
MENG F X, HAN M, LI C P, et al. Survey of concept drift detection and adaptation methods[J]. Computer Engineering and Applications, 2024, 60(4): 75-88.
[16] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of the 1995 International Conference on Neural Networks, 1995, 4: 1942-1948.
[17] KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm[C]//Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation, 1997, 5: 4104-4108.
[18] SUKANYA N S, THANGAIAH P R J. Customized particle swarm optimization algorithm for frequent pattern mining[C]//Proceedings of the 2020 International Conference on Computer Communication and Informatics, 2020: 1-4.
[19] DJENOURI Y, COMUZZI M. Combining Apriori heuristic and bio-inspired algorithms for solving the frequent patterns mining problem[J]. Information Sciences, 2017, 420: 1-15.
[20] DJENOURI Y, DJENOURI D, BELHADI A, et al. A new framework for metaheuristic-based frequent pattern mining[J]. Applied Intelligence, 2018, 48: 4775-4791.
[21] DJENOURI Y, DJENOURI D, BELHADI A, et al. A novel parallel framework for metaheuristic-based frequent pattern mining[C]//Proceedings of the 2019 IEEE Congress on Evolutionary Computation, 2019: 1439-1445.
[22] 郭宇红, 童云海, 苏燕青. 分组随机化隐私保护频繁模式挖掘[J]. 软件学报, 2021, 32(12): 3929-3944.
GUO Y H, TONG Y H, SU Y Q. Privacy preserving frequent pattern mining based on grouping randomization[J]. Journal of Software, 2021, 32(12): 3929-3944.
[23] SU T, XU H, ZHOU X. Particle swarm optimization-based association rule mining in big data environment[J]. IEEE Access, 2019, 7: 161008-161016.
[24] MOSLEHI F, HAERI A, MARTíNEZ-áLVAREZ F. A novel hybrid GA-PSO framework for mining quantitative association rules[J]. Soft Computing, 2020, 24: 4645-4666.
[25] ADEBAYO O S, ABDUL AZIZ N. Improved malware detection model with Apriori association rule and particle swarm optimization[J]. Security and Communication Networks, 2019. DOI:10.1155/2019/2850932.
[26] BARó G B, MARTíNEZ-TRINIDAD J F, ROSAS R M V, et al. A PSO-based algorithm for mining association rules using a guided exploration strategy[J]. Pattern Recognition Letters, 2020, 138: 8-15.
[27] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Cambridge: MIT Press, 1992.
[28] KABIR M M J, XU S, KANG B H, et al. Comparative analysis of genetic based approach and Apriori algorithm for mining maximal frequent item sets[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation, 2015: 39-45.
[29] DJENOURI Y, COMUZZI M. GA-Apriori: combining Apriori heuristic and genetic algorithms for solving the frequent patterns mining problem[C]//Trends and Applications in Knowledge Discovery and Data Mining, PAKDD 2017 Workshops, Jeju, May 23, 2017. Cham: Springer, 2017: 138-148.
[30] DJENOURI Y, BELHADI A, FOURNIER-VIGER P, et al. Mining diversified association rules in big datasets: a cluster/GPU/genetic approach[J]. Information Sciences, 2018, 459: 117-134.
[31] XU B, DING S, LI Y. Data association rules mining method based on genetic optimization algorithm[J]. Journal of Physics: Conference Series, 2020, 1570(1): 012006.
[32] GUPTA A, JAIN S, TIWARI A. Optimization and improvement of association rule mining using genetic algorithm and fuzzy logic[C]//Proceedings of the 2019 International Conference on Sustainable Computing in Science, Technology and Management, Jaipur, 2019.
[33] MENAGA D, SARAVANAN S. GA-PPARM: constraint-based objective function and genetic algorithm for privacy preserved association rule mining[J]. Evolutionary Intelligence, 2021, 15: 1487-1498.
[34] YANG X S. A new metaheuristic bat-inspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization, 2010: 65-74.
[35] HERAGUEMI K E, KAMEL N, DRIAS H. Association rule mining based on bat algorithm[J]. Journal of Computational and Theoretical Nanoscience, 2015, 12(7): 1195-1200.
[36] 梁文娟, 陈红, 赵素云, 等. 一种面向数据流top-[k]频繁模式发布的差分隐私保护方案[J]. 计算机学报, 2021, 44(4): 741-760.
LIANG W J, CHEN H, ZHAO S Y, et al. A differentially private scheme for top-[k] frequent itemsets mining over data streams[J]. Chinese Journal of Computers, 2021, 44(4): 741-760.
[37] NEELIMA S, SATYANARAYANA N, KRISHNA MURTHY P. Minimizing frequent patterns using hybrid ABCBAT algorithm[M]//Data engineering and intelligent computing, advances in intelligent systems and computing. Singapore: Springer, 2018: 91-97.
[38] HERAGUEMI K E, KAMEL N, DRIAS H. Multi-population cooperative bat algorithm for association rule mining[C]//Proceedings of the 7th International Conference on Computational Collective Intelligence, Madrid, Sep 21-23, 2015. Cham: Springer, 2015: 265-274.
[39] HERAGUEMI K E, KAMEL N, DRIAS H. Multi-swarm bat algorithm for association rule mining using multiple cooperative strategies[J]. Applied Intelligence, 2016, 45: 1021-1033.
[40] HERAGUEMI K E, KAMEL N, DRIAS H. Multi-objective bat algorithm for mining numerical association rules[J]. International Journal of Bio-Inspired Computation, 2018, 11(4): 239-248.
[41] SONG A, DING X, CHEN J, et al. Multi-objective association rule mining with binary bat algorithm[J]. Intelligent Data Analysis, 2016, 20(1): 105-128.
[42] SONG A, SONG J, DING X, et al. Utilizing bat algorithm to optimize membership functions for fuzzy association rules mining[C]//Proceedings of the 28th International Conference on Database and Expert Systems Applications, Lyon, Aug 28-31, 2017. Cham: Springer, 2017: 496-504.
[43] RAMESH R, SARAVANAN V. Proportion frequency occurrence count with bat algorithm (FOCBA) for rule optimization and mining of proportion equivalence fuzzy constraint class association rules (PEFCARs)[J]. Periodicals of Engineering and Natural Sciences, 2018, 6(1): 305-325.
[44] DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.
[45] SUNDARAMOORTHY S, SHANTHARAJAH D R S P. An improved ant colony algorithm for effective mining of frequent items[J]. Journal of Web Engineering, 2014: 263-276.
[46] GAO Y, TANG X L. Application of hybrid ant colony algorithm for mining maximum frequent item sets[C]//Proceedings of the 2015 IEEE International Conference on Signal Processing, Communications and Computing, 2015: 1-4.
[47] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Erciyes University. Engineering Faculty. Computer Engineering Department, 2005.
[48] DJENOURI Y, BENDJOUDI A, HABBAS Z, et al. Reducing thread divergence in GPU-based bees swarm optimization applied to association rule mining[J]. Concurrency and Computation: Practice and Experience, 2017, 29(9): e3836.
[49] QURESHI I, MOHAMMAD B, HABEEB M A. Optimizing association rule mining using walk back artificial bee colony (walkbackabc) algorithm[C]//Proceedings of the 6th International Conference on Innovations in Computer Science and Engineering. Singapore: Springer, 2019: 39-48.
[50] TELIKANI A, GANDOMI A H, SHAHBAHRAMI A, et al. Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony[J]. Expert Systems with Applications, 2020, 144: 113097.
[51] AFSHARI M H, DEHKORDI M N, AKBARI M. Association rule hiding using cuckoo optimization algorithm[J]. Expert Systems with Applications, 2016, 64: 340-351.
[52] BOUYER A, HATAMLOU A. An efficient hybrid clustering method based on improved cuckoo optimization and modified particle swarm optimization algorithms[J]. Applied Soft Computing, 2018, 67: 172-182.
[53] SHARMILA S, VIJAYARANI S. Association rule mining using fuzzy logic and whale optimization algorithm[J]. Soft Computing, 2021, 25: 1431-1446.
[54] MOULAI H, DRIAS H. Association rule mining using new discrete elephant swarm approaches[J]. Expert Systems, 2023, 40(2): e13159.
[55] MEHTA S, SINGH M, KAUR N. Firefly algorithm for optimization of association rules[C]//Proceedings of the 6th International Conference on Signal Processing and Communication, 2020: 143-148.
[56] HU K, QIU L, ZHANG S, et al. An animal dynamic migration optimization method for directional association rule mining[J]. Expert Systems with Applications, 2023, 211: 118617.
[57] LIN J C W, YANG L, FOURNIER-VIGER P, et al. A binary PSO approach to mine high-utility patterns[J]. Soft Computing, 2017, 21: 5103-5121.
[58] SONG W, HUANG C. Mining high utility patterns using bio-inspired algorithms: a diverse optimal value framework[J]. IEEE Access, 2018, 6: 19568-19582.
[59] SONG W, LI J. Discovering high utility patterns using set-based particle swarm optimization[C]//Proceedings of the 16th International Conference on Advanced Data Mining and Applications, Foshan, Nov 12-14, 2020. Cham: Springer, 2020: 38-53.
[60] SIVAMATHI C, VIJAYARANI S. Mining high utility patterns using shuffled complex evolution of particle swarm optimization (SCE-PSO) optimization algorithm[C]//Proceedings of the 2017 International Conference on Inventive Computing and Informatics, 2017: 640-644.
[61] SONG W, HUANG C. Mining high average-utility patterns based on particle swarm optimization[J]. Data Science and Pattern Recognition, 2020, 4(2): 19-32.
[62] 靳晓乐, 刘峡壁, 马骁. 基于双重二元粒子群优化的高效用项集挖掘算法[J]. 计算机工程, 2018, 44(12): 202-207.
JIN X L, LIU X B, MA X. High-utility itemsets mining algorithm based on double binary particle swarm optimization[J]. Computer Engineering, 2018, 44(12): 202-207.
[63] GUNAWAN R, WINARKO E, PULUNGAN R. A BPSO-based method for high-utility pattern mining without minimum utility threshold[J]. Knowledge-Based Systems, 2020, 190: 105164.
[64] LOGESWARAN K, SATHASIVAM R, SURESH P, et al. Discovery of potential high utility pattern from uncertain database using multi objective particle swarm optimization algorithm[C]//Proceedings of the 2022 International Conference on Advanced Computing Technologies and Applications, 2022: 1-6.
[65] FANG W, ZHANG Q, LU H, et al. High-utility itemsets mining based on binary particle swarm optimization with multiple adjustment strategies[J]. Applied Soft Computing, 2022, 124: 109073.
[66] ZHANG Q, FANG W, SUN J, et al. Improved genetic algorithm for high-utility pattern mining[J]. IEEE Access, 2019, 7: 176799-176813.
[67] LIN J C W, GAN W, FOURNIER-VIGER P, et al. High utility-pattern mining and privacy-preserving utility mining[J]. Perspectives in Science, 2016, 7: 74-80.
[68] LIN J C W, DJENOURI Y, SRIVASTAVA G, et al. Efficient evolutionary computation model of closed high-utility pattern mining[J]. Applied Intelligence, 2022, 52(9): 10604-10616.
[69] ARUNKUMAR M S, SURESH P, GUNAVATHI C. High utility infrequent pattern mining using a customized ant colony algorithm[J]. International Journal of Parallel Programming, 2020, 48: 833-849.
[70] PRAMANIK S, GOSWAMI A. Discovery of closed high utility patterns using a fast nature-inspired ant colony algorithm[J]. Applied Intelligence, 2022, 52(8): 8839-8855.
[71] STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341.
[72] KRISHNA G J, RAVI V. High utility pattern mining using binary differential evolution: an application to customer segmentation[J]. Expert Systems with Applications, 2021, 181: 115122.
[73] YANG F, MU N, LIAO X, et al. EA-HUFIM: optimization for fuzzy-based high-utility patterns mining[J]. International Journal of Fuzzy Systems, 2021, 23: 1652-1688.
[74] LOGESWARAN K, NIRANJAN R, SURESH P, et al. Discovery of potential high utility pattern from uncertain database using multi objective discrete differential evolutionary algorithm[C]//Proceedings of the 2022 International Conference on Computer Communication and Informatics, 2022: 1-5.
[75] PAZHANIRAJA N, SOUNTHARRAJAN S, SATHIS KUMAR B. High utility pattern mining: a boolean operators-based modified grey wolf optimization algorithm[J]. Soft Computing, 2020, 24: 16691-16704.
[76] PAZHANIRAJA N, SOUNTHARRAJAN S, SUGANYA E, et al. Optimizing high-utility item mining using hybrid dolphin echolocation and Boolean grey wolf optimization[J]. Journal of Ambient Intelligence and Humanized Computing, 2023, 14(3): 2327-2339.
[77] SONG W, HUANG C. Discovering high utility patterns based on the artificial bee colony algorithm[C]//Proceedings of the 22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Melbourne, Jun 3-6, 2018. Cham: Springer, 2018: 3-14.
[78] SONG W, LI J, HUANG C. Artificial fish swarm algorithm for mining high utility patterns[C]//Proceedings of the 12th International Conference on Swarm Intelligence, Qingdao, Jul 17-21, 2021. Cham: Springer, 2021: 407-419.
[79] 程浩东, 韩萌, 张妮, 等. 基于滑动窗口模型的数据流闭合高效用项集挖掘[J]. 计算机研究与发展, 2021, 58(11): 2500-2514.
CHENG H D, HAN M, ZHANG N, et al. Closed high utility itemsets mining over data stream based on sliding window model[J]. Journal of Computer Research and Development, 2021, 58(11): 2500-2514.