Implementation for the paper "GPU-based State Adaptive Random Forest for Evolving Data Streams".
The implementation includes both the GPU adaptive random forest and the GPU state adaptive random forest.
Random Forests is a classical ensemble method used to improve the performance of single tree classifiers. In evolving data streams, the classifier has also to be adaptive and work under very strict constraints of space and time. The computational load of using a large number of classifiers can make its application extremely expensive. One clear benefit of random forest is its ability to be executed in parallel. Most research concentrates on heuristics that optimize the code, fundamental approaches for fast execution of learned models based on computational architecture is rare. In our research we introduce a random forest model utilizing both GPU and CPU, called State-Adaptive Random Forest on GPU (GSARF). We address the pre-existing challenges of adapting random forest for data streams, specifically in the area of continual learning, whereby we reuse trees in the random forest when old concepts reappear. Current random forest in data streams stores two 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. Additionally, we store 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 these trees in a repository as they may become relevant at some future point and can be reused. By having this repository, we can reduce computation cost. Our approach has shown to outperform a baseline GPU-based approach in terms of accuracy performance.
CUDA Toolkit 10.0
Compile by running
make
Covtype is already included under data/covtype/. All the other datasets need to be generated
and binned by the following instructions:
Generate Agrawal datasets
cd ./moa/agrawal/
./agrawal_data_generator.sh
Generate LED datasets
cd ./moa/led/
./led_data_generator.sh
KDD99 can be found here. Download and
decompress it under data/kddcup/, then bin it by
running the following script:
./data/kddcup/convert.py
Running GARF and GSARF
./agrawal_batch_run.sh
./led_batch_run.sh
./covtype.sh
./kddcup.sh
Running ARF (MOA)
cd ./moa/agrawal/
./moa_arf_runner.sh
cd ./moa/led/
./moa_arf_runner.sh
Results of all the tests and scripts for interpreting the results can be found under each of the
dataset folder i.e. data/[dataset_name]/.
cd data/[dataset_name]/
Draw accuracy comparison chart between GARF and GSARF.
gnuplot -p draw.p
Draw gain chart.
gnuplot -p draw_gain.p
Evaluate memory consumption on host machine.
./mem_eval.sh
Calculate mean and standard deviation for accuracy on the 10 seeds.
./stats_eval.sh
Calculate mean and standard deviation for time on the 10 seeds.
./time_eval.sh
-c turns on the state-adaptive algorithm
-t number of trees
-i number of instances to be trained at the same time on GPU
-d depth of the trees [1, 11]
-e maximum edit distance
-k kappa threshold
-x drift warning threshold
-y drift threshold
-b delta threshold for adding background tree to the CPU tree pool
-p required. Path that contains the data file
-n required. Data file name
This project is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Please contact us for commercial usages.