Database Reference
In-Depth Information
that end, we use techniques related to those for discovering correlations
across streams, illustrating the relationship between the two problems.
Let us first assume that someone gives us a window size. Then, the
problem we want to solve is the following:
Problem 8.1 (Fixed-window optimal patterns)
Given a time se-
ries
x
t
,
t
=1
,
2
,...
and a window size
w
, find the patterns that best
summarize the series at this window size.
w
,cho-
sen so that they capture “most” of the information in the series (in a
way that we will make precise later).
In practice, however, we do not know
apriori
the right window size.
Therefore, with respect to the second requirement (multi-scale), we want
to solve the following problem:
[
v
i,
1
,...,v
i,w
]
T
The patterns are
w
-dimensional vectors
v
i
≡
∈
R
Problem 8.2 (Optimal local patterns)
Given a time series
x
t
and
a set of windows
W
{
w
1
,w
2
,w
3
,...
}
, find (i) the optimal patterns for
each of these, and (ii) the best window
w
∗
to describe the key patterns
in the series.
:=
So how do we go about finding these patterns? An elementary concept
we need to introduce is
time-delay coordinates
. We are given a time series
x
t
,
t
=1
,
2
,...
with
m
points seen so far. Intuitively, when looking for
patterns of length
w
, we divide the series in consecutive, non-overlapping
subsequences of length
w
. Thus, if the original series is a
m ×
1matrix
(not necessarily materialized), we substitute it with a
w
× w
matrix.
Instead of
m
scalar values we now have a sequence of
m/w
vectors with
dimension
w
. It is natural to look for patterns among these time-delay
vectors.
Definition 5.7 (Delay coordinates)
Given a sequence denoted by
x
≡
[
x
1
,x
2
,...,x
t
,...,x
m
]
T
and a
delay
(or window)
w
,the
delay co-
ordinates
are a
w
matrix with the
t
-th row equal to
X
(
w
)
m/w
×
(
t
)
:=
[
x
(
t
−
1)
w
+1
,x
(
t
−
1)
w
+2
,...,x
t
w
]
T
.
Of course, neither
x
nor
X
(
w
)
need to be fully materialized at any point
in time. In practice, we only need to store the last row of
X
(
w
)
.
Also, note that we choose non-overlapping windows. We could also
use overlapping windows, in which case
X
(
w
)
would have
m−w
+1rows,
with row
t
consisting of values
x
t
,x
t
+1
,...,x
t
+
w
. In this case, there are
some subtle differences [23], akin to the differences between “standard”
wavelets and
maximum-overlap
or
redundant
wavelets [46]. However,
in practice non-overlapping windows are equally effective for pattern
