# Classification of Uncertain Time Series by Propagating Uncertainty in Shapelet Transform

Michael Franklin Mbouopda, Engelbert Mephu Nguifo

► To cite this version:

Michael Franklin Mbouopda, Engelbert Mephu Nguifo. Classification of Uncertain Time Series by Propagating Uncertainty in Shapelet Transform. ECML/PKDD Tutorial and Workshop on Uncertainty in Machine Learning, Sep 2020, Ghent, Belgium. pp.1-12. hal-03099346

HAL Id: hal-03099346

https://uca.hal.science/hal-03099346

Submitted on 6 Jan 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Classification of Uncertain Time Series by
Propagating Uncertainty in Shapelet Transform

*

Michael Franklin MBOUOPDA¹[0000-0003-1916-1464] and Engelbert MEPHU
NGUIFO²[0000-0001-9119-678X]

University of Clermont Auvergne, CNRS, ENSMSE, LIMOS, F-63000
CLERMONT-FERRAND, FRANCE
https://limos.fr/
{michael mbouopda, engelbert.mephu.nguifo}@uca.fr

**Abstract.** Time series classification is a task that aims at classifying chronological data. It is used in a diverse range of domains such as meteorology, medicine and physics. In the last decade, many algorithms have been built to perform this task with very appreciable accuracy. However, the uncertainty in data is not explicitly taken into account by these methods. Using uncertainty propagation techniques, we propose a new uncertain dissimilarity measure based on euclidean distance. We also show how to classify uncertain time series using the proposed dis-similarity measure and shapelet transform, one of the best time series classification methods. An experimental assessment of our contribution is done on the well known UCR dataset.

**Keywords:** Time series · Classification · Uncertainty · Shapelet.

# 1 Introduction

The last decade have been characterized by the availability of measurements in a large and variate set of applications such as meteorology, astronomy and object tracking. Generally, these measurements are represented as time series [3], that means a sequence of data ordered in time. Meanwhile, there has been an increase of the number of methods for time series classification [6, 2]. However, to the best of our knowledge, all the existing methods assume that the measurements are always precise and complete, and hence they do not take uncertainty into account. Any measurement is subject to uncertainty that can be due to the environment, the mean of measurement, privacy constraint and other factors. Furthermore, even if uncertainty can be reduced, it cannot be eliminated [11]. In some applications, uncertainty cannot be neglected and has to be explicitly handled [9].

<footnote>* Thanks to the french Ministry of Higher Education, Research and Innovation who is funding this research.</footnote>
Shapelet based methods are one of the best approaches that have been devel-
oped for time series classification. They are especially appreciated for their in-
terpretability, their robustness and their classification speed [12]. This approach
can be summarized in three steps:

- the first step is the extraction of shapelets. This step can be seen as a feature selection,

- the second step is the shapelet transformation. Here, the feature vector of each instance in the dataset is computed,

- the third and last step consists of training a supervised classifier on the feature vectors computed in the second step.

In this paper, we show how this approach can be applied in the context of
uncertain time series classification. To do that, we firstly propose an uncertainty
dissimilarity measure based on euclidean distance. Secondly we integrate it in a
shapelet approach to classify uncertain time series.

The rest of this paper is organized as follows: related works are presented in section 2. In section 3, we present a new uncertain dissimilarity measure and in section 4, we built a shapelet method to classify uncertain time series. Section 5 is about experiments and section 6 finally concludes this paper.

## 2 Related Works

