# Shapelet Discovery by Lazy Time Series Classification

Authors: Wei Zhang; Zhihai Wang; Jidong Yuan; Shilei Hao
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

As a representation of discriminative features, the time series shapelet has recently received considerable research interest. However, most shapelet-based classification models evaluate the differential ability of the shapelet on the whole training dataset, neglecting characteristic information contained in each instance to be classified and the classwise feature frequency information. Hence, the computational complexity of feature extraction is high, and the interpretability is inadequate. To this end, the efficiency of shapelet discovery is improved through a lazy strategy fusing global and local similarities. In the prediction process, the strategy learns a specific evaluation dataset for each instance, and then the captured characteristics are directly used to progressively reduce the uncertainty of the predicted class label. Moreover, a shapelet coverage score is defined to calculate the discriminability of each time stamp for different classes. The experimental results show that the proposed method is competitive with the benchmark methods and provides insight into the discriminative features of each time series and each type in the data.


---

## Body

## 1. Introduction

In recent years, massive time series data have been generated in many fields, including weather forecasting [1], malware detection [2], voltage stability assessment [3], human identification [4], and biomedicine [5]. Hence, the study of time series has been widely applicable, among which classification is an important research field. The classification issue of time series is the same as the traditional classification problem. We hope to find a function that can map any time series to a target class label. Although a large number of time series classification algorithms have been proposed, extensive experiments show that the 1NN classifier combining different distance metrics is still a competitive model in many problem areas [6–12]. In addition to the common Euclidean distance, alternatives have been proposed to measure the similarity between time series, including dynamic time warping (DTW) [13], weighted DTW (WDTW) [14], edit distance with real penalty (ERP) [15], time warp edit (TWE) [16], and move-split-merge (MSM) [17].The improved distance function can help promote the performance of the nearest-neighbor model, but the 1NN classifier presents obvious drawbacks. This classifier cannot indicate the common characteristics of similar instances and the dissimilarity between different classes. In other words, its interpretability is insufficient. In reality, except for the accuracy, the features of distinct instances are our concern. These features provide a deeper understanding of data and improve the interpretability of the classification model. Unfortunately, time series usually have no definite features. Hence, various feature prototypes are proposed to mine potential patterns of time series [9, 18, 19]. Among them, the most classic is the local discriminative features “shapelet” [18].A shapelet (as shown in Figure1(a)) is a special discriminatory subsequence of time series, which is originally applied to construct the shapelet-based decision tree (SDT) [18] through recursively searching for the best shapelet in the training set. Since the shapelet can be used to establish an interpretable classification model, it has been widely studied [9]. Shapelet-based classification models can be divided into two categories. One type of the method utilizes the top-k shapelets to create a transformed dataset, on which the traditional classification algorithms [20–24] could be applied. The other uses the shapelets to build the classification model directly [18, 25–28].Figure 1
(a) The shapelet found by SDT for the ItalyPowerDemand dataset, and its corresponding training instances. The black bold part indicates the discovered time series shapelet. (b) Three time series from the ItalyPowerDemand training dataset and their corresponding shapelets captured by LSCR.Train9 and Train44 (in blue and red, respectively) are instances with different classes, while Train9 and Train46 (in blue) are instances of the same type Class2. Based on the discovered shapelets, our model can make correct predictions for the three instances. (c) The classwise shapelet coverage score obtained on the training set for each sampling point.
(a)(b)(c)One major problem that all shapelet-based approaches generally face is the massive size of the candidate shapelet set. To solve this problem, researchers have put forward several methods. These methods can be roughly divided into four categories: (1) training instances are selected to generate the candidate shapelets. For example, Ji et al. [29] put forward a subclass splitting method to sample the training instances for candidate shapelet generation. (2) Heuristic shapelet search method. Grabocka et al. [27] presented a heuristic gradient descent shapelet search algorithm, which created a smaller candidate shapelet set. Rakthanmanon et al. [26] proposed a fast shapelet discovery algorithm based on Symbolic Aggregate approXimation (SAX). Similarly, Fang et al. [28] introduced a novel method to search shapelets based on piecewise aggregate approximation (PAA). (3) A random selection mechanism is used to select shapelets. Renard et al. [30] first proposed a random-shapelet algorithm to build the decision trees. Karlsson et al. [31] constructed the shapelet-based random forest, in which each decision tree is built based on instances and shapelets selected randomly. Further, to omit the shapelet threshold search, Shi et al. [32] have put forward the random pairwise shapelet forest. (4) Reformulating the shapelet search problem into a numerical optimization problem. For example, Hou et al. [33] treated the shapelet search task as a numerical optimization problem, and then the shapelets were learned by numerical analysis methods. Likewise, Wang et al. [34] designed a semisupervised shapelet learning model, which transforms the feature search problem into a joint optimization problem. Ma et al. [35] proposed an end-to-end model to learn the most discriminative shapelets by the gradient descent method. Zhao et al. [36] recently proposed a regularized shapelet learning framework to improve the shapelet learning efficiency. Although the above methods improve the classification efficiency of shapelet-based models to some extent, the vast majority of shapelet-based global classification models still has the following disadvantages:(1)
The shapelets captured by most shapelet-based models cannot adequately reflect the information of feature distribution and frequency of each class in the dataset. For example, due to the existence of intraclass variation, a few instances in different classes may have low-frequency discriminative features.(2)
The whole training set is generally applied for the discriminatory evaluation of candidate shapelets. Owing to the influence of the redundant instances and the intraclass variability, the extracted shapelets are merely the best on average for instances in the training dataset and cannot accurately reflect the local characteristics of the instance to be classified. In other words, the established shapelet-based model is not suitable or efficient for each test instance. Targeted evaluation strategies are not given enough attention.To address these problems, we have first proposed a lazy shapelet-based model to capture the local features of each instance in the literature [37] (the literature [37] is a poster in the conference ICONIP 2018. In the conference manuscript, we simply proposed a lazy model to classify the instance based on its own local features. However, in this paper, the extended version further studies the fusion of global and local similarity, the local feature distribution and frequency information discovery, etc. In addition, this paper includes details about how to discover the local features for each instance to be classified in the shapelet-based model, how to use the local characteristics of each instance to determine the classwise discriminatory information, more experiments on parameter setting, statistical analysis, model comparison, and case studies). However, the proposed model still cannot get insight into the feature distribution and frequency information of the time series data. For that, we significantly extend the research on the data-driven, shapelet-based model (lazy shapelet classification route, LSCR) to study the feature distribution and frequency information discovery. Here, the advantages of our model are interpreted in conjunction with Figure 1. From Figure 1(b), it can be found that the heterogeneous instances are different, and that there are also differences between the homogeneous instances. Since LSCR performs targeted analysis for each instance, compared with the SDT shapelet (as shown in Figure 1(a)), our model may capture characteristics that SDT cannot discover. For example, the shapelet S046 does not appear in the model built by SDT. Further, to evaluate the classwise discriminative feature frequency, the shapelet coverage score is defined. From Figure 1(c), we find that the scores can not only indicate the local discriminant intervals for different classes but also reflect their frequency information. For instance, the low-frequency discriminative interval [0, 7] reflects the location of the local features detected by our model on a few instances of Class2, which are usually caused by intraclass variation and ignored by the global shapelet-based model. The main contributions of this paper are summarized as follows:(1)
In contrast with the classicalkNN or 1NN model based on global similarity, our model is a fusion of global and local similarities. For the consideration of global similarity, the instance selection strategy is used in evaluating the discrimination of shapelets. The smaller evaluation dataset can eliminate the interference of intraclass variation and improve the classification performance. In addition, local similarity is applied instead of global similarity for prediction, which makes the proposed model more interpretable.(2)
To reduce the massive number of redundant candidate shapelets generated by the brute-force algorithm, a novel strategy is proposed for extracting candidate shapelets from the instance to be classified. This strategy can guarantee that the extracted shapelets accurately reflect the local characteristics of each test instance.(3)
The shapelet coverage score of each sampling point is calculated to analyze the local characteristics of different classes in the dataset. Since the proposed model can efficiently analyze the local features of each instance, more accurate local characteristic information can be obtained. In particular, the classwise discriminative feature frequency and distribution information can be presented, which can help us to understand the data more comprehensively.The remainder of the paper is organized as follows. Section2 introduces related concepts and basic theories. Section 3 describes the proposed model and algorithm design in detail. Section 4 presents the experimental analysis. Section 5 offers the conclusion of this paper.


## 2. Definitions and Notation

