How to cite this WIREs title:
WIREs Data Mining Knowl Discov

Impact Factor: 4.476

A survey on association rules mining using heuristics

Advanced Review

Seyed Mohssen Ghafari, Christos Tjortjis

Published Online: Apr 01 2019

DOI: 10.1002/widm.1307

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Association rule mining (ARM) is a commonly encountred data mining method. There are many approaches to mining frequent rules and patterns from a database and one among them is heuristics. Many heuristic approaches have been proposed but, to the best of our knowledge, there is no comprehensive literature review on such approaches, yet with only a limited attempt. This gap needs to be filled. This paper reviews heuristic approaches to ARM and points out their most significant strengths and weaknesses. We propose eight performance metrics, such as execution time, memory consumption, completeness, and interestingness, we compare approaches against these performance metrics and discuss our findings. For instance, comparison results indicate that SRmining, PMES, Ant‐ARM, and MDS‐H are the fastest heuristic ARM algorithms. HSBO‐TS is the most complete one, while SRmining and ACS require only one database scan. In addition, we propose a parameter, named GT‐Rank for ranking heuristic ARM approaches, and based on that, ARMGA, ASC, and Kua emerge as the best approaches. We also consider ARM algorithms and their characteristics as transactions and items in a transactional database, respectively, and generate association rules that indicate research trends in this area. This article is categorized under: Algorithmic Development > Association Rules Technologies > Association Rules Fundamental Concepts of Data and Knowledge > Motivation and Emergence of Data Mining

Comparison of execution time with apriori and FP‐growth

[ Normal View | Magnified View ]

Average memory consumption

[ Normal View | Magnified View ]

Comparison from the point of view of number of rules/itemsets

[ Normal View | Magnified View ]

Number of database scans

[ Normal View | Magnified View ]

Comparison based on the fitness values

[ Normal View | Magnified View ]

Comparison of GA‐based and PSO‐based ARM algorithms

[ Normal View | Magnified View ]

First execution time comparison

[ Normal View | Magnified View ]

References

