基于加权与动态选择的不平衡数据流分类算法

doi:10.3778/j.issn.1002-8331.2406-0107

摘要/Abstract

摘要： 在数据挖掘领域中，数据流挖掘是一项关键任务，旨在处理不断产生和演化的数据流。与传统的批处理数据挖掘不同，数据流挖掘强调对实时数据的处理和分析，具有更高的时效性和实用性。然而，现实世界的数据流中存在多类别不平衡、变化的类别不平衡比和概念漂移等实际挑战，会极大地降低分类器的性能。针对这些问题，提出了一种基于加权与动态选择的不平衡数据流分类算法（sample difficulty weighting and dynamic ensemble selection，SDW-DES），通过综合考虑样本难度和数据动态性，为实时应用提供可靠解决方案。引入一种基于样本分类难度的加权策略，结合样本的边际值和Focal Loss，以更有效地关注易分类错误的样本和少数类样本，从而提高分类器的准确性。提出一种灵活的动态集成选择方法，通过设计样本滑动窗口和困难样本滑动窗口，来综合分析分类器在不同窗口上的表现并加权，选出集成中最好的分类器进行预测，以适应数据分布的动态变化。在多种数据流环境和评估指标上与9种先进的算法进行了全面的实验评估，实验结果表明SDW-DES在4个评估指标中平均排名第一，并且更能够适应数据流中的不平衡和概念漂移问题。

关键词: 数据流分类, 多类不平衡, 概念漂移, 样本加权, 动态集成选择

Abstract: In the field of data mining, data stream mining is a critical task aimed at processing continuously generated and evolving data streams. Unlike traditional batch data mining, data stream mining emphasizes real-time data processing and analysis, offering higher timeliness and practicality. However, real-world data streams present practical challenges such as multi-class imbalance, varying class imbalance ratios, and concept drift, which can significantly degrade classifier performance. To address these issues, an imbalanced stream classification algorithm based on weighted and dynamic selection (SDW-DES) is proposed. This algorithm provides a reliable solution for real-time applications by comprehensively considering sample difficulty and data dynamics. A weighting strategy based on sample classification difficulty is introduced, which incorporates margin values and Focal Loss to more effectively focus on easily misclassified samples and minority class samples, thereby improving classifier accuracy. A flexible dynamic ensemble selection method is proposed, which utilizes sample sliding windows and hard sample sliding windows to comprehensively analyze classifier performance across different windows. This method assigns weights and selects the best classifiers for ensemble prediction to adapt to the dynamic changes in data distribution. A comprehensive experimental evaluation is conducted on various data stream environments and evaluation metrics, SDW-DES is compared with 9 advanced algorithms. The experimental results demonstrate that SDW-DES achieves the highest average ranking across 4 evaluation metrics, and possess superior adaptability to the challenges of imbalance and concept drift in data streams.

Key words: data stream classification, multi-class imbalance, concept drift, sample weighting, dynamic ensemble selection

韩萌, 李春鹏, 李昂, 孟凡兴, 何菲菲, 张瑞华. 基于加权与动态选择的不平衡数据流分类算法[J]. 计算机工程与应用, 2025, 61(10): 79-95.

HAN Meng, LI Chunpeng, LI Ang, MENG Fanxing, HE Feifei, ZHANG Ruihua. Imbalanced Stream Classification Algorithm Based on Weighted and Dynamic Selection[J]. Computer Engineering and Applications, 2025, 61(10): 79-95.

参考文献

