Accurate decision trees for mining high-speed data streams

ABSTRACT

In this paper we study the problem of constructing accurate decision tree models from data streams. Data streams are incremental tasks that require incremental, online, and any-time learning algorithms. One of the most successful algorithms for mining data streams is VFDT. In this paper we extend the VFDT system in two directions: the ability to deal with continuous data and the use of more powerful classification techniques at tree leaves. The proposed system, VFDTc, can incorporate and classify new information online, with a single scan of the data, in time constant per example. The most relevant property of our system is the ability to obtain a performance similar to a standard decision tree algorithm even for medium size datasets. This is relevant due to the any-time property. We study the behaviour of VFDTc in different problems and demonstrate its utility in large and medium data sets. Under a bias-variance analysis we observe that VFDTc in comparison to C4.5 is able to reduce the variance component.

REFERENCES

• 1: C. Blake, E. Keogh, and C. Merz. UCI repository of Machine Learning databases, 1999.
• 2: Pedro Domingos, A Unifeid Bias-Variance Decomposition and its Applications, Proceedings of the Seventeenth International Conference on Machine Learning, p.231-238, June 29-July 02, 2000
• 3: 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]
• 4: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 5: Joao Gama, An Analysis of Functional Trees, Proceedings of the Nineteenth International Conference on Machine Learning, p.155-162, July 08-12, 2002
• 6: J. Gratch. Sequential inductive learning. In Proc. of Thirteenth National Conference on Artificial Intelligence, volume 1, pages 779--786, 1996.
• 7: 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]
• 8: Dimitrios Kalles , Tim Morris, Efficient incremental induction of decision trees, Machine Learning, v.24 n.3, p.231-242, Sept. 1996 [doi>10.1023/A:1018295910873]
• 9: R. Kohavi. Scaling up the accuracy of naive Bayes classifiers: a decision tree hybrid. In Proc. of the 2nd International Conference on Knowledge Discovery and Data Mining. AAAI Press, 1996.
• 10: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 11: P. Utgoff. Perceptron trees - a case study in hybrid concept representation. In Proc. of the Seventh National Conference on Artificial Intelligence. Morgan Kaufmann, 1988.
• 12: Paul E. Utgoff , Neil C. Berkman , Jeffery A. Clouse, Decision Tree Induction Based on Efficient Tree Restructuring, Machine Learning, v.29 n.1, p.5-44, Oct. 1997 [doi>10.1023/A:1007413323501]

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

Keywords:
data streams, functional leaves, incremental decision trees