Categorizing and mining concept drifting data streams

ABSTRACT

Mining concept drifting data streams is a defining challenge for data mining research. Recent years have seen a large body of work on detecting changes and building prediction models from stream data, with a vague understanding on the types of the concept drifting and the impact of different types of concept drifting on the mining algorithms. In this paper, we first categorize concept drifting into two scenarios: Loose Concept Drifting (LCD) and Rigorous Concept Drifting (RCD), and then propose solutions to handle each of them separately. For LCD data streams, because concepts in adjacent data chunks are sufficiently close to each other, we apply kernel mean matching (KMM) method to minimize the discrepancy of the data chunks in the kernel space. Such a minimization process will produce weighted instances to build classifier ensemble and handle concept drifting data streams. For RCD data streams, because genuine concepts in adjacent data chunks may randomly and rapidly change, we propose a new Optimal Weights Adjustment (OWA) method to determine the optimum weight values for classifiers trained from the most recent (up-to-date) data chunk, such that those classifiers can form an accurate classifier ensemble to predict instances in the yet-to-come data chunk. Experiments on synthetic and real-world datasets will show that weighted instance approach is preferable when the concept drifting is mainly caused by the changing of the class prior probability; whereas the weighted classifier approach is preferable when the concept drifting is mainly triggered by the changing of the conditional probability.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 4: Charu C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Yixin Chen , Guozhu Dong , Jiawei Han , Benjamin W. Wah , Jianyong Wang, Multi-dimensional regression analysis of time-series data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.323-334, August 20-23, 2002, Hong Kong, China
• 6: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, On demand classification of data streams, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014110]
• 7: Ralf Klinkenberg , Thorsten Joachims, Detecting Concept Drift with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.487-494, June 29-July 02, 2000
• 8: Ying Yang , Xindong Wu , Xingquan Zhu, Combining proactive and reactive predictions for data streams, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081961]
• 9: Jing Gao , Wei Fan , Jiawei Han, On Appropriate Assumptions to Mine Data Streams: Analysis and Practice, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.143-152, October 28-31, 2007 [doi>10.1109/ICDM.2007.96]
• 10: 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]
• 11: Jeremy Z. Kolter , Marcus A. Maloof, Using additive expert ensembles to cope with concept drift, Proceedings of the 22nd international conference on Machine learning, p.449-456, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102408]
• 12: M. Scholz and R. Klinkenberg. 2005. An Ensemble Classifier for Drifting Concepts. In Proc. of the 2nd International Workshop on Knowledge Discovery in Data Streams.
• 13: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, 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.956778]
• 14: Xingquan Zhu , Peng Zhang , Xiaodong Lin , Yong Shi, Active Learning from Data Streams, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.757-762, October 28-31, 2007 [doi>10.1109/ICDM.2007.101]
• 15: Wenyuan Dai , Qiang Yang , Gui-Rong Xue , Yong Yu, Boosting for transfer learning, Proceedings of the 24th international conference on Machine learning, p.193-200, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273521]
• 16: H. Shimodaira, 2000. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90,227--244.
• 17: M. Sugiyama, & K. Müüller, 2005. Model selection under covariate shift. In Proc. of ICANN.
• 18: Steffen Bickel , Michael Brückner , Tobias Scheffer, Discriminative learning for differing training and test distributions, Proceedings of the 24th international conference on Machine learning, p.81-88, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273507]
• 19: Bickel, S., & Scheffer, T. 2007. Dirichlet-enhanced spam filtering based on biased samples. Advances in Neural Information Processing Systems.
• 20: M. Dudik, R. Schapire, & S. Phillips, 2005. Correcting sample selection bias in maximum entropy density estimation. Advances in Neural Info. Processing Systems.
• 21: J. Huang, A. Smola, A. Gretton, K. Borgwardt, & B. Schöölkopf, 2007. Correcting sample selection bias by unlabeled data. Advances in Neural Info. Proc. Systems.
• 22: K. Tumer & J. Ghosh.1996. Analysis of decision boundaries in linearly combined neural classifiers, Pattern Recognition, 29(2).
• 23: 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
• 24: Daniel Kifer , Shai Ben-David , Johannes Gehrke, Detecting change in data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.180-191, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
classification, concept drifting, data streams, ensemble learning