Information Technology Reference
In-Depth Information
(a)
x
2
(b)
1134
3
1
x
1
1
2
3
3
4
1
0 0
2577
11
1
34
5
33
1
22
4
55
1
224
882
12
5
88443
2
|
3
−
3
|
+ min
{
2
,
3
,
4
}
=2
(c)
113431
123341
Fig. 11.2
Example for the calculation of the DTW-matrix.
a
The DTW-matrix calculated with
c
DTW
tr
(
v
A
,
v
B
)
=|
v
A
−
v
B
|
,
c
DTW
el
=
0.Thetimeseries
x
1
and
x
2
are shown on the
left
and
top
of the
matrix respectively.
b
The calculation of the value of a cell.
c
The (implicitly) constructed mapping
between the values of the both time series. The cells are leading to the minimum in Formula (
11.1
),
i.e., the ones that allow for this mapping, are marked in the DTW-matrix
d
DT W
0
d
DT W
(
x
1
,
x
2
)
=
(
l
1
−
1
,
l
2
−
1
).
(11.2)
An example for the calculation of DTW is shown in Fig.
11.2
.
Note that the described method implicitly constructs a mapping between the posi-
tions of the time series
x
1
and
x
2
: by back-tracking which of the possible cases leads
to the minimum in the Formula (
11.1
) in each step, i.e., which of the above discussed
three possible cases leads to the minimal transformation costs in each step, we can
reconstruct the mapping of positions between
x
1
and
x
2
.
For the final result of the distance calculation, the values close to the diagonal
of the matrix are usually the most important ones (see Fig.
11.2
for an illustration).
Therefore, a simple, but effective way of speeding-up dynamic time warping is to
restrict the calculations to the cells around the diagonal of the matrix [
45
]. This
means that one limits the elongations allowed when matching the both time series
(see Fig.
11.3
).
Restricting thewarpingwindowsize to a pre-defined constant
w
DTW
(see Fig.
11.3
)
implies that it is enough to calculate only those cells of the matrix that are at most
w
DTW
positions far from the main diagonal along the vertical direction:
d
DT W
0
w
DT W
(
i
,
j
)
is calculated
⃔|
i
−
j
|≤
.
(11.3)
The warping window size
w
DTW
is often expressed in percentage relative to the
length of the time series. In this case,
w
DTW
=
100% means calculating the entire
matrix, while
w
DTW
0% refers to the extreme case of not calculating any entries
at all. Setting
w
DTW
to a relatively small value such as 5%, does not negatively affect
the accuracy of the classification, see e.g. [
8
] and the references therein.
In the settings used throughout this chapter, the cost of elongation,
c
DTW
el
=
,isset
to zero:
c
DT W
el
=
.
0
(11.4)
Search WWH ::
Custom Search