T-SMOTE: Temporal-oriented Synthetic Minority Oversampling Technique for Imbalanced Time Series Classification

1 Introduction

Time series classification has attracted great attention since it is fundamental in machine learning. However, in many real-world applications [Chi et al., 2020; Bhattacharya et al., 2017; Wang et al., 2015; Jo et al., 2015; Goroshin et al., 2015; Zhang et al., 2018], time series classification suffers from the class imbalance problem - the number of samples from majority class is much greater than that of samples from minority class, which hinders most machine learning algorithms from achieving good performance [Liu and Hsieh, 2020].

To address the class imbalance problem, many general, practical oversampling methods have been proposed, including: Random Repetition [He and Garcia, 2009], SMOTE [Chawla et al., 2002], Borderline-SMOTE [Han et al., 2005], ADASYN [He et al., 2008], MWMOTE [Barua et al., 2014], MBS [Liu and Hsieh, 2020], etc. However, most of them do not consider the temporal information (i.e., gradually and continuously changing characteristics) of time series data, which degrades their performance. SPO [Cao et al., 2011], INOS [Cao et al., 2013] and MBO [Gong and Chen, 2016] are specific oversampling methods for handling time-series data. However, SPO and INOS can only be applied on univariate time series data, while MBO loses the sequential structure of newly-generated samples.

∗Chuan Luo is the corresponding author of this work (Email: chuanluophd@outlook.com).

Further, in many real-world scenarios of time series classification, early prediction is desirable [He et al., 2013]. Specifically, given a time series, the task of early prediction is to conduct forecasting based on the prefix sub-time series rather than taking the whole time series as input. In industrial practice, early prediction is important; for instance, in the application scenario of failure prediction in cloud platforms, hardware failures are required to be predicted as early as possible, so that proactive actions could be taken in time to mitigate negative consequences [Luo et al., 2021].

In this paper, a novel, temporal-oriented oversampling approach, dubbed T-SMOTE, is proposed for synthesizing samples for minority class. First, we consider the nature of classification that the samples, which are closer to class border, may contribute more than other samples, which are far away from class border [Han et al., 2005]. Also, considering that the nature of time series data is gradually and continuously changing, T-SMOTE generates candidate samples near class border based on the temporal characteristics of each sample in minority class, and the newly generated candidates would bring more pattern information. Then, for each generated sample x near class border, in order to incorporate temporal information, T-SMOTE utilizes a new method to determine x's neighbor based on temporal characteristics, instead of using the conventional K-Nearest-Neighbors (KNN) method adopted by existing methods; after determining x's neighbor based on temporal characteristics, T-SMOTE synthesizes more samples based x and x's neighbor. Finally, T-SMOTE employs a weighted sampling method on all generated samples near class border and all synthetic samples to mitigate the sample noise. In this way, compared to existing methods, T-SMOTE can better capture the temporal nature, and also T-SMOTE handles class imbalance problem more effectively and achieves higher performance in early prediction. We summarize the main contributions as follows:

• We propose a novel and effective oversampling method dubbed T-SMOTE for imbalanced time series classification. In order to handle the class imbalance problem on time series data effectively, T-SMOTE aims to generate more samples near class border for minority class.
• T-SMOTE proposes to utilize a new method to synthesize more samples for minority class based on temporal characteristics, compared to existing methods that adopt conventional KNN method.
• We conduct extensive experiments on both univariate and multivariate datasets to compare T-SMOTE against 8 state-of-the-art competitors, and the results show that T-SMOTE better handles class imbalance problem on both univariate time series data and multivariate time series data. Further, our evaluations present that T-SMOTE can achieve better performance in early prediction.

2 Our Proposed T-SMOTE Approach

In this section, we present the technical details of our proposed T-SMOTE approach.

2.1 Preliminaries

Following the common practice without loss of generality, we treat the minority class as positive class and the majority class as negative class. Therefore, in the context of imbalanced time series classification, the number of positive samples is much less than the the number of negative samples. The goal of our method is to re-balance the training set by generating more positive synthetic samples, in order to achieve better performance in the subsequent classification task.