In this section, some definitions and formulas related to our model will be presented.Definition 1.
(time series). A time seriesT is an ordered sequence that contains m actual observation values t1,t2,…, and tm, i.e., T=t1,t2,…,tm, ti∈R. The symbol D=T1,T2,…,Tn represents the dataset containing n time series.Definition 2.
(time series subsequence and shapelet). Given a time seriesT=t1,t2,…,tm, a subsequence S of T contains l consecutive values from T; that is, S=ti,ti+1,…,ti+l−1, where 1 ≤ i ≤ m − l + 1. A shapelet is a tuple (S, δ) that consists of a subsequence S and a distance threshold δ.Definition 3.
(candidate shapelet set). The candidate shapelet set is composed of subsequences of time series.
The symbolDnode is a dataset corresponding to an arbitrary tree node in the model SDT or LSCR, and WlDnode is a set of candidate shapelets with length l built on the dataset Dnode. WlDnode in SDT could be represented as follows:(1)WlDnode=∪Ti∈DnodeWlTi,where WlTi denotes the set of subsequences with length l from Ti.
However, in our work, since the best shapelets are searched from the subsequence space of the instance to be classified, the set of shapelet candidates of lengthl for each node in LSCR is(2)WlDnode=WlT,where T is the test instance.
Then, the whole candidate shapelet setsWDnode for each node in SDT and LSCR can be obtained through the following equation:(3)WDnode=∪l=minmaxWlDnode,where min and max are the minimum and maximum candidate lengths, respectively.
Therefore, compared with SDT, LSCR reduces the scale of candidate shapelets in a single node by an order of magnitude.Definition 4.
(similarity of equal-length time series). LetdistTi,Tj be a similarity function of time series, which takes Ti and Tj with equal length as the input. The function will return a nonnegative value, which represents the similarity degree.
Generally, the smaller the distance is between two time series, the more similar the two time series are. In reality, we often need to judge the similarity between unequal time series. For example, in our work, we need to determine whether a time series contains a specific local feature through the distance between a subsequence and a whole time series.Definition 5.
(similarity of unequal-length time series). LetdistulT,S be a similarity function, in which time series T and S have different lengths. The function returns a nonnegative optimal matching distance between two sequences as the degree of similarity. The distance between time series T and sequence S is(4)distulT,S=mindistSi,S,Si∈WS,where the symbol WS represents the subsequence set with length S of time series T (S and T denote the length of sequences S and T, respectively, and S≤T.
In our model, the distance between subsequences with equal length is calculated by the Euclidean distance, while the distance between complete time series is measured by the specified distance function.
In reality, different subsequences may have disparate discriminability. In our work, information gain is used to measure the discrimination of shapelets. To reduce distance computation and improve the shapelet discriminant property, the concept of the evaluation dataset is put forward.Definition 6.
(shapelet evaluation dataset). The shapelet evaluation dataset is a specific subset of the training dataset, which is designed to evaluate the discriminability of local features of each test case.Definition 7.
(entropy of dataset). The entropy of a given datasetD is calculated by the following formula:(5)HD=−∑i=0C−1pDcilogpDci,where ci is an element in the class value set C of D, Dci is the subset of instances with class ci in D, and the proportion pDci is calculated by(6)pDci=DciD.Definition 8 (shapelet information gain).
Given a shapeletS and a dataset D containing instances with different classes, the information gain of S is calculated as follows:(7)IGD,S=argmaxHDs−DleftDHDleft−DleftDHDright,where s is a split distance that can be applied to divide the dataset into two subsets: Dleft=TidistulTi,S≤s and Dright=TidistulTi,S>s.
Finally, the maximum value of information gain is normally treated as the shapelet discrimination, and the corresponding distances is taken as threshold δ. The split distance s usually takes the middle distance between two distance points. The detailed calculation process can be found in the literature [18]. In our model, the shapelet information gain calculated by equation (7) on a specific evaluation dataset reflects the reduction in uncertainty in the predicted class label of the test instance. Here, the mathematical description of our model is introduced.
Given a specific test instanceT, its uncertainty of predicted class in our model is(8)UT=HDeT,where DeT is the initial evaluation dataset of T.
In the prediction process, the proposed model LSCR tries to progressively reduce the uncertainty by its own characteristics. The model can be formulated as(9)minmizeUTS=minimizeIGT,DeTS−∑i=0S−1IGDTei,Si,where Si denotes the ith element in the learned shapelet set S of T.
Additionally,DTei is the corresponding evaluation dataset of Si, which is determined by(10)DTei=DeT,i=0,T′distT′,Si−1≤Si−1.δ,T′∈DTei−1,i>0.
Finally, the main class property of the datasetDTeS−1 would be taken as the predicted class value of T. Generally, there will be only one type of instance left in the final evaluation dataset.


## 3. Targeted Shapelet Extraction Technique

### 3.1. Overview

To provide a brief introduction to the model LSCR, a schematic diagram is first presented in Figure2. As determined from the figure, the evaluation dataset De for the test instance T is first generated; second, the candidate shapelets from T are evaluated on De, and then the best shapelet is employed to exclude the instances that do not contain the local feature represented by S0T; third, the optimal shapelet on the dataset De′ is continually searched until termination. Generally, there will be only one class of instances left in the final dataset, and the class will be taken as the predicted value.Figure 2
A shapelet classification route diagram with 3 nodes. The symbolSiT denotes the ith shapelet on the classification route of the test instance T, and δi is its corresponding split threshold. The circle, rectangle, and triangle icons represent neighbors of T from Class1, Class2, and Class3, respectively. They are distributed around the center (the black spot) of the circle according to their distances from T.The predicted result may be different from the class value of the nearest neighbor or the majority class in the initial dataset. This is the greatest difference between our model and the nearest-neighbor models. Here, the model will be described in detail.


### 3.2. Building Shapelet Evaluation Dataset

From the perspective of information theory, the purpose of extracting the best shapelet is to minimize the uncertainty of the class label of the test instance. The uncertainty is reflected in the class distribution of each subdataset generated based on whether the instance contains the specific feature. Hence, the more unbalanced the distribution of the subset of instances selected based on the shapelet, the more discriminative the feature. For example, for a binary classification problem, it is ideal to use the shapelet to divide the dataset containing instances with different class values into two subsets, each of which contains only one type of instance.For the large-scale dataset, the running time of the searching shapelet is unbearable, so we attempt to sample the training instances for shapelet evaluation. In this paper, instances are selected based on the neighbor distance and the class value of the closest neighbor. Moreover, if the nearest-neighbor instances in the neighborhoods corresponding to the initial node of the classification path belong to the same class, then the route degrades into a single node. In particular, when the size of neighborhoods is set to 1, the model degenerates into 1NN, and the discriminant feature cannot be extracted effectively. In view of these problems, we propose to build a small targeted subset that contains instances with different classes for the instance to be classified. The subset ensures that the distinguishing nature of the local features can be evaluated. In addition, the data sampling strategy can eliminate the impact of intraclass variation on the local feature discriminant evaluation.As shown in Algorithm1, according to the class value of the nearest-neighbor instance, we select k identical and different instances for the test instance to construct a shapelet evaluation dataset (lines 2–6).Algorithm 1:GetEvaluationDataForT (D, T, k, dist).
Input: training dataset: D; test instance: T; the number of homogeneous and heterogeneous instances: k; the distance function used to calculate the similarity between complete time series: dist.Output: the shapelet evaluation dataset: shapeletEvaluationData.(1)
shapeletEvaluationData⟵∅(2)
doublec ⟵ getNearestNeighborClass (D, T)(3)
homogeneityData ⟵ getTopKHomogeneityNearestNeighbors(D, T, k, c)(4)
heterogeneousData ⟵ getTopKHeterogeneousNearestNeighbors (D, T, k, c)(5)
shapeletEvaluationData ⟵ homogeneityData ∪ heterogeneousData(6)
returnshapeletEvaluationData


### 3.3. Finding the Optimal Shapelet

To reduce the computational complexity of extracting the best shapelet and make the extracted shapelets better reflect the characteristics of the test instance, a data-driven shapelet search algorithm is further proposed to find the best shapelet. We only search the best shapelets from the subsequence space of the instance to be classified so that the extracted shapelet accurately reflects the local features of each test instance. The process of generating the candidate shapelets collection for the test instance is given in Algorithm2. In the algorithm, each subsequence of T with starting point i and length j constitutes the candidate shapelet set (line 4).Algorithm 2:GenerateCandidatesForT (T, min, max).
Input: test instance: T; the minimum and maximum length of the shapelet: min and max.Output: the candidate shapelets set: CandidatesSet.(1)
CandidatesSet⟵∅(2)
for each i=0 to Tdo(3)
for each j = min to max do(4)
S ⟵ generateCandidate (T, i, j)(5)
CandidatesSet.add (S)(6)
end for(7)
end for(8)
returnCandidatesSetThe candidate set corresponding to each node in the model SDT containsO (nm2) candidate shapelets, where n is the number of time series and m is the length of each time series. In our model, we only consider the subsequences of test instance T, so there are only O (m2) candidate shapelets to be evaluated for each node. Our work reduces the size of candidate shapelet collection of each node by one order of magnitude.The purpose of extracting shapelets from time series is to classify the time series using the discriminator. The discriminability of shapelets provides us with a way to explain the classification results. Algorithm3 introduces the method for finding the best shapelet for the instance to be classified on the evaluation dataset. First, the candidate shapelet set is generated for T (line 3). Then, each candidate is evaluated by equation (7) to search for the best shapelet (lines 4–8).Algorithm 3:FindingBestShapelet (T, DeT, min, max).
Input: test instance: T; shapelet evaluation dataset for T: DeT; the minimum and maximum length of shapelet: min and max.Output: the best shapelet of the test case: bestShapelet.(1)
bestShapelet ⟵ null(2)
doublebestGain ⟵ 0(3)
CandidateSet ⟵ GenerateCandidatesForT(T, min, max)(4)
for each S∈CandidateSetdo(5)
doublegain ⟵ assessCandidate (DeT, S)(6)
ifgain > bestGainthen(7)
bestGain ⟵ gain(8)
bestShapelet ⟵ S(9)
end if(10)
end for(11)
returnbestShapeletThe time complexity of our model to find the optimal feature isO (km4), while that of the brute-force search algorithm in SDT is O (n2m4). Considering that k is smaller than n, the calculation in the progress of searching for the best shapelet is significantly less. In addition, two ways to improve the efficiency of shapelet search are used [18, 25]: the early abandonment mechanism and the shapelet entropy pruning strategy.


### 3.4. Lazy Shapelet Classification Algorithm

A classification route based on shapelets for each instance to be classified is built through Algorithm4.Algorithm 4:LSCRdist (D, T).
Input: training dataset: D; the test instance: T; the distance function used to calculate the similarity between complete time series: dist.Output: the classification route for T: CRForT.(1)
Build the initial evaluation datasetDeT for T at the root node by Algorithm 1(2)
Generate the candidate shapelet setWDnode for T by Algorithm 2(3)
Evaluate each candidate shapelet inWDnode based on DeT using Algorithm 3 and search for the best shapelet S.(4)
if no discriminatory shapelet S can be found in WDnodethen(5)
returnCRForT and the majority class c in DeT is taken as the predictive value(6)
else(7)
Update the evaluation datasetDeT to exclude instances that do not contain the feature S(8)
Build the child node(9)
end if(10)
repeat steps 2 to 9 until the end(11)
returnCRForTAlgorithm4 mainly consists of five steps. First, the targeted shapelet evaluation dataset is established for T (line 1). Second, the candidate shapelet set is generated for T (line 2). Third, the model searches for the best shapelet on the evaluation dataset (line 3) and judges whether the termination condition is satisfied (line 4). It does not meet the termination condition at the initial node; that is, it will not degrade to the single node route. Generally, a best shapelet S is found. Fourth, the extracted shapelet S is applied to update the evaluation dataset for the child node (lines 7–8). Only the training instances whose distances are not greater than the split threshold are selected to form the subdataset. Fifth, the model repeats steps 2–8 until the termination condition is satisfied (line 10). Last, the shapelet-based classification route for T is returned (line 11).


### 3.5. Computing Shapelet Coverage Score

Definition 9 (shapelet coverage).
Shapelet coverage refers to the corresponding time interval of a given shapeletS. If a time stamp t falls within the shapelet coverage of S, then we state that t is covered by S.
In our work, the discriminatory score is calculated for each time stamp based on the coverage intervals of all obtained shapelets. First, an indicator function is presented to determine whether a time stampt is covered by a given shapelet S:(11)It,S=1,ift∈S.sp,S.sp+|S|−1,0,otherwise,where sp denotes the starting position of S in the time series.
Then, based on shapelets captured on the decision path of all correctly predicted time series, the importance of time stamps for different classes can be evaluated through the following formula:(12)scoret,c=∑T∈Dcorrectc∑S∈STIt,S,where Dcorrectc represents the set of correctly predicted instances with class value c and ST indicates the set of shapelets captured on the classification path of T.
In essence, the coverage scorescoret,c reflects the discriminability of the time stamp t, which can be used to detect the distribution of distinguishing feature intervals and the feature frequency information for each category. Generally, the interval composed of several consecutive time stamps with similar scores corresponds to the local differentiating features. Therefore, in our work, the interval satisfying the condition would be regarded as the local feature location. In addition, the scores demonstrate their occurrence frequency.
Here, the algorithm of computing the shapelet coverage scores for different classes in the dataset will be introduced.
In Algorithm5, to compute the shapelet coverage score for each class, the dataset Dcorrecti of the correctly predicted instances with the specific class is first obtained (lines 2-3). Then, all shapelets captured by LSCR for every instance in Dcorrecti are collected (lines 4–6). Finally, the scores reflecting the discriminability of each time stamp for every class are calculated based on equation (12) (line 7).Algorithm 5:ComputeScore (Dcorrect, C, m).
Input: the dataset of correctly predicted instances: Dcorrect; the set of class values: C; the length of time series: m.Output: the shapelet coverage scores: Scores.(1)
Initialization of aC×m matrix Scores(2)
for each i=1 to Cdo(3)
Select the instances with classci from Dcorrect to form the dataset Dcorrecti(4)
for each T in Dcorrectido(5)
Get the shapelet setST of T on its classification route learned by Algorithm 4(6)
end for(7)
Calculate the shapelet coverage scoreScores[][] based on equation (12)(8)
end for(9)
returnScores


## 3.1. Overview

To provide a brief introduction to the model LSCR, a schematic diagram is first presented in Figure2. As determined from the figure, the evaluation dataset De for the test instance T is first generated; second, the candidate shapelets from T are evaluated on De, and then the best shapelet is employed to exclude the instances that do not contain the local feature represented by S0T; third, the optimal shapelet on the dataset De′ is continually searched until termination. Generally, there will be only one class of instances left in the final dataset, and the class will be taken as the predicted value.Figure 2
A shapelet classification route diagram with 3 nodes. The symbolSiT denotes the ith shapelet on the classification route of the test instance T, and δi is its corresponding split threshold. The circle, rectangle, and triangle icons represent neighbors of T from Class1, Class2, and Class3, respectively. They are distributed around the center (the black spot) of the circle according to their distances from T.The predicted result may be different from the class value of the nearest neighbor or the majority class in the initial dataset. This is the greatest difference between our model and the nearest-neighbor models. Here, the model will be described in detail.


## 3.2. Building Shapelet Evaluation Dataset

From the perspective of information theory, the purpose of extracting the best shapelet is to minimize the uncertainty of the class label of the test instance. The uncertainty is reflected in the class distribution of each subdataset generated based on whether the instance contains the specific feature. Hence, the more unbalanced the distribution of the subset of instances selected based on the shapelet, the more discriminative the feature. For example, for a binary classification problem, it is ideal to use the shapelet to divide the dataset containing instances with different class values into two subsets, each of which contains only one type of instance.For the large-scale dataset, the running time of the searching shapelet is unbearable, so we attempt to sample the training instances for shapelet evaluation. In this paper, instances are selected based on the neighbor distance and the class value of the closest neighbor. Moreover, if the nearest-neighbor instances in the neighborhoods corresponding to the initial node of the classification path belong to the same class, then the route degrades into a single node. In particular, when the size of neighborhoods is set to 1, the model degenerates into 1NN, and the discriminant feature cannot be extracted effectively. In view of these problems, we propose to build a small targeted subset that contains instances with different classes for the instance to be classified. The subset ensures that the distinguishing nature of the local features can be evaluated. In addition, the data sampling strategy can eliminate the impact of intraclass variation on the local feature discriminant evaluation.As shown in Algorithm1, according to the class value of the nearest-neighbor instance, we select k identical and different instances for the test instance to construct a shapelet evaluation dataset (lines 2–6).Algorithm 1:GetEvaluationDataForT (D, T, k, dist).
Input: training dataset: D; test instance: T; the number of homogeneous and heterogeneous instances: k; the distance function used to calculate the similarity between complete time series: dist.Output: the shapelet evaluation dataset: shapeletEvaluationData.(1)
shapeletEvaluationData⟵∅(2)
doublec ⟵ getNearestNeighborClass (D, T)(3)
homogeneityData ⟵ getTopKHomogeneityNearestNeighbors(D, T, k, c)(4)
heterogeneousData ⟵ getTopKHeterogeneousNearestNeighbors (D, T, k, c)(5)
shapeletEvaluationData ⟵ homogeneityData ∪ heterogeneousData(6)
returnshapeletEvaluationData


## 3.3. Finding the Optimal Shapelet

To reduce the computational complexity of extracting the best shapelet and make the extracted shapelets better reflect the characteristics of the test instance, a data-driven shapelet search algorithm is further proposed to find the best shapelet. We only search the best shapelets from the subsequence space of the instance to be classified so that the extracted shapelet accurately reflects the local features of each test instance. The process of generating the candidate shapelets collection for the test instance is given in Algorithm2. In the algorithm, each subsequence of T with starting point i and length j constitutes the candidate shapelet set (line 4).Algorithm 2:GenerateCandidatesForT (T, min, max).
Input: test instance: T; the minimum and maximum length of the shapelet: min and max.Output: the candidate shapelets set: CandidatesSet.(1)
CandidatesSet⟵∅(2)
for each i=0 to Tdo(3)
for each j = min to max do(4)
S ⟵ generateCandidate (T, i, j)(5)
CandidatesSet.add (S)(6)
end for(7)
end for(8)
returnCandidatesSetThe candidate set corresponding to each node in the model SDT containsO (nm2) candidate shapelets, where n is the number of time series and m is the length of each time series. In our model, we only consider the subsequences of test instance T, so there are only O (m2) candidate shapelets to be evaluated for each node. Our work reduces the size of candidate shapelet collection of each node by one order of magnitude.The purpose of extracting shapelets from time series is to classify the time series using the discriminator. The discriminability of shapelets provides us with a way to explain the classification results. Algorithm3 introduces the method for finding the best shapelet for the instance to be classified on the evaluation dataset. First, the candidate shapelet set is generated for T (line 3). Then, each candidate is evaluated by equation (7) to search for the best shapelet (lines 4–8).Algorithm 3:FindingBestShapelet (T, DeT, min, max).
Input: test instance: T; shapelet evaluation dataset for T: DeT; the minimum and maximum length of shapelet: min and max.Output: the best shapelet of the test case: bestShapelet.(1)
bestShapelet ⟵ null(2)
doublebestGain ⟵ 0(3)
CandidateSet ⟵ GenerateCandidatesForT(T, min, max)(4)
for each S∈CandidateSetdo(5)
doublegain ⟵ assessCandidate (DeT, S)(6)
ifgain > bestGainthen(7)
bestGain ⟵ gain(8)
bestShapelet ⟵ S(9)
end if(10)
end for(11)
returnbestShapeletThe time complexity of our model to find the optimal feature isO (km4), while that of the brute-force search algorithm in SDT is O (n2m4). Considering that k is smaller than n, the calculation in the progress of searching for the best shapelet is significantly less. In addition, two ways to improve the efficiency of shapelet search are used [18, 25]: the early abandonment mechanism and the shapelet entropy pruning strategy.


## 3.4. Lazy Shapelet Classification Algorithm

A classification route based on shapelets for each instance to be classified is built through Algorithm4.Algorithm 4:LSCRdist (D, T).
Input: training dataset: D; the test instance: T; the distance function used to calculate the similarity between complete time series: dist.Output: the classification route for T: CRForT.(1)
Build the initial evaluation datasetDeT for T at the root node by Algorithm 1(2)
Generate the candidate shapelet setWDnode for T by Algorithm 2(3)
Evaluate each candidate shapelet inWDnode based on DeT using Algorithm 3 and search for the best shapelet S.(4)
if no discriminatory shapelet S can be found in WDnodethen(5)
returnCRForT and the majority class c in DeT is taken as the predictive value(6)
else(7)
Update the evaluation datasetDeT to exclude instances that do not contain the feature S(8)
Build the child node(9)
end if(10)
repeat steps 2 to 9 until the end(11)
returnCRForTAlgorithm4 mainly consists of five steps. First, the targeted shapelet evaluation dataset is established for T (line 1). Second, the candidate shapelet set is generated for T (line 2). Third, the model searches for the best shapelet on the evaluation dataset (line 3) and judges whether the termination condition is satisfied (line 4). It does not meet the termination condition at the initial node; that is, it will not degrade to the single node route. Generally, a best shapelet S is found. Fourth, the extracted shapelet S is applied to update the evaluation dataset for the child node (lines 7–8). Only the training instances whose distances are not greater than the split threshold are selected to form the subdataset. Fifth, the model repeats steps 2–8 until the termination condition is satisfied (line 10). Last, the shapelet-based classification route for T is returned (line 11).


## 3.5. Computing Shapelet Coverage Score

Definition 9 (shapelet coverage).
Shapelet coverage refers to the corresponding time interval of a given shapeletS. If a time stamp t falls within the shapelet coverage of S, then we state that t is covered by S.
In our work, the discriminatory score is calculated for each time stamp based on the coverage intervals of all obtained shapelets. First, an indicator function is presented to determine whether a time stampt is covered by a given shapelet S:(11)It,S=1,ift∈S.sp,S.sp+|S|−1,0,otherwise,where sp denotes the starting position of S in the time series.
Then, based on shapelets captured on the decision path of all correctly predicted time series, the importance of time stamps for different classes can be evaluated through the following formula:(12)scoret,c=∑T∈Dcorrectc∑S∈STIt,S,where Dcorrectc represents the set of correctly predicted instances with class value c and ST indicates the set of shapelets captured on the classification path of T.
In essence, the coverage scorescoret,c reflects the discriminability of the time stamp t, which can be used to detect the distribution of distinguishing feature intervals and the feature frequency information for each category. Generally, the interval composed of several consecutive time stamps with similar scores corresponds to the local differentiating features. Therefore, in our work, the interval satisfying the condition would be regarded as the local feature location. In addition, the scores demonstrate their occurrence frequency.
Here, the algorithm of computing the shapelet coverage scores for different classes in the dataset will be introduced.
In Algorithm5, to compute the shapelet coverage score for each class, the dataset Dcorrecti of the correctly predicted instances with the specific class is first obtained (lines 2-3). Then, all shapelets captured by LSCR for every instance in Dcorrecti are collected (lines 4–6). Finally, the scores reflecting the discriminability of each time stamp for every class are calculated based on equation (12) (line 7).Algorithm 5:ComputeScore (Dcorrect, C, m).
Input: the dataset of correctly predicted instances: Dcorrect; the set of class values: C; the length of time series: m.Output: the shapelet coverage scores: Scores.(1)
Initialization of aC×m matrix Scores(2)
for each i=1 to Cdo(3)
Select the instances with classci from Dcorrect to form the dataset Dcorrecti(4)
for each T in Dcorrectido(5)
Get the shapelet setST of T on its classification route learned by Algorithm 4(6)
end for(7)
Calculate the shapelet coverage scoreScores[][] based on equation (12)(8)
end for(9)
returnScores


## 4. Experiments

Experimental analyses are conducted on 20 datasets from the UCR time series repository [38], most of which are frequently used for evaluation of shapelet-based models [9, 21, 22, 24, 27]. The experimental data are divided into training and test parts. The former part is used to build the model, while the latter part is applied to calculate the classification accuracy. The information of datasets is listed in Table 1, including train (size of the training set), test (size of the test set), max_k (the minimum number of instances of a class in the training set; that is, the maximum value that parameter k can take.), length (the length of time series), and classes (the number of classes).Table 1
Introduction of the experimental datasets.
DatasetTrainTestmax_kLengthClassesArrowHead36175122513Beef303064705BeetleFly2020105122CBF3090081283ECGFiveDays2386191362FaceFour248833504FacesUCR2002050413114GunPoint50150241502ItalyPowerDemand67102933242Lightning7707383197MedicalImages38176069910MiddlePhalanxOutlineAgeGroup40015455803MoteStrain20125210842Plane10510591447ProximalPhalanxOutlineAgeGroup40020572803SonyAIBORobotSurface1206016702SonyAIBORobotSurface22795311652ToeSegmentation140228202772ToeSegmentation236130183432Wine5754272342


### 4.1. Parameterk Analysis

To study the effect of the size of the evaluation dataset on the discriminative evaluation of shapelets, the accuracy trends ofLSCRDTW within the specified range over 10 datasets are first analyzed as a representative. Then, the average accuracy curves of 5 fusion models (LSCRDTW, LSCRERP, LSCRED, LSCRTWE, and LSCRMSM) are presented for parameter setting.Figure3 shows the sensitivity of prediction results of different datasets to parameter k. From Figure 3(a), it can be seen that most accuracy rates on 5 binary-class datasets reach the maximum values when parameter k is 5, and then all of the curves show a significant downward trend. From Figure 3(b), except for the MiddlePhalanxOutlineAgeGroup, the accuracy rates on 4 multiclass datasets exhibit a growth trend as k increases in the previous stage. When k is greater than 6, the accuracy on each dataset tends to be stable or decrease. The above experimental results suggest that the accuracy of LSCR generally varies regularly with k. Therefore, we propose to set k based on the trend of average accuracy.Figure 3
The accuracy and time variations of the modelLSCRDTW on 5 binary-class and 5 multiclass datasets with the value k increasing.
(a)(b)(c)In Figure4(a), it can be seen that, on binary-class datasets, the average accuracy variations of 5 fusion models show two significantly different trends. One shows a trend of increasing and gradually becoming stable, while the other presents a significant decline in accuracy after passing the inflection point. In Figure 4(b), on multiclass datasets, the average accuracies of all fusion models first increase and then decrease slowly after reaching the peak. Finally, in our work, the value k corresponding to the highest average accuracy is set as the final parameter of LSCRdist on binary-class and multiclass datasets, respectively. See Table 2 for specific settings of the 5 fusion models.Figure 4
The average accuracy variations of the modelLSCRdist combined with different distance functions on (a) 5 binary-class and (b) 5 multiclass datasets with the parameter k increasing.
(a)(b)Table 2
Parameter settings of all fusion models.
LSCREDLSCRDTWLSCRTWELSCRMSMLSCRERPBinary1055107Multi66686In addition, the effect of instance selection on model performance is interpreted in Figure5. In the scatter diagram, each point stands for a dataset. The more points there are in the figure that fall below the diagonal line, the better the performance of LSCRDTW. Since the targeted evaluation dataset is very helpful to improve the feature quality, the proposed shapelet evaluation strategy can significantly improve the performance of our model. As shown in Figure 5, LSCRDTW outperforms LSCRDTW (whole) on almost all datasets. The accuracy rates of the above two models are listed in Table 3.Figure 5
Accuracy comparison betweenLSCRDTW combining instance selection for shapelet evaluation and LSCRDTW (whole) using the whole training set as the evaluation set on 20 datasets.Table 3
The accuracies ofLSCRDTW (whole), 5 fusion, and 1NN models.
DatasetLSCRDTWDTWLSCRERPERPLSCREDEDLSCRTWETWELSCRMSMMSMLSCRDTW (whole)ArrowHead0.7490.8000.7490.8000.7940.8000.7430.7940.7260.8060.629Beef0.7330.6670.6670.6670.7000.6670.7330.6000.7000.4670.733BeetleFly0.8000.6500.7000.7500.7500.7500.8000.7000.7000.6000.500CBF0.9910.9940.9930.9980.9840.8520.9890.9910.9970.9690.994ECGFiveDays0.8630.7970.9050.8060.8800.7970.8790.8290.9000.8910.533FaceFour0.9090.8980.8640.8640.9090.7840.8860.8520.8180.9430.807FacesUCR0.9240.9080.9260.9210.8110.7690.8540.9200.9260.9710.821GunPoint0.8800.9130.8930.9470.8870.9130.8730.9530.9270.9730.720ItalyPowerDemand0.9480.9550.9350.9550.9480.9550.9480.9480.9320.9440.881Lightning70.5890.7120.6160.7400.5480.5750.5210.7530.6580.7530.548MedicalImages0.6990.7470.6820.6760.6530.6840.6280.7110.6960.7410.507MiddlePhalanxOutlineAgeGroup0.5390.5190.5190.4810.5190.5190.5450.5190.4940.4940.422MoteStrain0.9030.8660.8580.8720.8590.8790.9080.7970.8810.8550.550Plane1.0001.0001.0001.0001.0000.9621.0001.0001.0001.0000.990ProximalPhalanxOutlineAgeGroup0.8100.7850.8150.7950.8000.7850.8050.8050.7270.7900.678SonyAIBORobotSurface10.7500.6960.8150.6890.7750.6960.7340.6810.7850.7300.704SonyAIBORobotSurface20.8430.8590.8640.8230.8770.8590.8460.8530.8850.8710.703ToeSegmentation10.8160.7500.8510.8330.6620.6800.8110.8200.7890.8160.632ToeSegmentation20.9000.9080.9150.9230.8230.8080.9380.7850.8920.7540.815Wine0.6110.6110.6110.6110.5740.6110.5930.5740.6480.5930.574Average0.8130.8020.8090.8070.7880.7670.8020.7940.8040.7980.687


### 4.2. Fusion Strategy Analysis

In this section, the effectiveness of the fusion strategy of global and local similarities is analyzed. Table3 presents the accuracies of 5 1NN models combined with different distance functions (DTW, ERP, ED, TWE, and MSM) and their corresponding five fusion models. The accuracies of the 1NN models are taken from the website [38].Figure6 shows a critical difference diagram studied in literature [39, 40] for the 10 classification models on 20 datasets. This diagram is used for the overall test of significance of average ranks and can group models without significant differences into cliques. From the figure, we find that there are no significant differences in the performance of the 10 models on the 20 datasets, but the rankings of all fusion models are better than those of the corresponding 1NN models. This result suggests that the fusion model can effectively improve the classification performance of the 1NN model to some extent. Since LSCRDTW ranks first, it will be used for further analysis in the following.Figure 6
The critical difference diagram for 5 fusion models and 5 corresponding 1NN models on 20 datasets.


### 4.3. Performance Analysis

In this section, the proposed model is compared with shapelet-based classifiers and 1NN classifiers combining with many commonly used distance functions and deep learning models.


#### 4.3.1. Comparison with Shapelet-Based Classifiers

Since the classification process of the model proposed is similar to the decision tree, for the sake of fairness, all shapelet-based comparison models choose the decision tree to make predictions. Our model is first compared with SDT, fast shapelet tree (FS) [26], and C4.5 model [41] based on two respective shapelet transform algorithms. The symbol SSC4.5 denotes the C4.5 model based on the transform algorithm proposed by Yuan et al. [22], and STC4.5 represents the C4.5 model based on the other one proposed by Lines et al. [20]. The shapelet length ranges from 3 to the full length of time series and increases by 1 each time. All experimental results are listed in Table 4, and the accuracies of FS are obtained from the website [38]. In addition, the last line in Table 4 provides the average accuracy of each model over 20 datasets.Table 4
The accuracies of 5 shapelet-based models and 3 DTW variants on 20 datasets.
DatasetLSCRDTWSDTSTC4.5SSC4.5FSWDTWCIDDDDTWArrowHead0.7490.7540.6860.6860.5940.8170.8290.789Beef0.7330.5330.5000.6000.5670.7000.6330.667BeetleFly0.8000.7500.6000.7000.7000.7000.7500.650CBF0.9910.9390.8810.9790.9400.9970.9990.997ECGFiveDays0.8630.9940.9580.9900.9980.7960.7820.769FaceFour0.9090.7950.7500.7500.9090.8750.8750.830FacesUCR0.9240.6450.6620.6310.7060.9200.8950.904GunPoint0.8800.9470.8930.9130.9470.9800.9270.980ItalyPowerDemand0.9480.9580.9540.9420.9170.9500.9560.950Lightning70.5890.5070.6990.5750.6440.7670.6990.671MedicalImages0.6990.5160.4870.6380.6240.7370.7420.737MiddlePhalanxOutlineAgeGroup0.5390.4740.4480.8250.5450.5190.5130.539MoteStrain0.9030.8230.7600.8180.7770.8590.7960.833Plane1.0000.9330.9050.8381.0001.0001.0001.000ProximalPhalanxOutlineAgeGroup0.8100.7810.7710.8440.7800.8050.7900.800SonyAIBORobotSurface10.7500.7350.8770.8490.6860.7370.8150.742SonyAIBORobotSurface20.8430.6590.7570.7950.7900.8310.8770.892ToeSegmentation10.8160.8950.8990.8820.9560.7940.7370.807ToeSegmentation20.9000.8690.8690.8000.6920.8920.8770.746Wine0.6110.7960.7590.7780.7590.5740.6110.574Average0.8130.7650.7560.7920.7770.8130.8050.794As observed from Figure7, it is clear that although there is no significant difference between LSCRDTW and the other 4 shapelet-based models, the average rank of LSCRDTW is the best.Figure 7
The critical difference diagram forLSCRDTW and 4 shapelet-based models on 20 datasets.Figure8 presents the scatter plot of accuracy comparison between LSCRDTW and the 4 classical shapelet-based classifiers. Figure 8(a) shows that LSCRDTW is better than SDT (14 of 20) over the 20 datasets. From Table 4, we find that compared with that of SDT built on the entire training set, the accuracies of LSCRDTW on datasets MoteStrain, FacesUCR, SonyAIBORobotSurface2, etc., are significantly improved. In particular, on the dataset FacesUCR, the accuracy of LSCRDTW is 20% greater than that of SDT. In Figures 8(b)–8(d), it can be concluded that LSCRDTW is also better than STC4.5 (13 of 16), SSC4.5 (13 of 20), and FS (14 of 20). Hence, Figure 8 demonstrates that LSCRDTW outperforms the existing shapelet-based decision tree model on the 20 datasets.Figure 8
Accuracy comparison betweenLSCRDTW and 4 shapelet-based classifiers.
(a)(b)(c)(d)To compare the time complexity ofLSCRDTW with other shapelet-based models, the changes in running times of 6 shapelet-based models with increasing number of instances and instance length are shown in Figure 9, respectively. LSCRDTW(single) represents the training time of a single model LSCRDTW for a specific test instance, while LSCRDTW represents the model running on the entire test set. In the experiment, a binary-class dataset with uniform distribution is designed to run the analysis models, and the size of the training set is always the same as that of the test dataset. For the first experiment, the sizes of training and test datasets increase by 10 at a time. The length of all instances remains 100. For another, the instance length increases by 10 at a time. The sizes of training and test sets are 100.Figure 9
The running time trends of 6 shapelet-based models with increasing training dataset size and instance length, respectively.
(a)(b)(c)(d)From Figures9(a) and 9(b), we can determine that the training time of LSCRDTW (single) is not sensitive to the size of the training set and is polynomial with respect to the length of the time series. In particular, it is faster than the current fastest shapelet-based model FS. Further, as observed from Figures 9(c) and 9(d), with increasing training set size and instance length, the time consumption gap between SDT, STC4.5, and LSCRDTW widens, while the gap between LSCRDTW and SSC4.5 is not obvious.In conclusion,LSCRDTW is an accurate and rapid shapelet-based classification model, which is the basis of learning feature distribution and frequency information.


#### 4.3.2. Comparison with Various 1NN Classifiers

In this section, except for the five distance functions listed above, we further compare our model with several DTW variants, including WDTW, complexity-invariant DTW (CID) [42], and derivativedistanceDTW (DDDTW) [43]. The accuracies for the above 1NN models are provided by the website [38] (see Table 4).Figure10 demonstrates that our model exhibits no significant difference from DTW and its variants, but the average ranks of LSCRDTW are the best. In Figure 11, it is clear that LSCRDTW is better than ED (16 of 20), TWE (14 of 20), ERP (13 of 20), MSM (12 of 20), DTW (11 of 20), WDTW (14 of 20), CID (11 of 20), and DDDTW (13 of 20).Figure 10
The critical difference diagram forLSCRDTW, DTW, and 3 DTW variants on 20 datasets.Figure 11
Accuracy comparison betweenLSCRDTW and 8 1NN classifiers based on different distance functions.
(a)(b)(c)(d)(e)(f)(g)(h)In summary,LSCRDTW is competitive with the 1NN model that depends on global similarity. The comparison results suggest that continuously narrowing the search space of class attributes based on local similarity is an effective way to make prediction.


#### 4.3.3. Comparison with Deep Learning Models

Now, various deep learning models have been widely studied in the field of time series classification. Karim et al. [44] attempted to improve the univariate time series classification performance of fully convolutional neural networks (FCNs) by using the long short-term memory recurrent neural network (LSTM-RNNs) submodules and attention mechanism and proposed the excellent models LSTM-FCN and ALSTM-FCN. Furthermore, the authors applied the above two models to the multivariate time series classification problem [45] and studied the reasons why the two models have superior performance [46]. Fawaz et al. [47] have reviewed some deep learning models of time series classification. Here, our model is compared with LSTM-FCN and 9 deep learning models (ResNet, FCN, Encoder, MLP, Time-CNN, TWIESN, MCDCNN, MCNN, and t-LeNet) analyzed in the literature [47]. All the experimental results were obtained from the corresponding literature (see Table 5).Table 5
The classification accuracies of 10 deep learning models on 20 datasets.
DatasetLSTM-FCNMLPFCNResNetEncoderMCNNt-LeNetMCDCNNTime-CNNTWIESNArrowHead0.9090.7780.8430.8450.8040.3390.3030.6850.7230.659Beef0.9000.7200.6970.7530.6430.2000.2000.5630.7630.537BeetleFly0.9500.8700.8600.8500.7450.5000.5000.5800.8900.730CBF0.9980.8720.9940.9950.9470.3320.3320.8200.9570.890ECGFiveDays0.9920.9700.9870.9750.9820.4990.4970.7620.8820.698FaceFour0.9430.8400.9280.9550.8150.2680.2950.7120.9060.855FacesUCR0.9290.8330.9460.9550.8740.1530.1430.7560.8690.644GunPoint1.0000.9271.0000.9910.9360.5130.4930.8670.9320.961ItalyPowerDemand0.9630.9540.9610.9630.9650.5000.4990.9550.9550.880Lightning70.8360.6300.8270.8450.6250.3100.2600.5340.6510.664MedicalImages0.8010.7210.7790.7700.7340.5140.5140.6400.6760.649MiddlePhalanxOutlineAgeGroup0.8130.5310.5530.5690.5790.1880.5710.5850.5660.581MoteStrain0.9390.8580.9370.9280.8400.5080.5390.7650.8820.785Plane1.0000.9781.0001.0000.9760.1300.1340.9650.9651.000ProximalPhalanxOutlineAgeGroup0.8930.8560.8310.8530.8440.4880.4880.8380.8280.844SonyAIBORobotSurface10.9820.6720.9600.9580.7430.4430.4290.6530.6870.638SonyAIBORobotSurface20.9780.8340.9790.9780.8390.5940.6170.7740.8410.697ToeSegmentation10.9830.5830.9610.9630.6590.5050.5260.4900.5950.865ToeSegmentation20.9310.7450.8800.9060.7950.6320.8150.4430.7380.842Wine0.8700.5650.5870.7440.5000.5000.5000.5000.5170.759Average0.9300.7870.8760.8900.7920.4060.4330.6940.7910.759Figure12 shows that, except for ResNet and FCN, LSTM-FCN is significantly better than other models, and that our model is significantly better than MCNN and t-LeNet. Among the 10 deep learning models, the average rank of our model is better than 7 of them. In Figure 13, it can be seen that LSCRDTW is better than Encoder (12 of 20), Time-CNN (12 of 20), MLP (12 of 20), TWIESN (13 of 20), MCDCNN (17 of 20), t-LeNet (19 of 20), and MCNN (20 of 20).Figure 12
The critical difference diagram forLSCRDTW and 10 deep learning models on 20 datasets.Figure 13
Accuracy comparison betweenLSCRDTW and 10 deep learning models.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Generally, to improve performance, deep learning model tuning requires an enormous computational cost. To pursue the optimal accuracy rate, Fawaz et al. [48] even proposed the neural network ensemble model with 60 deep learning models, but it is still not better than the traditional ensemble model HIVE-COTE [49]. It is unfair to compare our model with the deep learning model based on accuracy alone. In addition to improving accuracy, we believe that the model interpretability and data comprehensibility require more attention. However, the existing feature extraction methods for time series usually cannot simultaneously obtain the feature distribution and frequency information. For the deep learning model, it is difficult to train a targeted model for the specific instance on a small dataset. Accordingly, in our work, a highly interpretable classification model based on the lazy learning strategy is built for each target instance, which can be applied to gain insight into the local feature distribution and frequency information. The following is a detailed introduction.


### 4.4. Interpretability

To demonstrate the stronger interpretability of our model, this section separately analysesLSCRDTW on a binary-class dataset, MoteStrain, and the CBF multiclass dataset.


#### 4.4.1. MoteStrain Dataset

Sensing data in MoteStrain are originally collected to detect potential variables online in the sensor network [50]. The classification task on this dataset is to distinguish whether the sensor is used for humidity measurement or temperature measurement. The classification performance of our model is significantly better than that of the model used for comparison and is close to the current best classification result provided by Bagnall et al. [38] on this dataset.To further investigate the proposed model, the shapelet decision tree built by SDT is shown in Figure14, where the symbol S0,04 represents the shapelet extracted from the fourth training instance Train4 in the root node of the shapelet decision tree. As seen from Figure 14, there is only one shapelet in the decision tree, where d denotes the distance between the test instance and the shapelet and δ represents the split threshold of the shapelet. Based on the shapelet decision tree, when the distance between the test instance and the shapelet corresponding to the root node is not greater than the split threshold, the class prediction value of the test instance is Class1. Otherwise, it is Class2.Figure 14
The shapelet decision tree and the shapelets found by SDT.Figure15 shows six instances and their shapelets extracted through LSCRDTW. Our model can correctly predict the class properties of these six instances, while SDT fails. Meanwhile, it is obvious that there are not only significant differences between instances of different types but also intraclass variations among similar instances. For example, the differences among the three instances with the same class label, Test11, Test129, and Test189, are noticeable, while there are no obvious common features. However, in the shapelet decision tree built by SDT, only a shapelet is found, which is not sufficient to distinguish the two classes. In contrast to the illustration of the shapelet given in Figure 14, it is not difficult to find that the optimal shapelet obtained in the shapelet decision tree is not the most discriminatory feature for the test instances. This result verifies that the shapelets extracted from the entire dataset are the most discriminatory for each training instance in the average sense; this is also the reason for the poor performance of SDT on the MoteStrain dataset.Figure 15
Six test instances from the MoteStrain dataset and their shapelets found byLSCRDTW. The three instances (a–c) are from Class1, and the other three (d–f) are from Class2. (a) Test11, (b) Test129, (c) Test189, (d) Test3, (e) Test41, and (f) Test55.
(a)(b)(c)(d)(e)(f)Since the characteristics of each test instance have been considered in our model, in light of this situation, we can achieve better classification results. In addition, based on the shapelet obtained byLSCRDTW, the prediction process of each instance can be explained. For example, as shown in Figure 15, the reason why the 11th test instance belongs to Class1 is that the local feature S011 lies in its initial stage, while the local feature S041 of the 41st test instance in the middle part determines its predicted class label.Figure16 displays the scores of shapelets coverage on the MoteStrain training and test datasets. It is obvious that the high score intervals on training and test sets are very similar. Since there are only 20 instances in the training set, the scores of shapelet coverage (as shown in Figure 16(a)) may not accurately reflect the local characteristics. However, we propose to directly evaluate the local characteristics of test cases, which can help us utilize large amounts of test data. In Figure 16(b), it can be seen that local features with different coverage frequencies of various classes have been detected from the test dataset, which cannot be captured by other shapelet-based models. For example, the intervals [9, 16] (low frequency), [44, 54] (medium frequency), and [59, 76] (high frequency) (as shown in Figure 16(b)) are three significant discriminative intervals of Class2, while the interval [21, 50] (high frequency) is the most discriminative part of Class1. Based on the proposed model, using more instances with accurate labels results in obtaining more accurate local feature information. The statistical information helps us acquire more comprehensive local characteristic information of time series data, such as feature distribution and frequency.Figure 16
The shapelet coverage scores obtained on training and test datasets of MoteStrain: (a) training dataset and (b) test dataset.
(a)(b)


#### 4.4.2. CBF Dataset

This section studies the multiclass dataset CBF, which contains three types: Cylinder, Bell, and Funnel. Figure17 shows the coverage scores of the CBF test dataset. It can be determined that the interval [31, 75] covers the most discriminative intervals for all three classes. In addition, unlike Cylinder and Funnel, the local interval [0, 15] with relatively low coverage frequency is discriminative for Bell.Figure 17
The shapelet coverage scores obtained on the CBF test dataset.Next, four specific test instances are presented. As shown in Figure18, for the multiclass dataset, our model can not only detect high-frequency shapelets (as shown in Figures 18(a)–18(c)) but also effectively capture low-frequency shapelets (as shown in Figure 18(d)). The proposed model LSCRdist is helpful to make a targeted analysis of each category of data and each test instance.Figure 18
Four test instances from the CBF dataset and their shapelets found byLSCRDTW. The first two instances (a-b) are from Cylinder and Funnel, while the last two (c-d) are from Bell. (a) Test23, (b) Test5, (c) Test21, and (d) Test0.
(a)(b)(c)(d)


## 4.1. Parameterk Analysis

To study the effect of the size of the evaluation dataset on the discriminative evaluation of shapelets, the accuracy trends ofLSCRDTW within the specified range over 10 datasets are first analyzed as a representative. Then, the average accuracy curves of 5 fusion models (LSCRDTW, LSCRERP, LSCRED, LSCRTWE, and LSCRMSM) are presented for parameter setting.Figure3 shows the sensitivity of prediction results of different datasets to parameter k. From Figure 3(a), it can be seen that most accuracy rates on 5 binary-class datasets reach the maximum values when parameter k is 5, and then all of the curves show a significant downward trend. From Figure 3(b), except for the MiddlePhalanxOutlineAgeGroup, the accuracy rates on 4 multiclass datasets exhibit a growth trend as k increases in the previous stage. When k is greater than 6, the accuracy on each dataset tends to be stable or decrease. The above experimental results suggest that the accuracy of LSCR generally varies regularly with k. Therefore, we propose to set k based on the trend of average accuracy.Figure 3
The accuracy and time variations of the modelLSCRDTW on 5 binary-class and 5 multiclass datasets with the value k increasing.
(a)(b)(c)In Figure4(a), it can be seen that, on binary-class datasets, the average accuracy variations of 5 fusion models show two significantly different trends. One shows a trend of increasing and gradually becoming stable, while the other presents a significant decline in accuracy after passing the inflection point. In Figure 4(b), on multiclass datasets, the average accuracies of all fusion models first increase and then decrease slowly after reaching the peak. Finally, in our work, the value k corresponding to the highest average accuracy is set as the final parameter of LSCRdist on binary-class and multiclass datasets, respectively. See Table 2 for specific settings of the 5 fusion models.Figure 4
The average accuracy variations of the modelLSCRdist combined with different distance functions on (a) 5 binary-class and (b) 5 multiclass datasets with the parameter k increasing.
(a)(b)Table 2
Parameter settings of all fusion models.
LSCREDLSCRDTWLSCRTWELSCRMSMLSCRERPBinary1055107Multi66686In addition, the effect of instance selection on model performance is interpreted in Figure5. In the scatter diagram, each point stands for a dataset. The more points there are in the figure that fall below the diagonal line, the better the performance of LSCRDTW. Since the targeted evaluation dataset is very helpful to improve the feature quality, the proposed shapelet evaluation strategy can significantly improve the performance of our model. As shown in Figure 5, LSCRDTW outperforms LSCRDTW (whole) on almost all datasets. The accuracy rates of the above two models are listed in Table 3.Figure 5
Accuracy comparison betweenLSCRDTW combining instance selection for shapelet evaluation and LSCRDTW (whole) using the whole training set as the evaluation set on 20 datasets.Table 3
The accuracies ofLSCRDTW (whole), 5 fusion, and 1NN models.
DatasetLSCRDTWDTWLSCRERPERPLSCREDEDLSCRTWETWELSCRMSMMSMLSCRDTW (whole)ArrowHead0.7490.8000.7490.8000.7940.8000.7430.7940.7260.8060.629Beef0.7330.6670.6670.6670.7000.6670.7330.6000.7000.4670.733BeetleFly0.8000.6500.7000.7500.7500.7500.8000.7000.7000.6000.500CBF0.9910.9940.9930.9980.9840.8520.9890.9910.9970.9690.994ECGFiveDays0.8630.7970.9050.8060.8800.7970.8790.8290.9000.8910.533FaceFour0.9090.8980.8640.8640.9090.7840.8860.8520.8180.9430.807FacesUCR0.9240.9080.9260.9210.8110.7690.8540.9200.9260.9710.821GunPoint0.8800.9130.8930.9470.8870.9130.8730.9530.9270.9730.720ItalyPowerDemand0.9480.9550.9350.9550.9480.9550.9480.9480.9320.9440.881Lightning70.5890.7120.6160.7400.5480.5750.5210.7530.6580.7530.548MedicalImages0.6990.7470.6820.6760.6530.6840.6280.7110.6960.7410.507MiddlePhalanxOutlineAgeGroup0.5390.5190.5190.4810.5190.5190.5450.5190.4940.4940.422MoteStrain0.9030.8660.8580.8720.8590.8790.9080.7970.8810.8550.550Plane1.0001.0001.0001.0001.0000.9621.0001.0001.0001.0000.990ProximalPhalanxOutlineAgeGroup0.8100.7850.8150.7950.8000.7850.8050.8050.7270.7900.678SonyAIBORobotSurface10.7500.6960.8150.6890.7750.6960.7340.6810.7850.7300.704SonyAIBORobotSurface20.8430.8590.8640.8230.8770.8590.8460.8530.8850.8710.703ToeSegmentation10.8160.7500.8510.8330.6620.6800.8110.8200.7890.8160.632ToeSegmentation20.9000.9080.9150.9230.8230.8080.9380.7850.8920.7540.815Wine0.6110.6110.6110.6110.5740.6110.5930.5740.6480.5930.574Average0.8130.8020.8090.8070.7880.7670.8020.7940.8040.7980.687


## 4.2. Fusion Strategy Analysis

In this section, the effectiveness of the fusion strategy of global and local similarities is analyzed. Table3 presents the accuracies of 5 1NN models combined with different distance functions (DTW, ERP, ED, TWE, and MSM) and their corresponding five fusion models. The accuracies of the 1NN models are taken from the website [38].Figure6 shows a critical difference diagram studied in literature [39, 40] for the 10 classification models on 20 datasets. This diagram is used for the overall test of significance of average ranks and can group models without significant differences into cliques. From the figure, we find that there are no significant differences in the performance of the 10 models on the 20 datasets, but the rankings of all fusion models are better than those of the corresponding 1NN models. This result suggests that the fusion model can effectively improve the classification performance of the 1NN model to some extent. Since LSCRDTW ranks first, it will be used for further analysis in the following.Figure 6
The critical difference diagram for 5 fusion models and 5 corresponding 1NN models on 20 datasets.


## 4.3. Performance Analysis

In this section, the proposed model is compared with shapelet-based classifiers and 1NN classifiers combining with many commonly used distance functions and deep learning models.


### 4.3.1. Comparison with Shapelet-Based Classifiers

Since the classification process of the model proposed is similar to the decision tree, for the sake of fairness, all shapelet-based comparison models choose the decision tree to make predictions. Our model is first compared with SDT, fast shapelet tree (FS) [26], and C4.5 model [41] based on two respective shapelet transform algorithms. The symbol SSC4.5 denotes the C4.5 model based on the transform algorithm proposed by Yuan et al. [22], and STC4.5 represents the C4.5 model based on the other one proposed by Lines et al. [20]. The shapelet length ranges from 3 to the full length of time series and increases by 1 each time. All experimental results are listed in Table 4, and the accuracies of FS are obtained from the website [38]. In addition, the last line in Table 4 provides the average accuracy of each model over 20 datasets.Table 4
The accuracies of 5 shapelet-based models and 3 DTW variants on 20 datasets.
DatasetLSCRDTWSDTSTC4.5SSC4.5FSWDTWCIDDDDTWArrowHead0.7490.7540.6860.6860.5940.8170.8290.789Beef0.7330.5330.5000.6000.5670.7000.6330.667BeetleFly0.8000.7500.6000.7000.7000.7000.7500.650CBF0.9910.9390.8810.9790.9400.9970.9990.997ECGFiveDays0.8630.9940.9580.9900.9980.7960.7820.769FaceFour0.9090.7950.7500.7500.9090.8750.8750.830FacesUCR0.9240.6450.6620.6310.7060.9200.8950.904GunPoint0.8800.9470.8930.9130.9470.9800.9270.980ItalyPowerDemand0.9480.9580.9540.9420.9170.9500.9560.950Lightning70.5890.5070.6990.5750.6440.7670.6990.671MedicalImages0.6990.5160.4870.6380.6240.7370.7420.737MiddlePhalanxOutlineAgeGroup0.5390.4740.4480.8250.5450.5190.5130.539MoteStrain0.9030.8230.7600.8180.7770.8590.7960.833Plane1.0000.9330.9050.8381.0001.0001.0001.000ProximalPhalanxOutlineAgeGroup0.8100.7810.7710.8440.7800.8050.7900.800SonyAIBORobotSurface10.7500.7350.8770.8490.6860.7370.8150.742SonyAIBORobotSurface20.8430.6590.7570.7950.7900.8310.8770.892ToeSegmentation10.8160.8950.8990.8820.9560.7940.7370.807ToeSegmentation20.9000.8690.8690.8000.6920.8920.8770.746Wine0.6110.7960.7590.7780.7590.5740.6110.574Average0.8130.7650.7560.7920.7770.8130.8050.794As observed from Figure7, it is clear that although there is no significant difference between LSCRDTW and the other 4 shapelet-based models, the average rank of LSCRDTW is the best.Figure 7
The critical difference diagram forLSCRDTW and 4 shapelet-based models on 20 datasets.Figure8 presents the scatter plot of accuracy comparison between LSCRDTW and the 4 classical shapelet-based classifiers. Figure 8(a) shows that LSCRDTW is better than SDT (14 of 20) over the 20 datasets. From Table 4, we find that compared with that of SDT built on the entire training set, the accuracies of LSCRDTW on datasets MoteStrain, FacesUCR, SonyAIBORobotSurface2, etc., are significantly improved. In particular, on the dataset FacesUCR, the accuracy of LSCRDTW is 20% greater than that of SDT. In Figures 8(b)–8(d), it can be concluded that LSCRDTW is also better than STC4.5 (13 of 16), SSC4.5 (13 of 20), and FS (14 of 20). Hence, Figure 8 demonstrates that LSCRDTW outperforms the existing shapelet-based decision tree model on the 20 datasets.Figure 8
Accuracy comparison betweenLSCRDTW and 4 shapelet-based classifiers.
(a)(b)(c)(d)To compare the time complexity ofLSCRDTW with other shapelet-based models, the changes in running times of 6 shapelet-based models with increasing number of instances and instance length are shown in Figure 9, respectively. LSCRDTW(single) represents the training time of a single model LSCRDTW for a specific test instance, while LSCRDTW represents the model running on the entire test set. In the experiment, a binary-class dataset with uniform distribution is designed to run the analysis models, and the size of the training set is always the same as that of the test dataset. For the first experiment, the sizes of training and test datasets increase by 10 at a time. The length of all instances remains 100. For another, the instance length increases by 10 at a time. The sizes of training and test sets are 100.Figure 9
The running time trends of 6 shapelet-based models with increasing training dataset size and instance length, respectively.
(a)(b)(c)(d)From Figures9(a) and 9(b), we can determine that the training time of LSCRDTW (single) is not sensitive to the size of the training set and is polynomial with respect to the length of the time series. In particular, it is faster than the current fastest shapelet-based model FS. Further, as observed from Figures 9(c) and 9(d), with increasing training set size and instance length, the time consumption gap between SDT, STC4.5, and LSCRDTW widens, while the gap between LSCRDTW and SSC4.5 is not obvious.In conclusion,LSCRDTW is an accurate and rapid shapelet-based classification model, which is the basis of learning feature distribution and frequency information.


### 4.3.2. Comparison with Various 1NN Classifiers

In this section, except for the five distance functions listed above, we further compare our model with several DTW variants, including WDTW, complexity-invariant DTW (CID) [42], and derivativedistanceDTW (DDDTW) [43]. The accuracies for the above 1NN models are provided by the website [38] (see Table 4).Figure10 demonstrates that our model exhibits no significant difference from DTW and its variants, but the average ranks of LSCRDTW are the best. In Figure 11, it is clear that LSCRDTW is better than ED (16 of 20), TWE (14 of 20), ERP (13 of 20), MSM (12 of 20), DTW (11 of 20), WDTW (14 of 20), CID (11 of 20), and DDDTW (13 of 20).Figure 10
The critical difference diagram forLSCRDTW, DTW, and 3 DTW variants on 20 datasets.Figure 11
Accuracy comparison betweenLSCRDTW and 8 1NN classifiers based on different distance functions.
(a)(b)(c)(d)(e)(f)(g)(h)In summary,LSCRDTW is competitive with the 1NN model that depends on global similarity. The comparison results suggest that continuously narrowing the search space of class attributes based on local similarity is an effective way to make prediction.


### 4.3.3. Comparison with Deep Learning Models

Now, various deep learning models have been widely studied in the field of time series classification. Karim et al. [44] attempted to improve the univariate time series classification performance of fully convolutional neural networks (FCNs) by using the long short-term memory recurrent neural network (LSTM-RNNs) submodules and attention mechanism and proposed the excellent models LSTM-FCN and ALSTM-FCN. Furthermore, the authors applied the above two models to the multivariate time series classification problem [45] and studied the reasons why the two models have superior performance [46]. Fawaz et al. [47] have reviewed some deep learning models of time series classification. Here, our model is compared with LSTM-FCN and 9 deep learning models (ResNet, FCN, Encoder, MLP, Time-CNN, TWIESN, MCDCNN, MCNN, and t-LeNet) analyzed in the literature [47]. All the experimental results were obtained from the corresponding literature (see Table 5).Table 5
The classification accuracies of 10 deep learning models on 20 datasets.
DatasetLSTM-FCNMLPFCNResNetEncoderMCNNt-LeNetMCDCNNTime-CNNTWIESNArrowHead0.9090.7780.8430.8450.8040.3390.3030.6850.7230.659Beef0.9000.7200.6970.7530.6430.2000.2000.5630.7630.537BeetleFly0.9500.8700.8600.8500.7450.5000.5000.5800.8900.730CBF0.9980.8720.9940.9950.9470.3320.3320.8200.9570.890ECGFiveDays0.9920.9700.9870.9750.9820.4990.4970.7620.8820.698FaceFour0.9430.8400.9280.9550.8150.2680.2950.7120.9060.855FacesUCR0.9290.8330.9460.9550.8740.1530.1430.7560.8690.644GunPoint1.0000.9271.0000.9910.9360.5130.4930.8670.9320.961ItalyPowerDemand0.9630.9540.9610.9630.9650.5000.4990.9550.9550.880Lightning70.8360.6300.8270.8450.6250.3100.2600.5340.6510.664MedicalImages0.8010.7210.7790.7700.7340.5140.5140.6400.6760.649MiddlePhalanxOutlineAgeGroup0.8130.5310.5530.5690.5790.1880.5710.5850.5660.581MoteStrain0.9390.8580.9370.9280.8400.5080.5390.7650.8820.785Plane1.0000.9781.0001.0000.9760.1300.1340.9650.9651.000ProximalPhalanxOutlineAgeGroup0.8930.8560.8310.8530.8440.4880.4880.8380.8280.844SonyAIBORobotSurface10.9820.6720.9600.9580.7430.4430.4290.6530.6870.638SonyAIBORobotSurface20.9780.8340.9790.9780.8390.5940.6170.7740.8410.697ToeSegmentation10.9830.5830.9610.9630.6590.5050.5260.4900.5950.865ToeSegmentation20.9310.7450.8800.9060.7950.6320.8150.4430.7380.842Wine0.8700.5650.5870.7440.5000.5000.5000.5000.5170.759Average0.9300.7870.8760.8900.7920.4060.4330.6940.7910.759Figure12 shows that, except for ResNet and FCN, LSTM-FCN is significantly better than other models, and that our model is significantly better than MCNN and t-LeNet. Among the 10 deep learning models, the average rank of our model is better than 7 of them. In Figure 13, it can be seen that LSCRDTW is better than Encoder (12 of 20), Time-CNN (12 of 20), MLP (12 of 20), TWIESN (13 of 20), MCDCNN (17 of 20), t-LeNet (19 of 20), and MCNN (20 of 20).Figure 12
The critical difference diagram forLSCRDTW and 10 deep learning models on 20 datasets.Figure 13
Accuracy comparison betweenLSCRDTW and 10 deep learning models.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Generally, to improve performance, deep learning model tuning requires an enormous computational cost. To pursue the optimal accuracy rate, Fawaz et al. [48] even proposed the neural network ensemble model with 60 deep learning models, but it is still not better than the traditional ensemble model HIVE-COTE [49]. It is unfair to compare our model with the deep learning model based on accuracy alone. In addition to improving accuracy, we believe that the model interpretability and data comprehensibility require more attention. However, the existing feature extraction methods for time series usually cannot simultaneously obtain the feature distribution and frequency information. For the deep learning model, it is difficult to train a targeted model for the specific instance on a small dataset. Accordingly, in our work, a highly interpretable classification model based on the lazy learning strategy is built for each target instance, which can be applied to gain insight into the local feature distribution and frequency information. The following is a detailed introduction.


## 4.3.1. Comparison with Shapelet-Based Classifiers

Since the classification process of the model proposed is similar to the decision tree, for the sake of fairness, all shapelet-based comparison models choose the decision tree to make predictions. Our model is first compared with SDT, fast shapelet tree (FS) [26], and C4.5 model [41] based on two respective shapelet transform algorithms. The symbol SSC4.5 denotes the C4.5 model based on the transform algorithm proposed by Yuan et al. [22], and STC4.5 represents the C4.5 model based on the other one proposed by Lines et al. [20]. The shapelet length ranges from 3 to the full length of time series and increases by 1 each time. All experimental results are listed in Table 4, and the accuracies of FS are obtained from the website [38]. In addition, the last line in Table 4 provides the average accuracy of each model over 20 datasets.Table 4
The accuracies of 5 shapelet-based models and 3 DTW variants on 20 datasets.
DatasetLSCRDTWSDTSTC4.5SSC4.5FSWDTWCIDDDDTWArrowHead0.7490.7540.6860.6860.5940.8170.8290.789Beef0.7330.5330.5000.6000.5670.7000.6330.667BeetleFly0.8000.7500.6000.7000.7000.7000.7500.650CBF0.9910.9390.8810.9790.9400.9970.9990.997ECGFiveDays0.8630.9940.9580.9900.9980.7960.7820.769FaceFour0.9090.7950.7500.7500.9090.8750.8750.830FacesUCR0.9240.6450.6620.6310.7060.9200.8950.904GunPoint0.8800.9470.8930.9130.9470.9800.9270.980ItalyPowerDemand0.9480.9580.9540.9420.9170.9500.9560.950Lightning70.5890.5070.6990.5750.6440.7670.6990.671MedicalImages0.6990.5160.4870.6380.6240.7370.7420.737MiddlePhalanxOutlineAgeGroup0.5390.4740.4480.8250.5450.5190.5130.539MoteStrain0.9030.8230.7600.8180.7770.8590.7960.833Plane1.0000.9330.9050.8381.0001.0001.0001.000ProximalPhalanxOutlineAgeGroup0.8100.7810.7710.8440.7800.8050.7900.800SonyAIBORobotSurface10.7500.7350.8770.8490.6860.7370.8150.742SonyAIBORobotSurface20.8430.6590.7570.7950.7900.8310.8770.892ToeSegmentation10.8160.8950.8990.8820.9560.7940.7370.807ToeSegmentation20.9000.8690.8690.8000.6920.8920.8770.746Wine0.6110.7960.7590.7780.7590.5740.6110.574Average0.8130.7650.7560.7920.7770.8130.8050.794As observed from Figure7, it is clear that although there is no significant difference between LSCRDTW and the other 4 shapelet-based models, the average rank of LSCRDTW is the best.Figure 7
The critical difference diagram forLSCRDTW and 4 shapelet-based models on 20 datasets.Figure8 presents the scatter plot of accuracy comparison between LSCRDTW and the 4 classical shapelet-based classifiers. Figure 8(a) shows that LSCRDTW is better than SDT (14 of 20) over the 20 datasets. From Table 4, we find that compared with that of SDT built on the entire training set, the accuracies of LSCRDTW on datasets MoteStrain, FacesUCR, SonyAIBORobotSurface2, etc., are significantly improved. In particular, on the dataset FacesUCR, the accuracy of LSCRDTW is 20% greater than that of SDT. In Figures 8(b)–8(d), it can be concluded that LSCRDTW is also better than STC4.5 (13 of 16), SSC4.5 (13 of 20), and FS (14 of 20). Hence, Figure 8 demonstrates that LSCRDTW outperforms the existing shapelet-based decision tree model on the 20 datasets.Figure 8
Accuracy comparison betweenLSCRDTW and 4 shapelet-based classifiers.
(a)(b)(c)(d)To compare the time complexity ofLSCRDTW with other shapelet-based models, the changes in running times of 6 shapelet-based models with increasing number of instances and instance length are shown in Figure 9, respectively. LSCRDTW(single) represents the training time of a single model LSCRDTW for a specific test instance, while LSCRDTW represents the model running on the entire test set. In the experiment, a binary-class dataset with uniform distribution is designed to run the analysis models, and the size of the training set is always the same as that of the test dataset. For the first experiment, the sizes of training and test datasets increase by 10 at a time. The length of all instances remains 100. For another, the instance length increases by 10 at a time. The sizes of training and test sets are 100.Figure 9
The running time trends of 6 shapelet-based models with increasing training dataset size and instance length, respectively.
(a)(b)(c)(d)From Figures9(a) and 9(b), we can determine that the training time of LSCRDTW (single) is not sensitive to the size of the training set and is polynomial with respect to the length of the time series. In particular, it is faster than the current fastest shapelet-based model FS. Further, as observed from Figures 9(c) and 9(d), with increasing training set size and instance length, the time consumption gap between SDT, STC4.5, and LSCRDTW widens, while the gap between LSCRDTW and SSC4.5 is not obvious.In conclusion,LSCRDTW is an accurate and rapid shapelet-based classification model, which is the basis of learning feature distribution and frequency information.


## 4.3.2. Comparison with Various 1NN Classifiers

In this section, except for the five distance functions listed above, we further compare our model with several DTW variants, including WDTW, complexity-invariant DTW (CID) [42], and derivativedistanceDTW (DDDTW) [43]. The accuracies for the above 1NN models are provided by the website [38] (see Table 4).Figure10 demonstrates that our model exhibits no significant difference from DTW and its variants, but the average ranks of LSCRDTW are the best. In Figure 11, it is clear that LSCRDTW is better than ED (16 of 20), TWE (14 of 20), ERP (13 of 20), MSM (12 of 20), DTW (11 of 20), WDTW (14 of 20), CID (11 of 20), and DDDTW (13 of 20).Figure 10
The critical difference diagram forLSCRDTW, DTW, and 3 DTW variants on 20 datasets.Figure 11
Accuracy comparison betweenLSCRDTW and 8 1NN classifiers based on different distance functions.
(a)(b)(c)(d)(e)(f)(g)(h)In summary,LSCRDTW is competitive with the 1NN model that depends on global similarity. The comparison results suggest that continuously narrowing the search space of class attributes based on local similarity is an effective way to make prediction.


## 4.3.3. Comparison with Deep Learning Models

Now, various deep learning models have been widely studied in the field of time series classification. Karim et al. [44] attempted to improve the univariate time series classification performance of fully convolutional neural networks (FCNs) by using the long short-term memory recurrent neural network (LSTM-RNNs) submodules and attention mechanism and proposed the excellent models LSTM-FCN and ALSTM-FCN. Furthermore, the authors applied the above two models to the multivariate time series classification problem [45] and studied the reasons why the two models have superior performance [46]. Fawaz et al. [47] have reviewed some deep learning models of time series classification. Here, our model is compared with LSTM-FCN and 9 deep learning models (ResNet, FCN, Encoder, MLP, Time-CNN, TWIESN, MCDCNN, MCNN, and t-LeNet) analyzed in the literature [47]. All the experimental results were obtained from the corresponding literature (see Table 5).Table 5
The classification accuracies of 10 deep learning models on 20 datasets.
DatasetLSTM-FCNMLPFCNResNetEncoderMCNNt-LeNetMCDCNNTime-CNNTWIESNArrowHead0.9090.7780.8430.8450.8040.3390.3030.6850.7230.659Beef0.9000.7200.6970.7530.6430.2000.2000.5630.7630.537BeetleFly0.9500.8700.8600.8500.7450.5000.5000.5800.8900.730CBF0.9980.8720.9940.9950.9470.3320.3320.8200.9570.890ECGFiveDays0.9920.9700.9870.9750.9820.4990.4970.7620.8820.698FaceFour0.9430.8400.9280.9550.8150.2680.2950.7120.9060.855FacesUCR0.9290.8330.9460.9550.8740.1530.1430.7560.8690.644GunPoint1.0000.9271.0000.9910.9360.5130.4930.8670.9320.961ItalyPowerDemand0.9630.9540.9610.9630.9650.5000.4990.9550.9550.880Lightning70.8360.6300.8270.8450.6250.3100.2600.5340.6510.664MedicalImages0.8010.7210.7790.7700.7340.5140.5140.6400.6760.649MiddlePhalanxOutlineAgeGroup0.8130.5310.5530.5690.5790.1880.5710.5850.5660.581MoteStrain0.9390.8580.9370.9280.8400.5080.5390.7650.8820.785Plane1.0000.9781.0001.0000.9760.1300.1340.9650.9651.000ProximalPhalanxOutlineAgeGroup0.8930.8560.8310.8530.8440.4880.4880.8380.8280.844SonyAIBORobotSurface10.9820.6720.9600.9580.7430.4430.4290.6530.6870.638SonyAIBORobotSurface20.9780.8340.9790.9780.8390.5940.6170.7740.8410.697ToeSegmentation10.9830.5830.9610.9630.6590.5050.5260.4900.5950.865ToeSegmentation20.9310.7450.8800.9060.7950.6320.8150.4430.7380.842Wine0.8700.5650.5870.7440.5000.5000.5000.5000.5170.759Average0.9300.7870.8760.8900.7920.4060.4330.6940.7910.759Figure12 shows that, except for ResNet and FCN, LSTM-FCN is significantly better than other models, and that our model is significantly better than MCNN and t-LeNet. Among the 10 deep learning models, the average rank of our model is better than 7 of them. In Figure 13, it can be seen that LSCRDTW is better than Encoder (12 of 20), Time-CNN (12 of 20), MLP (12 of 20), TWIESN (13 of 20), MCDCNN (17 of 20), t-LeNet (19 of 20), and MCNN (20 of 20).Figure 12
The critical difference diagram forLSCRDTW and 10 deep learning models on 20 datasets.Figure 13
Accuracy comparison betweenLSCRDTW and 10 deep learning models.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)Generally, to improve performance, deep learning model tuning requires an enormous computational cost. To pursue the optimal accuracy rate, Fawaz et al. [48] even proposed the neural network ensemble model with 60 deep learning models, but it is still not better than the traditional ensemble model HIVE-COTE [49]. It is unfair to compare our model with the deep learning model based on accuracy alone. In addition to improving accuracy, we believe that the model interpretability and data comprehensibility require more attention. However, the existing feature extraction methods for time series usually cannot simultaneously obtain the feature distribution and frequency information. For the deep learning model, it is difficult to train a targeted model for the specific instance on a small dataset. Accordingly, in our work, a highly interpretable classification model based on the lazy learning strategy is built for each target instance, which can be applied to gain insight into the local feature distribution and frequency information. The following is a detailed introduction.


## 4.4. Interpretability

To demonstrate the stronger interpretability of our model, this section separately analysesLSCRDTW on a binary-class dataset, MoteStrain, and the CBF multiclass dataset.


### 4.4.1. MoteStrain Dataset

Sensing data in MoteStrain are originally collected to detect potential variables online in the sensor network [50]. The classification task on this dataset is to distinguish whether the sensor is used for humidity measurement or temperature measurement. The classification performance of our model is significantly better than that of the model used for comparison and is close to the current best classification result provided by Bagnall et al. [38] on this dataset.To further investigate the proposed model, the shapelet decision tree built by SDT is shown in Figure14, where the symbol S0,04 represents the shapelet extracted from the fourth training instance Train4 in the root node of the shapelet decision tree. As seen from Figure 14, there is only one shapelet in the decision tree, where d denotes the distance between the test instance and the shapelet and δ represents the split threshold of the shapelet. Based on the shapelet decision tree, when the distance between the test instance and the shapelet corresponding to the root node is not greater than the split threshold, the class prediction value of the test instance is Class1. Otherwise, it is Class2.Figure 14
The shapelet decision tree and the shapelets found by SDT.Figure15 shows six instances and their shapelets extracted through LSCRDTW. Our model can correctly predict the class properties of these six instances, while SDT fails. Meanwhile, it is obvious that there are not only significant differences between instances of different types but also intraclass variations among similar instances. For example, the differences among the three instances with the same class label, Test11, Test129, and Test189, are noticeable, while there are no obvious common features. However, in the shapelet decision tree built by SDT, only a shapelet is found, which is not sufficient to distinguish the two classes. In contrast to the illustration of the shapelet given in Figure 14, it is not difficult to find that the optimal shapelet obtained in the shapelet decision tree is not the most discriminatory feature for the test instances. This result verifies that the shapelets extracted from the entire dataset are the most discriminatory for each training instance in the average sense; this is also the reason for the poor performance of SDT on the MoteStrain dataset.Figure 15
Six test instances from the MoteStrain dataset and their shapelets found byLSCRDTW. The three instances (a–c) are from Class1, and the other three (d–f) are from Class2. (a) Test11, (b) Test129, (c) Test189, (d) Test3, (e) Test41, and (f) Test55.
(a)(b)(c)(d)(e)(f)Since the characteristics of each test instance have been considered in our model, in light of this situation, we can achieve better classification results. In addition, based on the shapelet obtained byLSCRDTW, the prediction process of each instance can be explained. For example, as shown in Figure 15, the reason why the 11th test instance belongs to Class1 is that the local feature S011 lies in its initial stage, while the local feature S041 of the 41st test instance in the middle part determines its predicted class label.Figure16 displays the scores of shapelets coverage on the MoteStrain training and test datasets. It is obvious that the high score intervals on training and test sets are very similar. Since there are only 20 instances in the training set, the scores of shapelet coverage (as shown in Figure 16(a)) may not accurately reflect the local characteristics. However, we propose to directly evaluate the local characteristics of test cases, which can help us utilize large amounts of test data. In Figure 16(b), it can be seen that local features with different coverage frequencies of various classes have been detected from the test dataset, which cannot be captured by other shapelet-based models. For example, the intervals [9, 16] (low frequency), [44, 54] (medium frequency), and [59, 76] (high frequency) (as shown in Figure 16(b)) are three significant discriminative intervals of Class2, while the interval [21, 50] (high frequency) is the most discriminative part of Class1. Based on the proposed model, using more instances with accurate labels results in obtaining more accurate local feature information. The statistical information helps us acquire more comprehensive local characteristic information of time series data, such as feature distribution and frequency.Figure 16
The shapelet coverage scores obtained on training and test datasets of MoteStrain: (a) training dataset and (b) test dataset.
(a)(b)


