New ensemble methods for evolving data streams

ABSTRACT

Advanced analysis of data streams is quickly becoming a key area of data mining research as the number of applications demanding such processing increases. Online mining when such data streams evolve over time, that is when concepts drift or change completely, is becoming one of the core issues. When tackling non-stationary concepts, ensembles of classifiers have several advantages over single classifier methods: they are easy to scale and parallelize, they can adapt to change quickly by pruning under-performing parts of the ensemble, and they therefore usually also generate more accurate concept descriptions. This paper proposes a new experimental data stream framework for studying concept drift, and two new variants of Bagging: ADWIN Bagging and Adaptive-Size Hoeffding Tree (ASHT) Bagging. Using the new experimental framework, an evaluation study on synthetic and real-world datasets comprising up to ten million examples shows that the new ensemble methods perform very well compared to several known methods.

REFERENCES

• 1: Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
• 2: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 3: A. Asuncion and D. Newman. UCI machine learning repository, 2007.
• 4: M. Baena-Garcıa, J. D. Campo-Ávila, R. Fidalgo, A. Bifet, R. Gavaldà, and R. Morales-Bueno. Early drift detection method. In Fourth International Workshop on Knowledge Discovery from Data Streams, 2006.
• 5: A. Bifet and R. Gavaldà. Learning from time-changing data with adaptive windowing. In SIAM International Conference on Data Mining, pages 443--448, 2007.
• 6: L. Breiman et al. Classification and Regression Trees. Chapman&Hall, New York, 1984.
• 7: F. Chu and C. Zaniolo. Fast and light boosting for adaptive mining of data streams. In PAKDD, pages 282--292. Springer Verlag, 2004.
• 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: J. Gama, P. Medas, G. Castillo, and P. Rodrigues. Learning with drift detection. In SBIA Brazilian Symposium on Artificial Intelligence, pages 286--295, 2004.
• 10: João Gama , Ricardo Rocha , Pedro Medas, Accurate decision trees for mining high-speed data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956813]
• 11: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.416-427, August 24-27, 1998
• 12: M. Harries. Splice-2 comparative evaluation: Electricity pricing. Technical report, The University of South Wales, 1999.
• 13: G. Holmes, R. Kirkby, and B. Pfahringer. MOA: Massive Online Analysis. http://sourceforge.net/projects/ moa-datastream. 2007.
• 14: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 15: R. Kirkby. Improving Hoeffding Trees. PhD thesis, University of Waikato, November 2007.
• 16: Dragos D. Margineantu , Thomas G. Dietterich, Pruning Adaptive Boosting, Proceedings of the Fourteenth International Conference on Machine Learning, p.211-218, July 08-12, 1997
• 17: Manish Mehta , Rakesh Agrawal , Jorma Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.18-32, March 25-29, 1996
• 18: Anand Narasimhamurthy , Ludmila I. Kuncheva, A framework for generating data to simulate changing environments, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: artificial intelligence and applications, p.384-389, February 12-14, 2007, Innsbruck, Austria
• 19: N. Oza and S. Russell. Online bagging and boosting. In Artificial Intelligence and Statistics 2001, pages 105--112. Morgan Kaufmann, 2001.
• 20: Nikunj C. Oza , Stuart Russell, Experimental comparisons of online and batch versions of bagging and boosting, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.359-364, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502565]
• 21: R. Pelossof, M. Jones, I. Vovsha, and C. Rudin. Online coordinate boosting. http://arxiv.org/abs/0810.4553, 2008.
• 22: B. Pfahringer, G. Holmes, and R. Kirkby. New options for hoeffding trees. In AI, pages 90--99, 2007.
• 23: Jeffrey C. Schlimmer , Richard H. Granger, Jr., Incremental Learning from Noisy Data, Machine Learning, v.1 n.3, p.317-354, 1986 [doi>10.1023/A:1022810614389]
• 24: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 25: 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]
• 26: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 27: Peng Zhang , Xingquan Zhu , Yong Shi, Categorizing and mining concept drifting data streams, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401987]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
concept drift, data streams, decision trees, ensemble methods