Learning Unbiased Cluster Descriptors for Interpretable Imbalanced Concept Drift Detection
Authors: Yiqun Zhang, Zhanpei Huang, Mingjie Zhao, Chuyao Zhang, Yang Lu, Yuzhu Ji, Fangqing Gu, An Zeng
Organizations: the School of Computer Science and Technology, Guangdong University of Technology, Guangzhou 510006, China · the Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China · the Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, Xiamen 361000, China · the School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou 510006, China
Unlabeled streaming data are usually collected to describe dynamic systems, where concept drift detection is a vital prerequisite to understanding the evolution of systems. However, the drifting concepts are usually imbalanced in most real cases, which brings great challenges to drift detection. That is, the dominant statistics of large clusters can easily mask the drifting of small cluster distributions (also called small concepts), which is known as the `masking effect'. Considering that most existing approaches only detect the overall existence of drift under the assumption of balanced concepts, two critical problems arise: 1) where the small concept is, and 2) how to detect its drift. To address the challenging concept drift detection for imbalanced data, we propose Imbalanced Cluster Descriptor-based Drift Detection (ICD3) approach that is unbiased to the imbalanced concepts. This approach first detects imbalanced concepts by employing a newly designed multi-distribution-granular search, which ensures that the distribution of both small and large concepts is effectively captured. Subsequently, it trains a One-Cluster Classifier (OCC) for each identified concept to carefully monitor their potential drifts in the upcoming data chunks. Since the detection is independently performed for each concept, the dominance of large clusters is thus circumvented. ICD3 demonstrates highly interpretability by specifically locating the drifted concepts, and is robust to the changing of the imbalance ratio of concepts. Comprehensive experiments with multi-aspect ablation studies conducted on various benchmark datasets demonstrate the superiority of ICD3 against the state-of-the-art counterparts.
Figures & tables
Fig. 1: Comparison of drift detection in balanced and imbalanced cases. The chunk-wise drift detection can easily become incompetent under the imbalanced case because even though a significant drift appears on a small cluster, the corresponding impact can almost be masked by the large clusters in terms of the overall density distribution.
Fig. 2: Overall workflow of ICD3. ICD3 works on two adjacent chunks. In the base chunk Dt , fine-grained prototypes are first learned and used to partition the samples into multiple sub-clusters. Next, fusion queues are learned to merge these sub-clusters into interpretable clusters. Following this, descriptors are trained for each of the clusters. The learned prototypes guide the capture of the distribution in the incoming chunk Dt+1 , while the fusion queues guide the merging of sub-clusters into clusters. Concept drift detection is performed through the descriptors inherited from the base chunk.
Notations and Symbols
Explanations
Subscript e.g.“ h ” of xh
Element index indicator
Superscript, e.g.“ t ” of Dt
Chunk index indicator
Angle-bracketed superscript, e.g.“ ∗ ” of k∗
Annotation
Parentheses, e.g. Fi(⋅) , Li(⋅)
Function
Greek letters, e.g. α , β , and θ
Coefficients
Uppercase, calligraphic font, e.g. Q
Queue set
TABLE I: Frequently used notations and symbols.
Fig. 3: Comparison of: 1) one OCC for one chunk, 2) multi-class classifiers, and 3) one OCC for one cluster, in the scenario of concept drift detection.
Dataset
Feature
n
k
k′
M
Real
Avila
10
20867
12
3
2:1
Covtype
10
581012
4
3
2:1
Insect
49
5325
5
5
3:2
Noaa
9
18159
2
2
1:1
Occupy
4
20560
2
3
2:1
Posture
3
164860
11
4
2:2
TABLE II: Dataset statistics. n , k , and k′ represent the number of samples, clusters, and sampled cluster counts, respectively. M is the count ratio of large clusters to small clusters.
Metric
Dataset
QT-EWMA
EI-KMeans
OCDD
Qtree
MWW
MCD
OICD3 (ours)
MICD3 (ours)
ACC
Synthetic
2D-2G-M
0.5600 ± 0.0493
0.5061 ± 0.0000
0.5000 ± 0.0000
0.5391 ± 0.0271
0.4862 ± 0.0000
0.5002 ± 0.0006
0.7663 ± 0.0000
0.7260 ± 0.0000
2D-2G-C
0.5120 ± 0.0223
0.5040 ± 0.0000
0.5000 ± 0.0000
0.4911 ± 0.0174
0.5060 ± 0.0000
0.5000 ± 0.0000
0.9322 ± 0.0000
0.9243 ± 0.0000
2D-2G-V
0.5180 ± 0.0351
0.5540 ± 0.0000
0.5000 ± 0.0000
0.4961 ± 0.0200
0.4782 ± 0.0000
0.5025 ± 0.0078
0.9100 ± 0.0000
0.9282 ± 0.0000
2D-4G-M
0.5043 ± 0.0145
0.5042 ± 0.0000
0.5000 ± 0.0000
0.4933 ± 0.0282
0.4981 ± 0.0000
0.5000 ± 0.0000
0.6100 ± 0.0081
0.5690 ± 0.0083
2D-4G-C
0.4970 ± 0.0236
0.5220 ± 0.0000
0.5000 ± 0.0000
0.5140 ± 0.0151
0.4980 ± 0.0000
0.5000 ± 0.0000
0.7960 ± 0.0172
0.6580 ± 0.0304
2D-8G-M
0.5164 ± 0.0187
0.5000 ± 0.0000
0.5000 ± 0.0000
0.5050 ± 0.0154
0.5000 ± 0.0000
0.5000 ± 0.0000
0.7510 ± 0.0453
0.7141 ± 0.0273
TABLE III: Accuracy, AUC, and G-Mean results of drift detection. Bold indicates the optimal result, and underline indicates the second-best result. Using accuracy as an example, the row of “Ave. Acc” represents the average accuracy of each method, and the “Ave. Rank” row reports the average accuracy rankings. The same interpretation holds for AUC and G-Mean.
Fig. 4: Accuracy across chunks on 2D-4G-C and Noaa dataset.
Fig. 5: Comparison of the Accuracy of ICD3 and counterparts across different imbalance ratios.
Fig. 6: Drift detection performance of ICD3 and its three ablated versions (i.e., ICD3-A, ICD3-B, and ICD3-C) on all the 14 datasets.
Fig. 7: Interpretable drift detection process of ICD3. (a) illustrates the spatial distribution of samples in two chunks indicated by blue and yellow colors. θi represents the proportion of out-of-distribution samples in the i -th cluster of the incoming chunk, θi>γ indicates that the specific cluster occurs drift. (b) demonstrates that ICD3 accurately pinpointed the drift region and corresponding samples within the incoming chunk.
Fig. 8: Demonstration on the real-world Climate dataset. On the left column, the base chunk is depicted, where ICD3 learns fine-grained prototypes and captures the distribution of two clusters, and subsequently learns OCC boundaries for each cluster. On the right column, the incoming chunk is shown, where the previously learned prototypes are utilized to identify the two clusters, and the learned OCC boundaries are applied to detect drift. θi represents the proportion of out-of-distribution samples in the i -th cluster of the incoming chunk, θi>γ indicates that the specific cluster occurs drift.
Dataset
0.1
0.2
0.3
0.4
0.5
0.6
0.8
2D-2G-M
0.634
0.766
0.688
0.576
0.510
0.500
0.500
2D-2G-C
0.560
0.932
0.902
0.822
0.664
0.558
0.502
2D-2G-V
0.592
0.910
0.928
0.848
0.750
0.662
0.508
2D-4G-M
0.504
0.610
0.676
0.656
0.578
0.520
0.500
2D-4G-C
0.514
0.796
0.882
0.778
0.654
0.548
0.500
2D-8G-M
0.504
0.751
0.670
0.594
0.542
0.514
0.502
TABLE IV: Parameter sensitivity experiments are conducted to evaluate the impact of threshold γ on the Accuracy metric.
Data stream mining is fundamentally challenged by concept drift, where distributional changes can degrade model performance. Despite the proliferation of drift detection methods, progress in the field is hindered by inconsistent evaluation practices: studies rely on oversimplified synthetic data generators, adopt incompatible metrics, and lack transparency in hyperparameter selection, making fair comparisons difficult. We address this gap with a novel benchmarking framework comprising three contributions: (1) a drift simulation method that injects controlled distributional changes into real-world datasets via Monte Carlo trials, enabling supervised evaluation while preserving real-world data complexity; (2) an evaluation protocol for drift detection with timing-aware criteria, including the derivation of new metrics (e.g., F1 detection score, normalized detection time) that are comparable across streams; and (3) we advocate for a leave-one-dataset-out hyperparameter optimization protocol for drift detection methods that promotes configuration robustness across heterogeneous stream dynamics. We benchmark 14 widely used drift detection methods on 7 realworld datasets across 4 drift types (class prior, label swap, feature permutation, feature filtering), each under both abrupt and gradual transitions. Our experimental results provide insights into the strengths and weaknesses of current drift detection approaches while establishing baseline performance metrics for future research in this area. All code and experiments are publicly available.
Vitor Cerqueira, Heitor Murilo Gomes, Marco Heyden +2
University of Coimbra · Victoria University of Wellington · Commerzbank +2
Machine learning algorithms deployed for evolving streaming environments must handle the non-stationary data distributions, commonly referred to as concept drift. The presence of concept drift poses a major challenge for many real-world applications because it can severely degrade their predictive performance, hindering their ability to support robust decision-making. Consequently, the timely and efficient detection of drift events is critical for sustaining high accuracy over time. This study examines theoretically the concept drift characteristics and numerous drift detection algorithms across several categories. Furthermore, we evaluate their performance on both synthetic and real-world datasets exhibiting diverse streaming scenarios and drift characteristics, such as abrupt and gradual changes. This study aims to enhance understanding of the complex notion of concept drift characteristics and behavior of drift detectors, along with their applicability to diverse contexts.
Md Moman Ul Haque Khan, Samira Sadaoui
Department of Computer Science, University of Regina, Canada
Data streams are nowadays among the most frequently analyzed data structures, with the concept drift posing a major challenge encountered by processing systems. Despite the proposition of numerous solutions to counteract the accuracy degeneration due to concept drift, the scientific community has not yet established a unified framework for evaluating the concept drift detection task. Existing research often relies on classification quality metrics, but these can be affected by multiple factors and may not reliably reflect drift detection quality. In this work, we present an in-depth overview of the relationship between metrics for quantifying drift detection quality and classification performance in synthetic nonstationary data streams. The proposed research studies eight drift detection quality metrics in relation to the classifier's performance across seven synthetic data stream generation tools, additionally considering drift dynamics as a factor. The studies aim to identify the most informative set of drift detection quality metrics and provide a deep understanding of the method's evaluation.
Joanna Komorniczak
Department of Systems and Computer Networks, Wrocław University of Science and Technology