Information Technology Reference
In-Depth Information
shapes in a way that it allows for elongations: the
k
th position of time series
x
1
is
compared to the
k
th position of
x
2
, and
k
may or may not be equal to
k
.
DTW is an edit distance [
30
]. This means that we can conceptually consider the
calculation of the DTW distance of two time series
x
1
and
x
2
of length
l
1
and
l
2
respectively as the process of transforming
x
1
into
x
2
. Suppose we have already
transformed a prefix (possibly having length zero or
l
1
in the extreme cases) of
x
1
into a prefix (possibly having length zero or
l
2
in the extreme cases) of
x
2
. Consider
the next elements, the elements that directly follow the already-transformed prefixes,
of
x
1
and
x
2
. The following editing steps are possible, both of which being associated
with a cost:
1.
replacement
of the next element of
x
1
for the next element of
x
2
, in this case, the
next element of
x
1
is matched to the next element of
x
2
, and
2.
elongation
of an element: the next element of
x
1
is matched to the last element
of the already-matched prefix of
x
2
or vice versa.
As result of the replacement step, both prefixes of the already-matched elements
grow by one element (by the next elements of
x
1
and
x
2
respectively). In contrast,
in an elongation step, one of these prefixes grows by one element, while the other
prefix remains the same as before the elongation step.
The cost of transforming the entire time series
x
1
into
x
2
is the sum of the costs of
all the necessary editing steps. In general, there are many possibilities to transform
x
1
into
x
2
, DTW calculates the one with minimal cost. This minimal cost serves as
the distance between both time series. The details of the calculation of DTW are
described next.
DTWutilizes the dynamic programming approach [
45
]. Denoting the length of
x
1
by
l
1
, and the length of
x
2
by
l
2
, the calculation of the minimal transformation cost is
done by filling the entries of an
l
1
×
l
2
matrix. Each number in thematrix corresponds
to the distance between a subsequence of
x
1
and a subsequence of
x
2
. In particular,
the number in the
i
th row and
j
th column,
2
d
DT W
0
(
,
)
i
j
corresponds to the distance
between the subsequences
x
1
=
(
and
x
2
=
(
x
1
[
]
,...,
x
1
[
]
)
x
2
[
]
,...,
x
2
[
]
)
0
i
0
j
.This
is shown in Fig.
11.1
.
When we try to match the
i
th position of
x
1
and the
j
th position of
x
2
, there are
three possible cases: (i) elongation in
x
1
, (ii) elongation in
x
2
, and (iii) no elongation.
If there is no elongation, the prefix of
x
1
up to the
(
i
−
1
)
th position is matched
(transformed) to the prefix of
x
2
up to the
th position, and the
i
th position of
x
1
is matched (transformed) to the
j
th position of
x
2
.
Elongation in
x
1
at the
i
th position means that the
i
th position of
x
1
has already
been matched to at least one position of
x
2
, i.e., the prefix of
x
1
up to the
i
th position
is matched (transformed) to the prefix of
x
2
up to the
(
j
−
1
)
th position, and the
i
th
position of
x
1
is matched again, this time to the
j
th position of
x
2
. This way the
i
th
position of
x
1
is elongated, in the sense that it is allowed to match several positions
of
x
2
. The elongation in
x
2
can be described in an analogous way.
(
j
−
1
)
2
Please note that the numbering of the columns and rows begins with zero, i.e., the very-first
column/row of the matrix is called in this sense as the 0th column/row.
Search WWH ::
Custom Search