Building boosted classification tree ensemble with genetic programming

ABSTRACT

Adaptive boosting (AdaBoost) is a method for building classification ensemble, which combines multiple classifiers built in an iterative process of reweighting instances. This method proves to be a very effective classification method, therefore it was the major part of our evolutionary inspired classification algorithm.

In this paper, we introduce the Genetic Programming with AdaBoost (GPAB) which combines the induction of classification trees with genetic programming (GP) and AdaBoost for multiple class problems. Our method GPAB builds the ensemble of classification trees and uses AdaBoost through the evolution to weight instances and individual trees.

To evaluate the potential of the proposed evolutionary method, we made an experiment where we compared the GPAB with Random Forest and AdaBoost on several standard UCI classification benchmarks. The results show that GPAB improves classification accuracy in comparison to other two classifiers.

References

1. Rodrigo Coelho Barros, Marcio Porto Basgalupp, ACPLF De Carvalho, and Alex Alves Freitas. 2012. A survey of evolutionary algorithms for decision-tree induction. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on 42, 3 (2012), 291--312.
2. Leo Breiman. 1996. Bias, Variance, and Arcing Classifiers. Technical Report. Statistics Department, University of California at Berkeley.
3. Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable Tree Boosting System. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, 785--794.
4. P.G. Espejo, S. Ventura, and F. Herrera. 2010. A Survey on the Application of Genetic Programming to Classification. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 40, 2 (March 2010), 121--144.
5. Yoav Freund and Robert E. Schapire. 1996. Experiments with a New Boosting Algorithm. In Proceedings of the Thirteenth International Conference on International Conference on Machine Learning (ICML'96). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 148--156.
6. Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. 2000. Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors). The annals of statistics 28, 2 (2000), 337--407.
7. Muhammad Iqbal, Bing Xue, Harith Al-Sahaf, and Mengjie Zhang. 2017. Cross-domain reuse of extracted knowledge in genetic programming for image classification. IEEE Transactions on Evolutionary Computation 21, 4 (2017), 569--587.
8. Andy Liaw and Matthew Wiener. 2002. Classification and regression by random-Forest. R news 2, 3 (2002), 18--22.
9. V. Podgorelec, S. Karakatič, R. C. Barros, and M. P. Basgalupp. 2015. Evolving balanced decision trees with a multi-population genetic algorithm. In 2015 IEEE Congress on Evolutionary Computation (CEC). IEEE, Piscataway, NJ, 54--61.
10. Vili Podgorelec, Matej Šprogar, and Sandi Pohorec. 2013. Evolutionary design of decision trees. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 3, 2 (2013), 63--82.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Supervised learning by classification

    • Machine learning algorithms

      • Ensemble methods

        • Boosting

    • Machine learning approaches

      • Bio-inspired approaches

        • Genetic programming

      • Classification and regression trees