For simplicity, we denote the set of raw positive samples in training set as P = {X1, . . . ,Xi, . . . ,Xn}, where Xi is a positive sample with feature values collected at all timestamps. Positive sample Xi = (x1i · · · xTi ) ∈ RT×d is a 2-dimensional matrix consisting of a series of feature vectors, where T is the last timestamp and also indicates the sequence length. For timestamp j ∈ {1, . . . , T}, feature vector xji ∈ Rd is a 1-dimensional vector with d feature values collected at j-th timestamp. Notation N denotes the set of all negative samples in training set, and the imbalance ratio is r = |N|/|P |.

For each raw sample Xi, we generate new samples based on subsequences [He et al., 2013] with length w. As illustrated in Figure 1, a generated sample Xl i =

(xT -l-w+1 i , · · · , xT-l i ) is a subsequence of Xi with length w and the last timestamp of T - l, where l is the leading time of the generated sample. Given a specific leading time l, Xl = {Xl1 , . . . ,X l i , . . . ,X ln } is the set of all generated samples for raw samples in X.

2.2 Approach Overview

Our proposed T-SMOTE approach consists of three steps: (1) based on each positive sample, T-SMOTE generates a set of candidate samples near class border; (2) for each generated sample x near class border, T-SMOTE synthesizes more samples considering x's temporal characteristics; (3) T-SMOTE employs a weighted sampling method on all generated samples, in order to alleviate sample noise.

2.3 Generation of Near-border Samples

In the research field of machine learning, since the classification task aims to determine a class border between different classes, it is intuitive that near-border samples (i.e., samples near class border) would contribute more to the classification task than those far away from class border [Han et al., 2005]. For oversampling methods, the common practice of seeking near-border samples is based on KNN algorithm. However, conventional KNN algorithm is unsuitable for handling 2-dimensional time-series data [K¨oknar-Tezel and Latecki, 2011]. In fact, considering the gradually and continuously changing characteristics of time series data, compared to Xl i , sample Xl+1 i (with larger leading time) is closer to class border. Further, it is intuitive that, if the leading time l is too large-valued, then the corresponding sample with such large leading time would possibly belong to negative class. For example, in the scenario of hardware failure prediction (where positive and negative samples correspond to failure and health, respectively), a sample with larger leading time means that the corresponding timestamp is farther away from failure occurrence, so the hardware at the corresponding timestamp tends to be healthy.

Hence, for each raw positive sample Xi, the process of generating new near-border samples underlying T-SMOTE is illustrated in Figure 1. From Figure 1, T-SMOTE generates multiple samples X0 i ,X1 i , . . . ,X L i sequentially. As discussed before, with the increment of leading time, such generated samples with larger leading time would be closer to class border. Through this way, T-SMOTE can generate (L + 1) × |P | positive samples in total.

Furthermore, to verify the aforementioned intuition that the positive samples with larger leading time are closer to class border, we conduct empirical studies. It is recognized that the prediction score of positive samples tends to be 1, while the prediction score of negative samples tends to be 0; thus, if the intuition is reasonable, the prediction score of generated samples with larger leading time should be smaller (even around 0), since samples with enough large leading time would belong to negative class. In our empirical study, we first train a long short-term memory (LSTM) model [Hochreiter and Schmidhuber, 1997] based on various raw training sets, and then use such trained LSTM model to predict the generated samples with various leading time. Figure 2 presents the average prediction score output by our trained LSTM model with different leading time on various datasets (which will be described in the Experiments section). According to Figure 2, the prediction score decreases with the increment of leading time, which verifies our intuition.