Agrawal,, R., & Srikant,, R. (1994). Fast algorithms for mining association rules in large databases. In: Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo, eds. VLDB `94 proceedings of the 20th international conference on very large data bases (pp. 487–499). San Francisco, CA: Morgan Kaufmann Publishers.
Agrawal,, R., Imielinski,, T., & Swami,, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD Record, 22, 207–216.
Alatas,, B., & Akin,, E. (2006). An efficient genetic algorithm for automated mining of both positive and negative quantitative association rules. Soft Computing, 10, 230–237.
Alatas,, B., & Akin,, E. (2008). Rough particle swarm optimization and its applications in data mining. Soft Computing, 12, 1205–1218.
Alatas,, B., Akin,, E., & Karci,, A. (2008). MODENAR: Multi‐objective differential evolution algorithm for mining numeric association rules. Applied Soft Computing, 8, 646–656.
Alcalá‐Fdez,, J., Alcalá,, R., Gacto,, M. J., & Herrera,, F. (2009). Learning the membership function contexts for mining fuzzy association rules by using genetic algorithms. Fuzzy Sets and Systems, 160, 905–921.
Alim,, F., & Ivanov,, K. (2005). Heuristic rules embedded genetic algorithm to solve in‐core fuel management optimization problem. Paper presented at the GECCO `05 Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, Washington, DC: ACM.
Anandhavalli,, M., Ghose,, M. K., Gauthaman,, K., & Boosha,, M. (2010). Global search analysis of spatial gene expression data using genetic algorithm. Recent Trends in Network Security and Applications, 89, 593–602.
Baloković,, M., & Kürster,, M. (2008). An application of heuristic algorithms to radial velocity data from multiple‐planet extrasolar systems. Paper presented at the YSC`15 Proceedings of Contributed Papers (pp. 44–47), Kyivskyi Universyte.
Borgelt,, C. (2012). Frequent item set mining. Data Mining and Knowledge Discovery, 2, 437–456.
Calderaro,, V., Galdi,, V., Graber,, G., & Piccolo,, A. (2015). Deterministic vs heuristic algorithms for eco‐driving application in metro network. Paper presented at the International Conference on Electrical Systems for Aircraft, Railway, Ship Propulsion and Road Vehicles (ESARS) (pp. 1–6), Aachen, Germany: IEEE.
Cano,, A., Luna,, J. M., & Ventura,, S. (2013). High performance evaluation of evolutionary‐mined association rules on GPUs. The Journal of Supercomputing, 66, 1438–1461.
Chen,, C., Hong,, T., Tseng,, V. S., & Lee,, C. (2007). A genetic‐fuzzy mining approach for items with multiple minimum supports. Paper presented at the IEEE International Fuzzy Systems Conference, London, England: IEEE.
Chen,, C., Tseng,, V. S., & Hong,, T. (2008). Cluster‐based evaluation in fuzzy‐genetic data mining. IEEE Transactions on Fuzzy Systems, 16, 249–262.
Chen,, C., Hong,, T., & Tseng,, V. S. (2009a). Speeding up genetic‐fuzzy mining by fuzzy clustering. Paper presented at the IEEE International Conference on Fuzzy Systems (FUZZ‐IEEE), Jeju Island, South Korea: IEEE.
Chen,, C., Hong,, T., & Tseng,, V. S. (2009b). An improved approach to find membership functions and multiple minimum supports in fuzzy data mining. Expert Systems with Applications, 36, 10016–10024.
Chen,, Z., Cai,, S., Song,, Q., & Zhu,, C. (2011). An improved Apriori algorithm based on pruning optimization and transaction reduction. Paper presented at the 2nd International Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC), Deng Leng, China: IEEE.
Dash,, S. R., Dehuri,, S., & Rayaguru,, S. (2013). Discovering interesting rules from biological data using parallel genetic algorithm. Paper presented at the IEEE 3rd International Advance Computing Conferene (IACC), Ghaziabad, India: IEEE.
Deepa Shenoy,, P., Srinivasa,, K. G., Venugopal,, K. R., & Patnaik,, L. M. (2003). Evolutionary approach for mining association rules on dynamic databases. Pacific‐Asia Conference on Knowledge Discovery and Data Mining, 2637, 325–336.
del Jesus,, M. J., Gámez,, J. A., González,, P., & Puerta,, J. M. (2011). On the discovery of association rules by means of evolutionary algorithms. WIREs Data Mining and Knowledge Discovery, 1, 397–415.
Djenouri,, Y., Drias,, H., Habbas,, Z., & Mosteghanemi,, H. (2012). Bees swarm optimization for web association rule mining. Paper presented at the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, Macau, China: IEEE.
Djenouri,, Y., Drias,, H., & Chemchem,, A. (2013). A hybrid bees swarm optimization and Tabu search algorithm for association rule mining. Paper presented at the World Congress on Nature and Biologically Inspired Computing (NaBIC). Fargo, ND: IEEE.
Djenouri,, Y., Bendjoudi,, A., Mehdi,, M. & Nouali‐Taboudjemat,, N. (2014). Parallel association rules mining using GPUS and bees behaviors. Paper presented at IEEE 6th International Conference of Soft Computing and Pattern Recognition (SoCPaR). Tunis, Tunisia: IEEE.
Drias,, H. (2014). Genetic algorithm versus memetic algorithm for association rules mining. Paper presented at the Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC), Porto, Portugal: IEEE.
Du,, F., Rao,, N., Guo,, J., Yuan,, Z., & Wang,, R. (2009). Mining gene network by combined association rules and genetic algorithm. Paper presented at the International Conference on Communications, Circuits and Systems (ICCCAS), Milpitas, CA: IEEE.
Elloumi,, M., & Zomaya,, A. Y. (2014). Biological knowledge discovery handbook: Preprocessing, mining and postprocessing of biological data (1st ed.). Hoboken, NJ: John Wiley & Sons, Inc.
Ghafari,, S. M., & Tjortjis,, C. (2016). Association rules mining by improving the imperialism competitive algorithm (ARMICA). Paper presented at the IFIP AICT Proceedings of 12th International Conference on Artificial Intelligence Applications and Innovations (AIAI), Thessaloniki, Greece: Springer.
Ghafari,, S. M., Fazeli,, M., Patooghy,, A., & Rikhtechi,, L. (2013). Bee‐MMT: A load balancing method for power consumption management in cloud computing. Paper presented at the Sixth International Conference on Contemporary Computing (IC3) (pp. 76–80), Noida, India: IEEE.
Ghosh,, A., & Nath,, B. (2004). Multi‐objective rule mining using genetic algorithms. Information Sciences, 163, 123–133.
Ghosh,, A., Dehuri,, S., & Ghosh,, S. (2008). Multi‐objective evolutionary algorithms for knowledge discovery from databases (Vol. 98). Berlin, Germany: Springer.
Goyal,, V., Sureka,, A., & Patel,, D. (2015). Efficient skyline itemsets mining. Paper presented at the C3S2E `15 Proceedings of the Eighth International Conference on Computer Science & Software Engineering, Yokohama, Japan: ACM.
Guillet,, F., Kuntz,, P., & Lehn,, R. (1999). A genetic algorithm for visualizing networks of association rules. Multiple Approaches to Intelligent Systems, 1611, 145–154.
Guo,, H., & Zhou,, Y. (2009). An algorithm for mining association rules based on improved genetic algorithm and its application. Paper presented at the Third International Conference on Genetic and Evolutionary Computing, Guilin, China: IEEE.
Han,, J., Pei,, J., Yin,, Y., & Mao,, R. (2004). Mining frequent patterns without candidate generation: A frequent‐pattern tree approach. Data Mining and Knowledge Discovery, 8, 53–87.
He,, Y., & Hui,, S. C. (2009). Exploring ant‐based algorithms for gene expression data analysis. Artificial Intelligence in Medicine, 47, 105–119.
Hong,, T., Chen,, C., Wu,, Y., & Lee,, Y.‐C. (2006). A GA‐based fuzzy mining approach to achieve a trade‐off between number of rules and suitability of membership functions. Soft Computing, 10, 1091–1101.
Hong,, Z., & Bian,, F. (2008). A heuristic approach for fast mining association rules in transportation system. Paper presented at the Fifth International Conference on Fuzzy Systems and Knowledge Discovery. Shandong, China: IEEE.
Hong‐yun,, N., Jin‐lan,, L., & De‐gan,, Z. (2008). Self‐optimization rule‐chain mining based on potential association rule directed graph. Paper presented at the International Symposium on Computational Intelligence and Design, Wuhan, China: IEEE.
Hu,, J. & Yang‐Li,, X. (2007). Association rules mining using multi‐objective coevolutionary algorithm. Paper presented at the International Conference on Computational Intelligence and Security Workshop. Harbin, China: IEEE.
Hu,, Y. (2006). Determining membership functions and minimum fuzzy support in finding fuzzy association rules for classification problems. Knowledge‐Based Systems, 19, 57–66.
Iba,, K. (1994). Reactive power optimization by genetic algorithm. IEEE Transactions on Power Apparatus and Systems, 9, 685–692.
Ishibuchi,, H., & Yamamoto,, T. (2004). Fuzzy rule selection by multi‐objective genetic local search algorithms and rule evaluation measures in data mining. Fuzzy Sets and Systems, 141, 59–88.
Jorio,, L. D., Laurent,, A., & Teisseire,, M. (2008). Fast extraction of gradual association rules: A heuristic based method. Paper presented at CSTST`08: International Conference on Soft Computing as Transdisciplinary Science and Technology, Paris, France: ACM.
Kaya,, M., & Alhajj,, R. (2005). Genetic algorithm based framework for mining fuzzy association rules. Fuzzy Sets and Systems, 152, 587–601.
Kaya,, M., & Alhajj,, R. (2006). Utilizing genetic algorithms to optimize membership functions for fuzzy weighted association rules mining. Applied Intelligence, 24, 7–15.
Kaya,, M.t. (2006). Multi‐objective genetic algorithm based approaches for mining optimized fuzzy association rules. Soft Computing, 10, 578–586.
Khabzaoui,, M., Dhaenens,, C., & Ghazali Talbi,, E. (2004). A multicriteria genetic algorithm to analyze DNA microarray data. Paper presented at the Congress on Evolutionary Computation CEC, Portland, OR: IEEE.
Kuo,, R. J., & Shih,, C. W. (2007). Association rule mining through the ant colony system for National Health Insurance Research Database in Taiwan. Computers %26 Mathematics with Applications, 54, 1303–1318.
Kuoa,, R. J., Chaob,, C. M., & Chiu,, Y. T. (2011). Application of particle swarm optimization to association rule mining. Applied Soft Computing, 11, 326–336.
Le,, T., Vo,, B., & Nguyen,, G. (2014). A survey of erasable itemset mining algorithms. Data Mining and Knowledge Discovery, 4, 356–379.
Li,, C., & Yang,, M. (2004). Association rules data mining in manufacturing information system based on genetic algorithms. Paper presented at the 3rd International Conference on Computational Electromagnetics and Its Applications, ICCEA, Beijing, China.
Liang,, R.‐H., Tsai,, S.‐R., Chen,, Y.‐T., & Tseng,, W.‐T. (2011). Optimal power flow by a fuzzy based hybrid particle swarm optimization approach. Electric Power Systems Research, 81, 1466–1474.
Liang,, X., Xue,, C., & Huang,, M. (2010). Improved Apriori algorithm for mining association rules of many diseases. Paper presented at the 5th International Symposium on Intelligence Computation and Applications, ISICA, DaLian, China: Springer.
Liao,, B.. (2009). An improved algorithm of Apriori. Paper presented at the 4th International Symposium, ISICA, Huangshi, China: Springer.
Lim,, A. H. L., Lee,, C. S., & Raman,, M. (2012). Hybrid genetic algorithm and association rules for mining workflow best practices. Expert Systems with Applications, 39, 10544–10551.
Luna,, J. M., Romero,, J. R., & Ventura,, S. (2012). Design and behavior study of a grammar‐guided genetic programming algorithm for mining association rules. Knowledge and Information Systems, 32(1), 53–76.
Luna,, J. M., Romero,, J. R., & Ventura,, S. (2013). Grammar‐based multi‐objective algorithms for mining association rules. Data and Knowledge Engineering, 86, 19–37.
Luna,, J. M., Romero,, J. R., Romero,, C., & Ventura,, S. (2014). Reducing gaps in quantitative association rules: A genetic programming free‐parameter algorithm. Integrated Computer‐Aided Engineering, 21(4), 321–337.
Martín,, D., Rosete,, A., Alcalá‐Fdez,, J., & Herrera,, F. (2014). New multi‐objective evolutionary algorithm for mining a reduced set of interesting positive and negative quantitative association rules. IEEE Transactions on Evolutionary Computation, 18, 54–69.
Martín,, D., Alcalá‐Fdez,, J., Rosete,, A., & Herrera,, F. (2016). NICGAR: A niching genetic algorithm to mine a diverse set of interesting quantitative association rules. Information Sciences, 356, 208–228.
Mata,, J., Alvarez,, J. L., & Riquelme,, J. C. (2001). Mining numeric association rules with genetic algorithms. In V. Kůrková,, R. Neruda,, M. Kárný,, & N. C. Steele, (Eds.), Artificial neural nets and genetic algorithms (pp. 264–267). Vienna, Austria: Springer.
Mata,, J., Alvarez,, J. L., & Riquelme,, J. C. (2002). An evolutionary algorithm to discover numeric association rules. Paper presented at the SAC `02 Proceedings of the ACM Symposium on Applied Computing, New York, NY: ACM.
Minaei‐Bidgoli,, B., Barmaki,, R., & Nasiri,, M. (2013). Mining numerical association rules via multi‐objective genetic algorithms. Information Sciences, 233, 15–24.
Mukhopadhyay,, A., Maulik,, U., Bandyopadhyay,, S., & Coello,, C. A. (2014). Survey of multi objective evolutionary algorithms for data mining: Part II. IEEE Transactions on Evolutionary Computation, 18, 4–19.
Nandhini,, M., Janani,, M., & Sivanandham,, S. N. (2012). Association rule mining using swarm intelligence and domain ontology. Paper presented at the International Conference on Recent Trends In Information Technology (ICRTIT). Chennai, India: IEEE.
Narvekar,, M., & Syed,, S. F. (2015). An optimized algorithm for association rule mining using FP tree. Paper presented at the International Conference on Advanced Computing Technologies and Applications (ICACTA), Mumbai, India: Elsevier.
Nath,, B., Bhattacharyya,, D. K., & Ghosh,, A. (2013). Incremental association rule mining: A survey. Data Mining and Knowledge Discovery, 3, 157–169.
Olmo,, J. L., Luna,, J. M., Romero,, J. R., & Ventura,, S. (2013). Mining association rules with single and multi‐objective grammar guided ant programming. Integrated Computer‐Aided Engineering, 20(3), 217–234.
Orriols‐Puig,, A., Casillas,, J., & Bernadó‐Mansilla,, E. (2008). First approach toward on‐line evolution of association rules with learning classifier systems. Paper presented at the GECCO `08 Proceedings of the 10th Annual Conference on Companion on Genetic and Evolutionary Computation, New York, NY: ACM.
Orriols‐Puig,, A., Casillas,, J., & Mart`,, F. (2009). Unsupervised learning of fuzzy association rules for consumer behavior modeling. Math Ware and Soft Computing, 16, 29–43.
Padillo,, F., Luna,, J. M., Herrera,, F., & Ventura,, S. (2018). Mining association rules on big data through MapReduce genetic programming. Integrated Computer‐Aided Engineering, 25, 31–48.
Palacios,, A. M., Palacios,, J. L., Sanchez,, L., & Alcala‐Fdez,, J. (2015). Genetic learning of the membership functions for mining fuzzy association rules from low quality data. Information Sciences, 295, 358–378.
Pathak,, N., Shah,, V., & Ajmeera,, C. (2014). A memory efficient algorithm with enhance preprocessing technique for web usage mining. Paper presented at the ICTCS `14 Proceedings of the International Conference on Information and Communication Technology for Competitive Strategies, Gujarat, India: ACM.
Prasanna,, K., Seetha,, M., & Kumar,, A. P. S. (2014). CApriori: Conviction based Apriori algorithm for discovering frequent determinant patterns from high dimensional datasets. Paper presented at the International Conference on Science Engineering and Management Research (ICSEMR), Chennai, India: IEEE.
Qodmanan,, H. R., Nasiri,, M., & Minaei‐Bidgoli,, B. (2011). Multi objective association rule mining with genetic algorithm without specifying minimum support and minimum confidence. Expert Systems with Applications, 38, 288–298.
Saggar,, M., Agrawal,, A. K., & Lad,, A. (2004). Optimization of association rule mining using improved genetic algorithms. Paper presented at the IEEE International Conference on Systems Man and Cybernetics, The Hague, Netherlands.
Salleb‐Aouissi,, A., Vrain,, C., & Nortet,, C. (2007). QuantMiner: A genetic algorithm for mining quantitative association rules. Paper presented at the IJCAI`07 Proceedings of the 20th International Joint Conference on Artificial intelligence, San Francisco, CA: Morgan Kaufmann Publishers.
Schoonderwoerd,, R., Bruten,, J. L., Holland,, O. E., & Rothkrantz,, L. J. M. (1996). Ant‐based load balancing in telecommunications networks. Adaptive Behavior, 5, 169–207.
Soysal,, Ö. M. (2015). Association rule mining with mostly associated sequential patterns. Expert Systems with Applications, 42, 2582–2592.
Stojanović,, I., Brajević,, I., Stanimirović,, P. S., Kazakovtsev,, L. A., & Zdravev,, Z. (2017). Application of heuristic and metaheuristic algorithms in solving constrained weber problem with feasible region bounded by arcs. Mathematical Problems in Engineering, 2017, 1–13.
Thilagam,, P. S., & Ananthanarayana,, V. S. (2008). Extraction and optimization of fuzzy association rules using multi‐objective genetic algorithm. Pattern Analysis and Applications, 11, 159–168.
Tian,, Z., & Fong,, S. (2016). Survey of meta‐heuristic algorithms for deep learning training. In O. Baskan (Ed.), Optimization algorithms‐methods and applications. London, England: InTech.
UCI Machine Learning Repository. (2018). UCI Machine Learning Repository data sets. Retrieved from: http://archive.ics.uci.edu/ml/
Ventura,, S., & Luna,, J. M. (2016). Pattern mining with evolutionary algorithms. Cham, Switzerland: Springer.
Vyas,, P., & Chauhan,, A. (2013). Comparative optimization of efficient association rule mining through PSO and GA. Paper presented at the International Conference on Machine Intelligence Research and Advancement, Katra, India: IEEE.
Wang,, B., Zhou,, N., Liu,, D., Zhou,, L., & Wang,, P. (2008). Genetic algorithm‐based rules discovery for networked manufacturing resources management. Paper presented at the 4th International Conference on Wireless Communications, Networking and Mobile Computing. Dalian, China: IEEE.
Wang,, C., & Tjortjis,, C. (2004). PRICES: An efficient algorithm for mining association rules. Intelligent Data Engineering and Automated Learning, 3177, 352–358.
Wang,, M., Zou,, Q., & Liu,, C. (2011). Multi‐dimension association rule mining based on adaptive genetic algorithm. Paper presented at the International Conference on Uncertainty Reasoning and Knowledge Engineering, Bali, Indonesia: IEEE; .
Wang,, T., Liu,, Z., Chen,, Y., Xu,, Y., & Dai,, X. (2014). Load balancing task scheduling based on genetic algorithm in cloud computing. Paper presented at the IEEE 12th International Conference on Dependable, Autonomic and Secure Computing (DASC), IEEE.
Wang,, W., & Bridges,, S. M. (2000). Genetic algorithm optimization of membership functions for mining fuzzy association rules. Paper presented at the International Joint Conference on Information Systems, Fuzzy Theory and Technology, Atlantic City, NJ: Association for Intelligent Machinery.
Yakhchi,, M., Ghafari,, S. M., Yakhchi,, S., Fazeli,, M., & Patooghi,, A. (2015a). Proposing a load balancing method based on cuckoo optimization algorithm for energy management in cloud computing infrastructures. Paper presented at the 6th International Conference on Modeling, Simulation, and Applied Optimization (ICMSAO) (pp. 1–5), Istanbul, Turkey: IEEE.
Yakhchi,, S., Ghafari,, S. M., Yakhchi,, M., Fazeli,, M., & Patooghy,, A. (2015b). ICA‐MMT: A load balancing method in cloud computing environment. Paper presented at the 2nd World Symposium on Web Applications and Networking (WSWAN) (pp. 1–7), Sousse, Tunisia: IEEE.
Yan,, X., Zhang,, C., & Zhang,, S. (2009). Genetic algorithm‐based strategy for identifying association rules without specifying actual minimum support. Expert Systems with Applications, 36, 3066–3076.
Yu,, H., Wen,, J., Wang,, H., & Jun,, L. (2011). An improved Apriori algorithm based on the Boolean matrix and Hadoop. Procedia Engineering, 15, 1827–1831.
Yuan,, J., & Ding,, S. (2012). Research and improvement on association rule algorithm based on FP‐growth. Paper presented at the International Conference on Web Information Systems and Mining, WISM, Taiyuan, China: Springer.
Zhang,, M., & He,, C. (2010). Survey on association rules mining algorithms. Advancing Computing, Communication, Control and Management, 56, 111–118.
Zhu,, W., Wang,, J., Cao,, H., & Zhang,, Y. (2008). A novel association rule decision algorithm based on ant Colony optimization algorithm for ball mill pulverizing system. Paper presented at the International Conference on Computer Science and Software Engineering, Hubei, China: IEEE.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts