More Web Proxy on the site http://driver.im/

article

QAR-CIP-NSGA-II: A new multi-objective evolutionary algorithm to mine quantitative association rules

Authors:

J. Alcalá-Fdez,

F. HerreraAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 258

Pages 1 - 28

https://doi.org/10.1016/j.ins.2013.09.009

Published: 01 February 2014 Publication History

Abstract

Some researchers have framed the extraction of association rules as a multi-objective problem, jointly optimizing several measures to obtain a set with more interesting and accurate rules. In this paper, we propose a new multi-objective evolutionary model which maximizes the comprehensibility, interestingness and performance of the objectives in order to mine a set of quantitative association rules with a good trade-off between interpretability and accuracy. To accomplish this, the model extends the well-known Multi-objective Evolutionary Algorithm Non-dominated Sorting Genetic Algorithm II to perform an evolutionary learning of the intervals of the attributes and a condition selection for each rule. Moreover, this proposal introduces an external population and a restarting process to the evolutionary model in order to store all the nondominated rules found and improve the diversity of the rule set obtained. The results obtained over real-world datasets demonstrate the effectiveness of the proposed approach.

References

[1]

R. Agrawal, T. Imielinski, A. Swami, Mining association rules between sets of items in large databases, in: SIGMOD, Washington DC, 1993.

[2]

R. Agrawal, R. Srikant, Fast algorithms formining association rules, in: International Conference Large Data Bases, Santiago de Chile, Chile, 1994.

[3]

Ahn, K.-I. and Kim, J.-Y., Efficient mining of frequent itemsets and a measure of interest for association rule mining. Journal of Information & Knowledge Management. v3 i3. 245-257.

[4]

Alatas, B. and Akin, E., An efficient genetic algorithm for automated mining of both positive and negative quantitative association rules. Soft Computing. v10 i3. 230-237.

[5]

Alatas, B. and Akin, E., Modenar: multi-objective differential evolution algorithm for mining numeric association rules. Applied Soft Computing. v8 i1.

[6]

Alcala-Fdez, J., Alcala, R. and Herrera, F., A fuzzy association rule-based classification model for high-dimensional problems with genetic rule selection and lateral tuning. IEEE Transactions on Fuzzy Systems. v19 i5. 857-872.

[7]

Alcala-Fdez, J., Fernandez, A., Luego, J., Derrac, J., Garcia, S., Sanchez, L. and Herrera, F., KEEL data-mining software tool: data set repository, integration of algorithms and experimental analysis framework. Journal of Multiple-Valued Logic and Soft Computing. v17 i2-3. 255-287.

[8]

Alcala-Fdez, J., Flugy-Pape, N., Bonarini, A. and Herrera, F., Analysis of the effectiveness of the genetic algorithms based on extraction of association rules. Fundamenta Informaticae. v98 i1. 1001-1014.

[9]

Alcala-Fdez, J., Sanchez, L., Garcia, S., del Jesus, M., Ventura, S., Garrell, J.O.J., Romero, C., Bacardit, J., Rivas, V., Fernandez, J. and Herrera, F., KEEL: A software tool to assess evolutionary algorithms to data mining problems. Soft Computing. v13 i3. 307-318.

[10]

Measuring the accuracy and interest of association rules: a new framework. Intelligent Data Analysis. v6 i3. 221-235.

[11]

C. Borgelt, Efficient implementations of apriori and eclat, in: Workshop on Frequent Itemset Mining Implementations, vol. 90, CEUR Workshop Proc., Florida, USA, 2003.

[12]

Brin, S., Motwani, R., Ullman, J. and Tsur, S., Dynamic itemset counting and implication rules for market basket data. ACM SIGMOD Record. v26 i2. 255-264.

[13]

Finding Pareto-front membership functions in fuzzy data mining. International Journal of Computational Intelligence Systems. v5 i2. 343-354.

[14]

Coello, C., Lamont, G. and Veldhuizen, D.V., Evolutionary Algorithms for Solving Multi-Objective Problems. 2002. Kluwer Academic Publishers.

[15]

C. Coello, G. Toscano, A micro-genetic algorithm for multiobjective optimization, in: First International Conference on Evolutionary Multi-Criterion Optimization, LNCS 1993, London, UK, 2001, pp. 126-140.

[16]

D. Corne, N. Jerram, J. Knowles, M. Oates, PESA-II: region based selection in evolutionary multiobjective optimization, in: Genetic and Evolutionary Computation Conf., San Francisco, CA, 2001.

[17]

