# DTW+S: Shape-based Comparison of Time-series with Ordered Local Trends

Ajitesh Srivastava

###### Abstract

Measuring distance or similarity between time-series data is a fundamental
aspect of many applications including classification and clustering. Existing
measures may fail to capture similarities due to local trends (shapes) and may
even produce misleading results. Our goal is to develop a measure that looks
for similar trends occurring around similar times and is easily interpretable
for researchers in applied domains. This is particularly useful for
applications where time-series have a sequence of meaningful local trends that
are ordered, such as in epidemics (a surge to an increase to a peak to a
decrease). We propose a novel measure, DTW+S, which creates an interpretable
“closeness-preserving” matrix representation of the time-series, where each
column represents local trends, and then it applies Dynamic Time Warping to
compute distances between these matrices. We present a theoretical analysis
that supports the choice of this representation. We demonstrate the utility of
DTW+S in ensemble building and clustering of epidemic curves. We also
demonstrate that our approach results in better classification compared to
Dynamic Time Warping for a class of datasets, particularly when local trends
rather than scale play a decisive role.

##  1 Introduction

The distance between two time-series is a fundamental measure used in many
applications, including classification, clustering, and evaluation. In
classification and clustering, we want two “similar” time-series to have a low
distance between them so that they can be grouped together or classified with
the same label. In evaluation, the setting could be that we are generating
projections (long-term forecasts) of time-series, and retrospectively, we wish
to measure how close we are to the ground truth.

While many measures exist for these purposes, including Euclidean distance,
correlation, and dynamic time-warping (DTW) (Müller 2007), the choice of the
similarity measure can depend on the domain. Further, existing similarity
measures may fail to capture the desired properties of the task at hand, for
instance, when we wish to capture the similarity in trends over time. For
example, consider the scenario presented in Figure 1(a). Two models perform a
projection to estimate the time-series given by the ground truth. Model 1
produces a pattern that is similar to the ground truth, while Model 2 produces
a flat line. If we use mean absolute error to assess which model performed
better, Model 2 (flat line) will receive a better score. Although Model 1
produces identical trends and correctly predicts the peak timing, it loses to
a Model 2 which conveys no information. Now, consider the scenario presented
in Figure 1(b). Model 1 predicts the exact pattern but it slightly shifted in
time. Again, Model 1 – a flat line, produces a lower error. Finally, in Figure
1(c), Model 1 predict the overall pattern well, it only misjudges the height
of the peaks. Yet, Model 2, a straight line, is considered closer to the
ground truth. Some form of a range normalization could have addressed the
issue in Figure 1(a), and Dynamic Time Warping (DTW) (Müller 2007), which
allows stretching the time dimension to best match two time-series, can
address the issue raised in Figure 1(b). However, DTW and/or any normalization
of scale cannot address the issue presented in Figure 1(c).

(a) Similar trend different scale

(b) Similar scale, shifted in time

(c) Similar trends with varying scales

Figure 1: Simple measures like Mean Absolute Error can be deceiving. In all
these examples, Model 1 seems to be closer to the Ground truth, but receives a
higher distance compared to a straight line.

Our goal is to develop a measure of distance such that two time-series are
considered similar if and only if they have a similar sequence of trends and
similar trends occur around similar times. This is particularly useful in
public health where the time-series may represent meaningful local trends that
are ordered, e.g., a surge, followed by an increase, then a peak, and finally
a decrease. We define a trend as the local shape of a time-series. Further, we
wish this measure to be easily interpretable so that it can be adopted by
researchers in applied domains, such as epidemiology. To achieve this, we
propose a novel distance measure DTW+S that (i) produces a matrix
representation where each column encodes local trends, and (ii) uses Dynamic
Time Warping on these matrices to compute distances between a pair of time-
series. With this measure, we are able to perform better clustering and
ensembling (US SMH 2020, 2022; European CDC 2022) of epidemic curves where
local interpretable trends are of interest. While we do not intend to develop
a new time-series classification algorithm, we believe a good distance measure
should improve a simple distance-based classifier such as $k$-nearest
neighbors (Petitjean et al. 2014) on a class of tasks. Therefore, we also
demonstrate the success of 1-nearest neighbor using our measure on
classification.

#### Contributions

(1) We prove necessary and sufficient conditions for the shapelet space
representation (Srivastava, Singh, and Lee 2022) to be neighborhood-preserving
– two local trends are similar if and only if they are mapped to nearby points
(Section 3.1). (2) We propose a novel distance measure for time-series DTW+S
that leverages this representation along with DTW to find if similar trends
occur around similar times (Section 3.2). (3) We develop an ensembling
technique using DTW+S that can simultaneously summarize time-series in scale
and time (Section 3.4), and we demonstrate its utility on epidemic curves
(Section 4.2). (4) We demonstrate that DTW+S results in more sensible
clustering of epidemic curves (Section 4.1). Also, DTW+S outperforms Dynamic
Time Warping in classifying time-series on a subset of datasets, particularly,
those where local trends play a key role in classification (Section 4.3).

##  2 Related Work

###  2.1 Background

#### Shapelet Space Representation

In (Srivastava, Singh, and Lee 2022), the idea of the shapelet space
representation is introduced to compare short-term forecasts of epidemics. The
motivation is to compare the shape of the forecasts rather than exact
numerical values. Further, they wish to make the representation interpretable.
Each dimension represents the similarity of the vector with one of the chosen
shapes of interest, such as an increase $(1,2,3,4)$ and peak $(1,2,2,1)$.
These shapes of interest are termed Shapelets.

######  Definition 1 (Shapelet).

A shapelet $\mathbf{s}=[s_{1},\dots,s_{w}]\in\mathbb{R}^{w}$ is a vector that
represents a shape of interest.

######  Definition 2 (Shapelet-space Representation).

Given $d$ shapelets $\\{\mathbf{s_{1}},\dots\mathbf{s_{d}}\\}$, a Shapelet-
space Representation is a vector $\mathbf{x}$ as a $d$-dimensional point
$P_{x}=(p_{1},p_{2},\dots,p_{d})$ denoting the shape of
$\mathbf{x}\in\mathbb{R}^{w}$ and the co-ordinate
$p_{i}=sim(\mathbf{x},p_{i})$ for some measure of similarity. The function
$f:\mathbb{R}^{w}\rightarrow\mathbb{R}^{d}$ is the Shapelet-space
Transformation.

The similarity function is to be chosen in such a way that two shapes are
considered similar if and only if one shape can be approximated by translation
and scaling of the other. However, this may cause an issue – when the shape is
close to a “flat”, small noise can cause it to become similar to other shapes.
It is argued that there is an inherent concept of flatness in the domain of
interest. For instance, in influenza when the number of hospitalizations is
stable at a very low value, that shape is to be considered flat and not to be
considered similar to any other shape when hospitalizations are higher.
Therefore, a desirable property is the following.

