A Clustering-based framework for Classifying Data Streams

1 Introduction

The recent advances in information technology have led to an increasing trend in the application of data streams, and data stream classification has captured the attention of many researchers. Unlike traditional classification problems, data streams are continuously evolving such that the data distributions can change dynamically and new data patterns may appear. This non-stationary nature of data streams, known as concept drift and concept evolution [Masud et al., 2010; Gama et al., 2014], requires a continuous learning capability for traditional machine learning techniques to handle data streams [Aggarwal et al., 2006; Bouchachia, 2011; Mu et al., 2017]. The scarcity of data labels and expensive labeling costs also limit the conventional classification techniques [Din et al., 2020]. Besides, limited time and memory space pose an additional layer of challenges for classifying the large volume of data streams.

∗Contact Author

To address these challenges, a great number of studies have been conducted on classifying data streams considering two primary aspects, data stream classification through: (i) supervised and (ii) semi-supervised learning. For supervised data stream classification frameworks, most studies [Bifet et al., 2009; Bifet and Gavald`a, 2009; Bifet et al., 2010b; Losing et al., 2018; Gomes et al., 2017] focus on extending traditional offline machine learning techniques with an assumption that the label of each incoming sample will be available after it is classified. However, this assumption does not always hold in real-world data stream classification problems and the labeling of data streams is time-consuming and expensive. Additionally, to adapt to the change in data streams, the optimization of the learnable parameters also imposes high computational overhead for supervised approaches.

Semi-supervised approaches [Masud et al., 2012; Shao et al., 2016; Wagner et al., 2018; Zhu and Li, 2020; Din et al., 2020] are developed as an alternative solution to perform data stream classifications using a small portion of labeled data and have shown substantial success. However, several challenges still remain. First, the detection of a novel class strongly depends on certain threshold parameters and the determination of threshold parameters is an open challenge. Secondly, the overlap among different classes is a common problem in data stream classification problems while very little research work has been conducted on handling data streams with overlapped classes. Thirdly, most of the existing semi-supervised classification frameworks classify data streams with partially labeled data in a passive learning manner. For better classification performance, this requires an effective labeling strategy to actively guide the learning procedure.

Considering the limitations of the existing methods described earlier, we propose a Clustering-based Data Stream Classification framework with Active Learning, namely CDSC-AL, to handle non-stationary data streams. The proposed framework consists of three main steps: (i) concept drift and novel class detection through clustering, (ii) novel concept learning and concept drift adaptation through active learning, and (iii) classification of data streams using label propagation. With these three steps, CDSC-AL aims to perform non-stationary data stream classification by reducing the labeling costs and handling the overlap among classes. In summary, the contributions of this paper are as follows:

• Extend a density-based data stream clustering method to capture concept drift and concept evolution for nonstationary data streams with a dynamic threshold.
• Develop an effective distance-based active learning procedure to query a small portion of labels for adapting to changes in data streams.
• Propose a classification procedure to handle the overlap among classes by investigating the sub-cluster structure inside clusters.

The remainder of this paper is organized as follows. Section 2 provides a review of the related work. The details of the CDSC-AL framework are discussed in Section 3 and the complexity analysis of the CDSC-AL framework is described in Section 4. Section 5 presents the experimental results and comparison studies with the state-of-the-art methods. Concluding remarks and future work are outlined in Section 6.

2 RelatedWork

Over the past few decades, great efforts have been conducted to adapt offline supervised learning techniques for classifying streaming data. In [Aggarwal et al., 2006], the authors proposed a dynamic data classification framework using traditional classifiers to classify streaming data. A general framework was developed for adapting conventional classification techniques to perform data stream classification using clustering in [Masud et al., 2010; Masud et al., 2012]. In [Bifet and Gavalda, 2007; Bifet et al., 2013], ADaptive sliding WINdow (ADWIN) is proposed as a detector to capture the change of data streams and work collaboratively with traditional classification techniques for handling data streams. Later, ADWIN was widely used in ensemble-based data stream classification frameworks [Bifet et al., 2010b; Gomes et al., 2017]. To enhance the time and memory efficiency, a Self Adjusting Memory (SAM) model is introduced for offline classifiers to deal with non-stationary data streams in [Losing et al., 2018].

Unlike supervised approaches, semi-supervised methods utilize a more realistic assumption on the availability of labels for data streams. The Linear Neighborhood Propagation [Wang and Zhang, 2007] method is used to perform data stream classification using a limited amount of labeled data. In [Masud et al., 2012], ECSMiner is proposed to employ the clustering procedure for data stream classification in a semisupervised manner. A combination of semi-supervised Support Vector Machines and k-means clustering is employed in [Zhang et al., 2010] for classifying data streams. In [Hosseini et al., 2016], data streams are divided into chunks and an ensemble of cluster-based classifiers is used to propagate labels among each chunk. The Co-forest algorithm [Li and Zhou, 2007] is extended for data stream classification using a small amount of labeled data in [Wang and Li, 2018].

Recently, online graph-based semi-supervised data stream classification frameworks were investigated in [Ravi and Diao, 2016; Wagner et al., 2018]. In [Ravi and Diao, 2016], the authors continuously maintained a graph using both the labeled and unlabeled data over time and then predicted the label for incoming unlabeled instances through label propagation. Another novel online graph-based semi-supervised approach is introduced to reduce the time and memory complexity [Wagner et al., 2018]. Primarily, it utilizes a temporal label propagation procedure to not only label the new instances but also to learn from them.

Few recent studies on data stream classification incorporate active learning into the semi-supervised learning framework [Lughofer et al., 2016; Mohamad et al., 2018]. Such approaches handle the high labeling costs of data streams by actively querying labels for a small subset of interesting samples. In our proposed framework, we introduce a new active learning strategy to address the high labeling cost issue and combine it with a label propagation procedure to classify data streams in a semi-supervised manner.

3 Proposed Approach

In this section, the basic notations and assumptions for the CDSC-AL framework are introduced first. Then, we provide an overview of the CDSC-AL framework and discuss its three main components: concept drift and evolution detection through clustering, the adaptation of drifted and novel concepts using active learning, and classification through label propagation.

3.1 Notations and Assumptions

Notations. Let DS be an unknown data stream and CHt is a chunk of data from DS such that DS = ⋃∞t=1 {CHt} where t refers to the time index of a data chunk. For each data chunk, CHt = ⋃|CHt| i=1 {xit |xit ∈ Rm} where xit denotes a data sample in CHt and m is the dimension of xit . Assume HSt = {GSt,LSt} is the summary of a data stream where GSt and LSt represent the macro-level and the micro-level summary of DS. We use Z i t to represent the ith cluster center of DS at time t, and SC i,j t refers to the j th sub-cluster center of cluster i at time t. The notation yi,j t denotes the class label of SC i,j t .

Assumptions. Considering the non-stationary nature of data streams, the proposed CDSC-AL framework assumes:

• The characteristics of data streams can change abruptly or gradually.
• Multiple novel concepts may arise simultaneously.
• Overlapped classes will appear over time.

3.2 An Overview of CDSC-AL Framework

A general algorithm description of the CDSC-AL framework is presented in Algorithm 1. We extended the recently developed density-based stream clustering algorithm, namely dynamic fitness proportionate sharing (DFPS-clustering) [Yan et al., 2019; Yan et al., 2020], to perform the classification of data streams considering several aspects. First, a new merge procedure between clusters from the incoming data chunk and historical clusters is employed and the modified merge procedure is used to detect novel classes and drifted classes. Second, two levels of cluster summary are maintained continuously to reflect the characteristics of the data stream through an active learning procedure. Third, an effective classification procedure using the k-nearest-neighbor (KNN) rule [Altman,

Algorithm 1 An overview of CDSC-AL framework

Input: DS

Parameters: Ct: the set of clusters at time t; CHt: the current data chunk; CCHt : a set of clusters discovered in CHt; Qt: a small set of samples for active label querying in CHt; YQt : the label set of the queried samples Qt; YCHt : the label set for CHt.

Output: HSt

• 1: for t = 1 to∞do
• 2: Conduct recursive density evaluation on CHt and rank all samples of CHt according to their density values
• 3: Perform the search of possible clusters in CHt
• 4: Merge highly overlapped clusters to obtain CCHt
• 5: if t == 1 then
• 6: HSt = ∅, Ct = CCHt
• 7: [Qt, YQt ] = ACTIVEQUERY(HSt, Ct, CHt)
• 8: YCHt =CLASSIFY(HSt, Qt, YQt , CHt)
• 9: HSt=CLUSTERINGMODEL(HSt, CCHt , CHt)
• 10: else
• 11: Ct=CHECKMERGE(HSt, CCHt , CHt)
• 12: [Qt, YQt ]=ACTIVEQUERY(HSt, Ct, CHt)
• 13: YCHt =CLASSIFY(HSt, Qt, YQt , CHt)
• 14: HSt=CLUSTERINGMODEL(HSt, CCHt , CHt)
• 15: end if
• 16: Return HSt
• 17: end for

1992] is introduced to classify the incoming data chunk based on the summary and queried labels. Additionally, the overlap among classes is addressed by exploring the sub-cluster information from the micro-level summary.

3.3 Concept Drifts and Evolution Detection through Clustering

To capture the non-stationary property of data streams, we modified the DFPS-clustering algorithm substantially by employing a new cluster merge procedure between the historical clusters and new clusters. Then, we use the new DFPSclustering method to distinguish novel concepts from drifted concepts. Algorithm 2 summarizes the new cluster merge procedure for the detection of drifted and novel concepts.

As shown in Algorithm 2, the new merge procedure utilizes the density of boundary instances to decide whether a merge should happen between a historical cluster and its neighboring cluster from CHt. Then, it generates two types of clusters: (i) novel clusters and (ii) updated clusters. Clusters that are not merged with historical clusters are considered as novel clusters while the merged clusters are defined as updated clusters. Based on these two types of clusters, the novel concepts are captured by novel clusters and drifted concepts are identified as updated clusters. To validate the existence of novel clusters, we use the mean and standard deviation of the density values of historical clusters to compute a dynamic density threshold. Let C no t be a novel cluster and FCno t be its density value. The mean and standard deviations of historical clusters are denoted as µ(FCt ) and σ(FCt ), respectively. The following Remark is defined for novel cluster detection.

Remark 1 is derived from the three-sigma principle of Gaussian distribution used in [Yan et al., 2019] and it means

Algorithm 2 New cluster merge procedure

Parameters: LNC: a list of paired clusters between a historical cluster and its neighboring clusters in CHt, XB: a set of boundary samples between each pair of clusters in LNC

• 1: procedure CHECKMERGE(HSt, CCHt , CHt)
• 2: Identify the paired neighboring historical clusters in HSt for CCHt to obtain LNC
• 3: Extract XB for each pair of neighboring clusters in LNC
• 4: Evaluate the density of XB and check for the density drop for each pair of neighboring clusters
• 5: Merge each pair of neighboring clusters when there is no density drop in XB
• 6: Mark unmerged clusters as novel clusters and merged clusters as updated clusters
• 7: Validate the existence of novel clusters using Remark 1
• 8: Return Ct = [novel clusters, updated clusters]
• 9: end procedure

a cluster is considered as a valid novel cluster if its density value falls inside the one-sigma distance from the average density of historical clusters at time t. With Remark 1, a novel cluster detector with a dynamic density threshold is used for validating the existence of novel clusters.

3.4 Adaptation of Drifted and Novel Concepts using Active Learning

Considering time and space constraints, we maintain a summary of the data stream rather than keeping all historical samples fromDS. The maintained summary HSt consists of two levels of summary on DS: (i). macro-level summary GSt, and (ii) micro-level summary LSt. The definitions of these two levels of summary are expressed as:

and

Where F i t and Rit denote the density value and radius of the ith cluster at time t, respectively. yi,j t refers to the class label of SC i,j t and all samples from SC i,j t share the same label. LSt is used to explore the sub-cluster structure of each cluster when classes are highly overlapped. Specifically, we split each cluster into a set of sub-clusters such that each subcluster only has a unique class label. Instead of computing the mean vector for each sub-cluster, we consider only the sample with the highest density value in each sub-cluster as the sub-cluster center and use it for label propagation.

These two levels of summary are continuously updated to adapt to the change of DS using an active learning procedure. Since two types of clusters can be obtained from the clustering analysis, a hybrid active learning strategy of informativebased and representative-based sampling is introduced to reduce the labeling costs. The adaptation procedure of these two levels of summary is provided in Algorithm 3. In Algorithm 3, for novel clusters, the representative-based query

Algorithm 3 Adaptation of drifted and novel concepts

Parameters: Xno: a set of samples from novel clusters; Xup: a set of samples from updated clusters; QI: a set of queried samples using the Informative-based sampling; QR: a set of queried samples using Representative-based sampling; YCHt : the label set for CHt.

• 1: procedure CLUSTERINGMODEL(HSt, Ct, CHt)
• 2: [Qt, YQt ]=ACTIVEQUERY(Ct, CHt)
• 3: YCHt =CLASSIFY(HSt,Qt, YQt ,CHt)
• 4: Update the GSt according to Ct
• 5: Update the LSt using YCHt
• 6: return HSt = [GSt, LSt]
• 7: end procedure
• 8: procedure ACTIVEQUERY(Ct,CHt)
• 9: Extract novel clusters and updated clusters fromCt
• 10: Identify samples that are close to the novel clusters as Xno
• 11: Identify samples that are close to updated clusters as Xup
• 12: Representative-based sampling for Xno to obtain QR
• 13: Informative-based sampling for Xup to obtain QI
• 14: Qt = (QI ∪QR)
• 15: Query labels from human experts to obtain YQt
• 16: return [Qt, YQt ]
• 17: end procedure

[Gu et al., 2019] is performed by sampling from the centers of clusters. On the other hand, we conduct the informativebased query [Gu et al., 2019] in updated clusters through a distance-based strategy. Unlike the entropy-based sampling [Lughofer et al., 2016] strategy, samples that are relatively far from the updated clusters are selected as informative samples for label querying. Let Qt be the set of queried samples and YQt be the label set for Qt. After the active label query, the label propagation procedure begins to predict the label of the remaining samples in CHt using YQt and HSt. Finally, the predicted labels are used to update the LSt with a two-step procedure. First, we update the centers of sub-clusters within updated clusters with new samples that have higher density values. Second, we create a set of new sub-clusters for each novel cluster to capture the characteristics of novel concepts.

3.5 Classification through Label Propagation

To classify an incoming data chunk, we employ an effective label propagation procedure based on HSt and Qt. First, a set of prototypes with label information are obtained from HSt and Qt. Then, the KNN-based classification procedure is employed to propagate the labels of the prototypes to samples in CHt. Here, we set the value of k to five and the classification procedure is presented in Algorithm 4.

4 Complexity Analysis

Here, we discussed the time and memory complexity of the CDSC-AL framework using the following parameters:

• n: the number of samples from an incoming data chunk
• m: the number of dimensions of an incoming instance
• |SCt|: the total number of sub-clusters at time t
• |Ct|: the total number of clusters at time t
• k: the number of nearest neighbors

Algorithm 4 Classification through label propagation

Parameters: YCHt : the label set for CHt; Subr: a set of representatives from sub-clusters; Pt: a set of prototypes with labels.

• 1: procedure CLASSIFY(HSt,Qt, YQt ,CHt)
• 2: Extract sub-cluster centers and its labels fromHSt as Subr
• 3: Pt = Subr ∪ [Qt, YQt ]
• 4: Propagate labels from the prototype set to samples in CHt using KNN rule and obtain the predicted label set YCHt
• 5: return YCHt
• 6: end procedure
• |Qt| the number of queried samples at time t

Time Complexity. The density evaluation of the new DFPS-clustering procedure requires O(n2m) distance calculations. To update HSt, there will be O(nm|Ct| + nm|SCt|) ≤ O(2nm|SCt|) distance calculations where |Ct| ≤ |SCt|. The classification of the incoming data chunk will require O(knm(|SCt| + |Qt|)) distance calculations. Thus, the total time complexity of a single data chunk in terms of distance calculations is expressed as: O(n2m + 2nm|SCt| + knm(|SCt| + |Qt|)).

Memory Complexity. For LSt, the memory space complexity is expressed as O(|SCt|(m+ 1)) ≈ O(m|SCt|). In terms of GSt, it takes O(|Ct|(m+ 2)) ≈ O(m|Ct|) memory space. The total memory complexity will be O(m(|SCt| + |Ct|)).

5 Experimental Studies and Discussions

In this section, experiments are conducted on the CDSC-AL framework using nine benchmark datasets, and comparison studies with the state-of-the-art methods are presented.

5.1 Experimental Setup

Datasets and Streaming Settings. Ninemulti-class benchmark datasets, including three synthetic datasets and six wellknown real datasets from [Dheeru and Karra Taniskidou, 2017], are used in the experiments for performance evaluation. Table 1 summarizes these datasets in terms of sample size, dimensionality, number of classes, and class overlap. According to Table 1, the Forest, Syn-2, CIFAR10, and GasSensor datasets have highly overlapped classes. Following the setting in [Aggarwal et al., 2006; Din et al., 2020], we partition each benchmark dataset into a number of data chunks with a fixed size of 1000 samples and pass them sequentially to each algorithm in the experiment. In Syn-1, Syn-2, Sea, and Shuttle datasets, data chunks are arranged in an order to simulate abrupt concept drifts. For remaining datasets, we arrange data chunks in an order that generates the gradual concept drifts.

Compared Methods. We compared the CDSC-AL framework with the state-of-the-art methods considering two aspects: (i) comparison with semi-supervised approaches, and (ii) comparison with supervised approaches. We selected two existing semi-supervised methods, namely OReSSL [Din et al., 2020] and LNP [Wang and Zhang, 2007], and results are summarized in Table 2. Four supervised methods, including Leverage Bagging (LB) [Bifet et al., 2010b], OZA Bag ADWIN (OBA) [Bifet et al., 2009], Adaptive Hoeffding Tree (AHT) [Bifet and Gavald`a, 2009], and SAMkNN [Losing et al., 2018], are used for the second comparison study. The results are presented in Table 3. The MATLAB code for semisupervised methods is released by the authors and all codes for supervised methods can be found on the Massive Online Analysis (MOA) framework [Bifet et al., 2010a]. The python code of the CDSC-AL framework is available at the link 1 . All experiments are conducted on an Intel Xeon (R) machine with 64GB RAM operating on Microsoft Windows 10.

