Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Bagging and boosting are two popular ensemble methods that typically achieve better accuracy than a single classifier. These techniques have limitations on massive data sets, because the size of the data set can be a bottleneck. Voting many classifiers built on small subsets of data ("pasting small votes") is a promising approach for learning from massive data sets, one that can utilize the power of boosting and bagging. We propose a framework for building hundreds or thousands of such classifiers on small subsets of data in a distributed environment. Experiments show this approach is fast, accurate, and scalable.

REFERENCES

• 1: <i>Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining</i>, San Francisco, CA, 2001. ACM.
• 2: R. E. Banfield, L. O. Hall, K. W. Bowyer, and W. P. Kegelmeyer. A new ensemble diversity measure applied to thinning ensembles. In <i>Multiple Classifier Systems Workshop</i>, pages 306-316, Surrey, UK, 2003.
• 3: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 4: H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H. Weissig, I. N. Shindyalov, and P. E. Bourne. The protein data bank. <i>Nucleic Acids Research</i>, 28:235-242, 2000. http://www.pdb.org/.
• 5: C. L. Blake and C. J. Merz. UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
• 6: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 7: Leo Breiman, Pasting Small Votes for Classification in Large Databases and On-Line, Machine Learning, v.36 n.1-2, p.85-103, July-August 1999 [doi>10.1023/A:1007563306331]
• 8: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 9: P. Chan and S. Stolfo. Towards parallel and distributed learning by meta-learning. In <i>Working Notes AAAI Workshop on Knowledge Discovery and Databases</i>, pages 227-240, San Mateo, CA, 1993.
• 10: N. V. Chawla, S. Eschrich, and L. O. Hall. Creating ensembles of classifiers. In <i>First IEEE International Conference on Data Mining</i>, pages 581-583, San Jose, CA, 2000.
• 11: Nitesh V. Chawla , Lawrence O. Hall , Kevin W. Bowyer , Thomas E. Moore , W. Philip Kegelmeyer, Distributed Pasting of Small Votes, Proceedings of the Third International Workshop on Multiple Classifier Systems, p.52-61, June 24-26, 2002
• 12: Nitesh V. Chawla , Thomas E. Moore , Lawrence O. Hall , Kevin W. Bowyer , W. Philip Kegelmeyer , Clayton Springer, Distributed learning with bagging-like performance, Pattern Recognition Letters, v.24 n.1-3, p.455-471, January 2003 [doi>10.1016/S0167-8655(02)00269-6]
• 13: N. V. Chawla, T. E. Moore, Jr., L. O. Hall, K. W. Bowyer, W. P. Kegelmeyer, and C. Springer. Investigation of bagging-like effects and decision trees versus neural nets in protein secondary structure prediction. In <i>ACM SIGKDD Workshop on Data Mining in Bio-Informatics</i>, San Francisco, CA, 2001.
• 14: Donald Michie , D. J. Spiegelhalter , C. C. Taylor , John Campbell, Machine learning, neural and statistical classification, Ellis Horwood, Upper Saddle River, NJ, 1995
• 15: Thomas G. Dietterich, An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Machine Learning, v.40 n.2, p.139-157, Aug. 2000 [doi>10.1023/A:1007607513941]
• 16: P. Domingos. Using partitioning to speed up specific-to-general rule induction. In <i>AAAI Workshop on Integrating Multiple Learned Models</i>, pages 29-34, Portland, OR, 1996.
• 17: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 18: S. Eschrich, N. V. Chawla, and L. O. Hall. Learning to predict in complex biological domains. <i>Journal of System Simulation</i>, 2:1464-1471, 2002.
• 19: Scott E. Fahlman , Christian Lebiere, The cascade-correlation learning architecture, Advances in neural information processing systems 2, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 20: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth, From data mining to knowledge discovery: an overview, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 21: Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In <i>Thirteenth International Conference on Machine Learning</i>, Bari, Italy, 1996.
• 22: Giorgio Giacinto , Fabio Roli, An approach to the automatic design of multiple classifier systems, Pattern Recognition Letters, v.22 n.1, p.25-33, Jan. 2001 [doi>10.1016/S0167-8655(00)00096-9]
• 23: I. J. Good. <i>The Estimation of Probabilities: An essay on modern Bayesian methods</i>. MIT Press, 1965.
• 24: L. O. Hall, K. W. Bowyer, N. V. Chawla, T. E. Moore, and W. P. Kegelmeyer. Avatar: Adaptive Visualization Aid for Touring and Recovery. Technical Report SAND2000-8203, Sandia National Labs, 2000.
• 25: Lawrence O. Hall , Nitesh V. Chawla , Kevin W. Bowyer , W. Philip Kegelmeyer, Learning Rules from Distributed Data, Revised Papers from Large-Scale Parallel Data Mining, Workshop on Large-Scale Parallel KDD Systems, SIGKDD, p.211-220, August 15, 1999
• 26: Tin Kam Ho, The Random Subspace Method for Constructing Decision Forests, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.8, p.832-844, August 1998 [doi>10.1109/34.709601]
• 27: D. T. Jones. Protein secondary structure prediction based on decision-specific scoring matrices. <i>Journal of Molecular Biology</i>, 292:195-202, 1999.
• 28: Ludmila I. Kuncheva , Christopher J. Whitaker, Measures of Diversity in Classifier Ensembles and Their Relationship with the Ensemble Accuracy, Machine Learning, v.51 n.2, p.181-207, May 2003 [doi>10.1023/A:1022859003006]
• 29: L. Kuncheva, C. Whitaker, C. Shipp, and R. Duin. Is independence good for combining classifiers? In <i>Proceedings of 15th International Conference on Pattern Recognition</i>, pages 168-171, Barcelona, Spain, September 2000.
• 30: Patrice Latinne , Olivier Debeir , Christine Decaestecker, Limiting the Number of Trees in Random Forests, Proceedings of the Second International Workshop on Multiple Classifier Systems, p.178-187, July 02-04, 2001
• 31: Aleksandar Lazarevic , Zoran Obradovic, Boosting Algorithms for Parallel and Distributed Learning, Distributed and Parallel Databases, v.11 n.2, p.203-229, March 2002 [doi>10.1023/A:1013992203485]
• 32: Neal Leavitt, Data Mining for the Corporate Masses?, Computer, v.35 n.5, p.22-24, May 2002 [doi>10.1109/MC.2002.999772]
• 33: Lawrence Livermore National Laboratories. ASCI Blue Pacific. http://www.llnl.gov/asci/platforms/bluepac.
• 34: Lawrence Livermore National Laboratories. Protein Structure Prediction Center. http://predictioncenter.llnl.gov/, 1999.
• 35: R. Musick, J. Catlett, and S. Russell. Decision theoretic subsampling for induction on large databases. In <i>Proceedings of Tenth International Conference on Machine Learning</i>, pages 212- 219, Amherst, MA, 1993.
• 36: Claudia Perlich , Foster Provost , Jeffrey S. Simonoff, Tree induction vs. logistic regression: a learning-curve analysis, The Journal of Machine Learning Research, 4, p.211-255, 12/1/2003 [doi>10.1162/153244304322972694]
• 37: F. Provost and D. N. Hennessy. Scaling up: Distributed machine learning with cooperation. In <i>Proceedings of the Thirteenth National Conference on Artificial Intelligence, AAAI'96</i>, pages 74-79, Portland, Oregon, 1996.
• 38: Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999 [doi>10.1023/A:1009876119989]
• 39: Foster Provost , David Jensen , Tim Oates, Efficient progressive sampling, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.23-32, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312188]
• 40: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 41: D. B. Skalak. The sources of increased accuracy for two proposed boosting algorithms. In <i>AAAI Integrating Multiple Learned Models Workshop</i>, Portland, Oregon, 1996.
• 42: W. Nick Street , YongSeog Kim, A streaming ensemble algorithm (SEA) for large-scale classification, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.377-382, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502568]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Performance, Theory