LEGAL-tree: a lexicographic multi-objective genetic algorithm for decision tree induction

ABSTRACT

Decision trees are widely disseminated as an effective solution for classification tasks. Decision tree induction algorithms have some limitations though, due to the typical strategy they implement: recursive top-down partitioning through a greedy split evaluation. This strategy is limiting in the sense that there is quality loss while the partitioning process occurs, creating statistically insignificant rules. In order to prevent the greedy strategy and to avoid converging to local optima, we present a novel Genetic Algorithm for decision tree induction based on a lexicographic multi-objective approach, and we compare it with the most well-known algorithm for decision tree induction, J48, over distinct public datasets. The results show the feasibility of using this technique as a means to avoid the previously described problems, reporting not only a comparable accuracy but also, importantly, a significantly simpler classification model in the employed datasets.

REFERENCES

• 1: Martijn C. J. Bot , William B. Langdon, Application of Genetic Programming to Induction of Linear Classification Trees, Proceedings of the European Conference on Genetic Programming, p.247-258, April 15-16, 2000
• 2: Breiman, L., Friedman, J., Olshen, R., Stone, C. 1984 Classification and Regression Trees. Wadsworth.
• 3: Buntine, W. 1993. Learning Classification Trees. Statistics and Computing, v. 2 (2), 63--73.
• 4: Coello, C., Veldhuizen, D., Lamont, G. 2002 Evolutionary Algorithms for Solving Multi-Objective Problems. Springer.
• 5: Pedro Domingos, The Role of Occam‘s Razor in Knowledge Discovery, Data Mining and Knowledge Discovery, v.3 n.4, p.409-425, December 1999 [doi>10.1023/A:1009868929893]
• 6: Jesús K. Estrada-Gil , Juan C. Fernández-López , Enrique Hernández-Lemus , Irma Silva-Zolezzi , Alfredo Hidalgo-Miranda , Gerardo Jiménez-Sánchez , Edgar E. Vallejo-Clemente, GPDTI, Bioinformatics, v.23 n.13, p.i167-i174, July 2007 [doi>10.1093/bioinformatics/btm205]
• 7: Freitas, Alex A. 2007. A Review of Evolutionary Algorithms for Data Mining. Soft Computing for Knowledge Discovery and Data Mining. Springer-Verlag New York, Inc., 79--111.
• 8: Alex A. Freitas, A critical review of multi-objective optimization in data mining: a position paper, ACM SIGKDD Explorations Newsletter, v.6 n.2, December 2004 [doi>10.1145/1046456.1046467]
• 9: Freitas, Alex A., Wieser, Daniela C., Apweiler, Rolf. 2008. On the importance of comprehensible classification models for protein function prediction. To appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics.
• 10: Yoav Freund , Llew Mason, The Alternating Decision Tree Learning Algorithm, Proceedings of the Sixteenth International Conference on Machine Learning, p.124-133, June 27-30, 1999
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: John R. Koza, Concept Formation and Decision Tree Induction Using the Genetic Programming Paradigm, Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, p.124-128, October 01-03, 1990
• 13: Loveard, T., Ciesielski, V. 2001. Representing classification problems in genetic programming. Proceedings of the 2001 Congress on Evolutionary Computation, 1070--1077.
• 14: Loveard, T., Ciesielski, V. 2002. Employing nominal attributes in classification using genetic programming. Proceedings of the Fourth Asia-Pacific Conference on Simulated Evolution and Learning, 487--491.
• 15: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 16: Claude Nadeau , Yoshua Bengio, Inference for the Generalization Error, Machine Learning, v.52 n.3, p.239-281, September 2003 [doi>10.1023/A:1024068626366]
• 17: Newman, D. J., Hettich, S., Blake, C. L., Merz, C. J. 1998. UCI Repository of Machine Learning Databases, http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 18: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 19: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 20: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 21: Quinlan, J. R., 1996. Bagging, boosting, and C4.5. In Proceedings of the Fourteenth National Conference on Artificial Intelligence.
• 22: Shirasaka, M., Zhao, Q., Hammarmi, O., Kuroda, K., Saito, K. 1998. Automatic design of binary decision trees based on genetic programming. Proceedings of the Second Asia-Pacific Conference on Simulated Evolution and Learning.
• 23: Tür, G., Güvenir, H. A. 1996. Decision tree induction using genetic programming. Proceedings of the Fifth Turkish Symposium on Artificial Intelligence and Neural Networks.
• 24: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 25: Huimin Zhao, A multi-objective genetic programming approach to developing Pareto optimal decision trees, Decision Support Systems, v.43 n.3, p.809-826, April, 2007 [doi>10.1016/j.dss.2006.12.011]
• 26: Zhao, Q., Shirasaka, M. 1999. A study on evolutionary design of binary decision trees, Proceedings of the 1999 Congress on Evolutionary Computation, 1988--1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms

Keywords:
data mining, decision tree induction, evolutionary algorithms, lexicographic multi-objective genetic algorithms