Mining time-changing data streams

ABSTRACT

Most statistical and machine-learning algorithms assume that the data is a random sample drawn from a stationary distribution. Unfortunately, most of the large databases available for mining today violate this assumption. They were gathered over months or years, and the underlying processes generating them changed during this time, sometimes radically. Although a number of algorithms have been proposed for learning time-changing concepts, they generally do not scale well to very large databases. In this paper we propose an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner. This algorithm, called CVFDT, stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new becomes more accurate. CVFDT learns a model which is similar in accuracy to the one that would be learned by reapplying VFDT to a moving window of examples every time a new example arrives, but with O(1) complexity per example, as opposed to O(w), where w is the size of the window. Experiments on a set of large time-changing data streams demonstrate the utility of this approach.

REFERENCES

• 1: R. Agrawal and G. Psaila. Active data mining. In Proceedings of the First International Conference on Knowledge Discovery and Data Mining, pages 3-8, Montreal, Canada, 1995. AAAI Press.
• 2: Necip Fazil Ayan , Abdullah Uz Tansel , Erol Arkun, An efficient algorithm to update large itemsets with early pruning, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.287-291, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312252]
• 3: Peter L. Bartlett , Shai Ben-David , Sanjeev R. Kulkarni, Learning Changing Concepts by Exploiting the Structure of Change, Machine Learning, v.41 n.2, p.153-174, November 2000 [doi>10.1023/A:1007604202679]
• 4: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
• 5: J. Catlett. Megainduction: Machine Learning on Very Large Databases. PhD thesis, Basser Department of Computer Science, University of Sydney, Sydney, Australia, 1991.
• 6: Soumen Chakrabarti , Sunita Sarawagi , Byron Dom, Mining Surprising Patterns Using Temporal Description Length, Proceedings of the 24rd International Conference on Very Large Data Bases, p.606-617, August 24-27, 1998
• 7: David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996
• 8: A. Danyluk, T. Fawcett, and F. Provost, editors. Proceedings of the AAAI-98 Workshop onPredicting the Future: AI Approaches to Time-Series Analysis. AAAI Press, Madison, WI, 1998.
• 9: 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]
• 10: Tom Fawcett , Foster Provost, Activity monitoring: noticing interesting changes in behavior, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.53-62, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312195]
• 11: DEMON: Mining and Monitoring Evolving Data, Proceedings of the 16th International Conference on Data Engineering, p.439, February 28-March 03, 2000
• 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: W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
• 14: Mark G. Kelly , David J. Hand , Niall M. Adams, The impact of changing populations on classifier performance, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.367-371, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312285]
• 15: M. Kubat and G. Widmer, editors. Proceedings of the ICML-96 Workshop on Learning in Context-Sensitive Domains. Bari, Italy, 1996.
• 16: Philip M. Long, The Complexity of Learning According to Two Models of a Drifting Environment, Machine Learning, v.37 n.3, p.337-354, Dec. 1999 [doi>10.1023/A:1007666507971]
• 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: R. G. Miller, Jr. Simultaneous Statistical Inference. Springer, New York, NY, 2nd edition, 1981.
• 19: R. Musick, J. Catlett, and S. Russell. Decision theoretic subsampling for induction on large databases. In Proceedings of the Tenth International Conference on Machine Learning, pages 212-219, Amherst, MA, 1993. Morgan Kaufmann.
• 20: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 21: M. Salganicoff. Density-adaptive learning and forgetting. In Proceedings of the Tenth International Conference on Machine Learning, pages 276-283, Amherst, MA, 1993. Morgan Kaufmann.
• 22: N. L. Sarda , N. V. Srinivas, An Adaptive Algorithm for Incremental Mining of Association Rules, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.240, August 26-28, 1998
• 23: J. C. Schlimmer and R. H. Granger, Jr. Beyond incremental processing: Tracking concept drift. In Proceedings of the Fifth National Conference on Artificial Intelligence, pages 502-507, Philadelphia, PA, 1986. Morgan Kaufmann.
• 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: P. Turney. Context-sensitive learning bibliography. Online bibliography, Institute for Information Technology of the National Research Council of Canada, Ottawa, Canada, 1998. http://ai.iit.nrc.ca/- bibliographies/eontext-sensitive.html.
• 26: S. Vijayakumar and S. Schaal, editors. Proceedings of the NIPS-2000 Workshop on Real-Time Modeling for Complex Learning Tasks. NIPS Foundation, Breckenridge, Colorado, 2000.
• 27: 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]
• 28: G. Widmer and M. Kubat. Special issue on context sensitivity and concept drift: Machine Learning, 32(2), 1998.
• 29: A. Wolman, G. Voelker, N. Sharma, N. Cardweli, M. Brown, T. Landray, D. Pinnel, A. Karlin, and H. Levy. Organization-based analysis of Web-object sharing and caching. In Proceedings of the Second USENIX Conference on Internet Technologies and Systems, pages 25-36, Boulder, CO, 1999.

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
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Keywords:
Decision trees, Hoeffding bounds, concept drift, data streams, incremental learning, subsampling