GPU-based State Adaptive Random Forest for Evolving Data Streams

摘要

Random forest is an ensemble method used to improve the performance of single tree classifiers. In evolving data streams, the classifier needs to be adaptive and work under constraints of space and time. One benefit of random forest is its ability to be executed in parallel. In our research we introduce a random forest model utilizing a hybrid of both GPU and CPU, called GPU-based State-Adaptive Random Forest (GSARF). We address the pre-existing challenges of adapting random forest for data streams, specifically in the area of continual learning. Our novel approach reuses previously seen trees in the random forest when previous concepts reappear. This allows us to retain prior knowledge and provide a more stable predictive accuracy when changes occur in the data stream. Our random forest for data streams stores three types of trees, foreground trees which are trees that are currently used in prediction, background trees which are trees that are built when we are aware of possible changes in the data streams, and candidate trees which are trees that had been highly used in the previous concepts, but are now discarded due to changes in the data stream. We store candidate trees as they may be potentially useful at a later period in a repository and can be accessed when needed. We empirically show our technique performs up to 138 times the speed compared to current CPU-based random forest benchmarks. Our approach has shown to outperform a baseline GPU-based approach in terms of cumulative accuracy performance.