# Time Series Classification by Shapelet Dictionary Learning with SVM-Based Ensemble Classifier

Authors: Jitao Zhang; Weiming Shen; Liang Gao; Xinyu Li; Long Wen
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

Time series classification is a basic and important approach for time series data mining. Nowadays, more researchers pay attention to the shape similarity method including Shapelet-based algorithms because it can extract discriminative subsequences from time series. However, most Shapelet-based algorithms discover Shapelets by searching candidate subsequences in training datasets, which brings two drawbacks: high computational burden and poor generalization ability. To overcome these drawbacks, this paper proposes a novel algorithm named Shapelet Dictionary Learning with SVM-based Ensemble Classifier (SDL-SEC). SDL-SEC modifies the Shapelet algorithm from two aspects: Shapelet discovery method and classifier. Firstly, a Shapelet Dictionary Learning (SDL) is proposed as a novel Shapelet discovery method to generate Shapelets instead of searching them. In this way, SDL owns the advantages of lower computational cost and higher generalization ability. Then, an SVM-based Ensemble Classifier (SEC) is developed as a novel ensemble classifier and adapted to the SDL algorithm. Different from the classic SVM that needs precise parameters tuning and appropriate features selection, SEC can avoid overfitting caused by a large number of features and parameters. Compared with the baselines on 45 datasets, the proposed SDL-SEC algorithm achieves a competitive classification accuracy with lower computational cost.


---

## Body

## 1. Introduction

Time series classification (TSC) is a theoretical abstraction of many engineering problems, such as fault diagnosis, speech recognition, and electroencephalogram (EEG) identification. It has become an active research field in recent years [1]. To address the challenge of TSC problems, several methods have been proposed in the literature. An intuitive way to model time series by comparing the differences in time domain is called time domain similarity method. Time domain similarity methods process time series as high-dimensional points. A basic framework of time domain similarity based TSC method is utilizing different distance measurements to quantify similarity between time series and then combining 1-NN algorithm as the classifier. Several L1 or L2 norm distance measurements have been widely researched in [2]. To solve time axis distortion problem in time series, elastic distance measures are employed in TSC. Dynamic time warping (DTW) comes to be a popular elastic distance measurement. Several variants of DTW are compared in [2]. At the same time, some time series discretization techniques are proposed, such as symbolic aggregate approximation (SAX) [3], to reduce time series dimension and improve computational efficiency. Fuzzy similarity (FS) [4] is adapted into the characterizing defects problem, which is capable of processing time series signals affected by uncertainty and inaccuracy. In literatures, time domain similarity methods are proved intuitive and efficient but not suitable for complex dynamic systems.The model similarity method is another well-known way to deal with TSC problems. These methods represent time series by using multiple statistical models, such as Auto Regressive Moving Average (ARMA) [5], Hidden Markov Model (HMM) [6], and Gaussian Mixture Models (GMM) [7]. By comparing the parameters of the models, different class time series can be distinguished. In recent years, Deep Learning has become a common approach in machine learning and artificial intelligence fields, more and more neural network-based models have been introduced into TSC [8, 9]. Although model similarity methods have a high accuracy, the models used have a high level of abstraction, so these methods are not interpretable.Recently, more researchers are interested in the shape similarity method. It is human instinct to distinguish objects by their shapes. Such methods suggest imitating human intuition and use shapes to distinguish different classes of time series. Shape similarity methods discover local shape features, while other methods discover global statistic features. Therefore, these methods can obtain high accuracy with better interpretability. The base model of this article, the Shapelet algorithm, is a kind of shape similarity methods. Shapelet is a special concept which means one discriminative subseries in the time series [10]. More than high accuracy, Shapelet can also provide visualization results, which can point out further research directions for domain experts [11].Most of the existing Shapelet-based algorithms attend to discover Shapelets by searching candidates in the training dataset. Such algorithms have two drawbacks. First, the search requires extensive computation. As an illustration, the complexity of the original Shapelet algorithm isO (m4n2), where m is the length of time series and n is the number of instances in the dataset. Second, the searched Shapelet lacks generalization. Each Shapelet must be a segment in the existed instance, while the most discriminative Shapelet may never appear in the historical data. Thus, this paper proposes a novel algorithm named Shapelet Dictionary Learning with SVM-based Ensemble Classifier (SDL-SEC), which contributes following two points:(i)
Shapelet Dictionary Learning. Inspired by Dictionary Learning (DL), the proposed algorithm generates subseries (Shapelets) by optimizing an object function. Different from the searching method, SDL generates Shapelets directly.(ii)
SVM-Based Ensemble Classifier. According to our experience, different time series are sensitive to different features and different parameters. Classic SVM takes a lot of time to tune parameters and select feature subsets. To address this problem, we train a set of SVM models with randomly selected features and parameters and get final results through majority voting.The rest of this paper is organized as follows: Section2 reviews the research literature related to Shapelet algorithms and Dictionary Learning; Section 3 describes the structure of the proposed algorithm SDL-SEC; Section 4 presents the implementation of the SDL-SEC and compares the results with the baselines in 45 datasets; Section 5 concludes the paper and discusses future research directions.


## 2. Related Work

### 2.1. Shapelet Algorithm

The original Shapelet algorithm was constituted in [10] for time-series classification problem. In brief, there are three steps in the training stage of the original edition, as exhibited in Figure 1. First, a sliding window is used to extract time series segments, which are candidate Shapelets, and further figure out the minimum distances between candidate Shapelets and total time series in the dataset. Then, a candidate Shapelet orderline is built by arranging the minimum distances from small to large; thus, we can figure out the Information Gain (IG) and Optimal Split Point (OSP) of each orderline. High IG represents a good discrimination. The third step is to choose k-best Shapelets with higher IG. At the inference stage, a decision tree is built by k-best Shapelets’ OSPs, and untagged time series are classified by this decision tree.Figure 1
Original Shapelet algorithm procedure: (a) candidate Shapelet in a time series; (b) orderline; (c) best Shapelet.
(a)(b)(c)Followed the principle of Shapelet, many modified Shapelet-based algorithms have been proposed in recent years. These approaches have two main directions: speed-up the running time and improve the accuracy.The original Shapelet algorithm as described above is a recursive search method, calls for a high time complexity. Hence, some speed-up techniques are indispensable for improving Shapelet algorithm efficiency. Some efficient pruning strategies are suggested to avoid searching for unproductive Shapelets [11]. The representation methods map time series from the source space to a reduced-dimensional space, which reduce the searching time significantly [12]. Moreover, parallelizing the Shapelet algorithm makes it possible for GPU operations [13]. However, the speed-up techniques do not involve the substantial improvement of Shapelet discovery and therefore limit the accuracy of this family of methods.On the other hand, some Shapelet-based algorithms focus on improving accuracy. Grabocka et al. [11] suggest getting optimal Shapelet by optimizing a logistic loss objective function, which can further improve the classification accuracy. Instead of IG, Kruskall–Wallis and Mood’s median are employed as quality measurement for Shapelet selection [14]. Meanwhile, Hills et al. [14] suggest a feature transformation technique, which unbind the Shapelet algorithm from the decision tree classifier. Generally, this family of methods obtains high accuracy, but the computation cost is still high.In summary, most Shapelet-based algorithms do not achieve a good balance between efficiency and performance. A better Shapelet discovery mechanism is needed to improve the accuracy and reduce the runtime.


### 2.2. Dictionary Learning

Dictionary Learning is a widely used machine learning algorithm. Its main idea is assuming that signals can be represented by a linear combination of dictionaries. Strictly, the mathematical form of Dictionary Learning can be organized as(1)argminα,Z12T−αZ22+λα1s.t.zk2≤c,k=1,…,K,where T=T1,T2,…,Tn∈ℝn×m is the input time series signal, Z=Z1,Z2,…,ZK∈ℝK×m is a dictionary, α∈ℝn×K is a sparse coefficient, and we call Zk∈Z an atom of dictionary.Problem (1) is nonconvex when optimizing α and Z together. However, we can draw this problem to a two-step method: coefficient updating step and dictionary updating step. If Z is fixed, α updating subproblem is convex. Orthogonal Matching Pursuit (OMP) [15], Lasso [16], or Alternating Direction Method of Multipliers (ADMM) [17] are common methods to update α. If α is fixed, Z updating subproblem is a constrained least squares problem. Many convex optimization methods can solve this problem such as Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) [18], gradient descent [19], and K-SVD [20]. Perform the above two steps alternately until convergence.There are some similarities between Shapelet and Dictionary. Shapelet represents the time series local shape features; thus, the linear combination of Shapelets can represent time series partially or totally. This behaviour is similar to the main idea of Dictionary Learning. The linear combination of Dictionaries is considered to have the high representation ability for raw data. From this sight, those two kinds of methods can share the same underlying technique.To this end, Dictionary Learning technique is introduced to Shapelet discovery, which obtains a set of Shape-lets by solving several convex optimization problems. This will greatly reduce the amount of computation in the training phase. Different from search-based methods, the optimized Shapelet is a novel segment which does not appear in the existing data. This will improve the generalization ability of Shapelets.


