skip to main content
10.1145/1143997.1144139acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

Improving cooperative GP ensemble with clustering and pruning for pattern classification

Published: 08 July 2006 Publication History

Abstract

A boosting algorithm based on cellular genetic programming to build an ensemble of predictors is proposed. The method evolves a population of trees for a fixed number of rounds and, after each round, it chooses the predictors to include into the ensemble by applying a clustering algorithm to the population of classifiers. The method proposed runs on a distributed hybrid multi-island environment that combines the island and cellular models of parallel genetic programming. The large amount of memory required to store the ensemble makes the method heavy to deploy. The paper shows that by applying suitable pruning strategies it is possible to select a subset of the classifiers without increasing misclassification errors; indeed, up to 20 of pruning, ensemble accuracy increases. Experiments on several data sets show that combining clustering and pruning enhances classification accuracy of the ensemble approach.

References

[1]
A. Agresti. Categorical Data Analysis. John Wiley and Sons,Inc., 1990.
[2]
E. Alba and M. Tomassini. Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 6(5):443--462, 2002.
[3]
R. E. Banfield, L. O. Hall, K. W. Bowyer, and W.P . Kegelmeyer. Ensembles diversity measures and their application to thinning. Information Fusion, 6:49--62, 2005.
[4]
Eric Bauer and Ron Kohavi. An empirical comparison of voting classification algorithms: Bagging, boosting, and variants. Machine Learning, (36):105--139, 1999.
[5]
Leo Breiman. Bagging predictors. Machine Learning, 24(2):123--140, 1996.
[6]
Leo Breiman. Arcing classifiers. Annals of Statistics, 26:801--824, 1998.
[7]
Edmund Burke, Steven Gustafson, and Graham Kendall. A survey and analysis of diversity measures in genetic programming. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 716--723, New York, 2002. Morgan Kaufmann Publishers.
[8]
Edmund Burke, Steven Gustafson, Graham Kendall, and Natalio Krasnogor. Advanced population diversity measures in genetic programming. In Parallel Problem Solving from Nature - PPSN VII, number 2439 in Lecture Notes in Computer Science, LNCS, page 341 ff., Granada, Spain, 2002. Springer-Verlag.
[9]
E. Cantú-Paz and C. Kamath. Inducing oblique decision trees with evolutionary algorithms. IEEE Transaction on Evolutionary Computation, 7(1):54--68, February 2003.
[10]
N. Chawla, T. E. Moore, W. Bowyer K, L. O. Hall, C. Springer, and P. Kegelmeyer. Bagging-like effects for decision trees and neural nets in protein secondary structure prediction. In BIOKDD01: Workshop on Data mining in Bioinformatics (SIGKDD01), 2001.
[11]
Thomas G. Dietterich. An experimental comparison of three methods for costructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, (40):139--157, 2000.
[12]
R. C. Dubes and A. K. Jain. Algorithms for Clustering Data. MIT Press, Prentice Hall, 1988.
[13]
Anikó Ekárt and Sandor Z. Németh. Maintaining the diversity of genetic programs. Lecture Notes in Computer Science, EuroGP 2002, 2278:162--171, 2002.
[14]
G. Folino, C. Pizzuti, and G. Spezzano. A cellular genetic programming approach to classification. In Proc. Of the Genetic and Evolutionary Computation Conference GECCO99, pages 1015--1020, Orlando, Florida, July 1999. Morgan Kaufmann.
[15]
G. Folino, C. Pizzuti, and G. Spezzano. Ensemble techniques for parallel genetic programming based classifiers. In E. Costa C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, editor, Proceedings of the Sixth European Conference on Genetic Programming (EuroGP-2003), volume 2610 of LNCS, pages 59--69, Essex, UK, 2003. Springer Verlag.
[16]
G. Folino, C. Pizzuti, and G. Spezzano. A scalable cellular implementation of parallel genetic programming. IEEE Transaction on Evolutionary Computation, 7(1):37--53, February 2003.
[17]
G. Folino, C. Pizzuti, and G. Spezzano. Boosting technique for combining cellular gp classifiers. In M. Keijzer, U. O'Reilly, S. M. Lucas, E. Costa, and T. Soule, editors, Proceedings of the Seventh European Conference on Genetic Programming (EuroGP-2004), volume 3003 of LNCS, pages 47--56, Coimbra, Portugal, 2004. Springer Verlag.
[18]
Y. Freund and R. Scapire. Experiments with a new boosting algorithm. In Proceedings of the 13th Int. Conference on Machine Learning, pages 148--156, 1996.
[19]
Hitoshi Iba. Bagging, boosting, and bloating in genetic programming. In Proc. Of the Genetic and Evolutionary Computation Conference GECCO99, pages 1053--1060, Orlando, Florida, July 1999. Morgan Kaufmann.
[20]
J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Selection. MIT Press, Cambridge, MA, 1992.
[21]
L. I. Kuncheva and C. J. Whitaker. Diversity measures in classifier ensembles. Machine Learning, (51):181--207, 2003.
[22]
W. B. Langdon and B. F. Buxton. Genetic programming for combining classifiers. In Proc. Of the Genetic and Evolutionary Computation Conference GECCO'2001, pages 66--73, San Francisco, CA, July 2001. Morgan Kaufmann.
[23]
D. D. Margineantu and T. G. Dietterich. Pruning adaptive boosting. In Proceedings of the International Conference on Machine Learning, pages 211--218, 1997.
[24]
C. C. Pettey. Diffusion (cellular) models. In David B. Fogel Thomas Bäck and Zbigniew Michalewicz, editors, Handbook of Evolutionary Computation, pages C6.4:1--6. Institute of Physics Publishing and Oxford University Press, Bristol, New York, 1997.
[25]
R. E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197--227, 1990.
[26]
R. E. Schapire. Boosting a weak learning by maiority. Information and Computation, 121(2):256--285, 1996.
[27]
Terence Soule. Voting teams: A cooperative approach to non-typical problems using genetic programming. In Proc. Of the Genetic and Evolutionary Computation Conference GECCO99, pages 916--922, Orlando, Florida, July 1999. Morgan Kaufmann.