D. Corne, J. Knowles, M. Oates, The pareto envelopebased selection algorithm for multiobjective optimization, in: Parallel Problem Solving from Nature, LNCS 1917, Paris, France, 2000, pp. 839-848.

[18]

Deb, K., Multi-Objective Optimization using Evolutionary Algorithms. 2001. Kluwer Academic.

[19]

Deb, K., Agrawal, S., Pratab, A. and Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions Evolutionary Computation. v6 i2. 182-197.

[20]

Deb, K., Mohan, M. and Mishra, S., Evaluating the epsilon-domination based multiobjective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolutionary Computation. v13 i4. 501-525.

[21]

Demsar, J., Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research. v7. 1-30.

Digital Library

[22]

Elhossini, A., Areibi, S. and Dony, R., Strength Pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization. Evolutionary Computation. v18 i1. 127-156.

[23]

M. Erickson, A. Mayer, J. Horn, The niched Pareto genetic Algorithm 2 applied to the design of groundwater remediation systems, in: First International Conference on Evolutionary MultiCriterion Optimization, LNCS 1993, London, UK, 2001, pp. 681-695.

[24]

M. Fidelis, H. Lopes, A. Freitas, Discovering comprehensible classification rules with a genetic algorithm, in: Proceedings of the 2000 Congress on Evolutionary Computation, CA, USA, 2000.

[25]

Finner, H., On a monotonicity problem in step-down multiple test procedures. Journal of the American Statistical Association. v88 i423. 920-923.

[26]

C. Fonseca, P. Fleming, Genetic algorithms for multiobjective optimization: formulation, discussion and generalization, in: 5th International Conference on Genetic Algorithms, San Mateo, CA, 1993.

Digital Library

[27]

C. Fonseca, L. Paquete, M. Lopez-Ibanez, An improved dimension-sweep algorithm for the hypervolume indicator, in: IEEE Congress on Evolutionary Computation, Vancouver, Canada, 2006.

[28]

Friedman, M., The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association. v32 i200. 675-701.

[29]

Garcia, S., Fernandez, A., Luengo, J. and Herrera, F., A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Computing. v13 i10. 959-977.

[30]

Garcia, S. and Herrera, F., An extension on statistical comparisons of classifiers over multiple data sets for all pairwise comparisons. Journal of Machine Learning Research. v9. 2579-2596.

[31]

Garcia, S., Molina, D., Lozano, M. and Herrera, F., A study on the use of non-parametric tests for analyzing the evolutionary algorithms behaviour: A case study on the cec 2005 special session on real parameter optimization. Journal of Heuristics. v15. 617-644.

[32]

Geng, L. and Hamilton, H., Interestingness measures for data mining: a survey. ACM Computing Surveys. v38 i3. 1-32.

[33]

Ghosh, A. and Nath, B., Multi-objective rule mining using genetic algorithms. Information Sciences. v163 i1-3. 123-133.

[34]

Han, J. and Kamber, M., Data Mining: Concepts and Techniques. 2006. second ed. Morgan Kaufmann.

[35]

Holm, S., A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics. v6. 65-70.

[36]

Hong, T.-P., Chen, C.-H., Lee, Y.-C. and Wu, Y.-L., Genetic-fuzzy data mining with divide-and-conquer strategy. IEEE Transactions on Evolutionary Computation. v12 i2. 252-265.

[37]

J. Horn, N. Nafpliotis, D. Goldberg, A niched pareto genetic algorithm for multiobjective optimization, in: First IEEE Conf. on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Piscataway, NJ, 1994.

[38]

Approximations of the critical region of the Friedman statistic. Communications in Statistics - Theory and Methods. v9 i6. 571-595.

[39]

Janssens, D., Brijs, T., Vanhoof, K. and Wets, G., Evaluating the performance of cost-based discretization versus entropy and error-based discretization. Computers and Operations Research. v33 i11. 3107-3123.

[40]

Knowles, J. and Corne, D., Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation. v8 i2. 149-172.

[41]

HCS: a new local search strategy for memetic multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation. v14 i1. 112-132.

[42]

Lee, C.-H., A hellinger-based discretization method for numerical attributes in classification learning. Knowledge-Based Systems. v20 i4. 419-425.

[43]

Li, H. and Zhang, Q., Multiobjective optimization problems with complicated Pareto sets MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation. v13 i2. 284-302.

[44]

Liu, H., Hussain, F., Tan, C. and Dash, M., Discretization: an enabling technique. Data Mining and Knowledge Discovery. v6 i4. 393-423.