## 2.1. Shapelet Algorithm

The original Shapelet algorithm was constituted in [10] for time-series classification problem. In brief, there are three steps in the training stage of the original edition, as exhibited in Figure 1. First, a sliding window is used to extract time series segments, which are candidate Shapelets, and further figure out the minimum distances between candidate Shapelets and total time series in the dataset. Then, a candidate Shapelet orderline is built by arranging the minimum distances from small to large; thus, we can figure out the Information Gain (IG) and Optimal Split Point (OSP) of each orderline. High IG represents a good discrimination. The third step is to choose k-best Shapelets with higher IG. At the inference stage, a decision tree is built by k-best Shapelets’ OSPs, and untagged time series are classified by this decision tree.Figure 1
Original Shapelet algorithm procedure: (a) candidate Shapelet in a time series; (b) orderline; (c) best Shapelet.
(a)(b)(c)Followed the principle of Shapelet, many modified Shapelet-based algorithms have been proposed in recent years. These approaches have two main directions: speed-up the running time and improve the accuracy.The original Shapelet algorithm as described above is a recursive search method, calls for a high time complexity. Hence, some speed-up techniques are indispensable for improving Shapelet algorithm efficiency. Some efficient pruning strategies are suggested to avoid searching for unproductive Shapelets [11]. The representation methods map time series from the source space to a reduced-dimensional space, which reduce the searching time significantly [12]. Moreover, parallelizing the Shapelet algorithm makes it possible for GPU operations [13]. However, the speed-up techniques do not involve the substantial improvement of Shapelet discovery and therefore limit the accuracy of this family of methods.On the other hand, some Shapelet-based algorithms focus on improving accuracy. Grabocka et al. [11] suggest getting optimal Shapelet by optimizing a logistic loss objective function, which can further improve the classification accuracy. Instead of IG, Kruskall–Wallis and Mood’s median are employed as quality measurement for Shapelet selection [14]. Meanwhile, Hills et al. [14] suggest a feature transformation technique, which unbind the Shapelet algorithm from the decision tree classifier. Generally, this family of methods obtains high accuracy, but the computation cost is still high.In summary, most Shapelet-based algorithms do not achieve a good balance between efficiency and performance. A better Shapelet discovery mechanism is needed to improve the accuracy and reduce the runtime.


## 2.2. Dictionary Learning

Dictionary Learning is a widely used machine learning algorithm. Its main idea is assuming that signals can be represented by a linear combination of dictionaries. Strictly, the mathematical form of Dictionary Learning can be organized as(1)argminα,Z12T−αZ22+λα1s.t.zk2≤c,k=1,…,K,where T=T1,T2,…,Tn∈ℝn×m is the input time series signal, Z=Z1,Z2,…,ZK∈ℝK×m is a dictionary, α∈ℝn×K is a sparse coefficient, and we call Zk∈Z an atom of dictionary.Problem (1) is nonconvex when optimizing α and Z together. However, we can draw this problem to a two-step method: coefficient updating step and dictionary updating step. If Z is fixed, α updating subproblem is convex. Orthogonal Matching Pursuit (OMP) [15], Lasso [16], or Alternating Direction Method of Multipliers (ADMM) [17] are common methods to update α. If α is fixed, Z updating subproblem is a constrained least squares problem. Many convex optimization methods can solve this problem such as Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) [18], gradient descent [19], and K-SVD [20]. Perform the above two steps alternately until convergence.There are some similarities between Shapelet and Dictionary. Shapelet represents the time series local shape features; thus, the linear combination of Shapelets can represent time series partially or totally. This behaviour is similar to the main idea of Dictionary Learning. The linear combination of Dictionaries is considered to have the high representation ability for raw data. From this sight, those two kinds of methods can share the same underlying technique.To this end, Dictionary Learning technique is introduced to Shapelet discovery, which obtains a set of Shape-lets by solving several convex optimization problems. This will greatly reduce the amount of computation in the training phase. Different from search-based methods, the optimized Shapelet is a novel segment which does not appear in the existing data. This will improve the generalization ability of Shapelets.


## 3. Shapelet Dictionary Learning with SVM-Based Ensemble Classifier

In this section, we introduce the structure of Shapelet Dictionary Learning with SVM-based Ensemble Classifier. SDL is a generative Shapelet discovery algorithm which combines DL and Shapelet. We train SDL in a supervised way and get subdictionary for each class. Then, the transformation technique uses subdictionaries to map time series from time domain to feature domain. Last, we present an SVM-based Ensemble Classifier to improve accuracy further.


### 3.1. Build SDL Atom

The atoms of the original DL present global features, while Shapelets present local features. So, we must reconstruct the SDL atoms before making the overall model. From the introduction in Section2.2, the original DL atom dimension is equal to the input signal dimension. More specifically, consider the following situation, an input signal T with m dimension, and the atom in DL with p dimension. In the original DL based algorithms, p is set equal to m inevitably. Nevertheless, in the SDL algorithm, an atom is a representation of the Shapelet; thus, the dimension p needs small than m. To address this problem, we introduce the Shift-Invariant Dictionary Learning (SIDL) technique [21] into our work, which use a sliding window to build the SDL atom and relax the constraint of p to p ≤ m.Figure2 explains how to generate the SDL atom. The SDL atom is denoted as d′∈ℝm, and the Shapelet is denoted as d∈ℝp, where p ≤ m. Shapelet may match anywhere in the time series, thus the sliding window which represents a Shapelet, which is sliding along the SDL atom to match the optimal location. In an SDL atom, only the Shapelet part has practical significance, and the rest part is assigned 0. In Figure 2, a Shapelet is matched at location q, the values in red blocks need to optimize, while the blue blocks are assigned 0. The matched location q is unique for each time series.Figure 2
Construction of SDL atom. The red window represents the Shapelet, and the blue blocks are assigned to 0.Q(d, q) is a function describes the mapping relationship between the Shapelet and the SDL atom. Given q and d, the SDL atom can be generated as follows [21]:(2)di′=Qd,qi=di−q,ifq+1≤i≤q+p,0,otherwise.


### 3.2. The SDL Model

To build the complete SDL model, further more constraints must be made. The complete SDL model is(3)argminα,q,d12∑i=1nTi−∑k=1KαikQdk,qik22+λ∑i=1nαi1s.t.dk2≤c,k=1,…,K0≤qik≤m−p,i=1,…,n;k=1,…,Kαik≥0,i=1,…,n;k=1,…,K,where Ti is a time series from the input dataset; the sparse coefficient {αik}, the corresponding shifts {qik}, and the Shapelet dictionary D=d1,d2,…,dK∈ℝK×p are outputs of the model which need to be optimized; the length of the Shapelet p, the number of Shapelets K, the weight λ, and the scale factor c are hyperparameters which need to be tuned. The scale constraint of dk avoids producing trivial solutions. The constraint of q controls the sliding window does not exceed the boundary. The nonnegative constraint of sparse coefficients is added to avoid the Shapelet inverted.Equation (3) is an unsupervised learning model, while time series classification is a supervised problem. To deal with this, we learn sub-Shapelet dictionaries for each class independently.


### 3.3. Optimization of the SDL

Equation (3) is a nonconvex problem. Commonly, a two-step optimization strategy is suitable for this problem. Sparse coefficients and Shapelet dictionary are updated alternately. The subobject of each step is convex.


#### 3.3.1. Update Sparse Coefficients

In this step, sparse coefficient is updated. Fix thed, and equation (3) turns to(4)argminα,q12∑i=1nTi−∑k=1KαikQdk,qik22+λ∑i=1nαi1s.t.0≤qik≤m−p,i=1,…,n;k=1,…,Kαik≥0,i=1,…,n;k=1,…,K.We optimizeα and q for each Ti independently, the problem turns to(5)argminαk12Ti−αkQdk,qk−∑j≠kKαjQdj,qj2+λαks.t.0≤qk≤m−p,k=1,…,Kαk≥0,k=1,…,K,where {αj}j≠k and {qj}j≠k are fixed.We use an enumeration method to find the bestqk, which calculates the object value with all possible locations, and the solution is located which minimizes equation (5):(6)qk∗=argmaxqkQdk,qkTt^,where t^≜Ti−∑j≠kαjQdj,qj.Because of the nonnegative constraint ofα, equation (5) is different from that of [21]. With the optimal qk∗, the update solution of αk is(7)αk∗=Qdk,qkTt^−λdk2,ifQdk,qkTt^>λ,0,otherwise.