Then, we need to address how to decide the maximum leading time L that not only makes the generated samples near class border but also makes the samples possibly belong to positive class. To address this problem, we employ a spy-based method, which has shown success in the field of positive-unlabeled learning to identify true negative samples from unlabeled data [Liu et al., 2002]. Following the standard practice [Liu et al., 2002], we randomly select 15% of negative samples and relabel them to positive to act as spies Pspy and mix them with positive samples P , resulting in a new set of spy-injected positive samples P ′ = P ∪ Pspy and a new set of negative samples N ′ = N-Pspy. Then, we re-balance the P ′ and N ′ by randomly repeating [He and Garcia, 2009] the true positive samples in P ′ , and train a classifier f based on the balanced P ′ and N ′ . Afterwards, we can obtain prediction scores of all spy samples Pspy based on f, and set the maximum score as threshold h. Finally, we iteratively generate samples Xl with leading time of l (l increases from 0): in the iteration where l = l0, if the average prediction score Sl0 = Σni=0 f (Xl0 i )/n of Xl0 is smaller than threshold h, T-SMOTE considers that Xl0 belongs to negative class and should be neglected; meanwhile, the process of generating near-border samples is terminated. Hence, we obtain L = l0 - 1, and all generated samples with leading time no greater than L are regarded as positive ones.

After the generation of near-border samples, we can obtain L+ 1 generated positive samples for each Xi, and each sample has a related prediction score sli = f(Xl i ), resulting in a sample-score pair (Xl i , sli ), where sli indicates the probability of Xl i that belongs to positive class.

2.4 Generation of More Synthetic Samples

In traditional SMOTE method and its variants, the key process is to find a suitable neighbor for each positive sample and then generate a synthetic sample along the line segment between this positive sample and its neighbor. In our approach, we follow this direction, but propose a new method to synthesize more samples for minority class regarding temporal characteristics. Compared to SMOTE that calculates the Euclidean distance between the feature vectors to find the knearest neighbors, T-SMOTE defines a novel concept of temporal neighbor as follows: for each positive sample Xl i with leading time l, Xl i and Xl+1 i are temporal neighbors. In particular, T-SMOTE uses temporal neighbor to exploit the temporal characteristics of time series data. In more detail, for sample Xl i , T-SMOTE synthesizes more samples along the line segment between Xl i and its temporal neighbor Xl+1 i :

where α is a random value generated by Beta distribution B(sli , sl+1 i ), which is a continuous probability distributions defined on the interval [0, 1] and is the conjugate prior probability distribution for the Bernoulli distribution. The reason why T-SMOTE does not use Gaussian Distribution as other works do is that T-SMOTE can make full use of the prior knowledge. Besides, if a feature is categorical, T-SMOTE selects the specific value from Xl i with the probability of α (i.e., selecting the specific value from Xl+1 i with probability of 1 - α) as the new feature value. The score of the newly synthetic Xnew is as follows:

Then, we need to address how many synthetic samples should be generated for each Xl i . Inspired by safe-levelSMOTE and ADASYN, the number of synthetic samples should be decided based on the safe level of Xl i . In practice, if the prediction score of Xl i is larger, then Xl i is with higher safe level. Hence, it is advisable to synthesize more samples with regard to higher safe level. Specifically, T-SMOTE determines the number of synthetic samples as follows:

where r is the imbalance ratio (as defined in Section 2.1). Afterwards, we can obtain mli synthetic, positive samples based on each Xl i . Also, each synthetic sample has a related score to indicate the probability to be positive.

2.5 Weighted SamplingMethod

As mentioned in [Bunkhumpornpat et al., 2009; Liu and Hsieh, 2020], the samples near class border may lead to an ambiguous situation. To address this issue, T-SMOTE utilizes a weighted sampling method to reduce the risk from nearborder samples. For each sample X, we first assign to X a weight w = max(0, s - h), where s is the prediction score of X, and h is the threshold determined in the generation of near-border samples. Finally, T-SMOTE constructs the final positive dataset P ′ by randomly selecting |N| samples from all generated positive samples with the selection probability that is proportional to the each sample's weight w.

3 Experiments

In this section, to demonstrate the effectiveness of T-SMOTE, we conduct extensive experiments on 7 public univariate and 3 multivariate time-series datasets to compare T-SMOTE against 8 state-of-the-art competitors.