[45]

J. Mata, J. Alvarez, J.J. Riquelme, Mining numeric association rules with genetic algorithms, in: 5th International Conference on Artificial Neural Networks and Genetic Algorithms, Taipei, Taiwan, 2001.

[46]

J. Mata, J. Alvarez, J. Riquelme, An evolutionary algorithm to discover numeric association rules, in: ACM Symposium on Applied Computing, Madrid, Spain, 2002.

[47]

O. Mersmann, emoa: Evolutionary Multiobjective Optimization Algorithms, 2013. <http://cran.r-project.org/web/packages/emoa/>.

[48]

G. Piatetsky-Shapiro, Discovery, analysis, and presentation of strong rules, in: C. MIT Press (Ed.), Knowledge Discovery in Databases, Cambridge, MA, 1991, pp. 229-248.

[49]

Qodmanan, H., Nasiri, M. and Minaei-Bidgoli, B., Multi objective association rule mining with genetic algorithm without specifying minimum support and minimum confidence. Expert Systems with Applications. v38. 288-298.

[50]

S. Ramaswamy, S. Mahajan, A. Silberschatz, On the discovery of interesting patterns in association rules, in: 24rd International Conference on Very Large Data Bases, San Francisco, CA, USA, 1998.

[51]

R. Rosenberg, Simulation of genetic populations with biochemical properties, Master's thesis, University of Michigan, Ann Harbor, Michigan, 1967.

[52]

J. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in: First International Conference on Genetic Algorithms, Pittsburgh, USA, 1985.

[53]

Sheskin, D., Handbook of Parametric and Nonparametric Statistical Procedures. 2003. Chapman & Hall/CRC, London, UK/Boca Raton.

[54]

Shortliffe, E. and Buchanan, B., A model of inexact reasoning in medicine. Mathematical Biosciences. v23 i3-4. 351-379.

[55]

Silverstein, C., Brin, S. and Motwani, R., Beyond market baskets: generalizing association rules to dependence rules. Data Mining and Knowledge Discovery. v2 i1. 39-68.

[56]

R. Srikant, R. Agrawal, Mining quantitative association rules in large relational tables, in: ACM SIGMOD International Conference on Management of data (SIGMOD96), Montreal, Quebec, Canada, 1996.

Digital Library

[57]

Srinivas, N. and Deb, K., Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation. v2 i3. 221-248.

[58]

Srinivasan, S. and Ramakrishnan, S., Evolutionary multi objective optimization for rule mining: a review. Artificial Intelligence Review. v36 i3. 205-248.

[59]

T. Tanino, M. Tanaka, C. Hojo, An interactive multicriteria decision making method by using a genetic algorithm, in: 2nd International Conference on Systems Science and Systems Engineering, 1993.

[60]

Tsai, C., Lee, C. and Yang, W., A discretization algorithm based on class-attribute contingency coefficient. Information Science. v178 i3. 714-731.

[61]

Wang, C.-H., Hong, T.-P. and Tseng, S.-S., Integrating membership functions and fuzzy rule sets from multiple knowledge sources. Fuzzy Sets and Systems. v112 i1. 141-154.

[62]

Wilcoxon, F., Individual comparisons by ranking methods. Biometrics. v1 i6. 80-83.

[63]

Yan, X., Zhang, C. and Zhang, S., Genetic algorithm-based strategy for identifying association rules without specifying actual minimum support. Expert Systems with Applications. v36 i2. 3066-3076.

[64]

Zaki, M., Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering. v12 i3. 372-390.

[65]

Zhang, C. and Zhang, S., . 2002. Lecture Notes in Computer Science, LNAI 2307, 2002.Springer-Verlag, Berlin.

[66]

Zhang, Q. and Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation. v11 i6. 712-731.

[67]

Zhou, A., Qu, B.-Y., Li, H., Zhao, S.-Z., Suganthan, P.-N. and Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm and Evolutionary Computation. v1 i1. 32-49.

[68]

E. Zitzler, S. Kunzli, Indicator-based selection in multiobjective search, in: Parallel Problem Solving from Nature, LNCS 3242, 2004, pp. 832-842.

[69]

E. Zitzler, M. Laumanns, L. Thiele, SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization, in: Evolutionary Methods for Design, Optimization and Control with applications to Industrial Problems, Barcelona, Spain, 2001.

[70]

Zitzler, E. and Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions Evolutionary Computation. v3 i4. 257-271.

[71]

Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M. and da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation. v7 i2. 117-132.

