Article

Maximum margin decision surfaces for increased generalisation in evolutionary decision tree learning

Authors:

Alexandros Agapitos,

Michael O'Neill,

Anthony Brabazon,

Theodoros TheodoridisAuthors Info & Claims

EuroGP'11: Proceedings of the 14th European conference on Genetic programming

Pages 61 - 72

Published: 27 April 2011 Publication History

Abstract

Decision tree learning is one of the most widely used and practical methods for inductive inference. We present a novel method that increases the generalisation of genetically-induced classification trees, which employ linear discriminants as the partitioning function at each internal node. Genetic Programming is employed to search the space of oblique decision trees. At the end of the evolutionary run, a (1+1) Evolution Strategy is used to geometrically optimise the boundaries in the decision space, which are represented by the linear discriminant functions. The evolutionary optimisation concerns maximising the decision-surface margin that is defined to be the smallest distance between the decision-surface and any of the samples. Initial empirical results of the application of our method to a series of datasets from the UCI repository suggest that model generalisation benefits from the margin maximisation, and that the new method is a very competent approach to pattern classification as compared to other learning algorithms.

References

[1]

Koza, J.R.: Genetic Programming: on the programming of computers by means of natural selection. MIT Press, Cambridge (1992).

Digital Library

[2]

Vladimir, V.: The nature of statistical learning theory, 2nd edn. Springer, Heidelberg (1999).

[3]

Koza, J.R.: Concept formation and decision tree induction using the genetic programming paradigm. In: Schwefel, H.-P., Männer, R. (eds.) PPSN 1990. LNCS, vol. 496, pp. 124-128. Springer, Heidelberg (1991).

Digital Library

[4]

Folino, G., Pizzuti, C., Spezzano, G.: Genetic Programming and Simulated Annealing: A Hybrid Method to Evolve Decision Trees. In: Poli, R., Banzhaf, W., Langdon, W.B., Miller, J., Nordin, P., Fogarty, T.C. (eds.) EuroGP 2000. LNCS, vol. 1802, pp. 294-303. Springer, Heidelberg (2000).

Digital Library

[5]

Eggermont, J.: Evolving Fuzzy Decision Trees with Genetic Programming and Clustering. In: Foster, J.A., Lutton, E., Miller, J., Ryan, C., Tettamanzi, A.G.B. (eds.) EuroGP 2002. LNCS, vol. 2278, pp. 71-82. Springer, Heidelberg (2002).

Digital Library

[6]

Rouwhorst, S.E., Engelbrecht, A.P.: Searching the forest: Using decision trees as building blocks for evolutionary search in classification databases. In: Proceedings of the, Congress on Evolutionary Computation CEC 2000, vol. 1, pp. 633-638 (2000).

[7]

Bot, M., Langdon, W.B.: Application of genetic programming to induction of linear classification trees. In: Proceedings of the Eleventh Belgium/Netherlands Conference on Artificial Intelligence, BNAIC 1999 (1999).

[8]

Marmelstein, R.E., Lamont, G.B.: Pattern classification using a hybrid genetic program decision tree approach. In: Genetic Programming 1998: Proceedings of the Third Annual Conference (1998).

[9]

Tsakonas, A.: A comparison of classification accuracy of four genetic programming-evolved intelligent structures. Information Sciences 176(6), 691-724 (2006).

Digital Library

[10]

Mugambi, E.M., Hunter, A., Oatley, G., Kennedy, L.: Polynomial-fuzzy decision tree structures for classifying medical data. Knowledge-Based Systems 17(2-4), 81-87 (2004).

Digital Library

[11]

Mitchel, T.: Machine Learning. McGraw-Hill, New York (1997).

[12]

Estrada-Gil, J.K., Fernandez-Lopez, J.C., Hernandez-Lemus, E., Silva-Zolezzi, I., Hidalgo-Miranda, A., Jimenez-Sanchez, G., Vallejo-Clemente, E.E.: GPDTI: A genetic programming decision tree induction method to find epistatic effects in common complex diseases. Bioinformatics 13(13), i167-i174 (2007).

Digital Library

[13]

Kuo, C.-S., Hong, T.-P., Chen, C.-L.: Applying genetic programming technique in classification trees. Soft Computing 11(12), 1165-1172 (2007).

