RDDM: Reactive drift detection method
Introduction
Data stream environments frequently contain very large amounts of data, which may be infinite, flowing rapidly and continuously. Thus, methods that learn from data streams normally are under restrictions regarding the usage of memory and run-time. Also, reading the same instance of data more than once is usually not possible. In addition, this scenario, often referred to as online learning, considers the possibility of concept drift (Gama, Žliobaitė, Bifet, Pechenizkiy, & Bouchachia, 2014), a situation commonly characterized by changes in the target distribution of the data over time.
The most common classification of concept drift is based on the speed of the changes. When the changes from one concept to another are sudden and/or rapid, they are called abrupt and, when the transitions between concepts occur over a number of instances, they are called gradual.
There are many examples of online learning applications, including the detection of climate change or spam in e-mail messages, as well as monitoring movement data from sensors or changes in water temperature, among others.
Drift Detection Method (DDM) (Gama, Medas, Castillo, & Rodrigues, 2004) is probably the best known, most used, and cited drift detector, especially because it presents a good all-round performance (Gonçalves, Santos, Barros, & Vieira, 2014), despite being reasonably simple.
One of the well-known problems with DDM is that its performance usually worsens when the concepts are very large (Salperwyck, Boullé , & Lemaire, 2015), because it tends to become less sensitive to concept drifts, taking too many instances to detect the changes.
This work proposes the Reactive Drift Detection Method (RDDM), which is based on DDM and, among other heuristic modifications, adds an explicit mechanism to discard older instances of very long concepts to overcome or at least alleviate the performance loss problem of DDM. We claim RDDM is better than DDM as it should deliver higher or equal global accuracy in most situations by detecting most drifts earlier than DDM would.
In addition, using the Massive Online Analysis (MOA) framework (Bifet, Holmes, Kirkby, & Pfahringer, 2010a), we tested DDM, RDDM, and other detectors in a considerably large number of scenarios, with both artificial and real-world datasets, and statistically evaluated the results.
The rest of this article is organized as follows: Section 2 briefly surveys related work, with special attention given to DDM; Section 3 describes RDDM and presents its abstract pseudo-code; Section 4 details the experiments configuration, also including brief descriptions of the datasets used in the tests; Section 5 discusses the results obtained, analyses the drift identifications, and performs statistical evaluations of accuracy and of memory and run-time consumption; and, finally, Section 6 introduces our conclusions and proposes future work.
Section snippets
Related work: drift detection
Different approaches have been proposed to learn from data streams containing concept drift. One of the simplest is based on concept drift detection methods (Gonçalves et al., 2014), lightweight software that usually work together with a separate base classifier.
Other proposals adopt more sophisticated strategies, sometimes using ensembles with a base learner and computing different weighting functions to perform the classification, e.g. Dynamic Weighted Majority (DWM) (Kolter & Maloof, 2007),
Reactive drift detection method
This section provides a detailed description of RDDM, our original proposal to overcome deficiencies and thus improve the detections and accuracy results of DDM. This includes our motivation and heuristic assumptions, as well as all important details of the corresponding implementation in MOA.
As already mentioned, the main idea behind RDDM is to periodically shorten the number of instances of very long stable concepts to tackle a known performance loss problem of DDM. It is assumed that such a
Experimental setting
This section describes all the relevant information on the experiments designed to test and evaluate RDDM against DDM and other drift detectors.
To allow for a fair comparison, all the drift detection methods used NB as base learner, because it is a simple, fast, efficient, and freely available method, which is often used in experiments in the data stream area. Also, the first three parameters of RDDM were exceptionally set with the same values used by DDM, i.e. .
The accuracy
Experimental results and analysis
This section presents the results of the experiments and includes analyses of accuracy, concept drift identifications, as well as memory and run-time usage over the 51 tested datasets.
Conclusion
This article proposed RDDM, a new method for concept drift detection in data streams, rooted in DDM, and motivated by a drop in performance, caused by sensitivity loss, which usually affects DDM when the concepts become very long.
Specifically, RDDM implements a softer type of concept drift that does not affect the base learner and is performed after long periods within a stable concept state, periodically recalculating the DDM statistics responsible for detecting the warning and drift levels,
Acknowledgments
Silas Santos is supported by a postgraduate grant from CNPq. The authors also thank Bruno Maciel for his MOA script generator and results extraction tool, which is still under development but greatly helped speed up the generation of scripts and the analysis of the results of the experiments.
References (35)
- et al.
A comparative study on concept drift detectors
Expert Systems with Applications
(2014) - et al.
One pass concept change detection for data streams
Advances in knowledge discovery and data mining
(2013) - et al.
Database mining: A performance perspective
IEEE Transactions on Knowledge and Data Engineering
(1993) - et al.
Paired learners for concept drift
Proceedings of the 8th IEEE international conference on data mining (ICDM’08) Pisa, Italy
(2008) - et al.
Early drift detection method
Proceedings of the fourth international workshop on knowledge discovery from data streams
(2006) Advances in data stream mining with concept drift
(2017)- et al.
A boosting-like online learning ensemble
Proceedings of the international joint conference on neural networks (IJCNN)
(2016) - et al.
Learning from time-changing data with adaptive windowing
Proceedings of the 7th SIAM international conference on data mining (SDM’07),Minneapolis, MN, USA
(2007) - et al.
MOA: Massive online analysis
Journal of Machine Learning Research
(2010) - et al.
Leveraging bagging for evolving data streams
Machine learning and knowledge discovery in databases
(2010)
New ensemble methods for evolving data streams
Proceedings of the 15th ACM international conference on knowledge discovery and data mining (KDD’09), Paris, France
Pitfalls in benchmarking data stream classification and how to avoid them
Machine learning and knowledge discovery in databases
Introduction to algorithms
Present position and potential developments: Some personal views: Statistical theory: The prequential approach
Journal of the Royal Statistical Society. Series A (General)
Statistical comparisons of classifiers over multiple data sets
Journal of Machine Learning Research
A selective detector ensemble for concept drift detection
The Computer Journal
Online and non-parametric drift detection methods based on hoeffding’s bounds
IEEE Transactions on Knowledge and Data Engineering
Cited by (145)
Adaptive tree-like neural network: Overcoming catastrophic forgetting to classify streaming data with concept drifts
2024, Knowledge-Based SystemsEntropy-based concept drift detection in information systems
2024, Knowledge-Based SystemsA comprehensive analysis of concept drift locality in data streams
2024, Knowledge-Based SystemsA novel Edge architecture and solution for detecting concept drift in smart environments
2024, Future Generation Computer SystemsComplexity-based drift detection for nonstationary data streams
2023, Neurocomputing