Abstract Dealing with memory and time constraints are current challenges when learning from data streams with a massive amount of data. Many algorithms have been proposed to handle these difficulties, among them, the Very Fast Decision Tree (VFDT) algorithm. Although the VFDT has been widely used in data stream mining, in the last years, several authors have suggested modifications to increase its performance, putting aside memory concerns by proposing memory-costly solutions. Besides, most data stream mining solutions have been centred around ensembles, which combine the memory costs of their weak learners, usually VFDTs. To reduce memory costs, keeping predictive performance, this study proposes the Strict VFDT (SVFDT), a novel algorithm based on the VFDT. The SVFDT algorithm minimises unnecessary tree growth, substantially reducing memory usage and keeping competitive predictive performance. Moreover, since it creates much more shallow trees than VFDT, the SVFDT can achieve a shorter processing time. Experiments were carried out comparing the SVFDT with the VFDT in 11 benchmark data stream datasets. This comparison assessed the trade-off between accuracy, memory, and processing time. Statistical analysis showed that the proposed algorithm obtained similar predictive performance and significantly reduced processing time and memory use. Thus, SVFDT is a suitable option for data stream mining with memory and time limitations, recommended as a weak learner in ensemble-based solutions.
In a similar work, @cite_2 proposed Optimised-VFDT (OVFDT), whose goal was also to increase accuracy avoiding tree size explosion, substituting @math by statistics about the HB. OVFDT was compared with three algorithms: VFDT (with multiple @math values); Genuine Tie Detection; and Hoeffding Option Tree (HOT) . It must be observed that none of the compared algorithms try to reduce tree size. When compared with VFDT with @math (VFDT-0.05), OVFDT obtained a small accuracy improvement (3 extended the OVFDT adding statistical constraints related to leaf accuracy. When compared with VFDT-0.05, despite the small improvement in predictive performance, they always produced larger trees.
@cite_2
1485652503
Very Fast Decision Tree (VFDT) in data stream mining has been widely studied for more than a decade. VFDT in essence can mine over a portion of an unbounded data stream at a time, and the structure of the decision tree gets updated whenever new data feed in; hence it can predict better upon the input of fresh data. Inherent from traditional decision trees that use information gains for tree induction, VFDT may suffer the same over-fitting problem where noise in the training data leads to excessive tree branches therefore decline in prediction accuracy. This problem is aggravated in stream mining because limited run-time memory (for storing the whole decision tree) and reasonable accuracy are often the criteria for implementing VFDT. Post-pruning that was a popular technique used in traditional decision tree to keep the tree size in check, however may not be applicable for VFDT in situ. In this paper a new model that extends from VFDT called Optimized VFDT is proposed, for controlling the tree size while sustaining good prediction accuracy. This is enabled by using an adaptive threshold tie and incremental pruning in tree induction. Experimental results show that an optimal ratio of tree size and accuracy can be achieved by OVFDT.