Affiliations: [a] LIACC, FEP – University of Porto, Rua de Ceuta, 118-6, 4050-190 Porto, Portugal. E-mail: jgama@liacc.up.pt | [b] Department of Mathematics, University of Aveiro, Aveiro, Portugal. E-mail: tbs@mat.ua.pt, ricardor@mat.ua.pt
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. We have extended VFDT in three directions: the ability to deal with continuous data; the use of more powerful classification techniques at tree leaves, and the ability to detect and react to concept drift. VFDTc system 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 also extend VFDTc with the ability to deal with concept drift, by continuously monitoring differences between two class-distribution of the examples: the distribution when a node was built and the distribution in a time window of the most recent examples. We study the sensitivity of VFDTc with respect to drift, noise, the order of examples, and the initial parameters in different problems and demonstrate its utility in large and medium data sets.
Keywords: Data streams, concept drift, incremental decision trees