Uncertain time series analysis is a well known problem, and some reported works have been performed to tackle it. These works led to the development of probabilistic similarity measures. Given two uncertain time series, probabilistic similarity measures compute the probability that the magnitude of the similarity between them is not greater than a given user defined threshold [3]. Probabilistic similarity have been coupled with 1-NN classifier to perform uncertain time series classification, for instance [9] has classified uncertain time series using its proposed probabilistic measure called DUST and a 1-NN classifier. Probabilistic measures are not always applicable in practice; In fact, they are based on some assumptions that are not always satisfied. For instance, the probabilistic measure PROUD [13] requires the uncertainty deviation to be the same at each time point of a series [9]. MUNICH [1], another probabilistic measure requires many observations at each time step of a series. DUST avoids the limitations of PROUD and MUNICH, but requires the uncertainty distribution at the same time step of every time series to be the same. Lately, the dissimilarity measure FOTS [10] has been proposed; it is robust to uncertainty but do not explicitly take it as input. Another limitation that is shared by all of these measures is that they all take uncertain data as input and output a value without any uncertainty; It is not possible to compare uncertain measures with 100% reliability. For all these reasons, we propose in section 3, UED, an uncertain dissimilarity measure that makes no assumption on the distribution of the uncertainty and outputs the dissimilarity value with a confidence interval.
Firstly introduced by [12] as shapelet decision trees, time series classification based on shapelets have been generalized by [5] as shapelet transformation. This generalization allows shapelet approaches to be applicable with any supervised classifier. [5] also shown that coupling shapelet transformation with a good classifier significantly improves the classification accuracy. To the best of our knowledge, the best time series classification method reported in the state of the art is HIVE-COTE [7]. It is an ensemble methods containing several modules of different time series models and one of its module is based on shapelet transformation. To build an uncertain HIVE-COTE, each module of HIVE-COTE should take uncertainty into account and in this paper we take a first step in this way by showing in section 4 how uncertain time series can be classified using shapelet transformation.

## 3 Uncertain dissimilarity measure

As stated by [11], uncertainty is different from error since it cannot be eliminated; but it can be reduced up to a certain magnitude. Regardless of the measurement method, there is always an uncertainty and uncertain measures cannot be compared with a 100% reliability: the result of the comparison of uncertain values should also be uncertain. There are many ways to represent uncertainty, but in this paper an uncertain measure $x$ is represented like in [11] by its best guess $\hat{x}$ and the uncertainty $\delta x$ on that guess.

$$x = \hat{x} \pm \delta x \qquad (1)$$

The previous formula means that the real value of $x$ is the interval $[\hat{x}-\delta x, \hat{x}+\delta x]$.

Euclidean distance (ED) is widely used in the literature to measure the dissimilarity between time series. It is particularly used in shapelet-based approaches [12, 5, 2]. Given two time series $T_1 = (t_{11}, t_{12}, ..., t_{1n})$ and $T_2 = (t_{21}, t_{22}, ..., t_{2n})$, the ED between them is defined as follows:

$$ED(T_1, T_2) = \sum_{i=1}^{n} (t_{1i} - t_{2i})^2 \qquad (2)$$

When each $t_{ij}$ is an uncertain measure, $T_1$ and $T_2$ are called uncertain time series and the distance between them cannot be 100% reliable because of uncertainty. We compute this uncertainty using uncertainty propagation techniques [11]. Let $x = \hat{x} \pm \delta x$ and $y = \hat{y} \pm \delta y$ be two uncertain measures then we have the following properties:

$$-z = x + y = \hat{z} \pm \delta z, \text{ where } \hat{z} = \hat{x} + \hat{y} \text{ and } \delta z = \delta x + \delta y$$

$$-z = x - y = \hat{z} \pm \delta z, \text{ where } \hat{z} = \hat{x} - \hat{y} \text{ and } \delta z = \delta x + \delta y$$

$$-z = x^n = \hat{z} \pm \delta z, \text{ where } \hat{z} = (\hat{x})^n \text{ et } \delta z = |n \frac{\delta x}{\hat{x}} \hat{x}^n|$$

Using these properties, an uncertain similarity based on ED can be computed for two uncertain time series $T_1$ and $T_2$ by propagating uncertainty in the ED
formula. We named the obtained measure UED and it is defined as follows:

