Evolving rule-based classifiers with genetic programming on GPUs for drifting data streams. (March 2019)

• Record Type: Journal Article
• Authors: Cano, Alberto; Krawczyk, Bartosz
• Is Part Of: Pattern recognition. Volume 87(2019:Mar.)
• Page Start: 248
• Page End: 268
• Publication Date: 2019-03
• Subjects: Machine learning -- Data streams -- Concept drift -- Genetic programming -- Rule-based classification -- GPU -- High-performance data mining; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2018.10.024
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Grammar-guided genetic programming rule-based classifier for drifting data streams. Online induction of highly accurate and interpretable rules. Fast adaptation to any type of concept drift. Mechanisms for rule diversification and adaptation. Efficient implementation on GPUs suitable for high-speed data streams. Abstract: Designing efficient algorithms for mining massive high-speed data streams has become one of the contemporary challenges for the machine learning community. Such models must display highest possible accuracy and ability to swiftly adapt to any kind of changes, while at the same time being characterized by low time and memory complexities. However, little attention has been paid to designing learning systems that will allow us to gain a better understanding of incoming data. There are few proposals on how to design interpretable classifiers for drifting data streams, yet most of them are characterized by a significant trade-off between accuracy and interpretability. In this paper, we show that it is possible to have all of these desirable properties in one model. We introduce ERulesD 2 S: evolving rule-based classifier for drifting data Streams. By using grammar-guided genetic programming, we are able to obtain accurate sets of rules per class that are able to adapt to changes in the stream without a need for an explicit drift detector. Additionally, we augment our learning model with new proposals for rule propagation and data stream sampling, in order to maintain a balance between learning and forgetting of concepts. To improve efficiency of mining massive and non-stationary data, we implement ERulesD 2 S parallelized on GPUs. A thorough experimental study on 30 datasets proves that ERulesD 2 S is able to efficiently adapt to any type of concept drift and outperform state-of-the-art rule-based classifiers, while using small number of rules. At the same time ERulesD 2 S is highly competitive to other single and ensemble learners in terms of accuracy and computational complexity, while offering fully interpretable classification rules. Additionally, we show that ERulesD 2 S can scale-up efficiently to high-dimensional data streams, while offering very fast update and classification times. Finally, we present the learning capabilities of ERulesD 2 S for sparsely labeled data streams.