### 4.4.2. CBF Dataset

This section studies the multiclass dataset CBF, which contains three types: Cylinder, Bell, and Funnel. Figure17 shows the coverage scores of the CBF test dataset. It can be determined that the interval [31, 75] covers the most discriminative intervals for all three classes. In addition, unlike Cylinder and Funnel, the local interval [0, 15] with relatively low coverage frequency is discriminative for Bell.Figure 17
The shapelet coverage scores obtained on the CBF test dataset.Next, four specific test instances are presented. As shown in Figure18, for the multiclass dataset, our model can not only detect high-frequency shapelets (as shown in Figures 18(a)–18(c)) but also effectively capture low-frequency shapelets (as shown in Figure 18(d)). The proposed model LSCRdist is helpful to make a targeted analysis of each category of data and each test instance.Figure 18
Four test instances from the CBF dataset and their shapelets found byLSCRDTW. The first two instances (a-b) are from Cylinder and Funnel, while the last two (c-d) are from Bell. (a) Test23, (b) Test5, (c) Test21, and (d) Test0.
(a)(b)(c)(d)


## 4.4.1. MoteStrain Dataset

Sensing data in MoteStrain are originally collected to detect potential variables online in the sensor network [50]. The classification task on this dataset is to distinguish whether the sensor is used for humidity measurement or temperature measurement. The classification performance of our model is significantly better than that of the model used for comparison and is close to the current best classification result provided by Bagnall et al. [38] on this dataset.To further investigate the proposed model, the shapelet decision tree built by SDT is shown in Figure14, where the symbol S0,04 represents the shapelet extracted from the fourth training instance Train4 in the root node of the shapelet decision tree. As seen from Figure 14, there is only one shapelet in the decision tree, where d denotes the distance between the test instance and the shapelet and δ represents the split threshold of the shapelet. Based on the shapelet decision tree, when the distance between the test instance and the shapelet corresponding to the root node is not greater than the split threshold, the class prediction value of the test instance is Class1. Otherwise, it is Class2.Figure 14
The shapelet decision tree and the shapelets found by SDT.Figure15 shows six instances and their shapelets extracted through LSCRDTW. Our model can correctly predict the class properties of these six instances, while SDT fails. Meanwhile, it is obvious that there are not only significant differences between instances of different types but also intraclass variations among similar instances. For example, the differences among the three instances with the same class label, Test11, Test129, and Test189, are noticeable, while there are no obvious common features. However, in the shapelet decision tree built by SDT, only a shapelet is found, which is not sufficient to distinguish the two classes. In contrast to the illustration of the shapelet given in Figure 14, it is not difficult to find that the optimal shapelet obtained in the shapelet decision tree is not the most discriminatory feature for the test instances. This result verifies that the shapelets extracted from the entire dataset are the most discriminatory for each training instance in the average sense; this is also the reason for the poor performance of SDT on the MoteStrain dataset.Figure 15
Six test instances from the MoteStrain dataset and their shapelets found byLSCRDTW. The three instances (a–c) are from Class1, and the other three (d–f) are from Class2. (a) Test11, (b) Test129, (c) Test189, (d) Test3, (e) Test41, and (f) Test55.
(a)(b)(c)(d)(e)(f)Since the characteristics of each test instance have been considered in our model, in light of this situation, we can achieve better classification results. In addition, based on the shapelet obtained byLSCRDTW, the prediction process of each instance can be explained. For example, as shown in Figure 15, the reason why the 11th test instance belongs to Class1 is that the local feature S011 lies in its initial stage, while the local feature S041 of the 41st test instance in the middle part determines its predicted class label.Figure16 displays the scores of shapelets coverage on the MoteStrain training and test datasets. It is obvious that the high score intervals on training and test sets are very similar. Since there are only 20 instances in the training set, the scores of shapelet coverage (as shown in Figure 16(a)) may not accurately reflect the local characteristics. However, we propose to directly evaluate the local characteristics of test cases, which can help us utilize large amounts of test data. In Figure 16(b), it can be seen that local features with different coverage frequencies of various classes have been detected from the test dataset, which cannot be captured by other shapelet-based models. For example, the intervals [9, 16] (low frequency), [44, 54] (medium frequency), and [59, 76] (high frequency) (as shown in Figure 16(b)) are three significant discriminative intervals of Class2, while the interval [21, 50] (high frequency) is the most discriminative part of Class1. Based on the proposed model, using more instances with accurate labels results in obtaining more accurate local feature information. The statistical information helps us acquire more comprehensive local characteristic information of time series data, such as feature distribution and frequency.Figure 16
The shapelet coverage scores obtained on training and test datasets of MoteStrain: (a) training dataset and (b) test dataset.
(a)(b)