MBO are proposed specifically for time series data: MBO can handle multivariate time-series data by default; Since original INOS is only designed for univariate time series data, to address this problem, for INOS we treat each multivariate sample as multiple univariate samples and process them separately. Besides INOS and MBO, other competitors can only accept 1-dimensional vector as input, while time series samples are 2-dimensional matrix which contains both timestamp and feature dimensions. In our experiments, we concatenate the raw 2-dimensional sample along the timestamp dimension to flatten the matrix as 1-dimensional vector for these competitors that only accept 1-dimensional vector.

3.3 Experimental Setup

Evaluation Metrics

We adopt three widely used metrics in imbalance learning to evaluate the performance of each approach, including (1) AUC, the Area Under the ROC Curve, which used in [Gong and Chen, 2016; Yan et al., 2017; Yin et al., 2020; Barua et al., 2014]; (2) F1: a general metric in classification as adopted by [Cao et al., 2013; Gong and Chen, 2016; Liu and Hsieh, 2020; Liang and Zhang, 2012; Cao et al., 2011; Yin et al., 2020; Barua et al., 2014]; (3) AUPRC: the Area Under the Precision-Recall Curve, a useful performance indicator for imbalanced data in the scenarios focusing finding positive samples, as used in [Huang et al., 2020; Yan et al., 2017].

Classifier Specification

In our experiments, after getting the re-balanced training datasets generated by T-SMOTE and all its competitors, we employ a uniform classifier to evaluate the quality of the generated datasets. In particular, in our experiments we adopt

3.1 Datasets

There are ten datasets that are commonly used in the context of imbalanced time-series classification [Cao et al., 2011; Cao et al., 2013; Gong and Chen, 2016]: (1) seven univariate datasets from UCR 1 time series repository, including Adiac, 50Words, FaceAll, SLeaf, TwoPats, Wafer and Yoga; (2) three multivariate datasets fromUCI 2 time series repository, including Libras, Hand and AUS. Following the common preprocessing practices in [Cao et al., 2013] and [Gong and Chen, 2016]: as these datasets originally contain multiple classes, we convert them into two-class by randomly selecting one class as the positive class and treat the rest classes as the negative class. Additionally, in order to create high imbalance ratio and simulate the scenario of rare positive instances, we randomly select partial samples from the positive class and abandon others. For the split of training set and testing set, we randomly select 70% as training set and 30% as testing for each multivariate dataset in UCI following [Gong and Chen, 2016]; as these univariate datasets from UCR contain both training set and testing set, no extra processing is required. A summary of the datasets in our experiments is reported in Table 1.

3.2 Competitors

To evaluate T-SMOTE, we compare T-SMOTE with eight widely used, state-of-the-art competitors, including Repeat [He and Garcia, 2009], B-SMOTE [Chawla et al., 2002], ADASYN [He et al., 2008], MWMOTE [Barua et al., 2014], MBS [Liu and Hsieh, 2020], INOS [Cao et al., 2013] and MBO [Gong and Chen, 2016]. Among them, INOS and LSTM [Hochreiter and Schmidhuber, 1997] as the uniform classifier, since LSTM is recognized to be a commonly-used and effective time series prediction model.

1 http://www.cs.ucr.edu/∼eamonn/time series data

2 https://archive.ics.uci.edu/ml/datasets.php

3.4 Experimental Results on All Dataset

Table 2 shows the comparative results of T-SMOTE and its 8 competitors on both 7 univariate and 3 multivariate datasets. For each dataset, the best results across all 9 methods are indicated in boldface. It is clear that T-SMOTE achieves the best or equal best performance across all metrics of F1, AUPRC, and AUC compared to all its competitors on both univariate and multivariate datasets.

In particular, on univariate datasets, in terms of F1, AUPRC and AUC, T-SMOTE achieves average values of 0.7763, 0.8412 and 0.9293, which are considerably higher than those achieved by all its competitors. Compared to the second best method MBO with the average AUC value of 0.9164, T-SMOTE achieves 3.10% improvement, which is substantial considering high AUC values achieved by baseline competitors. Besides, on the multivariate datasets, the average F1, AUPRC and AUC values achieved by T-SMOTE are 0.7956, 0.8688 and 0.9906, and T-SMOTE performs much better than all its competitors. In terms of the evaluation metric of AUC, T-SMOTE outperforms the second best method MBO with a relative improvement of 2.36%. Specifically, on dataset AUS, T-SMOTE yields the F1 value of 0.8333, which is 3.33% higher than MBO. Therefore, the results in Table 2 clearly demonstrate the superiority of T- SMOTE over all its competitors on both univariate and multivariate datasets, which indicates that T-SMOTE might be able to bring benefits in practice.