######  Property 1 (Closeness Preservation).

Two vectors have similar representation, if and only if (i) none of the
vectors are “almost flat” and one can be approximately obtained by scaling and
translating the other, or (ii) both vectors are “almost flat”.

They propose an approach that first identifies how similar a shape is to what
we could consider “flat”, and then updates the similarities of the shape with
respect to other shapelets. For some constants $m_{0},\beta\geq 0$, define
“flatness” as $\phi=\exp(-\beta(m-m_{0})),$ if $m>m_{0}$, otherwise $\phi=1$.
Here $m$ is the average absolute slope of the vector $\mathbf{x}$ whose
shapelet-space representation is desired, i.e., if
$\mathbf{x}=(x_{1},x_{2},x_{3},x_{4})$, then
$m=(|x_{2}-x_{1}|+|x_{3}-x_{2}|+|x_{4}-x_{3}|)/3$. The constant $m_{0}$
enforces that a vector with a very small average absolute slope is considered
flat and receives a $0$ similarity in all other dimensions. The constant
$\beta$ represents how quickly above the threshold $m_{0}$, the “flatness”
should reduce. Now, the co-ordinates of shapelet-space representation are
defined as

$sim(\mathbf{x},\mathbf{s_{i}})=\left\\{\begin{array}[]{@{}cl}2\phi-1,&\text{if
}\mathbf{s_{i}}\text{ is ``flat''},\\\
(1-\phi)corr(\mathbf{x},\mathbf{s_{i}}),&\text{otherwise}.\end{array}\right.$

It is shown that this definition satisfies Closeness Preservation (Property 1)
with $w$ or more shapelets including the “flat” shapelet. We prove that $w$
shapelets are not only sufficient but necessary to satisfy this property
(Theorem 2). We use Shapelet-space Representations of moving windows on the
given time-series to capture local trends over time.

#### Dynamic Time Warping

Dynamic Time Warping (DTW) is a distance measure between two time-series that
allows warping (local stretching and compressing) of the time component so
that the two time-series are optimally aligned. Given two time-series
$\mathbf{a}=[a(1),a(2),\dots]$ and $\mathbf{b}=[b(1),b(2),\dots]$, the
objective of DTW is to minimize $\sum_{i\leftrightarrow
j}\mathcal{D}(a(i),b(j)$, for some distance measure $\mathcal{D}$, and where
$i\leftrightarrow j$ represents aligning index $i$ of $\mathbf{a}$ with index
$j$ of $\mathbf{b}$. The alignment is done under some constraints – (1) if
$a(i)$ and $b(j)$ are aligned then $a(i+1)$ cannot be aligned with
$b(j^{\prime})$ for some $j^{\prime}<j$. (2) Every index is present in at
least one alignment. (3) The first index of both time-series are aligned with
each other. (4) The last index of both time-series are aligned with each
other. Further, a window constraint can be added (Ratanamahatana and Keogh
2004) suggesting that indices $i$ and $j$ can only be aligned if $|i-j|\leq
w$, for some non-negative integer $w$.

#### Time-series Ensemble

In applications like epidemic projection, multiple trajectories are generated
using different methods or different initializations. Then, an ensemble is
created which is then communicated to the public and policy makers (US SMH
2020). These ensembles are designed to capture the mean value at time $t$,
i.e., for $n$ trajectories $\mathbf{a}_{1},\dots,\mathbf{a}_{n}$, where
$\mathbf{a}_{i}=[{a}(1),\dots,a(n)]$ the ensemble is
$\bar{a}(t)=\sum_{i=1}^{n}a(t)/n$. As an unintended consequence, informative
aspects of individual trajectories may be lost. As an example, consider Figure
2. Two models produce almost identical projections but they are shifted in
time, and they have the same peak. The ensemble produces a trajectory that has
a peak that is significantly lower and wider than individual models. In public
health communication, this can cause a misjudgment of the severity of the
epidemic. While the ensemble correctly summarizes the expected outcome at time
$t$, the reader tends to infer other information such as peak timing and
severity. Our similarity measure can be used to build ensembles that better
preserve the properties of the individual models.

Figure 2: Failure of the mean ensemble in capturing the properties of
individual time-series – much lower peak.

#### Shapelets

In time-series literature, “shapelets” have been used to refer to informative
motifs that occur in time-series (Ye and Keogh 2009). A feature vector for
time-series can then be constructed by similarity of the best matching
subsequence of the time-series to these motifs. The motifs are selected based
on their representativeness of a class. In contrast, we use the term shapelet
as a pre-determined shape of interest coming from the domain. We prove that a
specific class of shapelet sets and similarity measures is needed to develop a
representation to satisfy the closeness-preserving property. We encode all
local trends of the time-series into a matrix representation, which is
compared using DTW.

###  2.2 Related Similarity Measures

While many similarity measures for time-series have been proposed in the
literature (Jeong and Jayaraman 2015; Lines and Bagnall 2015; Dhamo,
Ismailaja, and Kalluçi 2015), the closest work to our proposed measure DTW+S
is ShapeDTW (Zhao and Itti 2018). It was developed as an alignment algorithm
that captures point-wise local structures and preferentially aligns similarly-
shaped structures. It does so by generating shape descriptors that include the
raw sequence, piece-wise aggregation, Discrete Wavelet Transform (Van Fleet
2019), slopes, and derivatives. A key distinction from our approach is that we
utilize a set of shapelets that are shapes of interest in the desired
application, and hence our representation is directly interpretable. Further,
we present theoretical results on the closeness-preserving characteristics of
our approach. While shapeDTW is designed to be general-purpose by constructing
a variety of shape descriptors, our approach is particularly designed for
applications where the trend is more important than the scale. We later
demonstrate that our approach still outperforms shapeDTW for classification on
almost half of the 64 datasets considered (Section 4.3).

##  3 Methodology

Our approach111Code is available at:https://github.com/scc-usc/DTW˙S˙apps
consists of two major steps. First, we capture local trends (shapes) of the
time-series. To do so, we extend the notion of Shapelet-space Representation
to a time-series with a sliding window.

######  Definition 3 (Shapelet-space Representation - Time-series).

Given a time-series $\mathbf{a}\in\mathbb{R}^{T_{1}}$, a window $w$, and a
Shapelet-space Transformation $f:\mathbb{R}^{w}\rightarrow\mathbb{R}^{d}$, the
Shapelet-space Representation of $\mathbf{a}$ is the matrix
$\mathbf{A}\in\mathbb{R}^{d\times(T_{1}-w+1)}$ whose $i^{th}$ column is the
Shapelet-space Representation of the vector $(a_{i},\dots,a_{i+w-1})$.

This matrix encodes how the time-series changes over time in an interpretable
manner. Given two time-series, $\mathbf{a}\in\mathbb{R}^{T_{1}}$ and
$\mathbf{b}\in\mathbb{R}^{T_{2}}$, we first find there Shapelet-space
Representations – the matrices $\mathbf{A}\in\mathbb{R}^{d\times(T_{1}-w+1)}$,
and $\mathbf{B}\in\mathbb{R}^{d\times(T_{2}-w+1)}$. Each column (of size $d$)
of these matrices is obtained by sliding a $w$-length window on the respective
time-series and obtaining its $d$-dimensional Shapelet-space Representation
(SSR).

###  3.1 Choosing the Shapelet-Space

While Srivastava et. al. provide some indication of how to choose the set of
shapelets, they only prove that for vectors with $w$ elements, $w$ shapelets
are sufficient. For completeness, we present a proof here and then show that
$w$ shapelets are indeed necessary. Let
$f:\mathbb{R}^{w}\rightarrow\mathbb{R}^{d}$ be a shapelet transformation
obtained by a set of linearly independent vectors
$\mathbf{s_{1}},\dots,\mathbf{s}_{d-1}$ and the flat vector $\mathbf{s}_{0}$.
Consider two vectors $\mathbf{x}$ and $\mathbf{y}$ of length $w$. Suppose
$\mathbf{{x^{\prime}}}$ and $\mathbf{{y^{\prime}}}$ represent the
corresponding normalized vectors obtained as:
$\mathbf{x^{\prime}}=\frac{\mathbf{x}-\mu_{\mathbf{x}}}{\|\mathbf{x}\|}\mbox{
and
}\mathbf{y^{\prime}}=\frac{\mathbf{y}-\mu_{\mathbf{y}}}{\|\mathbf{y}\|}\,,$
where $\mu_{\mathbf{x}}$ and $\mu_{\mathbf{y}}$ are the mean of elements in
the vectors $\mathbf{x}$ and $\mathbf{x}$, respectively.

######  Theorem 1.

Property 1 is satisfied with any set of $w-1$ linearly independent shapelets
and the “flat” shapelet, i.e., with this choice
$\|f(\mathbf{x})-f(\mathbf{y})\|\leq\epsilon$ iff (i) both $\mathbf{x}$ and
$\mathbf{y}$ are “almost” flat, or (ii)
$\|\mathbf{x^{\prime}}-\mathbf{y^{\prime}}\|\leq\delta$, for some small
$\epsilon$ and $\delta$.

######  Theorem 2.

At least $w-1$ linearly independent shapelets are necessary with the “flat”
shapelet to satisfy property 1.

###  3.2 Time-series Similarity: DTW+S

Recall that our goal is to consider two time-series similar if they have
similar shapes around the same time, but not necessarily at the same time. To
allow this, we use Dynamic Time Warping where the distance between aligning
column $i$ with column $j$ is given by the square of the Euclidean distance
between the $i^{th}$ column of $\mathbf{A}$ and $j^{th}$ column of
$\mathbf{B}$, i.e., $\|\mathbf{A}[:,i]-\mathbf{B}[:,j]\|^{2}$. Figure 9
provides a visualization of SSR matrices. Details of the interpretation are
provided in Section 5. The choice of warping window $\tau$ depends on the
application. For a classification task, it can be treated as a hyper-parameter
and identified through validation on a held-out set. For epidemics, suppose,
two models generate projections under the same assumptions, they may be
predicting multiple peaks. Far-away peaks may refer to different events (e.g.,
two different variants causing two waves). However, peaks that occur 4-5 weeks
apart across models may be referring to the same event. Therefore, $\tau=5$
weeks would be a reasonable choice.

###  3.3 Clustering and Classification

We can use DTW+S to cluster time-series with any clustering or classification
algorithm that allows customizable distance measures. As a demonstration, we
use agglomeration clustering (Day and Edelsbrunner 1984) on the distance
matrix where each entry $\mathcal{D}(\mathbf{a}_{i},\mathbf{a}_{i^{\prime}})$
is the DTW+S distance of time-series $i_{1}$ and $i_{2}$. The algorithm starts
with each time-series as its own cluster, and then recursively merges clusters
greedily based on the distances. We use Silhouette Coefficient (Zhou and Gao
2014) to decide the optimal number of clusters. For classification, we use the
$1$-nearest neighbor method (Petitjean et al. 2014). The choice was made so
that the decisive factor in correct classification is the distance measure.
That is, two time-series that are closest to each other belong to the same
class. This is also a popular way of evaluating distance measures between
time-series (Mueen, Keogh, and Young 2011).

###  3.4 Ensemble Generation

The existing ensemble methods are designed to aggregate individual projections
over time, thus measuring the scale (e.g., number of hospitalizations) at time
$t$. They are not designed to aggregate when will an event (e.g., a peak) take
place. However, a viewer tends to interpret both the scale and timing from the
ensemble plot. We are interested in – given $n$ time-series,
$\mathbf{a}_{i}=[a_{i}(1),a_{i}(2),\dots,a_{i}(T)],i\in\\{1,\dots,n\\}$, find
an “ensemble” time-series that captures the aggregate behavior in both time
and scale. To address this, we assume that each trajectory tries to estimate a
sequence of latent “events”. With this perspective, for some sequence of event
$e_{1},e_{2},\dots$, a time-series captures the timing of $e_{j}$ and its
scale. Therefore, the time-series can be interpreted as
$\mathbf{a}_{i}=[(t_{i}(e_{1}),a_{i}(e_{1})),(t_{i}(e_{2}),a_{i}(e_{2})),\dots]$.
For any given event $e_{j}$, the aggregate time-series can be obtained by
averaging both the timing and the severity dimensions of the individual time-
series:

$\left(\bar{t}(e_{j}),\bar{a}(e_{j})\right)=\left(\frac{\sum_{i}t_{i}(e_{j})}{n},\frac{\sum_{i}a_{i}(e_{j})}{n}\right)$
(1)

However, we do not observe these “events” explicitly. We define an event to be
reflected in the time-series by a local trend. When two time-series are
aligned by DTW+S, each alignment corresponds to an event. Formally, in the
shapelet space representation $\mathbf{A}$ and $\mathbf{B}$, if columns
$\tau_{1}$ and $\tau_{2}$ are aligned, then the local trend at time
$[\tau_{1},\tau_{1}+w-1]$ in time-series $\mathbf{a}$ and that at time
$[\tau_{2},\tau_{2}+w-1]$ in time-series $\mathbf{b}$ are defined to be
corresponding to the same “event”. Suppose we use DTW+S to align $n$
projections. Then, each projection $i$ contributes one point
$(t_{i}(j),a_{i}(t_{j}))$ for each alignment $j$. This results in a set of
points, one for each alignment $j$, using Equation 1. Finally, if desired, we
can interpolate these points to estimate the value of $\bar{a}(t)$ for
$t\in\\{1,2,\dots,T\\}$. Note that this approach is based on the following
assumptions. First, each time-series has a similar sequence of shapes but may
differ in timing and severity/scale. Second, the interpolation assumes
smoothness in the desired ensemble.

Figure 3 demonstrates this approach for two time-series (in black solid line)
that have two peaks each with different scales. We compare our approach
against the mean ensemble and DTW (without SSR). Note that the mean ensemble
results in a small second peak which is closer to the smaller peak among the
input time-series. Further, its timing is biased towards the larger peak. The
DTW ensemble results in one large peak by aggregating scale and timing of the
first peak of one and the second peak of the other time-series. The DTW+S
ensemble results in two peaks as expected, where each peak correctly avergaes
the corresponding timing and scale of the input time-series.

Figure 3: Applying mean, DTW, and DTW+S to develop ensemble of two time-
series.

While similar aggregation has been discussed in the literature (Gupta et al.
1996; Petitjean, Ketterlin, and Gançarski 2011), two key differences exist.
First, our application is motivated by visual interpretation of “events”, such
as when the epidemic peaks. Second, our approach uses an interpretable shape-
based measure instead of directly using the Euclidean distance on time-series.
This allows us to define an “event”.

Optimally aligning multiple time-series is NP-Hard with some polynomial time
approximation algorithms (Petitjean, Ketterlin, and Gançarski 2011). Exploring
better algorithms for addressing this is beyond the scope of this work. Our
focus is on the similarity measure, and so, we take a simple approach for the
sake of demonstration. We pick one of the time-series as the “base” and
calculate pairwise alignment with all other time-series. While the choice of
the “base” time-series impacts the results, we experimentally demonstrate that
when the individual time-series have similar shapes, the impact on the
resulting ensemble is small.

Figure 4: Comparison of clustering results obtained from DTW+S against other
distance measures. DTW+S with Euclidean (default) and cosine distance produces
reasonable clustering. All other measures mix different patterns into one
cluster.

##  4 Experiments

We conduct a series of experiments to demonstrate the utility of DTW+S.
Specifically, we wish to demonstrate the following: (1) DTW+S results in a
more reasonable clustering compared to several other approaches. (2) DTW+S
leads to a more reasonable ensemble that captures the scale and timing of
events. (3) DTW+S produced better classification results for many
classification tasks, outperforming DTW. In all of our experiments, unless
stated otherwise, we used the following set of shapelets: (i) ‘increase’:
$[1,2,3,4]$, (ii) ‘surge’: $[1,2,4,8]$, (iii) ‘peak’: $[1,2,2,1]$, and (iv)
‘flat’: $[0,0,0,0]$. According to Theorems 1 and 2, these shapelets satisfy
Property 1. These were chosen because they are easily interpretable,
particularly in the domain of epidemics. Some other sets of shapelets that
satisfy Property 1 were also tried, and their results were not significantly
different.

(a) Selected similar time-series

(b) All time-series

Figure 5: DTW+S ensemble: Shape and scale (e.g., peak size) are better
captured compared to the mean ensemble.

###  4.1 Clustering: A Qualitative Evaluation

We consider time-series projections for weekly influenza hospitalization for a
US state by a model from Influenza Scenario Modeling Hub (US SMH 2022). It has
75 time-series, each corresponding to different choices of parameters and
initialization. We calculated the dissimilarity matrix (all pair distances)
using the following. (1) DTW+S: our method with infinite window for alignment;
(2): DTW+S (cos): same as DTW+S, except that cosine distance is used instead
of Euclidean for aligning SSRs; (3) DTW, normalized: Applying DTW after
normalizing all time-series to zero mean and unit variance – a common
normalization technique used with DTW (Chen et al. 2015); (4) DTW: DTW without
any transformation or normalization; (5) Euclidean, normalized: Euclidean
distance without any time warping on standard normal time-series; and (6)
Shapelet-only: Euclidean distance on the SSR without any time-warping. For
DTW+S, we generate hierarchical clusters with the number of clusters selected
using the Silhouette Coefficient as described in Section 3.3. We use the same
number of clusters for clustering using each of the above dissimilarity
measures.

Figure 4 shows the results of clustering from each of the distance measures.
We observe that DTW+S produces four clusters with similarly shaped time-
series. DTW with standard normalization mixes clusters 1, 2, and 4. The
Shapelet-only measure mixes clusters 1 and 3. Omitted for brevity, DTW+S (cos)
produces the same clustering (different ordering). DTW without normalization
does not produce any discernable pattern in the trends and instead seems to
group together those time-series that have similar peaks heights. Euclidean
distance with standard normalization mixes clusters 1, 2 and 4. Note that
Shapelet transformation is not sufficient to capture similar time-series due
to not being flexible across time. On the other hand, DTW with simple standard
normalization cannot capture similar trends that occur at different scales.
However, when they are combined in DTW+S, they produce reasonable clustering.

###  4.2 Ensembling

We pick all the time-series belonging to one of the clusters as identified
based on the distance measure DTW+S in Section 4.1, and attempt to create an
ensemble. Since all these time-series have similar shapes over time, we expect
that our ensemble based on DTW+S will be able to capture the scale and timing
behavior of the constituent time-series. As a baseline, we use the traditional
method – taking the mean along each time $t$. We compare this against our
approach where the alignment is obtained by DTW+S. Since our approach requires
selecting a “base”, we run our ensemble multiple times, once for each time-
series as the “base”.

The results are shown in Figure 5(a). First, note that the different ensembles
generated by different “base” time-series are very close to each other.
Second, all of them have a peak larger than the peak obtained by the mean
ensemble. Among the 26 time-series, the mean peak size (maximum value per
time-series) is 1219. The mean ensemble highly underestimates this as 1060. On
the other hand, the ensembles based on DTW+S produce peaks ranging from 1152
to 1219. While it is difficult to assess how the ensemble should look when the
individual time-series have different sequences of shapes, we attempt to get
an ensemble using our DTW+S approach. Figure 5(b) shows the result. Since the
approach is not designed for creating ensembles with differently shaped time-
series, there is more diversity in the ensemble depending on the choice of
“base” time-series. Yet, we find that DTW+S is able to capture the size of the
peak. The mean peak size of all the time-series is 1079. The peak of the mean
ensemble is significantly lower at 681, while our DTW+S ensembles produce peak
sizes of 891 to 1066.

###  4.3 Classification

For classification, we use 64 datasets available at UCR Time Series
Classification 2015 Archive (Chen et al. 2015). Since DTW+S is based on the
distance between local trends, we ignored very large time-series where trends
would be difficult to infer visually. Handling long time-series may require
some sampling and using larger shapelets. Further, an analysis of our approach
on multiple large datasets will require more optimized implementation. These
analyses and optimizations are beyond the scope of this work. Therefore, we
removed all the datasets where the length of the time-series was more than 800
and the number of training data instances where more than 700, giving us 64
datasets out of 86.

Figure 6: Performance of DTW+S on 64 datasets.

(a) better (0.0017) vs DTW (0.13)

(b) worse (0.23) vs DTW (0.067)

(c) worse (0.35) vs DTW (0.0044)

Figure 7: Section of time-series color-coded to show the different classes.
(a) DTW+S picks up small local trends that are not captured by DTW alone. (b)
The difference in the classes is the scale rather than the shape in certain
parts of the time-series, making it not a desirable dataset for DTW+S. (c) The
time-series possess noise preventing DTW+S from identifying trends. Figure 8:
Results obtained by DTW+S with smoothing. (a) Improvement on many datasets
where DTW+S was worse than DTW. (b) Comparison against shapeDTW.

For each dataset, we find the 1-nearest neighbor for each instance of test
time-series in the training set using DTW+S and assign its class. Then, we
evaluate our approach using error defined as the fraction of
misclassification, which is the commonly used evaluation method for these
datasets (Petitjean et al. 2014). We treat the warping window $\tau$ as a
hyperparameter. We use leave-one-out cross-validation to identify $\tau$ as a
fraction of the length of the time-series $T$ from a set of values –
$\tau=\\{0,0.01T,0.02T,\dots,0.07T\\}$. We compare our results with the
reported best performance of DTW (Chen et al. 2015). The results are presented
in Figure 6. In the scatter plot, each point represents errors on a dataset.
The blue line represents the line $y=x$, i.e., when DTW+S has the same error
as that of DTW. A point lying below (and to the right) of this line indicates
that DTW+S error was lower than DTW error. We observe that DTW+S outperforms
DTW on 57.7% datasets. The two measures lead to similar errors for many
datasets (along the $y=x$ line). “Corr only” represents the DTW+S measure
obtained by ignoring the “flat” shapelet. In this case, DTW+S reduces to the
set of Person correlations with the three other shapelets. DTW+S (corr) only
outperforms DTW in 39.1% datasets. Additionally, it produces some large
errors. Correlation ignores scale completely, and small fluctuations that are
not necessarily useful patterns, but noise can cause the measure to consider
it similar to some other significant patterns. Thus, the flatness dimension
has a significant contribution to the performance of DTW+S.

We note that DTW+S does not outperform DTW on all datasets. This is expected
as DTW+S focuses more on the shapes rather than the scale. Figure 7 shows
examples where DTW+S and DTW have significantly different performances. For
the dataset in Figure 7(a), DTW+S has an error of 0.0017 while DTW has an
error of 0.13. This is because DTW+S picks up small local trends (a spike
around time 30) present in one class and absent in another class. This is not
captured by DTW alone. For the dataset in Figure 7(b), DTW+S has an error of
0.23 while DTW has a much lower error of 0.07. For this dataset, the
difference in the classes is the scale rather than the shape in certain parts
of the time-series. DTW is able to identify this distinction, making it a less
desirable dataset for DTW+S.

#### Smoothing

Another type of dataset that would be undesirable for DTW+S is that where the
time-series have high noise (Figure 7(c)). This noise will impact the
identification of $\beta$ for the flatness parameter and the identification of
local trends. One way to address this is to smooth the time-series before
finding the Shapelet-space Transformation. While a domain expert may choose a
reasonable method for smoothing, we use a moving average method with the
window size chosen with leave-one-out cross-validation from the set
$\\{0,0.1T,0.2T,0.4T\\}$. The results are shown in Figure 8. The first plot
shows that allowing smoothness generally improves the error (many datasets
fall to the bottom right). For a very small number of datasets validation
results seem to pick a smoothing window that results in worse performance on
the test set. In practice, this could be mitigated by having a larger training
set. The second plot of Figure 8 shows that the smoothing significantly brings
down the error for some datasets (e.g., the three circles on the left of the
plot drop close to zero). As an example, the dataset in Figure 7(c) for which
DTW+S was significantly worse (error of 0.35) compared to DTW (0.0044),
smoothing results in an error dropping to 0.0022. Finally, the third plot in
Figure 8 compares our approach against shapeDTW (Zhao and Itti 2018). We
select “HOG1D” version of shapeDTW as it performs the best for this collection
of datasets. Without smoothing, there are a few datasets where DTW+S is much
worse than shapeDTW (higher in the plot). After smoothing, most datasets
accumulate around $y=x$ line.

##  5 Discussion

##### Interpretability

A key advantage of our approach is interpretability. Since the SSR is
determined by the similarity of the given trend with respect to pre-defined
shapes of interest, one can easily make sense of the representation. This is
particularly useful for application domains where there exist certain shapes
of interest (e.g., increase and peak in public health) and there is resistance
towards adopting black-box approaches. Figure 9 shows the SSR of two samples
each from two classes of a dataset. This is the dataset corresponding to
Figurer 7(a), where we observed small peaks appearing in one of the classes.
Based on the SSR of the samples, we observe that samples for class 1 show a
bright yellow (high value) corresponding to dimension 2. On the other hand,
samples from class 2 have a dull yellow (lower value) for the same dimension.
This dimension corresponds to the shapelet “peak” $=[1,2,2,1]$, thus
suggesting that a peak around the $t=25$ makes sample 1 in class 1 more
similar to sample 2 in class 1 compared to the samples in another class.

Figure 9: Interpreting the Shapelet Space Representation.

##### Limitations

Our approach is not designed for general-purpose classification or encoding,
particularly, where shapes have little impact compared to the scale.
Furthermore, while warping windows and smoothing parameters can be set through
validation, the best utilization of DTW+S would require some domain knowledge
to understand their appropriate setting and the choice of shapelets. However,
Theorems 1 and 2 act as guidelines to ensure that the chosen shapelets satisfy
the desired property of closeness preservation. Another limitation is the
implementation – currently, we use $\mathcal{O}(T^{2})$ time and space for DTW
on the distance matrix obtained from SSR. In future work, we will explore
existing optimizations of DTW (Keogh and Pazzani 2000).

##  6 Conclusion

We have proposed a novel interpretable distance measure for time-series that
looks for a sequence of similar trends occurring around the same time. It can
capture local trends in a representation that is closeness preserving. We have
demonstrated that our approach DTW+S, which applies DTW on our SSR matrices,
results in better clustering, which cannot be achieved by DTW or SSR alone. We
have developed an ensemble method using DTW+S that captures both the aggregate
scale and timing of the individual time-series significantly better than the
currently used mean ensemble. We have shown that DTW+S can result in better
classification compared to other measures for a large number of datasets,
particularly those where local trends play a key role.

## References

  * Chen et al. (2015) Chen, Y.; Keogh, E.; Hu, B.; Begum, N.; Bagnall, A.; Mueen, A.; and Batista, G. 2015\.  The UCR Time Series Classification Archive.  www.cs.ucr.edu/~eamonn/time˙series˙data/.
  * Day and Edelsbrunner (1984) Day, W. H.; and Edelsbrunner, H. 1984.  Efficient algorithms for agglomerative hierarchical clustering methods.  _Journal of classification_ , 1(1): 7–24.
  * Dhamo, Ismailaja, and Kalluçi (2015) Dhamo, E.; Ismailaja, N.; and Kalluçi, E. 2015.  Comparing the efficiency of CID distance and CORT coefficient for finding similar subsequences in time series.  In _Sixth International Conference ISTI_ , 5–6.
  * Divasón and Aransay (2013) Divasón, J.; and Aransay, J. 2013.  Rank-nullity theorem in linear algebra.  _Archive of Formal Proofs_.
  * European CDC (2022) European CDC. 2022.  European COVID-19 Scenario Hub.  https://github.com/covid19-forecast-hub-europe/covid19-scenario-hub-europe.
  * Gupta et al. (1996) Gupta, L.; Molfese, D. L.; Tammana, R.; and Simos, P. G. 1996.  Nonlinear alignment and averaging for estimating the evoked potential.  _IEEE transactions on biomedical engineering_ , 43(4): 348–356.
  * Jeong and Jayaraman (2015) Jeong, Y.-S.; and Jayaraman, R. 2015.  Support vector-based algorithms with weighted dynamic time warping kernel function for time series classification.  _Knowledge-based systems_ , 75: 184–191.
  * Keogh and Pazzani (2000) Keogh, E. J.; and Pazzani, M. J. 2000.  Scaling up dynamic time warping for datamining applications.  In _Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining_ , 285–289.
  * Lines and Bagnall (2015) Lines, J.; and Bagnall, A. 2015.  Time series classification with ensembles of elastic distance measures.  _Data Mining and Knowledge Discovery_ , 29: 565–592.
  * Mueen, Keogh, and Young (2011) Mueen, A.; Keogh, E.; and Young, N. 2011.  Logical-shapelets: an expressive primitive for time series classification.  In _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 1154–1162.
  * Müller (2007) Müller, M. 2007.  Dynamic time warping.  _Information retrieval for music and motion_ , 69–84.
  * Petitjean et al. (2014) Petitjean, F.; Forestier, G.; Webb, G. I.; Nicholson, A. E.; Chen, Y.; and Keogh, E. 2014.  Dynamic time warping averaging of time series allows faster and more accurate classification.  In _2014 IEEE international conference on data mining_ , 470–479. IEEE.
  * Petitjean, Ketterlin, and Gançarski (2011) Petitjean, F.; Ketterlin, A.; and Gançarski, P. 2011.  A global averaging method for dynamic time warping, with applications to clustering.  _Pattern recognition_ , 44(3): 678–693.
  * Ratanamahatana and Keogh (2004) Ratanamahatana, C. A.; and Keogh, E. 2004.  Making time-series classification more accurate using learned constraints.  In _Proceedings of the 2004 SIAM international conference on data mining_ , 11–22. SIAM.
  * Srivastava, Singh, and Lee (2022) Srivastava, A.; Singh, S.; and Lee, F. 2022.  Shape-based Evaluation of Epidemic Forecasts.  In _2022 IEEE International Conference on Big Data (Big Data)_ , 1701–1710. IEEE.
  * US SMH (2020) US SMH. 2020.  COVID-19 Scenario Modeling Hub.  https://github.com/midas-network/covid19-scenario-modeling-hub.
  * US SMH (2022) US SMH. 2022.  Flu Scenario Modeling Hub.  https://fluscenariomodelinghub.org/.
  * Van Fleet (2019) Van Fleet, P. J. 2019.  _Discrete wavelet transformations: An elementary approach with applications_.  John Wiley & Sons.
  * Ye and Keogh (2009) Ye, L.; and Keogh, E. 2009.  Time series shapelets: a new primitive for data mining.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 947–956.
  * Zhao and Itti (2018) Zhao, J.; and Itti, L. 2018.  shapedtw: Shape dynamic time warping.  _Pattern Recognition_ , 74: 171–184.
  * Zhou and Gao (2014) Zhou, H. B.; and Gao, J. T. 2014.  Automatic method for determining cluster number based on silhouette coefficient.  In _Advanced materials research_ , volume 951, 227–230. Trans Tech Publ.

## Supplementary Material

##  Appendix A Proofs

######  Theorem 3.

Property 1 is satisfied with any set of $w-1$ linearly independent shapelets
and the “flat” shapelet, i.e., with this choice
$\|f(\mathbf{x})-f(\mathbf{y})\|\leq\epsilon$ iff (i) both $\mathbf{x}$ and
$\mathbf{y}$ are “almost” flat, or (ii)
$\|\mathbf{x^{\prime}}-\mathbf{y^{\prime}}\|\leq\delta$, for some small
$\epsilon$ and $\delta$.

###### Proof.

Suppose $\|f(\mathbf{x})-f(\mathbf{y})\|\leq\epsilon$.

If both vectors are approximately flat then, without loss of generality, we
can assume that $\phi_{x}\geq\phi_{y}\geq 1-\varepsilon$, for some small
$\varepsilon$. Then, along the flat dimension,
$|2(\phi_{x}-1)-2(\phi_{y}-1)|^{2}\leq 4(1-(1-\varepsilon))^{2}\leq
4\varepsilon^{2}$. And, along any other dimension,

$\displaystyle|(1-\phi_{x})\mathbf{s^{\prime}}^{T}\mathbf{x^{\prime}}$
$\displaystyle-(1-\phi_{y})\mathbf{s^{\prime}}^{T}\mathbf{y^{\prime}}|^{2}$
$\displaystyle\leq|(1-\phi_{y})\cdot 1-(1-\phi_{x})\cdot(-1)|^{2}$
$\displaystyle=|2-(\phi_{x}+\phi_{y})|^{2}\leq|2-2(1-\varepsilon)|^{2}\leq
4\varepsilon^{2}.$

So, $\|f(\mathbf{x})-f(\mathbf{y})\|^{2}\leq
4(w-1)\varepsilon^{2}+4\varepsilon=4w\varepsilon^{2}=\epsilon^{2}$, where
$\varepsilon=\epsilon/(2\sqrt{w})$.

Now, suppose that both vectors are not “almost” flat and
$\phi_{x}\geq\phi_{y}$. Let $\epsilon^{2}=\sum_{i}\epsilon^{2}_{i}$, where
$\epsilon_{i}$ is the difference in the $i^{th}$ dimension of
$f(\mathbf{x})-f(\mathbf{y})$. Then, along the dimension corresponding to
$\mathbf{s}_{0}$:

$|(2\phi_{x}-1)-(2\phi_{y}-1)|\leq\epsilon_{0}\implies\phi_{\mathbf{x}}\leq\phi_{\mathbf{y}}+\epsilon_{0}/2.$
(2)

Now, since $\phi_{y}\leq\phi_{x}\leq\phi_{y}+\epsilon_{0}/2$, then a small
$\phi_{y}$ would imply that $\phi_{x}$ is also small. Therefore, both
$\phi_{x}$ and $\phi_{y}$ are not small.

Now, along any other dimension $i$,

$\displaystyle\epsilon_{i}$
$\displaystyle=|(1-\phi_{x})\mathbf{s^{\prime}}^{T}\mathbf{x^{\prime}}-(1-\phi_{y})\mathbf{s^{\prime}}^{T}\mathbf{y^{\prime}}|$
$\displaystyle=|(1-\phi_{x})\mathbf{s^{\prime}}^{T}(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})+(1-\phi_{x})\mathbf{s^{\prime}}^{T}\mathbf{y^{\prime}}-(1-\phi_{y})\mathbf{s^{\prime}}^{T}\mathbf{y^{\prime}}|$
$\displaystyle=|(1-\phi_{x})\mathbf{s^{\prime}}^{T}(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})+(\phi_{y}-\phi_{x})\mathbf{s^{\prime}}^{T}\mathbf{y^{\prime}}|$
$\displaystyle\geq|(1-\phi_{x})\mathbf{s^{\prime}}^{T}(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})|-\epsilon_{0}/2\,.$

And thus,

$\displaystyle|(1-\phi_{x})\mathbf{s^{\prime}}^{T}(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})|$
$\displaystyle\leq\epsilon_{i}+\epsilon_{0}/2$
$\displaystyle\implies|\mathbf{s^{\prime}}^{T}(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})|$
$\displaystyle\leq\frac{\epsilon_{i}+\epsilon_{0}/2}{1-\phi_{x}}\,,\forall
i\in\\{1\dots w-1\\}\,.$ (3)

Additionally, we note that due to the normalization,

$\mathbf{1}^{T}\mathbf{y^{\prime}}=\mathbf{1}^{T}\mathbf{x^{\prime}}=0\implies\mathbf{1}^{T}(\mathbf{y^{\prime}}-\mathbf{x^{\prime}})=0\,,$
(4)

where $\mathbf{1}$ is the vector of all ones. Now consider a matrix $C_{w}$
with $w$ rows whose $i^{th}$ row is given by $\mathbf{s^{\prime}}_{i}$, for
$i\leq w-1$ and $w^{th}$ row is $\mathbf{1}$.

$C_{w}(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})=\mathbf{e}\,,$ (5)

where $i^{th}$ row of $\mathbf{e}$ for $i<w$ is given by some
$|e_{i}|\leq\frac{\epsilon_{i}+\epsilon_{0}/2}{1-\phi_{x}}$ and the $w^{th}$
entry is 0. We show that $\mathbf{1}$ is linearly independent of all the $w-1$
other rows. Recall that $\mathbf{s^{\prime}}_{i}$ are all $\mu$-normalized,
and so $\mathbf{1}^{T}\mathbf{s^{\prime}}_{i}=0,\forall i$. Therefore, all $w$
rows of $C_{w}$ are linearly independent, i.e., $C_{w}$ is full rank and
invertible. So, we have