[1] 刘涛涛, 付钰, 王坤, 等. 基于VAE-CWGAN和特征统计重要性融合的网络流量异常检测方法[J/OL]. 通信学报 [2024-04-26]. http://kns.cnki.net/kcms/detail/11.2102.TN.20240223. 1312.006.html.
LIU T T, FU Y, WANG K, et al. Network traffic anomaly detection method based on VAE-CWGAN and fusion of statistical importance of feature[J/OL]. Journal on Communications [2024-04-26]. http://kns.cnki.net/kcms/detail/11.2102.TN.20240223.1312.006.html.
[2] CHERIF A, BADHIB A, AMMAR H, et al. Credit card fraud detection in the era of disruptive technologies: a systematic review[J]. Journal of King Saud University-Computer and Information Sciences, 2023, 35(1): 145-174.
[3] ED-DAOUDY A, MAALMI K, EL OUAAZIZI A. A scalable and real-time system for disease prediction using big data processing[J]. Multimedia Tools and Applications, 2023, 82(20): 30405-30434.
[4] BERNARDO A, DELLA VALLE E, BIFET A. Incremental rebalancing learning on evolving data streams[C]//Proceedings of the 2020 International Conference on Data Mining Workshops. Piscataway: IEEE, 2020: 844-850.
[5] ELREEDY D, ATIYA A F. A comprehensive analysis of synthetic minority oversampling technique (SMOTE) for handling class imbalance[J]. Information Sciences, 2019, 505: 32-64.
[6] CANO A, KRAWCZYK B. Kappa updated ensemble for drifting data stream mining[J]. Machine Learning, 2020, 109(1): 175-218.
[7] CANO A, KRAWCZYK B. ROSE: robust online self-adjusting ensemble for continual learning on imbalanced drifting data streams[J]. Machine Learning, 2022, 111(7): 2561-2599.
[8] SADEGHI F, VIKTOR H L, VAFAIE P. DynaQ: online learning from imbalanced multi-class streams through dynamic sampling[J]. Applied Intelligence, 2023, 53(21): 24908-24930.
[9] JIAO B T, GUO Y N, GONG D W, et al. Dynamic ensemble selection for imbalanced data streams with concept drift[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(1): 1278-1291.
[10] GOMES H M, BIFET A, READ J, et al. Adaptive random forests for evolving data stream classification[J]. Machine Learning, 2017, 106(9): 1469-1495.
[11] WANG S, MINKU L L, YAO X, et al. Dealing with multiple classes in online class imbalance learning[C]//Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016: 2118-2124.
[12] FERREIRA L E B, GOMES H M, BIFET A, et al. Adaptive random forests with resampling for imbalanced data streams[C]//Proceedings of the 2019 International Joint Conference on Neural Networks. Piscataway: IEEE, 2019: 1-6.
[13] CZARNOWSKI I. Weighted ensemble with one-class classification and over-sampling and instance selection (WECOI): an approach for learning from imbalanced data streams[J]. Journal of Computational Science, 2022, 61: 101614.
[14] BIFET A, HOLMES G, PFAHRINGER B. Leveraging bagging for evolving data streams[C]//Proceedings of the 2010 European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2010: 135-150.
[15] LOEZER L, ENEMBRECK F, BARDDAL J P, et al. Cost-sensitive learning for imbalanced data streams[C]//Proceedings of the 35th Annual ACM Symposium on Applied Computing. New York: ACM, 2020: 498-504.
[16] LIU W K, ZHANG H, DING Z Y, et al. A comprehensive active learning method for multiclass imbalanced data streams with concept drift[J]. Knowledge-Based Systems, 2021, 215: 106778.
[17] LIU W K, ZHU C, DING Z Y, et al. Multiclass imbalanced and concept drift network traffic classification framework based on online active learning[J]. Engineering Applications of Artificial Intelligence, 2023, 117: 105607.
[18] HAN M, LI C P, MENG F X, et al. An online ensemble classification algorithm for multi-class imbalanced data stream[J]. Knowledge and Information Systems, 2024, 66(11): 6845-6880.
[19] BIFET A, GAVALDà R. Learning from time-changing data with adaptive windowing[C]//Proceedings of the 2007 SIAM International Conference on Data Mining, 2007: 443-448.
[20] LIU S M, CHEN J H, LIU Z H. An empirical study of dynamic selection and random under-sampling for the class imbalance problem[J]. Expert Systems with Applications, 2023, 221: 119703.
[21] CRUZ R M O, SABOURIN R, CAVALCANTI G D C, et al. META-DES: a dynamic ensemble selection framework using meta-learning[J]. Pattern Recognition, 2015, 48(5): 1925-1935.
[22] CAVALHEIRO L P, DE SOUZA BRITTO A, BARDDAL J P, et al. Dynamically selected ensemble for data stream classification[C]//Proceedings of the 2021 International Joint Conference on Neural Networks. Piscataway: IEEE, 2021: 1-7.
[23] GARCíA S, ZHANG Z L, ALTALHI A, et al. Dynamic ensemble selection for multi-class imbalanced datasets[J]. Information Sciences, 2018, 445: 22-37.
[24] ZHANG Y, DU H L, KE G, et al. Dynamic weighted selective ensemble learning algorithm for imbalanced data streams[J]. The Journal of Supercomputing, 2022, 78(4): 5394-5419.
[25] HAN M, ZHANG X L, CHEN Z Q, et al. Dynamic ensemble selection classification algorithm based on window over imbalanced drift data stream[J]. Knowledge and Information Systems, 2023, 65(3): 1105-1128.
[26] DAI Q, LIU J W, YANG J P. SWSEL: sliding window-based selective ensemble learning for class-imbalance problems[J]. Engineering Applications of Artificial Intelligence, 2023, 121: 105959.
[27] MADKOUR A H, ABDELKADER H M, MOHAMMED A M. Dynamic classification ensembles for handling imbalanced multiclass drifted data streams[J]. Information Sciences, 2024, 670: 120555.
[28] GU X W, ANGELOV P P, SHEN Q. Semisupervised fuzzily weighted adaptive boosting for classification[J]. IEEE Transactions on Fuzzy Systems, 2024, 32(4): 2318-2330.
[29] DAVTALAB R, CRUZ R M O, SABOURIN R. A scalable dynamic ensemble selection using fuzzy hyperboxes[J]. Information Fusion, 2024, 102: 102036.
[30] 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, 2014, 25(1): 81-94.