Survey of Concept Drift Detection and Adaptation Methods

doi:10.3778/j.issn.1002-8331.2306-0406

Abstract

Abstract: With the rapid growth of data information, the characteristics of data stream are diversified, which put forward new requirements for the study of concept drift processing methods. The previous detection ideas based on performance degradation cannot cope with the non-instant availability environment of labels, which promotes the research of un-labeled detection methods. The research of ensemble and incremental learning promotes the progress of drift adaptation method. Firstly, the drift detection methods are analyzed in detail in two cases, namely whether the label is available and immediate or not, and based on the model composition, the drift adaptation methods are analyzed and explained with emphasis on the ensemble method. Secondly, the drift processing methods of different ideas are comprehensively summarized from the core ideas, comparison models, advantages and limitations, and the drift processing methods of different ideas are compared as a whole. Finally, the future research directions in this field are given, including noise discrimination, threshold setting and criterion diversification.

Key words: drift detection, drift adaptation, label availability, model composition

摘要： 随着数据信息的急速增长，数据流自身特征呈现多样化，这对概念漂移处理方法的研究提出了新的要求。以往基于性能退化的检测思路无法应对标签非即时可用环境，由此推动了无标签检测方法的研究。集成与增量学习的研究推动了漂移适应方法研究的进步。分别针对标签是否即时可用两种情况对漂移检测方法进行详细分析，同时以模型组成为基础，重点从集成角度对漂移适应方法进行分析说明。针对不同思路的漂移处理方法，从核心思路、对比模型、优点与局限性等方面进行全面总结，同时将不同思路的漂移处理方法进行整体对比。给出了该领域未来的研究方向，包括噪声区分、阈值设定与指标多样化的研究。

关键词: 漂移检测, 漂移适应, 标签可用性, 模型组成

MENG Fanxing, HAN Meng, LI Chunpeng, ZHANG Ruihua, HE Feifei. Survey of Concept Drift Detection and Adaptation Methods[J]. Computer Engineering and Applications, 2024, 60(4): 75-88.

孟凡兴, 韩萌, 李春鹏, 张瑞华, 何菲菲. 概念漂移检测与适应方法综述[J]. 计算机工程与应用, 2024, 60(4): 75-88.

References

