Database Reference
In-Depth Information
We will show that the most popular algorithms used by data miners can in
fact produce very poor approximations of the data. The results will be used
to motivate the need for a new algorithm that we will introduce and validate
in Section 4. Section 5 offers conclusions and directions for future work.
2. Background and Related Work
In this section, we describe the three major approaches to time series seg-
mentation in detail. Almost all the algorithms have 2 and 3 dimensional
analogues, which ironically seem to be better understood. A discussion of
the higher dimensional cases is beyond the scope of this chapter. We refer
the interested reader to [Heckbert and Garland (1997)], which contains an
excellent survey.
Although appearing under different names and with slightly different
implementation details, most time series segmentation algorithms can be
grouped into one of the following three categories:
•
Sliding Windows:
A segment is grown until it exceeds some error bound.
The process repeats with the next data point not included in the newly
approximated segment.
•
Top-Down:
The time series is recursively partitioned until some stopping
criteria is met.
•
Bottom-Up:
Starting from the finest possible approximation, segments
are merged until some stopping criteria is met.
Table 1 contains the notation used in this chapter.
Table 1. Notation.
T
A time series in the form
t
1
,t
2
,...,t
n
T
[
a
:
b
] The subsection of
T
from
a
to
b
,
t
a
,t
a
+1
,...,t
b
Seg TS
A piecewise linear approximation of a time series of length
n
with
K
segments. Individual segments can be addressed with
Seg TS
(
i
).
create segment
(
T
) A function that takes in a time series and returns a linear segment
approximation of it.
calculate error
(
T
)
A function that takes in a time series and returns the
approximation error of the linear segment approximation of it.
Given that we are going to approximate a time series with straight lines,
there are at least two ways we can find the approximating line.