Parameter Setting. For the semi-supervised methods and CDSC-AL, the portion of labeled data of each incoming data chunk is set as 10%. For supervised methods, the labels of all samples from an incoming data chunk are provided to update the classifier after classification while CDSC-AL utilized only 10% labeled data.

Evaluation Metrics. Due to the imbalanced class distributions in benchmark datasets, we use the balanced classification accuracy (BA) [Brodersen et al., 2010] and the macroaverage of F-score (Fmac) [Kelleher et al., 2020] as performance evaluation metrics. We recorded these two metrics over the entire data stream classification and reported the average values for performance evaluation. The best results are highlighted in bold-face. The Friedman and Nemenyi posthoc tests [Demˇsar, 2006] are employed to statistically analyze the experimental results with a significance level of 0.05.

1 https://github.com/XuyangAbert/CDSC-AL

5.2 Results and Discussions

Comparisonwith Semi-supervisedMethods. To compare the CDSC-AL method with the OReSSL and LNP methods, we repeated each experiment ten times and the average results are presented in Table 2. From Table 2, the balanced classification accuracy shows that the CDSC-AL method outperforms the other two methods on most data streams with the lowest rank of 1.11. In terms of Fmac, CDSC-AL also provides better performance on most data streams. For data streams with abrupt concept drifts, CDSC-AL still achieves slightly better or comparable performance. From the Nemenyi post-hoc test, Figures 1 and 2 reveal that there is a statistically significant difference between CDSC-AL and LNP in terms of BA and Fmac. Although CDSC-AL shows statistically comparable performance with the OReSSL method, it does not require any parameter optimization or an initial set of labeled data.