#### 3.3.2. Update Dictionary

In this step, we fixα and the q and update the Shapelet dictionary d. Further, we fix {dj} j ≠ k and optimize dk independently. Thus, the problem (3) turns to(8)argmindk12∑i=1nTi−αikQdk,qik−∑j≠kKαijQdj,qij2s.t.dk2≤c.Equation (8) is a least square with quadratic constraints, and it can be optimized via the Lagrange Multiplier method. The optimal dk is(9)dk∗=ct˜t˜,ift˜∑i=1nαik2≥c,1∑i=1nαik2t˜,otherwise,where t˜≜∑i=1nαikt^i1+qik,p+qik, and t^i≜Ti−∑j≠kαijQdj,qij, and superscript [1 + qik, p + qik] means the segment from index 1 + qik to p + qik. A proof can be found in [21].


### 3.4. Supervised Shapelet Dictionary Learning Method for Classification Problem

In this subsection, we introduce the supervised SDL to obtain subdictionary of each class and use subdictionaries to transform time series from the time domain to the feature domain.We train SDL model forL classes independently and obtain L subdictionaries. The complete Shapelet dictionary S = [D1, D2, …, Dl, …, DL], where Dl means lth subdictionary. See Algorithm 1 for pseudo-code of complete supervised SDL.Algorithm 1: Shapelet dictionary learning.
Input: time series data set T, parameters p, K, λ, c, stopping threshold ε;Output: complete Shapelet dictionary S;(1)
Forl = 1, 2, …, Ldo(2)
Initialize sub-dictionariesDl, sub-coefficient Al, sub-location ql(3)
Repeat(4)
Fork = 1, 2, …, Kdo(5)
updateqlk with (4)(6)
updateαlk with (5)(7)
End For(8)
Fork = 1, 2, …, Kdo(9)
updatedlk with (7)(10)
End For(11)
Until convergence(12)
End For(13)
S = [ D1, D2, … DL](14)
Return SIn the original Shapelet algorithm, the decision tree is embedded in the training process. In other words, the original Shapelet algorithm cannot use classifiers other than the decision tree. In order to unbind Shapelet discovery and decision tree, we use Shapelet transformation [14] technique to generate features which are suitable for any classifiers. Suppose H = L × K means the number of Shapelets in S. Transformation technique calculates the minimum distance vij between Ti and dj, and formed the feature vectors Vi = [vi1, vi2, …, viH]. V is actually a local reconstruction error. We do not feed sparse coefficients α to classifier because they lack discriminative ability. By implementing the transformation technique in both training set and testing set, we get Vtrain and Vtest.The choice of classifier is discretionary, and we use an SVM-based Ensemble Classifier which is described below.


### 3.5. SVM-Based Ensemble Classifier

SVM [22, 23] is a widely used classifier with high performance and low computational cost. We choose SVM as a base classifier. However, a single classifier is easily affected by uncontrollable factors such as noise, resulting in unstable performance. The Ensemble Learning method combines the results of weak base classifiers to form a strong classifier and improves the overall robustness of the algorithm [24]. Many ensemble SVM algorithms have been proved to be more powerful than single SVM algorithms [25, 26].Specifically, two problems need to be considered in the construction of ensemble methods. The first problem is the selection of features. We use redundant dictionaries, which result in a large number of Shaplets, and the sample after the transformation operation is a high-dimensional vector. Generally, researchers use ICA or other dimension reduction methods to reduce the features. However, different samples may be sensitive to the features of different dimensions. Dimension reduction will lead to the loss of information. The second problem is the selection of SVM parameters. There are many superparameters that need to be tuned in the SVM algorithm. Finding the optimal parameters is a complex problem. At the same time, like the first problem, different samples may be sensitive to different parameters.In order to address these two problems, we designed two strategies. First, instead of using all features, each base SVM uses randomly selected features for training. As long as the number of base SVMs is enough, each feature will be used, and no information will be lost without dimension reduction. Second, the parameters of each base SVM are generated randomly, which avoids the overfitting caused by using a set of specific parameters. As shown in Figure3, the steps of the SVM-based Ensemble Classifier are as follows:(1)
ConstructB training subsets and testing subsets. Each training subset randomly selects E features from the training feature set Vtrain, and the same E features are selected from the testing feature set Vtest to construct the corresponding testing subset. A feature is a column in the feature set. So, we get a series of subsets, Vbtrain=vb1train,vb2train,…,vbetrain,…,vbEtrain,b=1,2,…,B, where vbetrain is a random column of Vtrain, and vbetrain≠vbftrain,∀e≠f. In the same way, we get testing subsets Vbtest=vb1test,vb2test,…,vbetest,…,vbEtest,b=1,2,…,B.(2)
For each training subsetVbtrain, train an SVM model: SVMbktb,deb,gab,cob, where kernel type ktb, degree in kernel function deb, gamma in kernel function gab, and coef0 in kernel function cob are all chosen randomly. Then, test Vbtest by using model SVMb, and return test result Y^btest.(3)
Deploy majority voting to get the final test resultY^test.Figure 3
Flowchart of the proposed SVM-based Ensemble Classifier, with the following steps: (1) constructing training subsets and testing subsets; (2) training SVM models on training subsets and inferencing on testing subsets; (3) majority voting.


## 3.1. Build SDL Atom

The atoms of the original DL present global features, while Shapelets present local features. So, we must reconstruct the SDL atoms before making the overall model. From the introduction in Section2.2, the original DL atom dimension is equal to the input signal dimension. More specifically, consider the following situation, an input signal T with m dimension, and the atom in DL with p dimension. In the original DL based algorithms, p is set equal to m inevitably. Nevertheless, in the SDL algorithm, an atom is a representation of the Shapelet; thus, the dimension p needs small than m. To address this problem, we introduce the Shift-Invariant Dictionary Learning (SIDL) technique [21] into our work, which use a sliding window to build the SDL atom and relax the constraint of p to p ≤ m.Figure2 explains how to generate the SDL atom. The SDL atom is denoted as d′∈ℝm, and the Shapelet is denoted as d∈ℝp, where p ≤ m. Shapelet may match anywhere in the time series, thus the sliding window which represents a Shapelet, which is sliding along the SDL atom to match the optimal location. In an SDL atom, only the Shapelet part has practical significance, and the rest part is assigned 0. In Figure 2, a Shapelet is matched at location q, the values in red blocks need to optimize, while the blue blocks are assigned 0. The matched location q is unique for each time series.Figure 2
Construction of SDL atom. The red window represents the Shapelet, and the blue blocks are assigned to 0.Q(d, q) is a function describes the mapping relationship between the Shapelet and the SDL atom. Given q and d, the SDL atom can be generated as follows [21]:(2)di′=Qd,qi=di−q,ifq+1≤i≤q+p,0,otherwise.


## 3.2. The SDL Model

To build the complete SDL model, further more constraints must be made. The complete SDL model is(3)argminα,q,d12∑i=1nTi−∑k=1KαikQdk,qik22+λ∑i=1nαi1s.t.dk2≤c,k=1,…,K0≤qik≤m−p,i=1,…,n;k=1,…,Kαik≥0,i=1,…,n;k=1,…,K,where Ti is a time series from the input dataset; the sparse coefficient {αik}, the corresponding shifts {qik}, and the Shapelet dictionary D=d1,d2,…,dK∈ℝK×p are outputs of the model which need to be optimized; the length of the Shapelet p, the number of Shapelets K, the weight λ, and the scale factor c are hyperparameters which need to be tuned. The scale constraint of dk avoids producing trivial solutions. The constraint of q controls the sliding window does not exceed the boundary. The nonnegative constraint of sparse coefficients is added to avoid the Shapelet inverted.Equation (3) is an unsupervised learning model, while time series classification is a supervised problem. To deal with this, we learn sub-Shapelet dictionaries for each class independently.


## 3.3. Optimization of the SDL

Equation (3) is a nonconvex problem. Commonly, a two-step optimization strategy is suitable for this problem. Sparse coefficients and Shapelet dictionary are updated alternately. The subobject of each step is convex.