Cited By

Berteloot TKhoury RDurand A(2024)Association Rules Mining with Auto-encodersIntelligent Data Engineering and Automated Learning – IDEAL 202410.1007/978-3-031-77731-8_5(51-62)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-77731-8_5
Ma HZhang YSun SLiu TShan Y(2023)A comprehensive survey on NSGA-II for multi-objective optimization and applicationsArtificial Intelligence Review10.1007/s10462-023-10526-z56:12(15217-15270)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1007/s10462-023-10526-z
Liu MYang ZGuo YJiang JYang K(2022)MICAR: nonlinear association rule mining based on maximal information coefficientKnowledge and Information Systems10.1007/s10115-022-01730-464:11(3017-3042)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10115-022-01730-4
Show More Cited By

QAR-CIP-NSGA-II: A new multi-objective evolutionary algorithm to mine quantitative association rules
1. Computing methodologies
2. Information systems
  1. Information systems applications

Recommendations

Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics

Evolutionary multiobjective optimization (EMO) is an active research area in the field of evolutionary computation. EMO algorithms are designed to find a non-dominated solution set that approximates the entire Pareto front of a multiobjective ...
Multi-Objective Multiagent Credit Assignment in NSGA-II Using Difference Evaluations
AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems

Determining the contribution of an agent to a system-level objective function (credit assignment) is a key area of research in cooperative multiagent systems. Multi-objective optimization is a growing area of research, though mostly focused on single ...
Empirical Analysis of Using Weighted Sum Fitness Functions in NSGA-II for Many-Objective 0/1 Knapsack Problems
UKSIM '09: Proceedings of the UKSim 2009: 11th International Conference on Computer Modelling and Simulation

Handling of many-objective problems is a hot issue in the evolutionary multiobjective optimization (EMO) community. It is well-known that frequently-used EMO algorithms such as NSGA-II and SPEA do not work well on many-objective problems whereas they ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 258, Issue

February, 2014

463 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2013.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 February 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Berteloot TKhoury RDurand A(2024)Association Rules Mining with Auto-encodersIntelligent Data Engineering and Automated Learning – IDEAL 202410.1007/978-3-031-77731-8_5(51-62)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-77731-8_5
Ma HZhang YSun SLiu TShan Y(2023)A comprehensive survey on NSGA-II for multi-objective optimization and applicationsArtificial Intelligence Review10.1007/s10462-023-10526-z56:12(15217-15270)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1007/s10462-023-10526-z
Liu MYang ZGuo YJiang JYang K(2022)MICAR: nonlinear association rule mining based on maximal information coefficientKnowledge and Information Systems10.1007/s10115-022-01730-464:11(3017-3042)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10115-022-01730-4
Yacoubi SManita GAmdouni HMirjalili SKorbaa O(2022)A modified multi-objective slime mould algorithm with orthogonal learning for numerical association rules miningNeural Computing and Applications10.1007/s00521-022-07985-w35:8(6125-6151)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.1007/s00521-022-07985-w
Ledmi MMoumen HSiam AHaouassi HAzizi N(2021)A Discrete Crow Search Algorithm for Mining Quantitative Association RulesInternational Journal of Swarm Intelligence Research10.4018/IJSIR.202110010612:4(101-124)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.4018/IJSIR.2021100106
Wang XYuan JHua SDuan B(2020)Optimization of Wheel Reprofiling Based on the Improved NSGA-IIComplexity10.1155/2020/88738762020Online publication date: 23-Dec-2020
https://dl.acm.org/doi/10.1155/2020/8873876
Moslehi FHaeri AMartínez-Álvarez F(2019)A novel hybrid GA–PSO framework for mining quantitative association rulesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-04226-624:6(4645-4666)Online publication date: 20-Jul-2019
https://dl.acm.org/doi/10.1007/s00500-019-04226-6
Xia MZhang CWeng LLiu JWang YTiwari STrivedi MKohle M(2018)Robot path planning based on multi-objective optimization with local searchJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-16971135:2(1755-1764)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/JIFS-169711
Almasi MSaniee Abadeh M(2018)A new MapReduce associative classifier based on a new storage format for large-scale imbalanced dataCluster Computing10.1007/s10586-018-2812-921:4(1821-1847)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10586-018-2812-9
Padillo FLuna JHerrera FVentura S(2017)Mining association rules on Big Data through MapReduce genetic programmingIntegrated Computer-Aided Engineering10.3233/ICA-17055525:1(31-48)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/ICA-170555
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents