Shapelet based classification is a promising time series classification approach, which usually results in accurate predictions that are competitive with sophisticated and more complex classifiers, while it provides interpretability for the predictions. An important step in classification using shapelets is to select candidate subsequences based on some evaluation criteria. We adapt the Silhouette score, used originally in the context of clustering, in order to rank and select shapelet candidates for classification. We demonstrate empirically that our approach is faster compared to other methods in the literature, while being competitive in terms of the accuracy of classification. In particular, when the number of shapelets used for classification
is small, our approach is superior to all other evaluation methods.
based on diferent techniques such as Dictionaries [
The main drawback of information gain is the running
In 2009, a technique called Shapelets have been intro- time, since it needs to evaluate many splitting points other time series from the same class. This has many ben- faster to compute compared to the information gain.
Time series classification (TSC) is a very active research area, where the aim is to assign a class label from a finite set to a high dimensional data point. The main diference with classic tabular data classification is that the attributes of the time series are ordered and the ordering of the points is crucial, because it defines the local behaviors of the time series. Diferent models have been developed duced by Ye and Keogh [6]. This technique is based on ifnding local patterns where similar patterns appear in efits since it deals with local patterns of the time series rather than the global features of the time series. Another benefit is interpretability. Once a discriminating subsequence is found, it can be traced back to the original time series. This intuitive and simple approach turned out to be very efective in many time series mining tasks, and in particular for classification. However, it came with a computational challenge: a naive approach to find a shapelet needs to consider ( 2 ) candidates, resulting in an (
3 2) time complexity, where and are the length and number of time series, respectively.
To improve the running time, most algorithms use LGOBE DOLAP 2024: 26th International Workshop on Design, Optimization,
0000-0002-0339-5322 (A. Charane); 0000-0003-2783-0218 (M. Ceccarello); 0000-0002-7128-507X (J. Gamper) CEUR
CEUR some function to evaluate shapelets and to prune computations based on this evaluation. For instance, in [6] the authors evaluate the quality of shapelets using the information gain, which is based on the Shannon entropy. If the upper bound of the gain is less than the best shapelet found so far, the computation stops and the next candidate is considered. The authors also use early abandoning while computing the distances. Even though the time complexity remains the same, the pruning improves and compute the gain for each. Hills et al. [7] introduce diferent measures for evaluating shapelets, which are
To address the above-mentioned issues, we introduce a new evaluation method for shapelets based on the Silhouette score [8], which is both fast and results in higher accuracy. We adapt the Silhouette score, which is originally used to evaluate the quality of clusters and the iftting of each object in a cluster, to the evaluation of shapelets, where we consider the clusters as the distances between the shapelets with time series from the same and from diferent classes. We select only those shapelets that contribute positively according to the Silhouette score. Our proposed evaluation method is faster and more accurate than the existing approaches, especially when the number of shapelets used for the classification is small.
The rest of this document is organized as follows. In Section 2 we review related works. Section 3 introduces some notations and background necessary for the rest of the paper. Section 4 introduces our approach and compares it to existing methods. In Section 5 we experimentally compare our approach with others using datasets from the UCR archive [9]. Finally, in Section 6 CEUR
ceur-ws.org
Geurts [10] demonstrated that many time series classiifcation problems can be solved by using local patterns, and introduced a technique to find and combine local patterns in order to classify time series. Subsequently, Ye and Keogh [6] introduced shapelets, which is a time series primitive that solves many time series data mining tasks, including time series classification. Furthermore, this technique made it possible for domain experts to interpret the outcome of the classification. A shapelet is a subsequence of a time series that maximally predicts a target variable. For the computation of shapelets, Ye and Keogh used exhaustive search evaluating all possible subsequences. While being accurate, this approach is computationally exhausting. Therefore, the authors introduced early abandoning while the distances between subsequences are computed. They also adopted the information gain based on entropy as a criterion to stop the computation of subsequence distances, once it is clear that a subsequence cannot achieve a higher ranking compared to other subsequences already evaluated.
In the following, many techniques were proposed to reduce the computation time. For instance, Mueen et al. [11] cached in memory some statistics and reused them to speed up the computation.
Rakthanmanon and Keogh [12] used symbolic aggregate approximation (SAX) to first reduce the dimensionality of the time series. Then, the data is hashed, and the collision history is used for the identification of shapelets. Ji et al. [ 13] reduced the computation by first selecting a small subset tree, the accuracy of the classification increased. Our contribution is along the same lines as Hills et al., where we use the Silhouette score [8] to assess the quality of shapelets.
In this section we provide notations and some background necessary for the rest of the paper.
A time series is an ordered list of real-valued variables = 1, … , . A subsequence of of length , denoted by , , is a sequence of consecutive values starting from , i.e., , +1 , … , +−1 . To compute the distance between two subsequences and of length , we use the z-normalized Euclidean distance , defined as (, ) = ∑ ( √ =1
− ̄ − ̄ 2 −
) , of , respectively. where ̄ and are the mean and the standard deviation
The above definition of distance requires that the two sequences have the same size. However, in our case we need to compare a subsequence of length with a time series of length with > . Following the Shapelet literature, we tackle this problem by computing the distance to all − + 1 subsequences of length of the time of representative time series. Then, instead of consid- series. Then, the minimal distance is considered to be the ering all possible subsequences, only subsequences that distance between the shapelet and the time series. More contain local farthest deviation points are considered, formally, given a sequence of length and a time series the information gain to assess the quality of a candidate, representing a class ∈ based on the time series representation error. These two optimizations improved the computation by three orders of magnitude. Another widely used approach by Renard et al. [14] is to randomly select shapelets from the set of possible subsequences.
Despite the many works on time series classification using shapelets, surprisingly few works have focused on the evaluation metrics for the quality of the shapelets. In the paper introducing shapelets, Ye and Keogh [6] used and the gain was used as a splitting criterion for a decision tree classifier. Later on, Hills et al. [ 7] introduced F-statistic, which originally was proposed for the analysis of variance, Kruskal-Wallis and Moods medians, in order to evaluate and rank the shapelet candidates. In of length , the distance between and according to the normalized Euclidean distance is (, ) =
min ∈[1,…,−+1] (,
, ). extracted from a time series in
.
For the rest of the paper, we assume that we have a dataset
with time series, and each time series is assigned to a class from a set of classes. We denote the set of time series in a class ∈
as , and a shapelet as , i.e., a subsequence
In this paper, we use the terms subsequence and shapelet the same work, they also introduced a technique to trans- interchangeably, since a shapelet is a subsequence that form datasets from the time domain to a feature domain spanned by the distances between the shapelets and the represents a class of time series and discriminates other classes. We would like to stress that the original definitime series. The authors showed that (a) the transfor- tion of a shapelet introduced by Ye and Keogh [7] is not mation did not afect the classification accuracy and (b) that when using diferent classifiers instead of a decision just a subsequence, but a subsequence with its optimal split point according to the information gain, which we describe in subsection 3.3. However, most papers about shapelets that were published after [ 15, 14, 7] do not use the same original definition. Instead, a shapelet is simply a subsequence regardless of its information gain. In fact, our contribution is an alternative approach to the information gain in the context of selecting shapelets for classification.
Another important aspect we would like to highlight is that in our work, similar to the original, a shapelet is a subsequence that is extracted from the set of time series. However, this is not necessarily the case. For instance, Grabocka et al. [16] introduced an algorithm that formalizes an optimization objective function to learn the shapelets instead of extracting them from the data.
The result are shapelets that indeed represent a class and discriminate others, while they do not actually exist in the dataset.
Classifying time series using shapelets is a 3-step process:
2. evaluation of candidates, and 3. transformation of data using shapelets.
dataset. The distances are then sorted, and − 1 thresholds are considered, where a threshold (also called split point) is the average between two consecutive distances.
For a threshold , the data is then separated into two sets < and >, where < is the set of time series which have a distance to that is smaller than . The information gain is computed as
( , ) = − , where • is the gain before a split: = ( • is the gain after a split:
), = | <| ( <) + | >| ( >) | | | | , • | | is the cardinality of a set , and • is the Shannon binary entropy, which can be computed for a Bernoulli random variable , where IP( = 1) = , as: ( ) = − log() − (1 − )
log().
One drawback of the information gain is the computation time, since distances between time series and Extraction of Shapelet Candidates. There exists shapelets have to be sorted in order to find the optimal many approaches in the literature to extract shapelets splitting point. For that, Hills et al. [7] introduce other candidates. The first approach was brute force, i.e., slide evaluation methods that are much faster to compute, and a window of a fixed size over the time series with dif- the accuracy is not significantly diferent. Two of the ferent window lengths and consider each subsequence methods were non-parametric statistical tests, namely as a candidate [6, 17]. This method results in a set of Kruskal-Wallis and Moods medians, to test if samples candidates in the order of ( 2). A faster approach originated from the same distribution or not based on introduced later reduced the number of candidates by their medians. The third method introduced was the randomly selecting subsequences from diferent positions F-statistic for variance analysis. Compared to the two with diferent lengths [ 14, 15]. A more recent method non-parametric tests and the information gain, the Fintroduced in [13] reduces the space of candidates by first statistic was the fastest in terms of running time and the selecting some representative time series, which reduces time to find the best shapelet. It had also the best classithe number of time series to be considered, and second, fication accuracy. At the end, the authors recommended by ignoring non-interesting subsequences. Instead, it that the F-statistic should be the default when evaluating generates shapelet candidates by finding the important the quality of shapelets. For the rest of this paper, we data points (IDP) in a time series, which is the point will compare our evaluation approach, Silhouettes, with with the largest fitting error when the time series is rep- both the F-statistic and the information gain. resented with a linear representation, and keep finding IDPs recursively. The IDPs found are then used to extract shapelets.
Transform Data Using Shapelets. The shapelets selected from the large pool of candidates are of diferent lengths, and standard classifiers, such as K-Nearest NeighEvaluation of Candidates. The extraction step usu- bor, logistic regression and neural networks cannot be ally results in a large set of candidates. Then, one has directly applied to these subsequences of diferent size. to evaluate these candidates in order to choose a smaller In the original paper [6], the shapelets were included in subset to be used as a primitive for classification. The first a decision tree by using the shapelet’s information comshapelet evaluation method is the information gain [6]. puted as a splitting criterion at each node, which resulted To evaluate a candidate , the algorithm first computes in the coupling of shapelet evaluation and scoring. the distance between and all the time series in the In the shapelet transform paper [7], the authors introduced a data transformation, and show empirically that dissociating shapelet discovery from classification does we select the top ranked ones. Formally, the Silhouette not reduce the accuracy. When the data is transformed, score for a candidate shapelet is higher. transform of the data is it becomes possible to use any out of the box standard classifiers. Furthermore, the authors have shown that when the classification is done with a diferent model than a decision tree, the classification accuracy becomes
Formally, after the shapelets are selected, the shapelet = ⎛ ⎜ ⎜ ( ( 1, 1) 2, 1) ⋯ ( ( 1, 2) 2, 2) ⋯ ⎝( , 1) ( , 2) ⋯ ⋯ ⋯ ⋯ ( ( 1, ) ⎞ 2, ) ⎟ ⋯
⎟ ( , )⎠ where represents the ’th time series in the dataset and is the ’th selected shapelet. The matrix and the labels of the time series are then fed to a standard classifier for training. In order to classify an unlabeled time series , the time series is first transformed: tion is done using the trained classifier. [( , 1), ( , 2), ⋯ , ( ,
)] and then the classifica
This section describes the idea behind our approach and compares how Silhouettes difers from information gain and F-statistic.
The goal of shapelet evaluation is to select a good subset from the set of shapelet candidates, which can then be used for classification and achieves a high accuracy. Each is the average distance between the shapelet and time series from the same class, the average distance between the shapelet and time series from diferent classes.
Notice that the score of the Silhouette is based only on whether a time series is in the same class of the shapelet or not. In the original work of Rousseeuw [8], the Silhouette works with many clusters, and is the distance to the closest cluster that the object is not assigned to. Our decision is following the recommendation from Bostrom and Bagnall [17] where they introduce the binary shapelet. The authors show that, when a shapelet is selected to represent one class against all other classes instead of how well it splits all the classes, the classification results in higher accuracy for multiple-class datasets; additionally, it allows speeding up the computations as it facilitates frequently early abandoning.
In this subsection we would like to highlight the major diferences between our approach and others.
Information Gain.
The first diference is that Silhou( ) =
− max(, )
, where • = ∈
and • = ∉ ∑ ( | ∖ ∑ (
, ) | | , ) | approach assigns a real number to the candidates, termed ettes do not need to sort the distances and find the best evaluation score or rank of the shapelet, where usually a splitting. The overhead of sorting the distances to all higher score means higher accuracy. Then, the shapelets time series for every shapelet makes the information with the highest rank are selected. Our method exploits gain approach slower [7]. The second and most importhe idea of Silhouettes introduced by Rousseeuw [8] and tant diference is that the gain assigned does not consider originally used to evaluate the outcome of clustering al- if the split diferentiates between a specific class and the gorithms by comparing the within and between cluster rest, or just finds a good balance. This is not a problem dissimilarities. The score assigned to each object is beby itself since the classifier will learn how to classify the tween -1 and 1. A high value close to 1 means that the data based on how well each shapelet splits the classes. object is well assigned to the cluster it lies in; -1 means However, problems start occurring when the dataset has that the object is assigned to a wrong cluster; and a value multiple classes, and especially if a class is more distinct around 0 means that the object is between two clusters.
from the others. The outcome is a set of many redundant In our case, we want to select from the large set of shapelets for a class, which can discriminate a class very all possible subsequences, a smaller set in which each well but not the others. This behavior has been noted subsequence chosen represents a class and discriminates in [17], and to address it, the authors decided to extract the other classes. In other words, we want to find a set of patterns representing some class , such that the patterns will have a small distance to time series in compared to time series in , ≠ . We use the Silhouette score to assign a rank to each subsequence, and and evaluate shapelets from each class independently.
This way, even if one class is easy to classify, which will result in many shapelets that have a high score, they guarantee that shapelets representing other classes will be selected. class 2, and 8 for class 3. The test set had 900 time se- classification datasets, 16 have 3 classes, 9 have 4 classes, as the ration of between group variability and within group variability. For a shapelet , the F-statistic is defined as ( ) = ∑ =1 ( − ) 2 × | |
−1 ∑=1 |
| ∑ =1 ( − )2 × − 1
, where • is the average distance of time series from , • is the average distance with all time series, and • is the distance to the ’th time series from .
The major diference between F-statistic and Silhouette is the use of variance, whereas in Silhouettes we use the mean. Despite the similarity between the two methods, the resulting shapelets are very diferent. Figure
1 shows the distribution of distances from shapelets selected by each of the three approaches for the CBF dataset from the UCR archive [9]. The CBF dataset has 3 classes. We used 30 time series in training set: 10 for class 1, 12 for ries, namely 300, 298, and 302 for the classes 1, 2, and 3, respectively. We extract 30 shapelets from each class using the three evaluation methods, and we color the distribution of distances with time series from the same class with blue, and the distribution of distances to other classes with orange. The X-axis represents the distance, and the Y-axis represent the density of distances. Notice that all the three approaches managed to select shapelets that are close to 0 from the same class compared to other classes. It is clear from the figure that Silhouettes select more shapelets (higher density) that have a small distance to time series from the same class, and at the same time, the two distributions (blue and orange) are separate from each other. Our assumption is that if we select shapelets that separate well the two distributions, in a high classification accuracy.
This experimental evaluation aims to answer the following questions: • How is the classification accuracy afected by the shapelets selected using the three approaches? • How does the evaluation score of each approach correlate with the overall classification performance of the dataset? • How does the evaluation scores for each class correlate with the true positives and false negatives of instances of that class? compare to existing approaches? • How does the running time of the Silhouette score For all our experiments, we use 94 datasets from the UCR archive [9]. From the 94 datasets, 37 are binary and 32 have 5 classes or more. There are 6 datasets where the most prevalent class has over 10 times the number of instances compared to the least represented, while 10 datasets exhibit an imbalance exceeding a factor of 5.
The extraction of shapelet candidates is an important phase in time series classification. However, in this work, our focus is on the evaluation of shapelets and its efect on the classification. For a fair comparison between the three methods, we first randomly sample a large set of shapelets for each dataset from diferent starting positions and with diferent lengths. More precisely, for each dataset we randomly extract shapelets for each class. The value of is set to the maximum of 300 and 20% of the length of the time series, i.e., = max(300, 0.2 × ) . Next, we pre-compute and store the distances between the shapelets and the time series, since they will be needed in order to evaluate the shapelets, and also to transform the data for classification. The large set of randomly selected shapelets and their corresponding distances to all the time series will be used as a starting point for all our experiments, and they are the same for all comparisons between the approaches.
In this experiment we compare the efect of the evaluation using Silhouette, information gain and F-statistic on the classification. Instead of fixing an arbitrary number of shapelets to select and transform the data with, we start from a small number, namely = 5 for each class. The CBF dataset example has 3 classes, so we select 15 shapelets in total, and we gradually increase .
For every value, we select the top shapelets per class using the three methods, transform the data (using the pre-computed distances) and run the classification.
For the classification, we fix 6 standard classifiers. The ifrst classifier is the decision tree as it was the standard approach in the literature when classifying with shapelets.
We also include the 1-Nearest Neighbor (1-NN) and support vector classifier (SVC) since they were used in the evaluation in Hills work [7]. We also add the Logistic Regression classifier as an extra linear classifier, and KNearest Neighbor as an extra non-linear classifier, which is also a generalization of 1-NN. Finally, we also include an ensemble method, namely ADABoost, which iteratively builds multiple decision trees, and each new tree is trained with a penalty on instances that were wrongly classified by the previous trees.
The parameters of the models are found during the training by cross validation using five splits. The hyperparameters are found by grid search. Finally, we train a new model using the best combination of parameters found, and report the results of the test set.
Figure 2 shows the performance of 94 datasets from the UCR archive. On the top of the figure, the classification is done with the best 100 shapelets per class. On the X-axis we list the datasets, and the Y-axis represents the accuracy. Each color refers to the result of a method.
With such a high number of shapelets, almost all meth- the Silhouette score. This confirms the behavior seen in ods have the same performance. However, when only Figure 3. a few shapelets are used (e.g., 5 shapelets as shown at the bottom of the figure), the Silhouette becomes the Table 1 most accurate method, most of the time even with a big Pearson coeficient between the accuracy of the dataset and margin. the evaluation methods scores.
A pattern that we observed is that, when the number Method Pearson correlation of shapelets is small, the Silhouette score results in a high 5 shapelets 100 shapelets accuracy, and it does not change much if the number of sohuatptoelebtesaisstianbclreeamsienthg;otdh. uOsnththeeSiolthhoeurehttaensdc,otrhee taucrcnus- IFSn-ilfshotoarmtuiesatttiticeon gain 000...210929 (((223 ××× 111000−−−311))) 000...342001 (((253 ××× 111000−−−352))) racy achieved by the information gain and the F-statistic increases when the number of shapelets is increasing.
Figure 3 shows this behavior for the CBF dataset. By only using 5 shapelets per class, the Silhouette approach 5.4. Evaluation Methods and already achieves 97.88% accuracy, whereas F-statistic and Classification Performance for each information gain are around 42%. In this example, the Class CBF data has a small training set and a much larger test set, containing 30 and 900 time series, respectively. The number of shapelets required for the F-statistic and the information gain to start approaching the same accuracy as the Silhouette is more than 200 shapelets per class.
This means that the data transformed using the Silhouette score can be 40 times smaller, yet achieving a higher accuracy.
In the previous section, we compared the average score of each approach with the accuracy achieved on datasets.
In this experiment, we want to compare the behavior of the three evaluation methods with respect to class performance, i.e., when a class in the dataset is easy or hard to distinguish compared to other classes. For that, we compute the correlation between the evaluation scores and the accuracy of each class , which we define as
We investigate how the Silhouette score relates to the accuracy of classifying a dataset using shapelets. If the Silhouette scores assigned to the top candidate shapelets are all high (close to 1), we expect the dataset to be classiifed with high accuracy since the shapelets separate the diferent classes well. For example, from Figure 2 we can see that the dataset GunPointMaleVersusFemale has a higher accuracy (96%) compared to the Wine dataset, and it turns out that the average Silhouette scores are 0.56 and 0.25, respectively. To confirm this hypothesis, we use the results reported in Figure 2 and do the following: 1. Compute the average score of the selected shapelets using an evaluation method for each dataset. 2. Compute the correlation between the average score and the accuracy.
We normalize by the maximum of the number of predictions and the actual number of instances labeled in the test set. This is equivalent to the minimum of recall and precision, meaning that for each class the score reports whether the model trained on the transformed data is both precise (few false positives) but also making many successful predictions (few false negatives).
Table 2 shows the results achieved by the three approaches for both 5 and 100 shapelets per class. The results reported are using 65 datasets from the UCR archive, because we only kept datasets that have 3 classes or more. The reason to keep only datasets with at least 3 classes is that in a binary classification setup, if one class can be identified well using some shapelets, the other class is automatically discriminated as well.
When using many shapelets, all three approaches are highly correlated, with the information gain having the most significant correlation. In contrast, if only a few shapelets are used, the information gain is uncorrelated. This is due to the fact that the information gain is determining the optimal split point that results in the highest gain regardless of the class of the shapelet itself. For the F-statistic, the correlation is very high when a few shapelets is used. This can be justified by the denominator of the statistic, where the variance of distances is minimized, which favors shapelets that are similar to each other. Finally, notice again that for the Silhouette score the correlation does not change when the number of shapelets changes.
In this experiment we compare the running time of the three methods. Table 3 shows the mean, standard deviation and the percentiles of the running time for datasets from the UCR archive. As mentioned above, the number of extracted shapelets, , depends on the datasets. The Silhouette is the fastest method, followed by the F-statistic and finally the information gain. This corresponds also to the respective algorithmic complexities: () , () and ( log()) , respectively. Even though the F-statistic and the Silhouette have the same algorithmic complexity, the F-statistic has to cache and reuse some computations in order to compute the variances in linear time (for each shapelet). For the information gain, besides the overhead of sorting, the algorithm has also to evaluate the gain at each splitting point, which results in a higher running time.
We introduced a new shapelet evaluation method to score the utility of the candidate shapelets for time series classification. The idea is to select shapelets based on the Silhouette score used originally for evaluating clusters.
This tends to select shapelets that are very similar to the time series from the same class, but also very diferent from the time series of diferent classes. We have shown through experiments using 94 time series from the UCR archive [9] that the classification using Silhouettes is not only competitive with existing approaches in the literature in terms of the accuracy of predictions, but also much better when the number of shapelets is very small.
This property results in a much smaller training data size after the transformation.
The scores of our approach correlate with the accuracy classifications. In a first experiment we computed the Pearson correlation between the average score of all the selected shapelets and the achieved accuracy. This means that a high Silhouette score for a dataset will likely result in a high accuracy. We have also seen in Table 1 that the correlation does not change with the number of shapelets.
Thus, it is suficient to use a small number shapelets for the classification since the accuracy will likely not change much, unlike for the F-statistic and the information gain, which both require many shapelets to achieve a high accuracy.
Finally, we have compared the running time between the three approaches. Silhouette and F-statistic both have acceptable running time as both have an average time in the order of milliseconds. However, the bottleneck is the actual computation of distances.
In this work, our main focus was on the evaluation of the shapelets, and its efect on the accuracy of time series classification. Given that the Silhouette score results in high accuracy with a very small number of shapelets, we plan to speed up the whole classification process using shapelets by integrating the Silhouette in the candidate selection step and also exploiting them for early computation abandoning.
URL: https://doi.org/10.1007/978-3-030-33607-3_2. tion, in: Proceedings of the 17th ACM SIGKDD doi:10.1007/978-3-030-33607-3_2. International Conference on Knowledge Discovery [3] M. Flynn, J. Large, T. Bagnall, The contract random and Data Mining, KDD ’11, Association for Cominterval spectral ensemble (c-RISE): The efect of puting Machinery, New York, NY, USA, 2011, p. contracting a classifier on accuracy, in: Lecture 1154–1162. URL: https://doi.org/10.1145/2020408. Notes in Computer Science, Springer International 2020587. doi:10.1145/2020408.2020587. Publishing, 2019, pp. 381–392. URL: https://doi. [12] T. Rakthanmanon, E. Keogh, Fast shapelets: A scalorg/10.1007/978-3-030-29859-3_33. doi:10.1007/ able algorithm for discovering time series shapelets, 978-3-030-29859-3_33. in: Proceedings of the 2013 SIAM International [4] B. Lucas, A. Shifaz, C. Pelletier, L. O’Neill, N. Zaidi, Conference on Data Mining, Society for Industrial B. Goethals, F. Petitjean, G. I. Webb, Proximity and Applied Mathematics, 2013. URL: http://dx. forest: an efective and scalable distance-based clas- doi.org/10.1137/1.9781611972832.74. doi:10.1137/ sifier for time series, Data Mining and Knowl- 1.9781611972832.74. edge Discovery 33 (2019) 607–635. URL: https:// [13] C. Ji, C. Zhao, L. Pan, S. Liu, C. Yang, L. Wu, A doi.org/10.1007/s10618-019-00617-3. doi:10.1007/ fast shapelet discovery algorithm based on impors10618-019-00617-3. tant data points, International Journal of Web Ser[5] A. J. Bagnall, J. Lines, A. Bostrom, J. Large, vices Research 14 (2017) 67–80. URL: https://doi.
E. J. Keogh, The great time series classifica- org/10.4018/ijwsr.2017040104. doi:10.4018/ijwsr. tion bake of: a review and experimental evalu- 2017040104. ation of recent algorithmic advances, Data Min. [14] X. Renard, M. Rifqi, W. Erray, M. Detyniecki, Knowl. Discov. 31 (2017) 606–660. URL: https:// Random-shapelet: An algorithm for fast shapelet doi.org/10.1007/s10618-016-0483-9. doi:10.1007/ discovery, in: 2015 IEEE International Conference s10618-016-0483-9. on Data Science and Advanced Analytics (DSAA), [6] L. Ye, E. Keogh, Time series shapelets: A new prim- IEEE, 2015. URL: https://doi.org/10.1109/dsaa.2015. itive for data mining, in: Proceedings of the 15th 7344782. doi:10.1109/dsaa.2015.7344782. ACM SIGKDD International Conference on Knowl- [15] A. Guillaume, C. Vrain, W. Elloumi, Random edge Discovery and Data Mining, KDD ’09, Asso- dilated shapelet transform: A new approach ciation for Computing Machinery, New York, NY, for time series shapelets, in: Pattern Recognition USA, 2009, p. 947–956. URL: https://doi.org/10.1145/ and Artificial Intelligence, Springer International 1557019.1557122. doi:10.1145/1557019.1557122. Publishing, 2022, pp. 653–664. URL: https://doi. [7] J. Hills, J. Lines, E. Baranauskas, J. Mapp, org/10.1007/978-3-031-09037-0_53. doi:10.1007/ A. Bagnall, Classification of time series by 978-3-031-09037-0_53. shapelet transformation, Data Mining and Knowl- [16] J. Grabocka, N. Schilling, M. Wistuba, L. Schmidtedge Discovery 28 (2013) 851–881. URL: https:// Thieme, Learning time-series shapelets, in: doi.org/10.1007/s10618-013-0322-1. doi:10.1007/ Proceedings of the 20th ACM SIGKDD Internas10618-013-0322-1. tional Conference on Knowledge Discovery and [8] P. J. Rousseeuw, Silhouettes: A graphical aid Data Mining, KDD ’14, Association for Comto the interpretation and validation of cluster puting Machinery, New York, NY, USA, 2014, analysis, Journal of Computational and Applied p. 392–401. URL: https://doi.org/10.1145/2623330. Mathematics 20 (1987) 53–65. URL: https://doi. 2623613. doi:10.1145/2623330.2623613. org/10.1016/0377-0427(87)90125-7. doi:10.1016/ [17] A. Bostrom, A. Bagnall, Binary shapelet transform 0377-0427(87)90125-7. for multiclass time series classification, in: Big [9] H. A. Dau, E. Keogh, K. Kamgar, C.-C. M. Yeh, Data Analytics and Knowledge Discovery, Springer Y. Zhu, S. Gharghabi, C. A. Ratanamahatana, Yan- International Publishing, 2015, pp. 257–269. URL: ping, B. Hu, N. Begum, A. Bagnall, A. Mueen, https://doi.org/10.1007/978-3-319-22729-0_20. G. Batista, Hexagon-ML, The ucr time series clas- doi:10.1007/978-3-319-22729-0_20. sification archive, 2018. https://www.cs.ucr.edu/ ~eamonn/time_series_data_2018. [10] P. Geurts, Pattern Extraction for Time Series Classification, Springer Berlin Heidelberg, 2001, p. 115–127. URL: http://dx.doi.org/10.1007/ 3-540-44794-6_10. doi:10.1007/3-540-44794-6_ 10. [11] A. Mueen, E. Keogh, N. Young, Logical-shapelets:
An expressive primitive for time series classifica