A streaming ensemble algorithm (SEA) for large-scale classification

ABSTRACT

Ensemble methods have recently garnered a great deal of attention in the machine learning community. Techniques such as Boosting and Bagging have proven to be highly effective but require repeated resampling of the training data, making them inappropriate in a data mining context. The methods presented in this paper take advantage of plentiful data, building separate classifiers on sequential chunks of training points. These classifiers are combined into a fixed-size ensemble using a heuristic replacement strategy. The result is a fast algorithm for large-scale or streaming data that classifies as well as a single decision tree built on all the data, requires approximately constant memory, and adjusts quickly to concept drift.

REFERENCES

• 1: 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]
• 2: C. L. Blake and C. J. Merz. UCI repository of machine learning databases {http: //www.ics.uci.edu/~mlearn/M LRepository, html}, 1998. University of California, Irvine, Department of Information and Computer Sciences.
• 3: J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Madison, WI, July 1998.
• 4: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 5: L. Breiman. Arcing classifiers. Annals of Statistics, 26(3):801-849, 1998.
• 6: C. L. Carter, C. Allen, and D. E. Henson. Relation of tumor size, lymph node status, and survival in 24,740 breast cancer cases. Cancer, 63:181-187, 1989.
• 7: Philip K. Chan , Salvatore J. Stolfo, On the Accuracy of Meta-learning for Scalable Data Mining, Journal of Intelligent Information Systems, v.8 n.1, p.5-28, Jan./Feb. 1997 [doi>10.1023/A:1008640732416]
• 8: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 9: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 10: Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 148-156, 1996.
• 11: Glenn Fung , Olvi L. Mangasarian, Data selection for support vector machine classifiers, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.64-70, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347105]
• 12: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 13: L. O. Hall, K. W. Bowyer, W. P. Kegelmeyer, T. E. Moore, and C. Chao. Distributed learning on very large data sets. In Workshop on Distributed and Parallel Knowledge Discovery (KDD-O0), pages 79-84, Aug 2000.
• 14: Robert A. Jacobs, Methods for combining experts' probability assessments, Neural Computation, v.7 n.5, p.867-888, Sept. 1995 [doi>10.1162/neco.1995.7.5.867]
• 15: R. Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pages 202-207, 1996.
• 16: O. L. Mangasarian and D. R. Musicant. Massive support vector regression. Machine Learning, to appear.
• 17: David W. Opitz, Feature selection for ensembles, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.379-384, July 18-22, 1999, Orlando, Florida, United States
• 18: D. Opitz and R. Maclin. Popular ensemble methods: An empirical study. Journal of Artificial Intelligence Research, 11:169-198, 1999.
• 19: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 20: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 21: P. Sollich and A. Krogh. Learning with ensembles: How overfitting can be useful. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8. MIT Press, 1996.
• 22: Gerhard Widmer , Miroslav Kubat, Learning in the presence of concept drift and hidden contexts, Machine Learning, v.23 n.1, p.69-101, April 1996 [doi>10.1023/A:1018046501280]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
ensemble classification, streaming data