Cited By

View all
  • (2023)A survey of evolutionary algorithms for supervised ensemble learningThe Knowledge Engineering Review10.1017/S026988892300002438Online publication date: 1-Mar-2023
  • (2013)Modeling Aggressive Behaviors With Evolutionary TaxonomersIEEE Transactions on Human-Machine Systems10.1109/TSMC.2013.225233743:3(302-313)Online publication date: May-2013
  • (2007)Multi-objective competitive coevolution for efficient GP classifier problem decomposition2007 IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.2007.4414009(1930-1937)Online publication date: Oct-2007
  • Show More Cited By

Index Terms

  1. Improving cooperative GP ensemble with clustering and pruning for pattern classification

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation
    July 2006
    2004 pages
    ISBN:1595931864
    DOI:10.1145/1143997
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. classification
    2. data mining
    3. ensemble
    4. genetic programming

    Qualifiers

    • Article

    Conference

    GECCO06
    Sponsor:
    GECCO06: Genetic and Evolutionary Computation Conference
    July 8 - 12, 2006
    Washington, Seattle, USA

    Acceptance Rates

    GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;
    Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 16 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)A survey of evolutionary algorithms for supervised ensemble learningThe Knowledge Engineering Review10.1017/S026988892300002438Online publication date: 1-Mar-2023
    • (2013)Modeling Aggressive Behaviors With Evolutionary TaxonomersIEEE Transactions on Human-Machine Systems10.1109/TSMC.2013.225233743:3(302-313)Online publication date: May-2013
    • (2007)Multi-objective competitive coevolution for efficient GP classifier problem decomposition2007 IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.2007.4414009(1930-1937)Online publication date: Oct-2007
    • (2007)Using restricted loops in genetic programming for image classification2007 IEEE Congress on Evolutionary Computation10.1109/CEC.2007.4425070(4569-4576)Online publication date: Sep-2007

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media