Comparison with Supervised Methods. Table 3 presents the results of CDSC-AL and the four supervised methods. Using only 10% of the labels, Table 3 demonstrates that the CDCS-AL method achieves the best performance on six of the benchmark data streams including Syn-1, Syn-2, Sea, GasSensor, MNIST, and CIFAR10. In Figures 3 and 4, CDCS-AL shows statistically comparable performance to the LB, OBA, and AHT methods on the remaining three data streams from the Nemenyi test. Also, CDSC-AL has statistically better performance than the SAMkNN approach. For data streams with abrupt concept drifts, CDSC-AL presents slightly better or comparable performance relative to supervised approaches. In summary, the comparison study with supervised methods reveals that CDSDF-AL always provides statistically better or comparable performance than the supervised methods using only a small proportion of labeled data.

6 Conclusions and FutureWork

We presented a clustering-based data stream classification framework through active learning (CDSC-AL) to handle non-stationary data streams. We developed a new cluster merge procedure as a part of the new DFPS-clustering procedure and used the new DFPS-clustering procedure to capture the drifted concepts and novel concepts. Two levels of cluster summaries were maintained to effectively classify the incoming data samples in the presence of overlapped classes, and an active learning technique was introduced to learn the change of data distributions. The primary advantages of the CDSC-AL method can be summarized from several points of view: (i) no dependency on initial label set, (ii) effective detection for drifted concepts and novel concepts with dynamic threshold, and (iii) high-quality classification performance in the presence of overlapped classes with a small proportion of labeled data. The comparison studies with the semi-supervised and supervised methods justify the efficacy of CDSC-AL methods on both synthetic and real data.

In the future, we will investigate solutions to reduce the time complexity of CDSC-AL and implement the CDSCAL framework in some real-world applications such as text/image stream classifications.

Acknowledgements

This work is supported by the Air Force Research Laboratory and the OSD under agreement number FA8750-15-2-0116. Also, this work is partially funded by the NASA University Leadership Initiative (ULI), the National Science Foundation, and the OSD RTL under grants number 80NSSC20M0161, 2000320, and W911NF-20-2-0261 respectively. The authors would like to thank them for their support.