You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
Ant colony optimization (ACO) algorithms have been successfully applied to discover a list of classification rules. In general, these algorithms follow a sequential covering strategy, where a single rule is discovered at each iteration of the algorithm in order to build a list of rules. The sequential covering strategy has the drawback of not coping with the problem of rule interaction, i.e., the outcome of a rule affects the rules that can be discovered subsequently since the search space is modified due to the removal of examples covered by previous rules. This paper proposes a new sequential covering strategy for ACO classification algorithms to mitigate the problem of rule interaction, where the order of the rules is implicitly encoded as pheromone values and the search is guided by the quality of a candidate list of rules. Our experiments using 18 publicly available data sets show that the predictive accuracy obtained by a new ACO classification algorithm implementing the proposed sequential covering strategy is statistically significantly higher than the predictive accuracy of state-of-the-art rule induction classification algorithms.
[1] G. Piatetsky-Shapiro and W. Frawley, Knowledge Discovery in Databases. AAAI Press, 1991, 525 pages.
[2] U. Fayyad, G. Piatetsky-Shapiro, and P. Smith, “From data mining to knowledge discovery: an overview,” in Advances in Knowledge Discovery & Data Mining, U. Fayyad, G. Piatetsky-Shapiro, P. Smith, and R. Uthurusamy, Eds. MIT Press, 1996, pp. 1-34.
[3] V. Dhar, D. Chou, and F. Provost, “Discovering interesting patterns for investment decision making with GLOWER - a genetic learner overlaid with entropy reduction,” Data Mining and Knowledge Discovery, vol. 4, no. 4, pp. 251-280, 2000.
[4] A. Freitas, D. Wieser, and R. Apweiler, “On the importance of comprehensible classification models for protein function prediction,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 7, no. 1, pp. 172-182, 2010.
[5] M. Dorigo and G. Di Caro, “The Ant Colony Optimization meta-heuristic,” in New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, Eds., 1999, pp. 11-32.
[6] M. Dorigo, G. Di Caro, and L. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life, vol. 5, no. 2, pp. 137-172, 1999.
[7] M. Dorigo and T. Stu¨tzle, Ant Colony Optimization. MIT Press, 2004, 328 pages.
[8] R. Parpinelli, H. Lopes, and A. Freitas, “An ant colony based system for data mining: applications to medical data,” in Genetic and Evolutionary Computation Conference (GECCO-2001), 2001, pp. 791-798.
[9] --, “Data mining with an ant colony optimization algorithm,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 4, pp. 321-332, 2002.
[10] D. Martens, B. Baesens, and T. Fawcett, “Editorial survey: swarm intelligence for data mining,” Machine Learning, vol. 82, no. 1, pp. 1-42, 2011.
[11] B. Liu, H. Abbass, and B. McKay, “Density-based heuristic for rule discovery with ant-miner,” in 6th Australasia-Japan joint workshop on intelligent and evolutionary systems (AJWIS-2002), 2002, pp. 180-184.
[12] --, “Classification rule discovery with ant colony optimization,” in Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology (IAT-2003), 2003, pp. 83-88.
[13] A. Chan and A. Freitas, “A new classification-rule pruning procedure for an ant colony algorithm,” in Artificial Evolution (Proceedings of the EA-2005), ser. Lecture Notes in Artificial Intelligence 3871, 2005, pp. 25-36.
[14] F. Otero, A. Freitas, and C. Johnson, “cAnt-Miner: an ant colony classification algorithm to cope with continuous attributes,” in Proceedings of the 6th International Conference on Swarm Intelligence (ANTS 2008), Lecture Notes in Computer Science 5217, M. Dorigo, M. Birattari, C. Blum, M. Clerc, T. Stu¨tzle, and A. Winfield, Eds. Springer-Verlag, 2008, pp. 48-59.
[15] --, “Handling continuous attributes in ant colony classification algorithms,” in Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Data Mining (CIDM 2009). IEEE, 2009, pp. 225-231.
[16] D. Martens, M. D. Backer, R. Haesen, J. Vanthienen, M. Snoeck, and B. Baesens, “Classification with ant colony optimization,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 5, pp. 651-665, 2007.
[17] K. Salama and A. Abdelbar, “Extensions to the Ant-Miner Classification Rule Discovery Algorithm,” in Proceedings of the 7th International Conference on Swarm Intelligence (ANTS 2010), Lecture Notes in Computer Science 6234, 2010, pp. 167-178.
[18] K. Salama, A. Abdelbar, and A. Freitas, “Multiple pheromone types and other extensions to the ant-miner classification rule discovery algorithm,” Swarm Intelligence, vol. 5, no. 3-4, pp. 149-182, 2011.
[19] A. Gonza´lez, R. Pe´rez, and J. Verdegay, “Learning the structure of a fuzzy rule: a genetic approach,” Fuzzy System and Artificial Intelligence, vol. 3, pp. 57-70, 1994.
[20] G. Venturini, “SIA: A supervised inductive algorithm with genetic search for learning attributes based concepts,” Machine Learning: ECML-93, pp. 280-296, 1993.
[21] L. Booker, “Intelligent Behavior as an Adaptation to the Task Environment,” Ph.D. dissertation, University of Michigan, 1982, 342 pages.
[22] L. Booker, D. Goldberg, and J. Holland, “Classifier Systems and Genetic Algorithms,” Artificial Intelligence, pp. 235-282, 1989.
[23] S. Smith, “A learning system based on genetic adaptive algorithms,” Ph.D. dissertation, University of Pittsburgh, 1980, 214 pages.
[24] --, “Flexible learning of problem solving heuristics through adaptive search,” in Proceedings of the 8th International Conference on Artificial Intelligence. Morgan Kaufmann, 1983, pp. 422-425.
[25] A. Freitas, Data Mining and Knowledge Discovery with Evolutionary Algorithms. Springer-Verlag, 2002, 264 pages.
[26] T. Stu¨tzle and H. Hoos, “Improvements on the Ant System: Introducing MAX -MIN ant system,” in Proceedings of Artificial Neural Nets and Genetic Algorithms 1997, 1998, pp. 245-249.
[27] --, “MAX -MIN ant system,” Future Generation Computer Systems, vol. 16, no. 8, pp. 889-914, 2000.
[28] A. Asuncion and D. Newman, “UCI Machine Learning Repository,” 2010, University of California, Irvine, School of Information and Computer Sciences. [Online]. Available: http://www.ics.uci.edu/∼mlearn/MLRepository.html
[29] U. Fayyad and K. Irani, “On the Handling of Continuous-Valued Attributes in Decision Tree Generation,” Machine Learning, vol. 8, pp. 87-102, 1992.
[30] N. Holden and A. Freitas, “A hybrid PSO/ACO algorithm for discovering classification rules in data mining,” Journal of Artificial Evolution and Applications (JAEA), special issue on Particle Swarms: The Second Decade, 2008, 11 pages. [Online]. Available: http://dx.doi.org/10.1155/2008/316145
[31] P. Clark and T. Niblett, “The CN2 rule induction algorithm,” Machine Learning, vol. 3, no. 4, pp. 261-283, 1989.
[32] J. Quinlan, C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993, 302 pages.
[33] --, “Improved Use of Continuous Attributes in C4.5,” Artificial Intelligence Research, vol. 7, pp. 77-90, 1996.
[34] E. Frank and I. Witten, “Generating Accurate Rule Sets Without Global Optimization,” in Proceedings of the Fifteenth International Conference on Machine Learning, J. Shavlik, Ed. Morgan Kaufmann, 1998, pp. 144-151.
[35] I. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, 2nd ed. Morgan Kaufmann, 2005, 560 pages.
[36] W. Cohen, “Fast effective rule induction,” in Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann, 1995, pp. 115-123.
[37] M. Birattari, T. Stu¨tzle, L. Paquete, and K. Varrentrapp, “A Racing Algorithm for Configuring Metaheuristics,” in Genetic and Evolutionary Computation Conference (GECCO-2002), 2002, pp. 11-18.
[38] W. Conover, Practical Nonparametric Statistics. John Wiley & Sons, 1999, 592 pages.
[39] J. Demsˇar, “Statistical Comparisons of Classifiers over Multiple Data Sets,” Machine Learning Research, vol. 7, pp. 1-30, 2006.
[40] S. Garc´ıa and F. Herrera, “An Extension on 'Statistical Comparisons of Classifiers over Multiple Data Sets' for all Pairwise Comparisons,” Machine Learning Research, vol. 9, pp. 2677-2694, 2008.
[41] J. Huysmans, K. Dejaeger, C. Mues, J. Vanthienen, and B. Baesens, “An empirical evaluation of the comprehensibility of decision table, tree and rule based predictive models,” Decision Support Systems, vol. 51, no. 1, pp. 141-154, 2011.
[42] B. Baesens, T. Van Gestel, S. Viaene, M. Stepanova, J. Suykens, and J. Vanthienen, “Benchmarking state-of-the-art classification algorithms for credit scoring,” The Journal of the Operational Research Society, vol. 54, no. 6, pp. 627-635, 2003.
[43] D. Hosmer and S. Lemeshow, Applied Logistic Regression, 2nd ed. John Wiley & Sons, 2000, 392 pages.
[44] G. Fung, S. Sandilya, and R. Bharat Rao, “Rule extraction from linear support vector machines,” in Proc. of the th11 ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD-05), 2005, pp. 32-40.
[45] H. Nu´n˜ez, C. Angulo, and A. Catala`, “Rule extraction from support vector machines,” in Proc. of the European Symposium on Artificial Neural Networks (ESANN-02), 2002, pp. 107-112.