$$ 
\begin{align} 
\mathrm{UED}(T_1, T_2) &= \sum_{i=1}^{n} (\hat{t}_{1i} - \hat{t}_{2i})^2 \pm 2 \sum_{i=1}^{n} |\hat{t}_{1i} - \hat{t}_{2i}| \times (\delta t_{1i} + \delta t_{2i}) \tag{3} \\
&= \mathrm{ED}(\hat{T}_1, \hat{T}_2) \pm 2 \sum_{i=1}^{n} |\hat{t}_{1i} - \hat{t}_{2i}| \times (\delta t_{1i} + \delta t_{2i}) 
\end{align} 
$$

where $\hat{T}_i$ is obtained by removing uncertainty in $T_i$, i.e by setting every uncertainty to 0.

The output of UED is an uncertain measure representing the similarity between the two uncertain time series given as inputs. In order to use UED to classify time series, especially with a shapelet algorithm, an ordering relation for the set of uncertain measures is needed. We propose two ways to compare uncertain measures: the first one is the simpler one and is based on confidence, the second one is a stochastic order.

## Simple ordering for uncertain measures

This ordering is based on two simple properties. Let $x$ and $y$ be two uncertain measures, the first property is the property of equality and states that two uncertain measures are equals if their best guesses and their uncertainties are equals.

$$ x = y \iff \hat{x} = \hat{y} \land \delta x = \delta y \tag{4} $$

The property of inferiority is the second one and states that the uncertain measure $x$ is smaller than the uncertain measure $y$ if and only if the best guess of $x$ is smaller than the best guess of $y$. In the case where $x$ and $y$ have the same best guesses, the smaller is the one with the smallest uncertainty.

$$ x < y \iff (\hat{x} < \hat{y}) \lor ((\hat{x} = \hat{y}) \land (\delta x < \delta y)) \tag{5} $$

Unlike the property of equality which is straightforward, the property of inferiority need some explanations. Unfortunately, we don't have a mathematical justification of this property but it is guided by two points: firstly we are in some way confident about the best guess since it must have been given by an expert, and secondly we are more confident with smaller uncertainties.

Of course, these properties do not always give a correct ordering; in fact, if $x = 2 \pm 0.5$ and $y = 2 \pm 0.1$ then the inferiority property says that $y < x$. Now, if there is an oracle able to compute the exact value of any uncertain measure, it might says that $x = 1.8$ and $y = 2$, and thus invalidating our ordering. This observation also holds for the properties of equality.

## Stochastic ordering of uncertain measures

An uncertain measure can be considered as a random variable with mean the best guess and standard deviation the uncertainty. Given this consideration, a
stochastic order can be defined on the set of uncertain measures. A random variable X is stochastically less than or equal to (noted $\le_{st}$) another random variable Y if and only if $P(X > t) \le P(Y > t) \forall t \in \mathbb{R}$ [8]. Since the exact value of an uncertain measure x is in the interval $[\hat{x} - \delta x, \hat{x} + \delta x]$, the domain of t can be reduced to the interval $\mathbb{I} = [\min(X, Y); \max(X, Y)]$; where $\min(X, Y)$ and $\max(X, Y)$ repectively return the minimal and the maximal values of the union of possible values of X and Y. The stochastic order can be rewritten and developed as follows:

$$ 
\begin{align} 
X \le_{st} Y &\iff P(X > t) \le P(Y > t) \forall t \in \mathbb{I} \nonumber \\ 
&\iff 1 - P(X > t) > 1 - P(Y > t) \forall t \in \mathbb{I} \nonumber \\ 
&\iff P(X \le t) > P(Y \le t) \forall t \in \mathbb{I} \nonumber \\ 
&\iff CDF_X(t) > CDF_Y(t) \forall t \in \mathbb{I} \tag{6}
\end{align} 
$$

$CDF_X(t)$ is the cumulative distribution function of the random variable X evaluated at $t$. Because the size of $\mathbb{I}$ is infinite, we discretized it as being the set of the following values:

$$ \min(X, Y) + i \times \frac{\max(X, Y) - \min(X, Y)}{k} \quad (7) $$

$0 \le i \le k$ and $k$ is a whole number to be defined. Unlike the simple ordering which is a total order, this stochastic ordering is a partial order. That means that, the relation stochastically less than or equal to is not defined for any two random variables, and thus any two uncertain measures cannot be sorted using this stochastic order. This is clearly a limitation, but we did not find a total stochastic ordering in the literature.

Now that we know how to compare uncertain measures, let us see how to use UED to classify uncertain time series.

# 4 Uncertain shapelet classification

In this part, we describe how to classify uncertain time series using shapelets. We use the shapelet algorithm described by [5]. However we need to define the underlying concepts in the context of uncertain time series.

An uncertain time series $T$ is a series of $m$ (its length) uncertain measures.

$$ T = \hat{T} \pm \delta T = \{t_1 \pm \delta t_1, t_2 \pm \delta t_2, \dots, t_m \pm \delta t_m\} \quad (8) $$

An uncertain subsequence $S$ of an uncertain time series $T$ is a series of $l$ (its length) consecutive values in $T$.

$$ S = \hat{S} \pm \delta S = \{t_{i+1} \pm \delta t_{i+1}, \dots, t_{i+l} \pm \delta t_{i+l}\} \quad (9) $$

The dissimilarity between two uncertain subsequences $S$ and $R$ is computed using UED

$$ d = \text{UED}(S, R) = \text{UED}(R, S). \quad (10) $$
And the dissimilarity between an uncertain time series *T* and an uncertain subsequence *S* is defined as follows:

$$ UED(T, S) = \min\{UED(S, R) \mid \forall R \subseteq T, |S| = |R| \} \quad (11) $$

An uncertain separator *sp* for a dataset *D* of uncertain time series is an uncertain subsequence that divides *D* in two parts *D*₁ and *D*₂ such that:

$$ \begin{aligned} D_1 &= \{T \mid \text{UED}(T, sp) \le \epsilon, \forall T \in D\} \\ D_2 &= \{T \mid \text{UED}(T, sp) > \epsilon, \forall T \in D\} \end{aligned} \quad (12) $$

As in [5], the quality of a separator is measured using the information gain (IG). Given the previous definitions, we define an uncertain shapelet *S* for a dataset *D* of uncertain time series as being a separator that maximized the information gain.

$$ S = \underset{sp}{\operatorname{argmax}}(IG(D, sp)) \quad (13) $$

The shapelet transformation algorithm is described in detail in [5]. We give a summary here, meanwhile showing the change when in the context of uncertain time series.

Given a dataset *D* of uncertain time series, the first step is to select the top *k* best uncertain shapelets from the dataset. This step is achieved using the procedure described by Algo. 1 that takes as input, the dataset *D*, the number of uncertain shapelets to be extracted *k*, the minimum and the maximum length of an uncertain shapelet *MIN* and *MAX*. This algorithm uses three subprocedures:

- *GenCand*(*T*, *MIN*, *MAX*) which generates every possible uncertain shapelet candidates from the inputted uncertain time series *T*. These candidates are uncertain subsequences of *T*, with length at least *MIN* and at most *MAX*.

- *AssessCand*(*cands*, *D*) which computes the quality of each candidate in the list of candidates *cands*. The quality of a candidate is the information gain it produces when used as a separator for the dataset.

- *ExtracBest*(*C*, *Q*, *k*) which takes the list of uncertain shapelet candidates *C*, their associated qualities *Q* and return first *k* uncertain shapelets with highest qualities.

In summary, Algo. 1 generates every uncertain subsequence of length at least *MIN* and at most *MAX* from the dataset, assesses the quality of each one by computing the information gain obtained when it is used as separator for the dataset and finally returns the *k* subsequences that produce the highest information gain.

The next step after the top-*k* uncertain shapelets selection is the uncertain shapelet transformation. This is exactly the same as shapelet transformation described by [5], but with the difference that uncertainty is propagated during the transformation process. This step is done using Algo. 2 which takes as input the dataset *D*, the set of the top-*k* uncertain shapelets *S* and the number of
<caption>**Algorithm 1** Top-K Uncertain Shapelet Selection</caption>

1: **function** USHAPELETSELECTION(D, k, MIN, MAX)
2:     C ← ∅; Q ← ∅
3:     **for** i ← 1, n **do**
4:         cand ← GenCand(Ti, MIN, MAX)
5:         qualities ← AssessCand(cand, D)
6:         C ← C + cand
7:         Q ← Q + qualities
8:     **end for**
9:     S ← ExtractBest(C, Q, k)
10:    **return** S
11: **end function**

▷ Top k uncertain shapelets

uncertain shapelets *k*. For each uncertain time series in the dataset, its uncertain feature vector of length *k* is computed using UED. The *i*-th element of the vector is the UED between the uncertain time series and the uncertain shapelet *i*. The computed uncertain feature vectors are returned as the new transformed uncertain dataset.

<caption>**Algorithm 2** Uncertain Shapelet Transformation</caption>

function USHAPELETTRANSFORMATION(D, S, k)
    for i ← 1, n do
        temp ← ∅
        for j ← 1, k do
            tempj ← UED(Ti, Sj)
            **end for**
            Di ← tempj
        **end for**
        return D
    ▷ The transformed dataset
end function

The third and last step is the effective classification. A supervised classifier is trained on the uncertain transformed dataset, so that, given the feature vector of an unseen uncertain time series, it could predict its class label. Since the uncertainty have been propagated, the training process can be aware of uncertainty by taking it as part of the input. More specifically, best guesses are features and uncertainties are features of best guesses, and thus are metafeatures. If instead of UED, we had used one of the existing metrics from the state of the art (DUST, MUNICH, PROUD or FOTS), the classifier would have been trained without being aware of uncertainty in the input since the output of these metrics are apparently 100% reliable.

Fig. 1 gives an overview of the classification process. During the training step (illustrated black path), top-k uncertain shapelets are selected and a supervised model (illustrated here by a decision tree for simplicity) is trained on the un-
certain transformed dataset. Each node of the trained decision tree contains an uncertain shapelet, and the similarity at each node is the UED between the uncertain time series and the uncertain shapelet at that node. During the testing step (illustrated by the green path), the uncertain shapelets extracted during the training step are used to transform the test set, and the trained model is used to predict the class labels of the test set according to the result of the transformation. Let call this process UST for Uncertain Shapelet Transformation.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Uncertain time series classification process</figcaption></figure>

# 5 Experiments

In this section, we experimentally compare our approach to the state of the art. The comparison criterion is the model classification accuracy as it has been always done [2, 3, 5, 10]. Since the output of our model is the probability distribution over the set of classes, we take the most probable class as the predicted class and use it to compute the model accuracy. We have compared the four following models:

- **UST_FLAT**: this is the algorithm described in section 4. The uncertain feature vector is represented as a flat vector such that the first half contains best guesses and the second half contain uncertainties. This model also uses the simple ordering for uncertain measures.

- **UST_FLAT_ST**: this is the same as UST_FLAT, but with the difference that it uses the stochastic order to sort uncertain measures. This model considers an uncertain measure $x = \hat{x} \pm \delta x$ as a normal distributed random variable with mean $\hat{x}$ and standard deviation $\delta x$. The CDF of such a random variable is

$$CDF_X(t) = \frac{1}{2}(1 + erf(\frac{t - \hat{x}}{\delta x\sqrt{2}}))$$

where erf(.) is the gaussian error function. To discretize $\mathbb{I}$ (using Eq. 7), we fixed the value of $k$ to 100. Larger values of $k$ lead to best approximation of $\mathbb{I}$, however slow the classification process. We tried several values of $k$, but $k = 100$ worked better for most of our datasets. We have also used a relaxed
version of the stochastic ordering: given two random variables X and Y, we
considered X to be smaller or equal to Y if the number of values t in I such
that CDF_X(t) > CDF_Y(t) is greater than the number of values t in I such
that CDF_X(t) ≤ CDF_Y(t).

- **DUST_UNIFORM**: This is the UST algorithm where UED has been replaced by the uniform version of DUST. The data in each time series are assumed to be uniformly distributed. Hence there is no uncertainty propagation, and the supervised classifier is not aware of uncertainty in the dataset. To compare two uncertain measures, DUST required them to have the same uncertainty; hence, we used the highest uncertainty of both measures.

- **DUST_NORMAL**: like DUST_UNIFORM, but with the assumption that the data in each time series follow a Gaussian distribution.

Although other classifiers such as Support Vector Machine, Random Forest and Multi Layer Perceptron can be used to increase the accuracy, we choose to use the J48 decision tree as the supervised classifier in all these four uncertain shapelet models. We want the result to be only correlated to the uncertainty handling and not to the used classifier. However, it is highly recommended to try other classifiers when in real application.

## 5.1 Datasets

We used 29 datasets from the well known UCR repository [4]. Although the repository contains univariate and multivariate time series datasets, in this work, we only focus on univariate datasets. However the shapelet method is not limited to univariate time series. Each dataset on the repository is divided into a training set and a test set.

Since the datasets in this repository are without uncertainty, we manually add a random uncertainty. For each dataset, the added uncertainty follows a normal distribution of mean 0 and standard deviation c × σ, where σ is the standard deviation of the dataset. We used two different values of c which are: 0.1 and 0.2. The uncertainty result for an instance from the CBF dataset is shown by Fig. 2. The orange line is the original time series, and the blue one is the obtained uncertain time series. During the training, original time series are not used, only the uncertain time series and the standard deviation of the uncertainty are used. Each value in each uncertain time series has its own standard deviation.

## 5.2 Source Code

We have used the open source code from [2], hosted on github<fnref n="1" />. It's a github repository containing a Java implementation of state of the art time series classification algorithms such as shapelet transformation. We have added an imple-

<footnote n="1">¹ https://github.com/uea-machine-learning/tsml</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 2: Uncertainty for an instance from the Chinatown dataset for $c = 0.2$</figcaption></figure>

mentation of UED and UST and the updated code is available<fnref n="2" />. The code used to add uncertainty is also accessible on the same repository <fnref n="3" />.

## 5.3 Results and discussion

We have computed the accuracy of each model and used some statistics to compare them.

We summarized the statistics of USTjrjr, DUSTjrr, and DUSTjrrr using boxplots as shown on Fig 3. The green triangles represent the mean of the accuracy of each model on all the datasets. DUST based models (DUSTjrr and DUSTjrrr) are not significantly different, however DUSTjrr is a bit better than its Gaussian counterpart. USTjrjr is better than DUSTjrr based models, especially when the uncertainty is high (Fig 3 right); The best 3rd quartile for DUST based models is only at 0.6 while it is almost 0.8 for USTjrjr, meaning that 25% of the datasets are classified with an accuracy of 80%; more datasets are well classified with USTjrjr than with DUST based models. More particularly, for $c = 0.2$, the best accuracies given by DUST based models are 55% and 54% for the datasets DodgerLoopGame and BME respectively; while UST gives 77% accuracy for the dataset DodgerLoopGame, and 82% for BME.

Next, we have checked if the stochastic ordering improves the performances of the UST model by comparing USTjrjr to USTjrr. Since this ordering is not total, USTjrjr failed on 23 datasets; this is because unsortable uncertain measures have been found during the training or the testing phase. The performances we got from the 6 remaining datasets are summarized in Fig 4. The stochastic ordering has improved the performances for $c = 0.1$ (Fig. 4 left); In particular, the accuracy improved from 61% to 84% (23% better) for the dataset Chinatown and from 14% to 35% (21% better) for the dataset SonyAIBORobotSurface1. When $c = 0.2$ (Fig. 4 right), we observe no improvement, instead the accuracy particularly decreases for the dataset BME from 82% to 69% (13% worse) when using the stochastic ordering.

<footnote n="2">² https://github.com/frankl1/Uncertain-Shapelet-Transform</footnote>