3.5 Effectiveness of Using Temporal Information

To demonstrate the advantage of considering the temporal information, we further analyze the results in Table 2. As aforementioned, INOS, MBO and T-SMOTE are all designed to utilize temporal information, while other methods are not.

According to Table 2, it is apparent that, on all evaluation metrics of AUC, F1 and AUPRC, those methods that capture temporal information (i.e., INOS, MBO and T-SMOTE) achieve much better performance than other methods that do not utilize temporal information. Specifically, T-SMOTE is a variant of B-SMOTE and fully incorporates temporal information. When directly comparing T-SMOTE and B-SMOTE, the AUC, F1, AUPRC values achieved by T-SMOTE are 0.9476, 0.7821 and 0.8495, respectively, while those values obtained by B-SMOTE are 0.9143, 0.7193 and 0.8059, respectively. Hence, the performance improvement achieved by T-SMOTE is substantial. The observation confirms the considerable contribution of making the use of temporal information in both univariate and multivariate time series classification tasks.

3.6 Experimental Results of Early Prediction

We conduct experiments to demonstrate that the adoption of generating samples with larger leading time is able to help T-SMOTE achieve better early prediction performance. The testing dataset is constructed as follows: for each testing dataset, the positive samples are generated using the specific leading times of l = 3, l = 5, l = 10 separately (for example, l = 5 means we conduct prediction ahead of 5 timestamps). Then we test the performance of each method on testing dataset, and the related results are reported in Table 3.

The results presented in Table 3 clearly demonstrates that T-SMOTE achieves the best performance under all leading time, and its advantage becomes greater with the increment of leading time. For example, the average value of AUPRC achieved by T-SMOTE is 0.8290, which is 3.29% greater than the second best competitor MBO when the leading time is 3, and the performance improvement becomes 5.86% when leading time is 5. Furthermore, when leading time is 10, T-SMOTE outperforms MBO by 10.54%. This is intuitive, because the samples generated by T-SMOTE contains those ones with different leading times, which make the classifier learn more informative patterns and thus drive T-SMOTE outperform its competitors.

Also, from Table 3, with the increment of l from 3 to 10, the values of F1, AUPUR and AUC obtained by all oversampling methods degrade. Specifically, on the Adiac dataset, when leading time is 10, the F1 values achieved by INOS, MBO and T-SMOTE all drop to 0, which means that the classifiers trained with INOS, MBO and T-SMOTE fail to predict ahead of 10 timestamps. Actually, this is not surprising since samples with larger leading time are closer to or even across the class border from the positive class side to the negative class side, resulting in great class noise for the classifier.

To further study the effect between classification performance and leading time, we randomly select the AUS dataset to analyze their relationship. According to Figure 3, all methods suffer from the performance degradation with the increment of leading time. However, for any specific increment leading time, T-SMOTE still achieves the best performance. Besides, it is apparent that those methods that capture temporal information (i.e., T-SMOTE, INOS and MBO) always outperform other methods on various values of leading time.

4 Conclusions

Imbalanced time series classification is a popular and practical topic in diverse real-world applications. In this paper, we propose a novel temporal-oriented oversampling method dubbed T-SMOTE which considers the gradually and continuously changing characteristics in time-series datasets. T-SMOTE can process both univariate and multivariate datasets, and it can also perform well in the scenario of early prediction. Our extensive experiments on 10 datasets demonstrate that T-SMOTE achieves significantly better performance than all its state-of-the-art competitors. Moreover, T-SMOTE has been deployed to several scenarios in Microsoft Azure and Microsoft 365, such as disk failure prediction and high latency prediction, and has considerably improved the performance of the online models.