Mining high speed data streams: Hoeffding and VFDT

Editor's Notes

• #3: Let’s think about two situations. On the left, the smart city of the future, with thousands of sensors and control systems. On the right, present days banking systems, which generates millions of transactions per day, and are expected to grow even more as e-shopping continues to spread. Thinking about the data produced by those systems, what are its main characteristics? < change > Size and Quantity. No more standard big data analytics, but high-speed data stream mining.
• #4: Knowledge discovery systems are constrained by three main limited resources: time, memory and sample size. In traditional applications of machine learning and statistics, sample size tends to be the dominant limitation. In contrast, in many (if not most) present-day data mining applications, the bottleneck is time and memory, not examples. The latter are typically in over-supply, in the sense that it is impossible with current KDD systems to make use of all of them within the available computational resources. Currently, the most efficient algorithms available (e.g., SPRINT or BIRCH) concentrate on making it possible to mine databases that do not fit in main memory by only requiring sequential scans of the disk. But even these algorithms have only been tested on up to a few million examples. Ideally, we would like to have KDD systems that operate continuously and indefinitely, incorporating examples as they arrive, and never losing potentially valuable information. Incremental algorithms are out there, but they are either highly sensitive to example ordering, potentially never recovering from an unfavorable set of early examples, or produce results similar to batch classification with undesired overhead in computation time.
• #5: Introducing: VFDT, a decision-tree learning system that overcomes the shortcomings of incremental algorithms. It is I/O bound, which means it mines examples in less time than it takes to input them from the disk, it’s an anytime algorithm, meaning that the model is ready-to-use at anytime, it does not store any examples and learns by seeing them exactly once.
• #7: Hoeffding Trees are born from the limitations of classical decision tree learners, which assume all training data can be simultaneously stored in main memory. HT is based on the assumption that, in order to find the best attribute at a node, it may be sufficient to consider only a small subset of the training examples that pass through that node. Given a stream of examples, the first ones will be used to choose the root test; once the root attribute is chosen, the succeeding examples will be passed down to the corresponding leaves and used to choose the appropriate attributes there, and so on recursively. We solve the difficult problem of deciding exactly how many examples are necessary at each node by using a statistical result known as the Hoeffding bound.
• #8: So, how do we decide how many examples are enough?
• #10: If HTδ is the tree produced by the Hoeffding tree algorithm with desired probability δ given infinite examples (Table 1), DT∗ is the asymptotic batch tree, and p is the leaf probability, then E[∆i(HTδ, DT∗)] ≤ δ/p. The smaller δ/p , the more similar the Hoeffding tree is to a subtree of the asymptotic batch tree.
• #12: The Hoeffding tree algorithm was implemented into Very Fast Decision Tree learner (VFDT), which includes some enhancements for practical use. In case of ties, potentially many examples will be required to decide between them with some confidence, which is wasteful since they’re basically equivalent. VFDT splits on the current best attribute. Recomputing G is actually pretty expensive. In VFDT it is possible to define a parameter for the minimum number of examples read before recomputing G. Memory was an issue for HT, meaning that the moew the tree grew, the more memory it needed. VFDT deactivates inactive leaves, only keeping track of the probability of x falling into leaf l, times the observed error rate.