$\displaystyle\mathbf{x^{\prime}}-\mathbf{y^{\prime}}$
$\displaystyle=C_{w}^{-1}\mathbf{e}\implies\|\mathbf{x^{\prime}}-\mathbf{y^{\prime}}\|=\|C_{w}^{-1}\mathbf{e}\|$
$\displaystyle\leq\|C_{w}^{-1}\|\|\mathbf{e}\|\leq\|C_{w}^{-1}\|\sqrt{\sum_{i=1}^{w-1}\left(\frac{\epsilon_{i}+\epsilon_{0}/2}{1-\phi_{x}}\right)^{2}}=\delta\,,$
(6)

which is small for finite $\|C_{w}^{-1}\|$ and small $\epsilon_{i},\forall
i\geq 0$.

∎

######  Theorem 4.

At least $w-1$ linearly independent shapelets are necessary along with the
“flat” shapelet to satisfy property 1.

###### Proof.

We will show that choosing $w-2$ independent shapelets results in at least one
$\mathbf{y}\neq\mathbf{x}$, such that $f(\mathbf{x})=f(\mathbf{y})$ and none
of them are flat, i.e., $\phi_{x},\phi_{y}<1$. Since the vectors are equal
across all dimensions, $2\phi_{x}-1=2\phi_{y}-1\implies\phi_{x}=\phi_{y}$.
Therefore, for all other dimensions:

$(1-\phi_{x})\mathbf{s_{i}^{\prime}}^{T}\mathbf{x^{\prime}}=(1-\phi_{y})\mathbf{s_{i}^{\prime}}^{T}\mathbf{y^{\prime}}\implies\mathbf{s^{\prime}_{i}}^{T}(\mathbf{y^{\prime}}-\mathbf{x^{\prime}})=0\,.$
(7)

Consider the matrix $C_{w-1}$ whose $i^{th}$ row for $i\leq w-2$ is
$\mathbf{s^{\prime}}_{i}$ and $(w-1)^{th}$ row is $\mathbf{1}$. Since all of
its rows are independent, its rank is $w-1$. Using rank-nullity theorem
(Divasón and Aransay 2013), its nullity is 1. Therefore, $\exists$ a vector
$\mathbf{u}\in\mathbb{R}^{w}$, with $\|\mathbf{u}\|=1$ such that,

$\mathbf{y^{\prime}}-\mathbf{x^{\prime}}=p\mathbf{u}\implies\mathbf{y^{\prime}}=\mathbf{x^{\prime}}-p\mathbf{u}$
(8)

We will prove that there exists a solution to the above other than the trivial
solution $p=0$. First, taking the square of the norm of both sides of Equation
8

$\displaystyle\|\mathbf{y^{\prime}}\|^{2}$
$\displaystyle=\|\mathbf{x^{\prime}}+p\mathbf{u}\|^{2}\implies
1=\|\mathbf{x^{\prime}}\|^{2}+p^{2}\|\mathbf{u}\|^{2}+2p\mathbf{u}^{T}\mathbf{x^{\prime}}$
$\displaystyle\implies 1$
$\displaystyle=1+p(p+2\mathbf{x^{\prime}}^{T}\mathbf{u^{\prime}})\,\implies
p=0\mbox{ or }p=-2\mathbf{u}^{T}\mathbf{x^{\prime}}\,.$ (9)

Therefore, for any given $\mathbf{x^{\prime}}$, if
$\mathbf{u}^{T}\mathbf{x}\neq 0$, there exists
$\mathbf{y^{\prime}}\neq\mathbf{x^{\prime}}$ which has the same shapelet space
representation. In fact, there are infinitely many such $\mathbf{x^{\prime}}$
for which this holds. As a demonstration, pick any $\mathbf{x^{\prime}}$ which
is linearly independent with all the $w-1$ rows in $C_{w-1}$ and is not a zero
vector. To see that this choice works, note that if
$\mathbf{x^{\prime}}^{T}\mathbf{u}=0$, then the nullity of the matrix
$C_{w}^{\prime}$ formed by appending $x^{\prime}$ as a row to matrix $C_{w-1}$
is 1 (i.e., $\mathbf{u}$ spans the null space of $C_{w}$). However, as all $w$
rows of $C_{w}^{\prime}$ are linearly independent, its rank is $w$, which
violates the rank-nullity theorem. As a result, there exists a
$\mathbf{y^{\prime}}\neq\mathbf{x^{\prime}}$ such that
$f(\mathbf{x^{\prime}})=f(\mathbf{y^{\prime}})$. ∎

##  Appendix B Additional Details

###  B.1 Algorithm

Here we present the pseudocode for DTW+S. Algorithm 1 implements our approach.
It calls the function TimeSeriesShape to compute SSR of the input time-series,
which is presented in Algorithm 2. The function ShapeletSpaceTransform uses
the similarity and shapelets described in the paper.

Algorithm 1 Dynamic time warping with shapes

procedure DTW+S($\mathbf{a},\mathbf{b},\mathbf{S},\tau$)

$\mathbf{A}=$ TimeSeriesShape($\mathbf{a},S$)

$\mathbf{B}=$ TimeSeriesShape($\mathbf{b},S$)

return $DTW(\mathbf{A},\mathbf{B},\tau)$

end procedure

Algorithm 2 Extracting shapelet space representation of time-series using a
moving window

procedure TimeSeriesShape($\mathbf{a},\mathbf{S}$)

$w\leftarrow$ length of each shapelet in $\mathbf{S}$

$T\leftarrow$ length of the time-series $\mathbf{a}$

for $\ \textbf{do}t=1$ to $T-w+1$

$\mathbf{A}[:,t]$ = ShapeletSpaceTransform($\mathbf{a}[i:i+w-1],\mathbf{S}$)

$\triangleright$ Take a window of length w and transform it into the shapelet
space

end for

end procedure

##  Appendix C Experimental Setting

The chosen shapelets are: (i) ‘increase’: $[1,2,3,4]$, (ii) ‘surge’:
$[1,2,4,8]$, (iii) ‘peak’: $[1,2,2,1]$, and (iv) ‘flat’: $[0,0,0,0]$. The
matrix $C_{w}$ constructed as in Theorem 1, using the chosen set of shapelets
results in $\|C_{w}^{-1}\|=13.1$, which is small when multiplied with
functions of small $\epsilon_{0},\epsilon_{1}$ as in Equation A. Some other
sets of shapelets that satisfy Property 1 were also tried, and their results
were not significantly different.

