Mining time-changing data streams

TLDR

Most large data sets are non‑stationary, violating the random‑sample assumption of conventional algorithms and requiring methods that can adapt to changing underlying processes. This paper proposes an efficient algorithm for mining decision trees from continuously changing data streams. The proposed CVFDT algorithm extends VFDT by maintaining alternative subtrees for outdated splits and replacing them when newer data proves more accurate, achieving O(1) per‑example complexity instead of O(w). Experiments on large time‑changing data streams confirm that CVFDT delivers comparable accuracy to window‑based VFDT while scaling efficiently.

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.