Constructive induction and genetic algorithms for learning concepts with complex interaction

ABSTRACT

Constructive Induction is the process of transforming the original representation of hard concepts with complex interaction into a representation that highlights regularities. Most Constructive Induction methods apply a greedy strategy to find interacting attributes and then construct functions over them. This approach fails when complex interaction exists among attributes and the search space has high variation. In this paper, we illustrate the importance of applying Genetic Algorithms as a global search strategy for these methods and present MFE2/GA¹, while comparing it with other GA-based Constructive Induction methods. We empirically analyze our Genetic Algorithm's operators and compare MFE2/GA with greedy-based methods. We also performed experiments to evaluate the presented method when concept has attributes participating in more than one complex interaction. In experiments that are conducted, MFE2/GA successfully finds interacting attributes and constructs functions to represent interactions. Results show the advantage of using Genetic Algorithms for Constructive Induction when compared with greedy-based methods.

REFERENCES

• 1: D. W. Aha. Incremental constructive induction: An instance-based approach. In Proc. of the Eighth International Workshop on Machine Learning, pages 117--121, Evanston, Illinois, 1991. Morgan Kaufmann.
• 2: H. Bensusan and I. Kuscu. Constructive induction using genetic programming. In T. Fogarty and G. Venturini, editors, Proc. of Evolutionary Computing and Machine Learning Workshop (ICML'96), Bari, Italy, July 1996.
• 3: C. Blake and C. Merz. UCI repository of machine learning databases, 1998.
• 4: Kenneth A. De Jong , William M. Spears , Diana F. Gordon, Using Genetic Algorithms for Concept Learning, Machine Learning, v.13 n.2-3, p.161-188, Nov./Dec. 1993 [doi>10.1007/BF00993042]
• 5: T. G. Dietterich and R. S. Michalski. Inductive learning of structural descriptions: Evaluation criteria and comparative review of selected methods. Artificial Intelligence, 16(3):257--294, July 1981.
• 6: Alex A. Freitas, Understanding the Crucial Role of AttributeInteraction in Data Mining, Artificial Intelligence Review, v.16 n.3, p.177-199, November, 2001 [doi>10.1023/A:1011996210207 ]
• 7: Alex A. Freitas, Data Mining and Knowledge Discovery with Evolutionary Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 10: Robert C. Holte, Very Simple Classification Rules Perform Well on Most Commonly Used Datasets, Machine Learning, v.11 n.1, p.63-90, April 1993 [doi>10.1023/A:1022631118932]
• 11: Y. Hu. A genetic programming approach to constructive induction. In J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo, editors, Proc. of the Third Annual Genetic Programming Conference, pages 146--151, University of Wisconsin, Madison, Wisconsin, USA, July 1998. Morgan Kauffman.
• 12: Y. Hu and D. F. Kibler. Generation of attributes for learning algorithms. In Proc. of the Thirteenth National Conference on Artificial Intelligence, pages 806--811. AAAI, The MIT Press, August 1996.
• 13: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 14: Otavio Larsen , Alex A. Freitas , Júlio C. Nievola, Constructing X-of-n Attributes With A Genetic Algorithm, Proceedings of the Genetic and Evolutionary Computation Conference, p.1268, July 09-13, 2002
• 15: D. Levine. Users guide to the PGAPack parallel genetic algorithm library. Technical Report 18, Argonne National Laboratory, 1996.
• 16: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 17: F. E. B. Otero, M. M. S. Silva, A. A. Freitas, and J. C. Nievola. Genetic programming for attribute construction in data mining. In C. Ryan, T. Soule, M. Keijzer, E. P. K. Tsang, R. Poli, and E. Costa, editors, Proc. of the Sixth European Conference in Genetic Programming, volume 2610 of Lecture Notes in Computer Science, pages 384--393. Springer-Verlag, April 2003.
• 18: G. Pagallo. Adaptive Decision Tree Algorithms for Learning from Examples. PhD thesis, University of California at Santa Cruz, 1990.
• 19: Giulia Pagallo , David Haussler, Boolean Feature Discovery in Empirical Learning, Machine Learning, v.5 n.1, p.71-99, Mar. 1990 [doi>10.1023/A:1022611825350]
• 20: E. Pérez. Learning Despite Complex Interaction: An Approach Based on Relational Operators. PhD thesis, niversity of Illinois, Urbana-Champaign, 1997.
• 21: E. Pérez and L. A. Rendell. Using multidimensional projection to find relations. In Proc. of the Twelfth International Conference on Machine Learning, pages 447--455, Tahoe City, California, July 1995. Morgan Kaufmann.
• 22: N. Qian and T. J. Sejnowski. Predicting the secondary structure of globular proteins using neural network models. Journal of Molecular Biology, 202(4):865--884, August 1988.
• 23: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 24: H. Ragavan and L. A. Rendell. Lookahead feature construction for learning hard concepts. In Proc. of the Tenth International Conference on Machine Learning, pages 252--259, University of Massachusetts, Amherst, MA, USA, June 1993. Morgan Kaufmann.
• 25: O. Ritthoff, R. Klinkenberg, S. Fischer, and I. Mierswa. A hybrid approach to feature selection and generation using an evolutionary algorithm. In UK Workshop on Computational Intelligence, Birmingham, U.K., September 2002.
• 26: L. S. Shafti and E. Pérez. Genetic approach to constructive induction based on non-algebraic feature representation. In M. R. Berthold, H.-J. Lenz, E. Bradley, R. Kruse, and C. Borgelt, editors, Proc. of the Fifth International Symposium on Intelligent Data Analysis, Lecture Notes in Computer Science, pages 599--610. Springer-Verlag, August 2003.
• 27: L. S. Shafti and E. Pérez. Machine learning by multi-feature extraction using genetic algorithms. In C. Lemaître, C. A. Reyes, and J. A. González, editors, Proc. of the Ninth Ibero-American Conference on Artificial Intelligence - Advances in Artificial Intelligence, Lecture Notes in Computer Science, pages 246--255. Springer-Verlag, November 2004.
• 28: M. G. Smith and L. Bull. Feature construction and selection using genetic programming and a genetic algorithm. In C. Ryan, T. Soule, M. Keijzer, E. P. K. Tsang, R. Poli, and E. Costa, editors, Proc. of the sixth European Conference in Genetic Programming, volume 2610 of Lecture Notes in Computer Science, pages 229--237, Essex, UK, April 2003. Springer-Verlag.
• 29: Haleh Vafaie , Kenneth De Jong, Feature Space Transformation Using Genetic Algorithms, IEEE Intelligent Systems, v.13 n.2, p.57-65, March 1998 [doi>10.1109/5254.671093 ]
• 30: D. S. Yang, L. A. Rendell, and G. Blix. A scheme for feature construction and a comparison of empirical methods. In Proc. of the Twelfth International Joint Conference on Artificial Intelligence, pages 699--704, Sydney, Australia, August 1991. Morgan Kaufmann.
• 31: Zijian Zheng, Constructing X-of-N Attributes for Decision Tree Learning, Machine Learning, v.40 n.1, p.35-75, July 2000 [doi>10.1023/A:1007626017208 ]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Design, Experimentation

Keywords:
attribute interaction, constructive induction, feature construction, feature selection, genetic algorithms, shared attributes