Ensemble learning is a common tool for data stream
classification, mainly because of its inherent advantages of handling large
volumes of stream data and concept drifting. Previous studies, to date, have
been primarily focused on building accurate ensemble models from stream data.
However, a linear scan of a large number of base classifiers in the ensemble
during prediction incurs significant costs in response time, preventing
ensemble learning from being practical for many real-world time-critical data
stream applications, such as Web traffic stream monitoring, spam detection, and
intrusion detection. In these applications, data streams usually arrive at a
speed of GB/second, and it is necessary to classify each stream record in a
timely manner. To address this problem, we propose a novel Ensemble-tree
(E-tree for short) indexing structure to organize all base classifiers in an
ensemble for fast prediction. On one hand, E-trees treat ensembles as spatial
databases and employ an R-tree like height-balanced structure to reduce the
expected prediction time from linear to sub-linear complexity. On the other hand,
E-trees can be automatically updated by continuously integrating new
classifiers and discarding outdated ones, well adapting to new trends and
patterns underneath data streams. Theoretical analysis and empirical studies on
both synthetic and real-world data streams demonstrate the performance of our
approach.
No comments:
Post a Comment