[1] WIDMER G, KUBAT M. Learning in the presence of concept drift and hidden contexts[J]. Machine Learning, 1996, 23: 69-101.
[2] WAHAB O A. Intrusion detection in the IoT under data and concept drifts: online deep learning approach[J]. IEEE Internet of Things Journal, 2022, 9(20): 19706-19716.
[3] WANG H, FAN W, YU P S, et al. Mining concept-drifting data streams using ensemble classifiers[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003: 226-235.
[4] GAMA J, MEDAS P, CASTILLO G, et al. Learning with drift detection[C]//Proceedings of the 17th Brazilian Symposium on Artificial Intelligence, Sao Luis, Sep 29-Oct 1, 2004. Berlin, Heidelberg: Springer, 2004: 286-295.
[5] LU J, LIU A, DONG F, et al. Learning under concept drift: a review[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(12): 2346-2363.
[6] HAN M, CHEN Z, LI M, et al. A survey of active and passive concept drift handling methods[J]. Computational Intelligence, 2022, 38(4): 1492-1535.
[7] SATO D M V, DE FREITAS S C, BARDDAL J P, et al. A survey on concept drift in process mining[J]. ACM Computing Surveys, 2021, 54(9): 1-38.
[8] AGRAHARI S, SINGH A K. Concept drift detection in data stream mining: a literature review[J]. Journal of King Saud University-Computer and Information Sciences, 2022, 34(10): 9523-9540.
[9] GAMA J, ?LIOBAITE I, BIFET A, et al. A survey on concept drift adaptation[J]. ACM Computing Surveys, 2014, 46(4): 1-37.
[10] HU H, KANTARDZIC M, SETHI T S. No free lunch theorem for concept drift detection in streaming data classification: a review[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2020, 10(2): e1327.
[11] KHAMASSI I, SAYED-MOUCHAWEH M, HAMMAMI M, et al. Discussion and review on evolving data streams and concept drift adapting[J]. Evolving Systems, 2018, 9: 1-23.
[12] SUAREZ-CETRULO A L, QUINTANA D, CERVANTES A. A survey on machine learning for recurring concept drifting data streams[J]. Expert Systems with Applications, 2023, 213: 118934.
[13] GUO H, LI H, REN Q, et al. Concept drift type identification based on multi-sliding windows[J]. Information Sciences, 2022, 585: 1-23.
[14] WANG S, MACHIDA F. A robustness evaluation of concept drift detectors against unreliable data streams[C]//Proceedings of the 2021 IEEE 7th World Forum on Internet of Things, 2021: 569-574.
[15] KABIR M A, BEGUM S, AHMED M U, et al. CODE: a moving-window-based framework for detecting concept drift in software defect prediction[J]. Symmetry, 2022, 14(12): 2508.
[16] BIFET A, GAVALDA R. Learning from time-changing data with adaptive windowing[C]//Proceedings of the 2007 SIAM International Conference on Data Mining, 2007: 443-448.
[17] BAENA-GARCIA M, DEL CAMPO-áVILA J, FIDALGO R, et al. Early drift detection method[C]//Proceedings of the 4th International Workshop on Knowledge Discovery from Data Streams, 2006: 77-86.
[18] MACIEL B I F, HIDALGO J I G, DE BARROS R S M. An ultimately simple concept drift detector for data streams[C]//Proceedings of the 2021 IEEE International Conference on Systems, Man, and Cybernetics, 2021: 625-630.
[19] NISHIDA K, YAMAUCHI K. Detecting concept drift using statistical testing[C]//Proceedings of the 10th International Conference on Discovery Science. Berlin, Heidelberg: Springer, 2007: 264-269.
[20] DE LIMA CABRAL D R, DE BARROS R S M. Concept drift detection based on Fisher’s exact test[J]. Information Sciences, 2018, 442: 220-234.
[21] COLLELL G, PRELEC D, PATIL K R. A simple plug-in bagging ensemble based on threshold-moving for classifying binary and multiclass imbalanced data[J]. Neurocomputing, 2018, 275: 330-340.
[22] CANO A, KRAWCZYK B. Kappa updated ensemble for drifting data stream mining[J]. Machine Learning, 2020, 109: 175-218.
[23] YANG L, MANIAS D M, SHAMI A. PWPAE: an ensemble framework for concept drift adaptation in IoT data streams[C]//Proceedings of the 2021 IEEE Global Communications Conference, 2021: 1-6.
[24] KOZAL J, GUZY F, WOZNIAK M. Employing chunk size adaptation to overcome concept drift[J]. arXiv:2110.12881, 2021.
[25] YU H, ZHANG Q, LIU T, et al. Meta-ADD: a meta-learning based pre-trained model for concept drift active detection[J]. Information Sciences, 2022, 608: 996-1009.
[26] JAIN M, KAUR G, SAXENA V. A K-means clustering and SVM based hybrid concept drift detection technique for network anomaly detection[J]. Expert Systems with Applications, 2022, 193: 116510.
[27] PESARANGHADER A, VIKTOR H L. Fast Hoeffding drift detection method for evolving data streams[C]//Proceedings of the 2016 European Conference on Machine Learning and Knowledge Discovery in Databases, Riva del Garda, Sep 19-23, 2016: 96-111.
[28] PESARANGHADER A, VIKTOR H L, PAQUET E. McDiarmid drift detection methods for evolving data streams[C]//Proceedings of the 2018 International Joint Conference on Neural Networks, 2018: 1-9.
[29] BAIDARI I, HONNIKOLL N. Bhattacharyya distance based concept drift detection method for evolving data stream[J]. Expert Systems with Applications, 2021, 183: 115303.
[30] GUO H, LI H, SUN N, et al. Concept drift detection and accelerated convergence of online learning[J]. Knowledge and Information Systems, 2023, 65(3): 1005-1043.
[31] LI P, WU X, HU X, et al. Learning concept-drifting data streams with random ensemble decision trees[J]. Neurocomputing, 2015, 166: 68-83.
[32] SUN Y, DAI H. Constructing accuracy and diversity ensemble using Pareto-based multi-objective learning for evolving data streams[J]. Neural Computing and Applications, 2021, 33: 6119-6132.
[33] LEE S, PARK S H. Concept drift modeling for robust autonomous vehicle control systems in time-varying traffic environments[J]. Expert Systems with Applications, 2022, 190: 116206.
[34] GONCALVES P M, CHARTIER S, DE BARROS R S M. Statistical tests to identify virtual concept drifts[C]//Proceedings of the 2021 International Joint Conference on Neural Networks, 2021: 1-8.
[35] KORYCKI ?, KRAWCZYK B. Concept drift detection from multi-class imbalanced data streams[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering, 2021: 1068-1079.
[36] YU H, LIU W, LU J, et al. Detecting group concept drift from multiple data streams[J]. Pattern Recognition, 2023, 134: 109113.
[37] 袁泉, 郭江帆. 新型含噪数据流集成分类的算法[J]. 计算机应用, 2018, 38(6): 1591-1595.
YUAN Q, GUO J F. New ensemble classification algorithm for data stream with noise[J]. Journal of Computer Applications, 2018, 38(6): 1591-1595.
[38] CASTELLANI A, SCHMITT S, HAMMER B. Task-sensitive concept drift detector with constraint embedding[C]//Proceedings of the 2021 IEEE Symposium Series on Computational Intelligence, 2021.
[39] KLIKOWSKI J. Concept drift detector based on centroid distance analysis[C]//Proceedings of the 2022 International Joint Conference on Neural Networks, 2022: 1-8.
[40] NIKPOUR S, ASADI S. A dynamic hierarchical incremental learning-based supervised clustering for data stream with considering concept drift[J]. Journal of Ambient Intelligence and Humanized Computing, 2022, 13(6): 2983-3003.
[41] LI W, YANG X, LIU W, et al. DDG-DA: data distribution generation for predictable concept drift adaptation[C]//Proceedings of the 36th AAAI Conference on Artificial Intelligence, 2022: 4092-4100.
[42] GRECO S, CERQUITELLI T. Drift lens: real-time unsupervised concept drift detection by evaluating per-label embedding distributions[C]//Proceedings of the 2021 International Conference on Data Mining Workshops, 2021: 341-349.
[43] ZHENG X, LI P, HU X, et al. Semi-supervised classification on data streams with recurring concept drift and concept evolution[J]. Knowledge-Based Systems, 2021, 215: 106749.
[44] BIBINBE A M S N, MAHAMADOU A J, MBOUOPDA M F, et al. DragStream: an anomaly and concept drift detector in univariate data streams[C]//Proceedings of the 2022 IEEE International Conference on Data Mining Workshops, 2022: 842-851.
[45] MICEVSKA S, AWAD A, SAKR S. SDDM: an interpretable statistical concept drift detection method for data streams[J]. Journal of Intelligent Information Systems, 2021, 56: 459-484.
[46] CASADO F E, LEMA D, CRIADO M F, et al. Concept drift detection and adaptation for federated and continual learning[J]. Multimedia Tools and Applications, 2022, 81(3): 3397-3419.
[47] WU O, KOH Y S, DOBBIE G, et al. Nacre: proactive recurrent concept drift detection in data streams[C]//Proceedings of the 2021 International Joint Conference on Neural Networks, 2021: 1-8.
[48] QIAO H, NOVIKOV B, BLECH J O. Concept drift analysis by dynamic residual projection for effectively detecting Botnet cyber-attacks in IoT scenarios[J]. IEEE Transactions on Industrial Informatics, 2021, 18(6): 3692-3701.
[49] GULCAN B E, CAN F. Implicit concept drift detection for multi-label data streams[J]. arXiv: 2202. 00070, 2022.
[50] OKAWA Y, KOBAYASHI K. Concept drift detection via boundary shrinking[C]//Proceedings of the 2021 International Joint Conference on Neural Networks, 2021: 1-8.
[51] CAVALHERIO L P, BRITTO A D S, BARDDAL J P, et al. Dynamically selected ensemble for data stream classification[C]//Proceedings of the 2021 International Joint Conference on Neural Networks, 2021: 1-7.
[52] KOLTER J Z, MALOOF M A. Dynamic weighted majority: an ensemble method for drifting concepts[J]. The Journal of Machine Learning Research, 2007, 8: 2755-2790.
[53] ELWELL R, POLIKAR R. Incremental learning of concept drift in nonstationary environments[J]. IEEE Transactions on Neural Networks, 2011, 22(10): 1517-1531.
[54] BRZEZINSKI D, STEFANOWSKI J. Accuracy updated ensemble for data streams with concept drift[C]//Proceedings of the 6th International Conference on Hybrid Artificial Intelligent Systems, Wroclaw, May 23-25, 2011. Berlin, Heidelberg: Springer, 2011: 155-163.
[55] BRZEZINSKI D, STEFANOWSKI J. Reacting to different types of concept drift: the accuracy updated ensemble algorithm[J]. IEEE Transactions on Neural Networks and Learning Systems, 2013, 25(1): 81-94.
[56] BRZEZINSKI D, STEFANOWSKI J. Combining block-based and online methods in learning ensembles from concept drifting data streams[J]. Information Sciences, 2014, 265: 50-67.
[57] MYINT T M, LYNN K T. Handling the concept drifts based on ensemble learning with adaptive windows[J]. IAENG International Journal of Computer Science, 2021, 48(3): 1-16.
[58] ABBASI A, JAVED A R, CHAKRABORTY C, et al. ElStream: an ensemble learning approach for concept drift detection in dynamic social big data stream learning[J]. IEEE Access, 2021, 9: 66408-66419.
[59] LIU A, LU J, ZHANG G. Diverse instance-weighting ensemble based on region drift disagreement for concept drift adaptation[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 32(1): 293-307.
[60] JINDAL A, GUPTA P, SENGUPTA D. Enhash: a fast streaming algorithm for concept drift detection[J]. arXiv: 2011.03729, 2020.
[61] ZHAO L, ZHANG Y, JI Y, et al. Heterogeneous drift learning: classification of mix-attribute data with concept drifts[C]//Proceedings of the 2022 IEEE 9th International Conference on Data Science and Advanced Analytics, 2022: 1-10.
[62] YANG C, CHEUNG Y, DING J, et al. Concept drift-tolerant transfer learning in dynamic environments[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 33(8): 3857-3871.
[63] GRZYB J, KLIKOWSKI J, WOZNIAK M. Hellinger distance weighted ensemble for imbalanced data stream classification[J]. Journal of Computational Science, 2021, 51: 101314.
[64] GOEL K, BATRA S. Two-level pruning based ensemble with abstained learners for concept drift in data streams[J]. Expert Systems, 2021, 38(3): e12661.
[65] KHEZRI S, TANHA J, AHMADI A, et al. A novel semi-supervised ensemble algorithm using a performance-based selection metric to non-stationary data streams[J]. Neurocomputing, 2021, 442: 125-145.
[66] FREUND Y, SCHAPIRE R E. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences, 1997, 55(1): 119-139.
[67] PELOSSOF R, JONES M, VOVSHA I, et al. Online coordinate boosting[C]//Proceedings of the 2009 IEEE 12th International Conference on Computer Vision Workshops, 2009: 1354-1361.
[68] DAI W, YANG Q, XUE G R, et al. Boosting for transfer learning[C]//Proceedings of the 24th International Conference on Machine Learning, 2007: 193-200.
[69] SANTOS S G T C, GONCALVES JUNIOR P M, SILVA G D S, et al. Speeding up recovery from concept drifts[C]//Proceedings of the 2014 European Conference on Machine Learning and Knowledge Discovery in Databases, Nancy, Sep 15-19, 2014. Berlin, Heidelberg: Springer, 2014: 179-194.
[70] BAYRAM B, KOROGLU B, GONEN M. Improving fraud detection and concept drift adaptation in credit card transactions using incremental gradient boosting trees[C]//Proceedings of the 2020 19th IEEE International Conference on Machine Learning and Applications, 2020: 545-550.
[71] WANG K, LU J, LIU A, et al. Elastic gradient boosting decision tree with adaptive iterations for concept drift adaptation[J]. Neurocomputing, 2022, 491: 288-304.
[72] BAIDARI I, HONNIKOLL N. Accuracy weighted diversity-based online boosting[J]. Expert Systems with Applications, 2020, 160: 113723.
[73] HONNIKOLL N, BAIDARI I. Mean error rate weighted online boosting method[J]. The Computer Journal, 2023, 66(1): 1-15.
[74] BAIER L, REIMOLD J, KUHL N. Handling concept drift for predictions in business process mining[C]//Proceedings of the 2020 IEEE 22nd Conference on Business Informatics, 2020: 76-83.
[75] DONG F, LU J, SONG Y, et al. A drift region-based data sample filtering method[J]. IEEE Transactions on Cybernetics, 2021, 52(9): 9377-9390.
[76] LOSING V, HAMMER B, WERSING H. Self-adjusting memory: how to deal with diverse drift types[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, Aug 19-25, 2017: 4899-4903.
[77] YU E, SONG Y, ZHANG G, et al. Learn-to-adapt: concept drift adaptation for hybrid multiple streams[J]. Neurocomputing, 2022, 496: 121-130.
[78] GALMEANU H, ANDONIE R. Weighted incremental-decremental support vector machines for concept drift with shifting window[J]. Neural Networks, 2022, 152: 528-541.
[79] LIU A, ZHANG G, WANG K, et al. Fast switch na?ve Bayes to avoid redundant update for concept drift learning[C]//Proceedings of the 2020 International Joint Conference on Neural Networks, 2020: 1-7.
[80] STRAAT M, ABADI F, KAN Z, et al. Supervised learning in the presence of concept drift: a modelling framework[J]. Neural Computing and Applications, 2022, 34(1): 101-118.