### 3.3.1. Update Sparse Coefficients

In this step, sparse coefficient is updated. Fix thed, and equation (3) turns to(4)argminα,q12∑i=1nTi−∑k=1KαikQdk,qik22+λ∑i=1nαi1s.t.0≤qik≤m−p,i=1,…,n;k=1,…,Kαik≥0,i=1,…,n;k=1,…,K.We optimizeα and q for each Ti independently, the problem turns to(5)argminαk12Ti−αkQdk,qk−∑j≠kKαjQdj,qj2+λαks.t.0≤qk≤m−p,k=1,…,Kαk≥0,k=1,…,K,where {αj}j≠k and {qj}j≠k are fixed.We use an enumeration method to find the bestqk, which calculates the object value with all possible locations, and the solution is located which minimizes equation (5):(6)qk∗=argmaxqkQdk,qkTt^,where t^≜Ti−∑j≠kαjQdj,qj.Because of the nonnegative constraint ofα, equation (5) is different from that of [21]. With the optimal qk∗, the update solution of αk is(7)αk∗=Qdk,qkTt^−λdk2,ifQdk,qkTt^>λ,0,otherwise.


### 3.3.2. Update Dictionary

In this step, we fixα and the q and update the Shapelet dictionary d. Further, we fix {dj} j ≠ k and optimize dk independently. Thus, the problem (3) turns to(8)argmindk12∑i=1nTi−αikQdk,qik−∑j≠kKαijQdj,qij2s.t.dk2≤c.Equation (8) is a least square with quadratic constraints, and it can be optimized via the Lagrange Multiplier method. The optimal dk is(9)dk∗=ct˜t˜,ift˜∑i=1nαik2≥c,1∑i=1nαik2t˜,otherwise,where t˜≜∑i=1nαikt^i1+qik,p+qik, and t^i≜Ti−∑j≠kαijQdj,qij, and superscript [1 + qik, p + qik] means the segment from index 1 + qik to p + qik. A proof can be found in [21].


## 3.3.1. Update Sparse Coefficients

In this step, sparse coefficient is updated. Fix thed, and equation (3) turns to(4)argminα,q12∑i=1nTi−∑k=1KαikQdk,qik22+λ∑i=1nαi1s.t.0≤qik≤m−p,i=1,…,n;k=1,…,Kαik≥0,i=1,…,n;k=1,…,K.We optimizeα and q for each Ti independently, the problem turns to(5)argminαk12Ti−αkQdk,qk−∑j≠kKαjQdj,qj2+λαks.t.0≤qk≤m−p,k=1,…,Kαk≥0,k=1,…,K,where {αj}j≠k and {qj}j≠k are fixed.We use an enumeration method to find the bestqk, which calculates the object value with all possible locations, and the solution is located which minimizes equation (5):(6)qk∗=argmaxqkQdk,qkTt^,where t^≜Ti−∑j≠kαjQdj,qj.Because of the nonnegative constraint ofα, equation (5) is different from that of [21]. With the optimal qk∗, the update solution of αk is(7)αk∗=Qdk,qkTt^−λdk2,ifQdk,qkTt^>λ,0,otherwise.


## 3.3.2. Update Dictionary

In this step, we fixα and the q and update the Shapelet dictionary d. Further, we fix {dj} j ≠ k and optimize dk independently. Thus, the problem (3) turns to(8)argmindk12∑i=1nTi−αikQdk,qik−∑j≠kKαijQdj,qij2s.t.dk2≤c.Equation (8) is a least square with quadratic constraints, and it can be optimized via the Lagrange Multiplier method. The optimal dk is(9)dk∗=ct˜t˜,ift˜∑i=1nαik2≥c,1∑i=1nαik2t˜,otherwise,where t˜≜∑i=1nαikt^i1+qik,p+qik, and t^i≜Ti−∑j≠kαijQdj,qij, and superscript [1 + qik, p + qik] means the segment from index 1 + qik to p + qik. A proof can be found in [21].


## 3.4. Supervised Shapelet Dictionary Learning Method for Classification Problem

In this subsection, we introduce the supervised SDL to obtain subdictionary of each class and use subdictionaries to transform time series from the time domain to the feature domain.We train SDL model forL classes independently and obtain L subdictionaries. The complete Shapelet dictionary S = [D1, D2, …, Dl, …, DL], where Dl means lth subdictionary. See Algorithm 1 for pseudo-code of complete supervised SDL.Algorithm 1: Shapelet dictionary learning.
Input: time series data set T, parameters p, K, λ, c, stopping threshold ε;Output: complete Shapelet dictionary S;(1)
Forl = 1, 2, …, Ldo(2)
Initialize sub-dictionariesDl, sub-coefficient Al, sub-location ql(3)
Repeat(4)
Fork = 1, 2, …, Kdo(5)
updateqlk with (4)(6)
updateαlk with (5)(7)
End For(8)
Fork = 1, 2, …, Kdo(9)
updatedlk with (7)(10)
End For(11)
Until convergence(12)
End For(13)
S = [ D1, D2, … DL](14)
Return SIn the original Shapelet algorithm, the decision tree is embedded in the training process. In other words, the original Shapelet algorithm cannot use classifiers other than the decision tree. In order to unbind Shapelet discovery and decision tree, we use Shapelet transformation [14] technique to generate features which are suitable for any classifiers. Suppose H = L × K means the number of Shapelets in S. Transformation technique calculates the minimum distance vij between Ti and dj, and formed the feature vectors Vi = [vi1, vi2, …, viH]. V is actually a local reconstruction error. We do not feed sparse coefficients α to classifier because they lack discriminative ability. By implementing the transformation technique in both training set and testing set, we get Vtrain and Vtest.The choice of classifier is discretionary, and we use an SVM-based Ensemble Classifier which is described below.


## 3.5. SVM-Based Ensemble Classifier

SVM [22, 23] is a widely used classifier with high performance and low computational cost. We choose SVM as a base classifier. However, a single classifier is easily affected by uncontrollable factors such as noise, resulting in unstable performance. The Ensemble Learning method combines the results of weak base classifiers to form a strong classifier and improves the overall robustness of the algorithm [24]. Many ensemble SVM algorithms have been proved to be more powerful than single SVM algorithms [25, 26].Specifically, two problems need to be considered in the construction of ensemble methods. The first problem is the selection of features. We use redundant dictionaries, which result in a large number of Shaplets, and the sample after the transformation operation is a high-dimensional vector. Generally, researchers use ICA or other dimension reduction methods to reduce the features. However, different samples may be sensitive to the features of different dimensions. Dimension reduction will lead to the loss of information. The second problem is the selection of SVM parameters. There are many superparameters that need to be tuned in the SVM algorithm. Finding the optimal parameters is a complex problem. At the same time, like the first problem, different samples may be sensitive to different parameters.In order to address these two problems, we designed two strategies. First, instead of using all features, each base SVM uses randomly selected features for training. As long as the number of base SVMs is enough, each feature will be used, and no information will be lost without dimension reduction. Second, the parameters of each base SVM are generated randomly, which avoids the overfitting caused by using a set of specific parameters. As shown in Figure3, the steps of the SVM-based Ensemble Classifier are as follows:(1)
ConstructB training subsets and testing subsets. Each training subset randomly selects E features from the training feature set Vtrain, and the same E features are selected from the testing feature set Vtest to construct the corresponding testing subset. A feature is a column in the feature set. So, we get a series of subsets, Vbtrain=vb1train,vb2train,…,vbetrain,…,vbEtrain,b=1,2,…,B, where vbetrain is a random column of Vtrain, and vbetrain≠vbftrain,∀e≠f. In the same way, we get testing subsets Vbtest=vb1test,vb2test,…,vbetest,…,vbEtest,b=1,2,…,B.(2)
For each training subsetVbtrain, train an SVM model: SVMbktb,deb,gab,cob, where kernel type ktb, degree in kernel function deb, gamma in kernel function gab, and coef0 in kernel function cob are all chosen randomly. Then, test Vbtest by using model SVMb, and return test result Y^btest.(3)
Deploy majority voting to get the final test resultY^test.Figure 3
Flowchart of the proposed SVM-based Ensemble Classifier, with the following steps: (1) constructing training subsets and testing subsets; (2) training SVM models on training subsets and inferencing on testing subsets; (3) majority voting.


## 4. Experimental Results and Analyses

### 4.1. Dataset and Baseline Description