## 4.4.2. CBF Dataset

This section studies the multiclass dataset CBF, which contains three types: Cylinder, Bell, and Funnel. Figure17 shows the coverage scores of the CBF test dataset. It can be determined that the interval [31, 75] covers the most discriminative intervals for all three classes. In addition, unlike Cylinder and Funnel, the local interval [0, 15] with relatively low coverage frequency is discriminative for Bell.Figure 17
The shapelet coverage scores obtained on the CBF test dataset.Next, four specific test instances are presented. As shown in Figure18, for the multiclass dataset, our model can not only detect high-frequency shapelets (as shown in Figures 18(a)–18(c)) but also effectively capture low-frequency shapelets (as shown in Figure 18(d)). The proposed model LSCRdist is helpful to make a targeted analysis of each category of data and each test instance.Figure 18
Four test instances from the CBF dataset and their shapelets found byLSCRDTW. The first two instances (a-b) are from Cylinder and Funnel, while the last two (c-d) are from Bell. (a) Test23, (b) Test5, (c) Test21, and (d) Test0.
(a)(b)(c)(d)


## 5. Conclusions

Aiming at the problems of global shapelet-based models built on the whole training set, a data-driven model fusing global and local similarities is proposed. In the model, the shapelet discriminability is evaluated through a specific subdataset. A smaller evaluation dataset reduces the computational time and improves the quality of shapelets. Moreover, target learning for each instance helps us understand the prediction process clearly. For example, the shapelets extracted by our LSCR model can be directly used to explain what characteristics determine the class value of the test instance. Furthermore, the proposed shapelet coverage score is applied to accurately analyze the local feature information of each class, which provides comprehensive insight into data characteristics. In the future, the application of the model in specific fields will be further studied, including ECG detection and image contour feature discovery.



---

*Source: 1978310-2020-10-26.xml*