The flatness was calculated by setting $m_{0}=0$, and
$\beta=-\ln{0.1}/\theta$, where $\theta$ is the median of the maximum
“absolute” slope of each time-series. Recall that the “absolute” slope for a
given window is calculated by averaging successive differences over the
window. Choosing $\beta$ in such a way ensures that a window of time-series
with a median “absolute” slope gets a low flatness of 0.1.

###  C.1 Code

All our code and data used in the paper are publicly
available.222https://github.com/scc-usc/DTW˙S˙apps. The experiments were run
on a machine with Intel(R) Core(TM) i8 CPU, 3GHz, 6 cores, and 16GB RAM.

##  Appendix D Additional Results

###  D.1 Clustering

Here we present all results from all the methods used in Section 4.1. We note
that DTW+S with Euclidean and Cosine distance produce identical clustering.
All other methods mix different-looking time-series into the same clusters.

Figure 10: Comparison of clustering results obtained from DTW+S against other
distance measures. DTW+S with Euclidean (default) and cosine distance produces
reasonable clustering. All other measures mix different patterns into one
cluster.

###  D.2 Ensemble

Figure 11 shows an intermediate step of computing alignments. While DTW+S is
not specifically, designed to identify peaks, we observe that almost all peaks
among different time-series are aligned (marked with a pink ’x’). The circle
denotes the centroid, i.e., the ensemble point of these points. Thus, the
ensemble is able to provide a better estimate of the average size of the peak.

Figure 11:  An instance of alignment, marked by a pink ‘x’ on the individual
time-series. The pink circle represents the ensemble point. Previous circles
represent the ensemble points obtained from previous alignments.

###  D.3 Classification

Recall that we treat the warping window $\tau$ in DTW+S as a hyperparameter.
For one set of results, we arbitrarily set $\tau=10$. For another set of
results (shown in the paper) we use leave-one-out cross-validation to identify
$\tau$ as a fraction of the length of the time-series $T$ from a set of values
– $\tau=\\{0,0.01T,0.02T,\dots,0.07T\\}$. We compare our results with the
reported best performance of DTW (Chen et al. 2015). The results are presented
in Figure 12. In the scatter plot, each point represents errors on a dataset.
The blue line represents the line $y=x$, i.e., when DTW+S has the same error
as that of DTW. A point lying below (and to the right) of this line indicates
that DTW+S error was lower than DTW error. We observe that DTW+S outperforms
DTW on 45.3% datasets. The two measures lead to similar errors for many
datasets (along the $y=x$ line). With the windows learned through leave-one-
out validation the errors improve significantly on many datasets as DTW+S
outperforms DTW on 57.7% datasets. “Corr only” represents the DTW+S measure
obtained by ignoring the “flat” shapelet. In this case, DTW+S reduces to the
set of Person correlations with the three other shapelets. Now, even with the
learned warping window, DTW+S (corr) only outperforms DTW in 39.1% datasets.
Additionally, it produces some large errors. Correlation ignores scale
completely, and small fluctuations that are not necessarily useful patterns,
but noise can cause the measure to consider it similar to some other
significant patterns. Thus, the flatness dimension has a significant
contribution to the performance of DTW+S.

Figure 12: Performance of DTW+S on 64 datasets.

We also present results (Figure 13) highlighting the impact of smoothing vs
not smoothing the time-series before classification. We observe that smoothing
brings the error down for many datasets. For a few datasets, it makes the
results worse. While no-smoothing (smoothing with a window of 1) is also one
of the values in the hyper-parameter search, it may not be chosen in
validation sometimes because of slightly worse performance in the validation
set compared to some other smoothing window. For easy reference, we also show
how smoothing and no smoothing impact errors when compared against DTW.

Figure 13: Results obtained by DTW+S with smoothing. (a) Allowing smoothing
reduces errors for many datasets. (b) Improvement on many datasets where DTW+S
was worse than DTW.