Digital Library

[14]

Haruyama, S., Zhao, Q.: Designing smaller decision trees using multiple objective optimization based gps. In: IEEE International Conference on Systems, Man and Cybernetics, vol. 6, p. 5 (2002).

[15]

Folino, G., Pizzuti, C., Spezzano, G.: Improving induction decision trees with parallel genetic programming. In: Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, January 9-11, pp. 181-187. IEEE, Los Alamitos (2002).

Digital Library

[16]

Agapitos, A., O'Neill, M., Brabazon, A.: Evolutionary Learning of Technical Trading Rules without Data-Mining Bias. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN XI. LNCS, vol. 6238, pp. 294-303. Springer, Heidelberg (2010).

Digital Library

[17]

Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications 16(2), 264-280 (1971).

[18]

Shawe-Taylor, J., Bartlett, P.L., Williamson, R.C., Anthony, M.: Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory 44(5) (1998).

Digital Library

[19]

Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, Heidelberg (2006).

Digital Library

[20]

Newman, D.J., Hettich, S., Blake, C.L., Merz, C.J.: UCI repository of machine learning databases (1998).

[21]

Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The weka data mining software: an update. SIGKDD Explor. Newsl. 11, 10-18 (2009).

Digital Library

Cited By

Agapitos AO'Neill MBrabazon A(2013)Adaptive distance metrics for nearest neighbour classification based on genetic programmingProceedings of the 16th European conference on Genetic Programming10.1007/978-3-642-37207-0_1(1-12)Online publication date: 3-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37207-0_1
Agapitos ABrabazon AO'Neill M(2012)Controlling overfitting in symbolic regression based on a bias/variance error decompositionProceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part I10.1007/978-3-642-32937-1_44(438-447)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32937-1_44

Maximum margin decision surfaces for increased generalisation in evolutionary decision tree learning
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
    2. Machine learning approaches
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Face recognition using discriminant locality preserving projections based on maximum margin criterion

In this paper, we propose a new discriminant locality preserving projections based on maximum margin criterion (DLPP/MMC). DLPP/MMC seeks to maximize the difference, rather than the ratio, between the locality preserving between-class scatter and ...
Univariate Decision Tree Induction using Maximum Margin Classification

In many pattern recognition applications, first decision trees are used due to their simplicity and easily interpretable nature. In this paper, we propose a new decision tree learning algorithm called univariate margin tree where, for each continuous ...
Feature Extraction Using Laplacian Maximum Margin Criterion

Feature extraction by Maximum Margin Criterion (MMC) can more efficiently calculate the discriminant vectors than LDA, by avoiding calculation of the inverse within-class scatter matrix. But MMC ignores the local structures of samples. In this paper, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EuroGP'11: Proceedings of the 14th European conference on Genetic programming

April 2011

348 pages

ISBN:9783642204067

Editors:
Sara Silva
INESC-ID Lisboa, Lisboa, Portugal
,
James A. Foster
University of Idaho, Department of Biological Sciences, Moscow, ID
,
Miguel Nicolau
University College Dublin, Dublin 4, Ireland
,
Penousal Machado
University of Coimbra, Faculty of Sciences and Technology, Department of Informatics Engineering, Coimbra, Portugal
,
Mario Giacobini
University of Torino, Department of Animal Production Epidemiology and Ecology, Grugliasco, TO, Italy

Sponsors

The Museum of Human Anatomy: The Museum of Human Anatomy ("Luigi Rolando")
HuGeF: The Human Genetics Foundation of Torino
The Museum of Criminal Anthropology: The Museum of Criminal Anthropology ("Cesare Lombroso")
The University of Torino: The University of Torino

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 April 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agapitos AO'Neill MBrabazon A(2013)Adaptive distance metrics for nearest neighbour classification based on genetic programmingProceedings of the 16th European conference on Genetic Programming10.1007/978-3-642-37207-0_1(1-12)Online publication date: 3-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37207-0_1
Agapitos ABrabazon AO'Neill M(2012)Controlling overfitting in symbolic regression based on a bias/variance error decompositionProceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part I10.1007/978-3-642-32937-1_44(438-447)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32937-1_44

View Options

View options

Media

Figures

Other

Tables

View Table of Contents