Information Technology Reference
In-Depth Information
(a)
x
2
(b)
1
.
12 5
53
.
821
.
30
.
8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
...
...
x
1
0
.
75
2
.
3
4
.
1
4
1
3
2
The matrix
is filled in
this order.
Cost of
transforming
the marked
parts of
x
1
and
x
2
.
Cost of transforming
the entire
x
1
into
the entire
x
2
.
Fig. 11.1
The DTW-matrix. While calculating the distance (transformation cost) between two
time series
x
1
and
x
2
, DTW fills-in the cells of a matrix.
a
Thevaluesoftimeseries
x
1
=
(
.
,
.
,
.
,
,
,
,
)
are enumerated on the left of the matrix from
top
to
bottom
. Time series
x
2
isshownonthe
top
of the matrix. A number in a cell corresponds to the distance (transformation
cost) between two prefixes of
x
1
and
x
2
.
b
The order of filling the positions of the matrix
0
75
2
3
4
1
4
1
3
2
Out of these three possible cases, DTW selects the one that transforms the prefix
x
1
=
(
into the prefix
x
2
=
(
with minimal overall
costs. Denoting the distance between the subsequences
x
1
and
x
2
, i.e. the value of
the cell in the
i
th row and
j
th column, as
d
DTW
0
x
1
[
0
]
,...,
x
1
[
i
]
)
x
2
[
0
]
,...,
x
2
[
j
]
)
(
i
,
j
)
, based on the above discussion,
we can write:
⊧
⊨
⊫
⊬
d
DT W
0
c
DT W
el
(
i
,
j
−
1
)
+
d
DT W
0
c
DT W
el
d
DT W
0
c
DT W
tr
(
i
−
1
,
j
)
+
(
i
,
j
)
=
(
x
1
[
i
]
,
x
2
[
j
]
)
+
min
.
(11.1)
⊩
⊭
d
DT W
0
(
i
−
1
,
j
−
1
)
In this formula, the first, second, and third terms of the minimum correspond to
the above cases of elongation in
x
1
, elongation in
x
2
and no elongation, respectively.
The cost of matching (transforming) the
i
th position of
x
1
to the
j
th position of
x
2
is
c
DTW
tr
are identical, the cost of this replacement is
zero. This cost is present in all the three above cases. In the cases, when elongation
happens, there is an additional elongation cost denoted as
c
nDTW
(
x
1
[
i
]
,
x
2
[
j
]
)
.If
x
1
[
i
]
and
x
2
[
j
]
el
.
According to the principles of dynamic programming, Formula (
11.1
) can be
calculated for all
i
j
in a column-wise fashion. First, set
d
DTW
0
c
DTW
tr
,
(
0
,
0
)
=
(
x
1
[
0
]
,
x
2
[
0
]
)
. Thenwe begin calculating the very first column of thematrix (
j
=
0), followed
by the next column corresponding to
j
1, etc. The cells of each column are
calculated in order of their row-indexes: within one column, the cell in the row
corresponding
i
=
=
0 is calculated first, followed by the cells corresponding to
i
=
1,
i
2, etc. (see Fig.
11.1
). In some cases (in the very-first column and in the very-
first cell of each row), in the min function of Formula (
11.1
), some of the terms are
undefined (when
i
=
−
1or
j
−
1 equals
−
1). In these cases, the minimum of the other
(defined) terms are taken.
The DTW distance of
x
1
and
x
2
, i.e. the cost of transforming the entire time series
x
1
=
(
x
1
[
0
]
,
x
1
[
1
]
,...,
x
1
[
l
1
−
1
]
)
into
x
2
=
(
x
2
[
0
]
,
x
2
[
1
]
,...,
x
2
[
l
2
−
1
]
)
is
Search WWH ::
Custom Search