The 45 datasets from UCR Time Series Classification Repository [27] are used to verify the proposed algorithm. Table 1 summarises the details of 45 datasets.Table 1
Details of experiment datasets.
NoDatasetClassesLengthTraining InstancesTesting Instances150 words502704504552Adiac371763903913Beef547030304CBF3128309005Chlorine.316646738406CinC ECG416394013807Coffee228628288Cricket X123003903909Cricket Y1230039039010Cricket Z1230039039011Diatom43451630612ECG20029610010013ECGFive21362386114FaceAll14131560169015FaceFour4350248816FacesUCR14131200205017Fish746317517518Gun point21505015019Haptics5109215530820InlineSkate7188210055021ItalyPower22467102922Lighting22637606123Lighting77319707324MALLAT8102455234525MedicalImages109938176026MoteStrain28420125227Non.FatalECG.1427501800196528Non.FatalECG.2427501800196529OliveOil4570303030OSULeaf642720024231Sony.I2652795332Sony.II2702060133StarLight310241000823634SwedishLeaf1512850062535Symbols63982599536Synthetic66030030037Trace427510010038Two patterns41281000400039TwoLeadECG28223113940uWave.X8315896358241uWave.Y8315896358242uWave.Z8315896358243Wafer21521000617444WordsS2527026763845Yoga24263003000SDL-SEC is a modified version of the classical Shapelet algorithm; thus, we chose two typical Shapelet-based algorithms for comparison. More than that, a Deep Learning algorithm is also compared. The following three algorithms are chosen as baselines:Scalable Shapelet Discovery (SD) [11] uses an online clustering and pruning technique to avoid repeatedly measuring the classification accuracy of similar subsequences. SD takes low computational cost and handles GB-scale data in several minutes.Learning Time-Series Shapelets (LTS) [28] learns top-K Shapelets through optimizing a cost function which consists of classification accuracy and regularization terms. LTS reaches a strong performance among many Shapelet-based algorithms.Fully Convolutional Network (FCN) [29] is a Deep Learning structure method. Since the Deep Learning method plays an important role in many domains, and FCN is a strong baseline as authors claimed in their papers.We reproduced the results of LTS and FCN with the open-source code (http://www.timeseriesclassification.com/code.php, https://github.com/cauchyturing/UCR_Time_Series_Classification_Deep_Learning_Baseline). SD is well tested, and the hardware performance is close to ours, so we reuse the results in [11] directly. Also, we compare single SVM classifier with SVM-based Ensemble Classifier. Single SVM version is denoted as SDL-S, and ensemble version is denoted as SDL-SEC. Classification Accuracy is used as a quantitative performance comparison measure, which is the ratio of truly classified instances to total test instances. The runtime is used as a quantitative efficiency comparison measure, which includes training time and testing time.Our hardware environment is CPU: i7-9750H, RAM: 16 GB. We use Matlab 2019b to implement the SDL-SEC algorithm. SD and LTS are implemented by JAVA, and FCN is implemented by Python with TensorFlow. To be fair, we use CPU to compute only and use the default setting for all baselines.


### 4.2. Hyperparameter Search

There are four hyperparameters to be tuned in the SDL-SEC model,p, K, c, and λ. The classification accuracy has different sensitivities to these hyperparameters. Figure 4 reveals the accuracy variation trend of the Gun Point dataset in four situations. In Figure 4(a), the value of p is varying in the range of [0.1, 1] with the step size of 0.01, while the rest hyperparameters are fixed. In the same way, the remaining hyperparameters are fixed when the value of K is varying in the range of [1, 20] with the step size of 1 in Figure 4(b); the value of c is varying in the range of [200, 400] with the step size of 10 in Figure 4(c); the value of λ is varying in the range of [0.1, 10] with the step size of 0.1 in Figure 4(d). Obviously, the classification accuracy fluctuates dramatically when the values of p and K are varying. And, the classification accuracy fluctuates straightly when the values c and λ are varying. Thus, p and K need to be fine-tuned.Figure 4
Gun Point dataset classification accuracy varies with (a)p; (b) K; (c) c; (d) λ.
(a)(b)(c)(d)Based on the sensitivity analysis above, the hyperparameters tuning strategy are formulated. The grid search approach is used in hyperparameter tuning. According to experiments, redundant Shapelets can capture more unusual local shape features and improve the classification accuracy. Thereby, we search the number of ShapeletK in the range of [10, 100] with the step size of 10. The Shapelet length p is searched in the range of [0.05, 0.9] × m with the step size of 0.05 × m. The value of K × p determines the interpretability of Shapelet. When K × p > m, it means Shapelets are redundant and duplicate, such setting may cause higher accuracy but worse interpretability. We fix the coefficient λ to 0.01 and the coefficient c to 100.


### 4.3. Results and Analyses

This section describes and analyses the experimental results from two aspects: classification accuracy and runtime. At the same time, the limitation of proposed algorithm is also discussed.


#### 4.3.1. Classification Accuracy Comparison

We use two statistical indicators to compare the classification accuracies of all algorithms, total wins and average rank. The best algorithm has the most total wins and the highest average rank. The algorithm with better generalization ability can obtain higher accuracy in more data sets, so it is also an important index to evaluate the classification accuracy.Table2 summarises the classification accuracy statistical indicators of experiments. It should be noted that the accuracy of SDL-S is slightly different from those presented in [30], due to the updated parameters searching strategies. As shown in Table 2, the proposed algorithm has considerable classification effects. SDL-SEC achieves the best average rank of 1.91 and wins 15 times in 45 datasets. This result is better than that of SDL-S, showing that the SVM-based Ensemble Classifier is effective. FCN obtains the most total wins, 28 times, but the average rank is 1.96, lower than SDL-SEC. LTS also has good performance, but both indicators are worse than SDL-SEC. The accuracy of SD is obviously lower than other algorithms.Table 2
Accuracies for the 45 datasets.
NoDatasetClassification accuracySDLTSFCNSDL-SSDL-SEC150words0.6800.7680.6790.6920.7892Adiac0.5830.5220.8570.5910.7903Beef0.5070.8000.7500.8330.8674CBF0.9750.9901.0000.9940.9975Chlorine0.5530.5900.8430.6020.6166CinC ECG0.7730.8560.8130.8210.9267Coffee0.9611.0001.0001.0001.0008Cricket X0.6720.7440.8150.7510.7749Cricket Y0.6750.7180.7920.7410.76910Cricket Z0.6730.7210.8130.7820.80011Diatom.0.8960.9670.9300.8920.92212ECG2000.8180.8500.9000.8500.86013ECGFive0.9531.0000.9850.9991.00014FaceAll0.7140.7760.9290.7920.80315FaceFour0.8200.9660.9320.9320.95516FacesUCR0.8470.9430.9480.8930.92917Fish0.7550.9660.9710.9770.97718Gun point0.9311.0001.0000.9871.00019Haptics0.3560.4640.5510.4770.47720InlineSkate0.3850.3640.4110.3560.41521ItalyPower0.9200.9630.9700.9520.97122Lighting20.7950.8520.8030.7870.78723Lighting70.6520.8080.8630.7260.79524MALLAT0.9260.9530.9800.9210.95125MedicalImages0.6760.6790.7920.6640.70926MoteStrain0.7830.8580.9500.9050.90527Non.FatalECG.10.8140.8690.9610.8950.90628Non.FatalECG.20.8550.9110.9550.9120.93829OliveOil0.7900.7000.8330.9000.90030OSULeaf0.5660.7690.9880.9340.95531Sony.I0.8500.8270.9680.8130.81332Sony.II0.7800.8900.9620.9530.95333StarLight0.9330.9370.9670.9740.97434SwedishLeaf0.8490.9170.9660.9170.92535Symbols0.8650.9300.9620.9510.95136Synthetic.0.9830.9970.9900.9970.99737Trace0.9651.0001.0001.0001.00038Two patterns0.9810.9971.0000.9880.98839TwoLeadECG0.8670.9970.8970.9990.99940uWave.X0.7610.8010.7540.7850.79341uWave.Y0.6710.7120.7250.6990.70342uWave.Z0.6760.7520.7290.7310.74143Wafer0.9930.9960.9970.9970.99744WordsS0.6250.6800.5800.5940.67245Yoga0.6250.8310.8450.8390.839Average rank4.642.841.962.871.91Total wins01128815Figure5 is a 1-vs-1 comparison of SDL-SEC algorithm with other algorithms. In Figure 5, the points above the red line represent the higher accuracy of the baseline, and the points below the red line represent the higher accuracy of SDL-SEC algorithm. In comparison with SD and LTS algorithms, the points are more distributed in the area below the red line. In comparison with FCN, the points are roughly evenly distributed on both sides of the red line. It can be seen intuitively that the overall accuracy of SDL-SEC is close to FCN and higher than SD and LTS.Figure 5
1-vs-1 Comparison of SDL-SEC with Baselines: (a) SDL-SEC VS SD; (b) SDL-SEC VS LTS; (c) SDL-SEC VS FCN.
(a)(b)(c)By analyzing Table2 and Figure 5, we can draw a conclusion that SDL-SEC has a high classification accuracy with good generalization ability, which can adapt to most time series classification problems.


#### 4.3.2. Runtime Comparison

The runtime of each algorithm is analysed below. Table3 shows the runtimes of the comparison algorithms. The “n/a” in Table 3 indicates that the time or memory required by the algorithm exceeds the limitation of our hardware, and Table 2 uses the accuracy provided by the author. The results of LTS FCN and SDL-SEC are rounded. The runtime of SD algorithm is the shortest. As it was claimed, SD is an efficient time series classification algorithm. Although SDL-SEC runs longer than SD, it is generally acceptable. LTS and FCN run 2-4 orders of magnitude longer than SDL-SEC. Although FCN can be accelerated by the GPU, it is still a high computational expensive algorithm.Table 3
Runtime for 45 datasets.
NoDatasetRuntime (sec)SDLTSFCNSDL-SEC150 words0.494n/a93073842Adiac0.337681635361243Beef0.04711871300114CBF0.131283114155Chlorine0.6501009139341476CinC ECG2.1111481631540877Coffee0.04446102618Cricket X0.763537808889369Cricket Y0.65253663868516810Cricket Z0.80053699855917911Diatom0.1092363446312ECG2000.055411099213ECGFive0.13393752214FaceAll1.55723985817311315FaceFour0.1503721569216FacesUCR0.677818455425217Fish0.2281630955374218Gun point0.074251250119Haptics2.314375941309722920InlineSkate1.45114180222836453321ItalyPower0.06721598222Lighting21.939873279310923Lighting70.463292021765024MALLAT1.7432868338842531325MedicalImages0.690406040491726MoteStrain0.15364233127Non.FatalECG.18.721n/a90922210228Non.FatalECG.26.446n/a90826127629OliveOil0.06810431513430OSULeaf0.2441290065373531Sony.I0.099322620.332Sony.II0.10533319533StarLight12.56191024160381164134SwedishLeaf0.4561965161837135Symbols0.356109987661036Synthetic0.0995501992537Trace0.1579572375338Two patterns2.5552829161423339TwoLeadECG0.13043870240uWave.X6.322586363769612641uWave.Y5.1145894833952128042uWave.Z3.154586333228095543Wafer2.2369482352943444WordsS0.480123991715311245Yoga1.333198523449134To sum up, SDL-SEC has achieved a good balance between accuracy and runtime, greatly reducing the operating time while also having a high accuracy.


#### 4.3.3. Limitation of the Proposed Algorithm

In this part, we discuss the limitations of the proposed algorithm by analyzing two datasets with low classification accuracy. SDL performs worse in datasets Adiac and InlineSkate. The classification accuracies are 0.790 and 0.415, respectively. Figure6 draws time domain curves of Adiac and InlineSkate. Lines in different colors represent different instances in the dataset. In Figures 6(a) and 6(b), signals from different labels of Adiac dataset show the similar curves, and the shape features are not discriminative. In Figures 6(c) and 6(d), signals from the same label of InlineSkate show disorganized curves, and there is no common shape feature. Shapelet-based algorithms include the proposed algorithm will lose effectiveness in the above two situations: similar curves between different labels or disorganized curves.Figure 6
Time domain curves of (a) Adiac label 1; (b) Adiac label 2; (c) InlineSkate label 1; (d) InlineSkate label 2.
(a)(b)(c)(d)


## 4.1. Dataset and Baseline Description

The 45 datasets from UCR Time Series Classification Repository [27] are used to verify the proposed algorithm. Table 1 summarises the details of 45 datasets.Table 1
Details of experiment datasets.
NoDatasetClassesLengthTraining InstancesTesting Instances150 words502704504552Adiac371763903913Beef547030304CBF3128309005Chlorine.316646738406CinC ECG416394013807Coffee228628288Cricket X123003903909Cricket Y1230039039010Cricket Z1230039039011Diatom43451630612ECG20029610010013ECGFive21362386114FaceAll14131560169015FaceFour4350248816FacesUCR14131200205017Fish746317517518Gun point21505015019Haptics5109215530820InlineSkate7188210055021ItalyPower22467102922Lighting22637606123Lighting77319707324MALLAT8102455234525MedicalImages109938176026MoteStrain28420125227Non.FatalECG.1427501800196528Non.FatalECG.2427501800196529OliveOil4570303030OSULeaf642720024231Sony.I2652795332Sony.II2702060133StarLight310241000823634SwedishLeaf1512850062535Symbols63982599536Synthetic66030030037Trace427510010038Two patterns41281000400039TwoLeadECG28223113940uWave.X8315896358241uWave.Y8315896358242uWave.Z8315896358243Wafer21521000617444WordsS2527026763845Yoga24263003000SDL-SEC is a modified version of the classical Shapelet algorithm; thus, we chose two typical Shapelet-based algorithms for comparison. More than that, a Deep Learning algorithm is also compared. The following three algorithms are chosen as baselines:Scalable Shapelet Discovery (SD) [11] uses an online clustering and pruning technique to avoid repeatedly measuring the classification accuracy of similar subsequences. SD takes low computational cost and handles GB-scale data in several minutes.Learning Time-Series Shapelets (LTS) [28] learns top-K Shapelets through optimizing a cost function which consists of classification accuracy and regularization terms. LTS reaches a strong performance among many Shapelet-based algorithms.Fully Convolutional Network (FCN) [29] is a Deep Learning structure method. Since the Deep Learning method plays an important role in many domains, and FCN is a strong baseline as authors claimed in their papers.We reproduced the results of LTS and FCN with the open-source code (http://www.timeseriesclassification.com/code.php, https://github.com/cauchyturing/UCR_Time_Series_Classification_Deep_Learning_Baseline). SD is well tested, and the hardware performance is close to ours, so we reuse the results in [11] directly. Also, we compare single SVM classifier with SVM-based Ensemble Classifier. Single SVM version is denoted as SDL-S, and ensemble version is denoted as SDL-SEC. Classification Accuracy is used as a quantitative performance comparison measure, which is the ratio of truly classified instances to total test instances. The runtime is used as a quantitative efficiency comparison measure, which includes training time and testing time.Our hardware environment is CPU: i7-9750H, RAM: 16 GB. We use Matlab 2019b to implement the SDL-SEC algorithm. SD and LTS are implemented by JAVA, and FCN is implemented by Python with TensorFlow. To be fair, we use CPU to compute only and use the default setting for all baselines.


## 4.2. Hyperparameter Search

There are four hyperparameters to be tuned in the SDL-SEC model,p, K, c, and λ. The classification accuracy has different sensitivities to these hyperparameters. Figure 4 reveals the accuracy variation trend of the Gun Point dataset in four situations. In Figure 4(a), the value of p is varying in the range of [0.1, 1] with the step size of 0.01, while the rest hyperparameters are fixed. In the same way, the remaining hyperparameters are fixed when the value of K is varying in the range of [1, 20] with the step size of 1 in Figure 4(b); the value of c is varying in the range of [200, 400] with the step size of 10 in Figure 4(c); the value of λ is varying in the range of [0.1, 10] with the step size of 0.1 in Figure 4(d). Obviously, the classification accuracy fluctuates dramatically when the values of p and K are varying. And, the classification accuracy fluctuates straightly when the values c and λ are varying. Thus, p and K need to be fine-tuned.Figure 4
Gun Point dataset classification accuracy varies with (a)p; (b) K; (c) c; (d) λ.
(a)(b)(c)(d)Based on the sensitivity analysis above, the hyperparameters tuning strategy are formulated. The grid search approach is used in hyperparameter tuning. According to experiments, redundant Shapelets can capture more unusual local shape features and improve the classification accuracy. Thereby, we search the number of ShapeletK in the range of [10, 100] with the step size of 10. The Shapelet length p is searched in the range of [0.05, 0.9] × m with the step size of 0.05 × m. The value of K × p determines the interpretability of Shapelet. When K × p > m, it means Shapelets are redundant and duplicate, such setting may cause higher accuracy but worse interpretability. We fix the coefficient λ to 0.01 and the coefficient c to 100.


## 4.3. Results and Analyses

This section describes and analyses the experimental results from two aspects: classification accuracy and runtime. At the same time, the limitation of proposed algorithm is also discussed.


### 4.3.1. Classification Accuracy Comparison

We use two statistical indicators to compare the classification accuracies of all algorithms, total wins and average rank. The best algorithm has the most total wins and the highest average rank. The algorithm with better generalization ability can obtain higher accuracy in more data sets, so it is also an important index to evaluate the classification accuracy.Table2 summarises the classification accuracy statistical indicators of experiments. It should be noted that the accuracy of SDL-S is slightly different from those presented in [30], due to the updated parameters searching strategies. As shown in Table 2, the proposed algorithm has considerable classification effects. SDL-SEC achieves the best average rank of 1.91 and wins 15 times in 45 datasets. This result is better than that of SDL-S, showing that the SVM-based Ensemble Classifier is effective. FCN obtains the most total wins, 28 times, but the average rank is 1.96, lower than SDL-SEC. LTS also has good performance, but both indicators are worse than SDL-SEC. The accuracy of SD is obviously lower than other algorithms.Table 2
Accuracies for the 45 datasets.
NoDatasetClassification accuracySDLTSFCNSDL-SSDL-SEC150words0.6800.7680.6790.6920.7892Adiac0.5830.5220.8570.5910.7903Beef0.5070.8000.7500.8330.8674CBF0.9750.9901.0000.9940.9975Chlorine0.5530.5900.8430.6020.6166CinC ECG0.7730.8560.8130.8210.9267Coffee0.9611.0001.0001.0001.0008Cricket X0.6720.7440.8150.7510.7749Cricket Y0.6750.7180.7920.7410.76910Cricket Z0.6730.7210.8130.7820.80011Diatom.0.8960.9670.9300.8920.92212ECG2000.8180.8500.9000.8500.86013ECGFive0.9531.0000.9850.9991.00014FaceAll0.7140.7760.9290.7920.80315FaceFour0.8200.9660.9320.9320.95516FacesUCR0.8470.9430.9480.8930.92917Fish0.7550.9660.9710.9770.97718Gun point0.9311.0001.0000.9871.00019Haptics0.3560.4640.5510.4770.47720InlineSkate0.3850.3640.4110.3560.41521ItalyPower0.9200.9630.9700.9520.97122Lighting20.7950.8520.8030.7870.78723Lighting70.6520.8080.8630.7260.79524MALLAT0.9260.9530.9800.9210.95125MedicalImages0.6760.6790.7920.6640.70926MoteStrain0.7830.8580.9500.9050.90527Non.FatalECG.10.8140.8690.9610.8950.90628Non.FatalECG.20.8550.9110.9550.9120.93829OliveOil0.7900.7000.8330.9000.90030OSULeaf0.5660.7690.9880.9340.95531Sony.I0.8500.8270.9680.8130.81332Sony.II0.7800.8900.9620.9530.95333StarLight0.9330.9370.9670.9740.97434SwedishLeaf0.8490.9170.9660.9170.92535Symbols0.8650.9300.9620.9510.95136Synthetic.0.9830.9970.9900.9970.99737Trace0.9651.0001.0001.0001.00038Two patterns0.9810.9971.0000.9880.98839TwoLeadECG0.8670.9970.8970.9990.99940uWave.X0.7610.8010.7540.7850.79341uWave.Y0.6710.7120.7250.6990.70342uWave.Z0.6760.7520.7290.7310.74143Wafer0.9930.9960.9970.9970.99744WordsS0.6250.6800.5800.5940.67245Yoga0.6250.8310.8450.8390.839Average rank4.642.841.962.871.91Total wins01128815Figure5 is a 1-vs-1 comparison of SDL-SEC algorithm with other algorithms. In Figure 5, the points above the red line represent the higher accuracy of the baseline, and the points below the red line represent the higher accuracy of SDL-SEC algorithm. In comparison with SD and LTS algorithms, the points are more distributed in the area below the red line. In comparison with FCN, the points are roughly evenly distributed on both sides of the red line. It can be seen intuitively that the overall accuracy of SDL-SEC is close to FCN and higher than SD and LTS.Figure 5
1-vs-1 Comparison of SDL-SEC with Baselines: (a) SDL-SEC VS SD; (b) SDL-SEC VS LTS; (c) SDL-SEC VS FCN.
(a)(b)(c)By analyzing Table2 and Figure 5, we can draw a conclusion that SDL-SEC has a high classification accuracy with good generalization ability, which can adapt to most time series classification problems.


### 4.3.2. Runtime Comparison

The runtime of each algorithm is analysed below. Table3 shows the runtimes of the comparison algorithms. The “n/a” in Table 3 indicates that the time or memory required by the algorithm exceeds the limitation of our hardware, and Table 2 uses the accuracy provided by the author. The results of LTS FCN and SDL-SEC are rounded. The runtime of SD algorithm is the shortest. As it was claimed, SD is an efficient time series classification algorithm. Although SDL-SEC runs longer than SD, it is generally acceptable. LTS and FCN run 2-4 orders of magnitude longer than SDL-SEC. Although FCN can be accelerated by the GPU, it is still a high computational expensive algorithm.Table 3
Runtime for 45 datasets.
NoDatasetRuntime (sec)SDLTSFCNSDL-SEC150 words0.494n/a93073842Adiac0.337681635361243Beef0.04711871300114CBF0.131283114155Chlorine0.6501009139341476CinC ECG2.1111481631540877Coffee0.04446102618Cricket X0.763537808889369Cricket Y0.65253663868516810Cricket Z0.80053699855917911Diatom0.1092363446312ECG2000.055411099213ECGFive0.13393752214FaceAll1.55723985817311315FaceFour0.1503721569216FacesUCR0.677818455425217Fish0.2281630955374218Gun point0.074251250119Haptics2.314375941309722920InlineSkate1.45114180222836453321ItalyPower0.06721598222Lighting21.939873279310923Lighting70.463292021765024MALLAT1.7432868338842531325MedicalImages0.690406040491726MoteStrain0.15364233127Non.FatalECG.18.721n/a90922210228Non.FatalECG.26.446n/a90826127629OliveOil0.06810431513430OSULeaf0.2441290065373531Sony.I0.099322620.332Sony.II0.10533319533StarLight12.56191024160381164134SwedishLeaf0.4561965161837135Symbols0.356109987661036Synthetic0.0995501992537Trace0.1579572375338Two patterns2.5552829161423339TwoLeadECG0.13043870240uWave.X6.322586363769612641uWave.Y5.1145894833952128042uWave.Z3.154586333228095543Wafer2.2369482352943444WordsS0.480123991715311245Yoga1.333198523449134To sum up, SDL-SEC has achieved a good balance between accuracy and runtime, greatly reducing the operating time while also having a high accuracy.


### 4.3.3. Limitation of the Proposed Algorithm

In this part, we discuss the limitations of the proposed algorithm by analyzing two datasets with low classification accuracy. SDL performs worse in datasets Adiac and InlineSkate. The classification accuracies are 0.790 and 0.415, respectively. Figure6 draws time domain curves of Adiac and InlineSkate. Lines in different colors represent different instances in the dataset. In Figures 6(a) and 6(b), signals from different labels of Adiac dataset show the similar curves, and the shape features are not discriminative. In Figures 6(c) and 6(d), signals from the same label of InlineSkate show disorganized curves, and there is no common shape feature. Shapelet-based algorithms include the proposed algorithm will lose effectiveness in the above two situations: similar curves between different labels or disorganized curves.Figure 6
Time domain curves of (a) Adiac label 1; (b) Adiac label 2; (c) InlineSkate label 1; (d) InlineSkate label 2.
(a)(b)(c)(d)


## 4.3.1. Classification Accuracy Comparison

We use two statistical indicators to compare the classification accuracies of all algorithms, total wins and average rank. The best algorithm has the most total wins and the highest average rank. The algorithm with better generalization ability can obtain higher accuracy in more data sets, so it is also an important index to evaluate the classification accuracy.Table2 summarises the classification accuracy statistical indicators of experiments. It should be noted that the accuracy of SDL-S is slightly different from those presented in [30], due to the updated parameters searching strategies. As shown in Table 2, the proposed algorithm has considerable classification effects. SDL-SEC achieves the best average rank of 1.91 and wins 15 times in 45 datasets. This result is better than that of SDL-S, showing that the SVM-based Ensemble Classifier is effective. FCN obtains the most total wins, 28 times, but the average rank is 1.96, lower than SDL-SEC. LTS also has good performance, but both indicators are worse than SDL-SEC. The accuracy of SD is obviously lower than other algorithms.Table 2
Accuracies for the 45 datasets.
NoDatasetClassification accuracySDLTSFCNSDL-SSDL-SEC150words0.6800.7680.6790.6920.7892Adiac0.5830.5220.8570.5910.7903Beef0.5070.8000.7500.8330.8674CBF0.9750.9901.0000.9940.9975Chlorine0.5530.5900.8430.6020.6166CinC ECG0.7730.8560.8130.8210.9267Coffee0.9611.0001.0001.0001.0008Cricket X0.6720.7440.8150.7510.7749Cricket Y0.6750.7180.7920.7410.76910Cricket Z0.6730.7210.8130.7820.80011Diatom.0.8960.9670.9300.8920.92212ECG2000.8180.8500.9000.8500.86013ECGFive0.9531.0000.9850.9991.00014FaceAll0.7140.7760.9290.7920.80315FaceFour0.8200.9660.9320.9320.95516FacesUCR0.8470.9430.9480.8930.92917Fish0.7550.9660.9710.9770.97718Gun point0.9311.0001.0000.9871.00019Haptics0.3560.4640.5510.4770.47720InlineSkate0.3850.3640.4110.3560.41521ItalyPower0.9200.9630.9700.9520.97122Lighting20.7950.8520.8030.7870.78723Lighting70.6520.8080.8630.7260.79524MALLAT0.9260.9530.9800.9210.95125MedicalImages0.6760.6790.7920.6640.70926MoteStrain0.7830.8580.9500.9050.90527Non.FatalECG.10.8140.8690.9610.8950.90628Non.FatalECG.20.8550.9110.9550.9120.93829OliveOil0.7900.7000.8330.9000.90030OSULeaf0.5660.7690.9880.9340.95531Sony.I0.8500.8270.9680.8130.81332Sony.II0.7800.8900.9620.9530.95333StarLight0.9330.9370.9670.9740.97434SwedishLeaf0.8490.9170.9660.9170.92535Symbols0.8650.9300.9620.9510.95136Synthetic.0.9830.9970.9900.9970.99737Trace0.9651.0001.0001.0001.00038Two patterns0.9810.9971.0000.9880.98839TwoLeadECG0.8670.9970.8970.9990.99940uWave.X0.7610.8010.7540.7850.79341uWave.Y0.6710.7120.7250.6990.70342uWave.Z0.6760.7520.7290.7310.74143Wafer0.9930.9960.9970.9970.99744WordsS0.6250.6800.5800.5940.67245Yoga0.6250.8310.8450.8390.839Average rank4.642.841.962.871.91Total wins01128815Figure5 is a 1-vs-1 comparison of SDL-SEC algorithm with other algorithms. In Figure 5, the points above the red line represent the higher accuracy of the baseline, and the points below the red line represent the higher accuracy of SDL-SEC algorithm. In comparison with SD and LTS algorithms, the points are more distributed in the area below the red line. In comparison with FCN, the points are roughly evenly distributed on both sides of the red line. It can be seen intuitively that the overall accuracy of SDL-SEC is close to FCN and higher than SD and LTS.Figure 5
1-vs-1 Comparison of SDL-SEC with Baselines: (a) SDL-SEC VS SD; (b) SDL-SEC VS LTS; (c) SDL-SEC VS FCN.
(a)(b)(c)By analyzing Table2 and Figure 5, we can draw a conclusion that SDL-SEC has a high classification accuracy with good generalization ability, which can adapt to most time series classification problems.


## 4.3.2. Runtime Comparison

The runtime of each algorithm is analysed below. Table3 shows the runtimes of the comparison algorithms. The “n/a” in Table 3 indicates that the time or memory required by the algorithm exceeds the limitation of our hardware, and Table 2 uses the accuracy provided by the author. The results of LTS FCN and SDL-SEC are rounded. The runtime of SD algorithm is the shortest. As it was claimed, SD is an efficient time series classification algorithm. Although SDL-SEC runs longer than SD, it is generally acceptable. LTS and FCN run 2-4 orders of magnitude longer than SDL-SEC. Although FCN can be accelerated by the GPU, it is still a high computational expensive algorithm.Table 3
Runtime for 45 datasets.
NoDatasetRuntime (sec)SDLTSFCNSDL-SEC150 words0.494n/a93073842Adiac0.337681635361243Beef0.04711871300114CBF0.131283114155Chlorine0.6501009139341476CinC ECG2.1111481631540877Coffee0.04446102618Cricket X0.763537808889369Cricket Y0.65253663868516810Cricket Z0.80053699855917911Diatom0.1092363446312ECG2000.055411099213ECGFive0.13393752214FaceAll1.55723985817311315FaceFour0.1503721569216FacesUCR0.677818455425217Fish0.2281630955374218Gun point0.074251250119Haptics2.314375941309722920InlineSkate1.45114180222836453321ItalyPower0.06721598222Lighting21.939873279310923Lighting70.463292021765024MALLAT1.7432868338842531325MedicalImages0.690406040491726MoteStrain0.15364233127Non.FatalECG.18.721n/a90922210228Non.FatalECG.26.446n/a90826127629OliveOil0.06810431513430OSULeaf0.2441290065373531Sony.I0.099322620.332Sony.II0.10533319533StarLight12.56191024160381164134SwedishLeaf0.4561965161837135Symbols0.356109987661036Synthetic0.0995501992537Trace0.1579572375338Two patterns2.5552829161423339TwoLeadECG0.13043870240uWave.X6.322586363769612641uWave.Y5.1145894833952128042uWave.Z3.154586333228095543Wafer2.2369482352943444WordsS0.480123991715311245Yoga1.333198523449134To sum up, SDL-SEC has achieved a good balance between accuracy and runtime, greatly reducing the operating time while also having a high accuracy.


## 4.3.3. Limitation of the Proposed Algorithm

In this part, we discuss the limitations of the proposed algorithm by analyzing two datasets with low classification accuracy. SDL performs worse in datasets Adiac and InlineSkate. The classification accuracies are 0.790 and 0.415, respectively. Figure6 draws time domain curves of Adiac and InlineSkate. Lines in different colors represent different instances in the dataset. In Figures 6(a) and 6(b), signals from different labels of Adiac dataset show the similar curves, and the shape features are not discriminative. In Figures 6(c) and 6(d), signals from the same label of InlineSkate show disorganized curves, and there is no common shape feature. Shapelet-based algorithms include the proposed algorithm will lose effectiveness in the above two situations: similar curves between different labels or disorganized curves.Figure 6
Time domain curves of (a) Adiac label 1; (b) Adiac label 2; (c) InlineSkate label 1; (d) InlineSkate label 2.
(a)(b)(c)(d)


## 5. Conclusion and Future Work

In this paper, we present a Shapelet-based time series classification algorithm called Shapelet Dictionary Learning with SVM-based Ensemble Classifier. First, we propose a Shapelet discovery method Shapelet Dictionary Learning, which combines Dictionary Learning and Shapelet and generates a group of Shapelets instead of searching. The generated Shapelets are totally new subsequences which contain local shape features of all the time series data but not exist in original data. This encourages the generalization ability of Shapelet, reaches a higher accuracy in time series classification, and reduces runtime simultaneously. Furthermore, we propose an SVM-based Ensemble Classifier to execute the classification operation. The proposed SVM-based Ensemble Classifier trains a series of base SVM classifiers which are fed random features and parameters. This method decreases the dependence on feature and parameter selection and thus further improves the classification accuracy. Extensive experiments are performed on 45 benchmark datasets. The results show that the proposed algorithm has high accuracy, good robustness, and high efficiency.We also look into the future work from the limitations of the proposed algorithm. First, SDL-SEC discovers the time domain shape features. It will fail when the shape feature is not obvious. In order to address this issue, we may exploit a feature fusion method by combining frequency domain features and other statistical features. Second, the current SDL hyperparameter selection method is a grid search approach. This approach requires to design searching strategy manually. As an improvement direction, intelligent optimization algorithms can be exploited, such as evolutionary algorithms, to search hyperparameters automatically [31]. And, the third, only Euclidean Distance is considered in this work, so it is difficult to deal with real-world data with noise and uncertainty. Fuzzy Measurement [32, 33] is an excellent tool to handle this kind of problems, which we will investigate in our future work.



---

*Source: 5586273-2021-03-22.xml*