<footnote n="3">³ https://github.com/frankl1/Uncertain-Shapelet-Transform/blob/master/add-noise.ipynb</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 3: DUST vs UST for $c = 0.1$ (left) and $c = 0.2$ (right)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: UST_FLAT vs UST_FLAT_ST for $c = 0.1$ (left) and $c = 0.2$ (right)</figcaption></figure>

With UED, we are as good as, or better than state of the art uncertain similarity measures. However, our approach is limited. In fact, using the flat representation, the supervised classifier is not really aware of the propagated uncertainty. Although uncertainties should be considered as metafeatures, they are considered as normal features by the supervised classifier. We believe that a better way of handling the propagated uncertainty will lead to a better classification.

# 6 Conclusion

The goal of this paper was to classify uncertain time series using the shapelet transformation approach. To achieve this goal, we used uncertainty propagation techniques to defined an uncertain dissimilarity measure called UED. Then we adapted the well known shapelet algorithm to the context of uncertain time series using UED and proposed the uncertain shapelet transformation algorithm (UST). We have run experiments on some state of the art datasets and the results showed the effectiveness of our approach. As future work, we intend to assess our approach on a real uncertain dataset. Another future work is to use an uncertain supervised classifier instead of the simple, classical decision tree in the last step of UST.
References

1. Aßfalg, J., Kriegel, H.P., Kröger, P., Renz, M.: Probabilistic similarity search for uncertain time series. In: International Conference on Scientific and Statistical Database Management. pp. 435–443. Springer (2009)

2. Bagnall, A., Lines, J., Bostrom, A., Large, J., Keogh, E.: The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Mining and Knowledge Discovery 31(3), 606–660 (2017)

3. Dallachiesa, M., Nushi, B., Mirylenka, K., Palpanas, T.: Uncertain time-series simi-
ilarity: Return to the basics. Proceedings of the VLDB Endowment 5(11), 1662–
1673 (2012)

4. Dau, H.A., Bagnall, A., Kamgar, K., Yeh, C.C.M., Zhu, Y., Gharghabi, S., Ratanamahatana, C.A., Keogh, E.: The ucr time series archive (2018)

5. Hills, J., Lines, J., Baranauskas, E., Mapp, J., Bagnall, A.: Classification of time series by shapelet transformation. Data Mining and Knowledge Discovery 28(4), 851–881 (2014)

6. Ismail Fawaz, H., Forestier, G., Weber, J., Idoumghar, L., Muller, P.A.: Deep learning for time series classification: a review. Data Mining and Knowledge Discovery 33(4), 917–963 (Jul 2019)

7. Lines, J., Taylor, S., Bagnall, A.: Time series classification with hive-cote: The hierarchical vote collective of transformation-based ensembles. ACM Transactions on Knowledge Discovery from Data (TKDD) 12(5), 52 (2018)

8. Marshall, A.W., Olkin, I., Arnold, B.C.: Stochastic Ordering. In: Inequalities: Theor y of Majorization and Its Applications. pp. 693–756. Springer New York, New York, NY (2010)

9. Sarangi, S.R., Murthy, K.: DUST: a generalized notion of similarity between uncer-
tain time series. In: Proceedings of the 16th ACM SIGKDD international con-
ference on Knowledge discovery and data mining. pp. 383–392. ACM (2010)

10. Siyou Fotso, V.S., Mephu Gnuifo, E., Vaslin, P.: Frobenius correlation based u-shapelets discovery for time series clustering. Pattern Recognition 103, 107301 (2020)

11. Taylor, J.R.: An Introduction to Error Analysis: The Study of Uncertainties in Physical Measurements. University Science Books, 2 sub edn. (1996)

12. Ye, L., Keogh, E.: Time series shapelets: a new primitive for data mining. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 947–956. ACM (2009)

13. Yeh, M.Y., Wu, K.L., Yu, P.S., Chen, M.S.: Proud: a probabilistic approach to processing similarity queries over uncertain data streams. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. pp. 684–695. ACM (2009)