CSE 573 -- Artificial Intelligence -- Autumn 1999
TERM PROJECT #2

Machine Learning Ensembles: An Empirical Study and Novel Approach

AUTHORS: Daniel Grossman, Tammy VanDeGrift

Abstract

Two learning ensemble methods, Bagging and Boosting, have been applied to decision trees to improve classification accuracy over that of a single decision tree learner. We introduce Bagging and propose a variant of it -- Improved Bagging -- which, in general, outperforms the original bagging algorithm. We experiment on 22 datasets from the UCI repository, with emphasis on the ensemble's accuracy as the main performance measure. The variant of Bagging that we propose utilizes the ``out of bag'' samples in determining a decision tree's voting power, whereas in the classical Bagging algorithm, all trees have the same voting power. Our proposed algorithm creates bootstrap samples from the training data according to a forced probability distribution that emulates random sampling with replacement. We thus achieve a uniformly distributed training set for each base learner, and also identically-sized ``out of bag'' verification sets for each learner. Our 10-fold cross-validation results and single runs on large data sets show our novel Bagging variant to improve classification accuracy relative to both the original Bagging ensemble and standard Boosting.

Keywords: Bagging, Boosting, Classification, Decision Trees, ID3, Learning Ensembles, Machine Learning

Please download our paper here:   ImprovedBagging.ps

References

  1. Eric Bauer and Ron Kohavi. "An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants". Machine Learning, #36, 1999.
  2. C.L. Blake and C.J. Merz. "UCI Repository of Machine Learning Databases", http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
  3. Leo Breiman. "Out-of-bag Estimation". Unpublished.
  4. Leo Breiman. "Bagging Predictors". Technical Report #421, University of California, Berkeley, September 1994.
  5. Leo Breiman. "Bagging Predictors". Machine Learning, #24, 1996.
  6. Thomas Dean, James Allen, and Yiannis Aloimonos. Artificial Intelligence: Theory and Practice. Addison-Wesley Publishing Company, 1995.
  7. Thomas G. Dietterich. "Machine Learning Research: Four Current Directions". Unpublished.
  8. Pedro Domingos. "Why Does Bagging Work? A Bayesian Account and its Implications". American Association for Artificial Intelligence, 1997.
  9. Pedro Domingos. Personal communication and discussion. December 2, 1999.
  10. B. Efron and R. Tibshirani. An Introduction to the Bootstrap. Chapman & Hall, 1993.
  11. S. Hashem. Optimal linear combinations of neural networks. Ph.D. Thesis, Purdue University, 1993.
  12. Nitin Indurkhya and Sholom M. Weiss. "Estimating Performance Gains for Voted Decision Trees". Intelligent Data Analysis, 1998.
  13. Dennis Kibler and Pat Langley. "Machine Learning as an Experimental Science". Proceedings at the Third European Working Session on Learning, 1998.
  14. M. P. Perrone and L. N. Cooper. "When Networks Disagree: Ensemble Methods for Hybrid Neural Networks". Neural Networks for Speech and Image Processing, 1993.
  15. J. R. Quinlan. "Learning Decision Tree Classifiers". ACM Computing Surveys, Vol. 28(#1), March 1996.
  16. Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Inc., 1995.
  17. Kagan Tumer and Joydeep Ghosh. "Error Correlation and Error Reduction in Ensemble Classifiers". Technical report, University of Texas, Austin, July 1996.
This page last updated: Tuesday, June 27, 2000.
E-mail the authors: Daniel Grossman, Tammy VanDeGrift.