SEGMENTING TIME SERIES: A SURVEY AND NOVEL APPROACH - Data Mining in Time Series Databases - page 9

Finally Smyth and Ge use the algorithm to produce a representation
that can support a Hidden Markov Model approach to both change point
detection and pattern matching [Ge and Smyth (2001)].

2.3. The Bottom-Up Algorithm

The Bottom-Up algorithm is the natural complement to the Top-Down
algorithm. The algorithm begins by creating the finest possible approxima-
tion of the time series, so that

-
length time series. Next, the cost of merging each pair of adjacent segments
is calculated, and the algorithm begins to iteratively merge the lowest cost
pair until a stopping criteria is met. When the pair of adjacent segments

n /2 segments are used to approximate the n

i

and + 1 are merged, the algorithm needs to perform some bookkeeping.

First, the cost of merging the new segment with its right neighbor must be
calculated. In addition, the cost of merging the

i

1segmentswithitsnew
larger neighbor must be recalculated. The pseudocode for the algorithm is
showninTable4.
Two and three-dimensional analogues of this algorithm are common in
the field of computer graphics where they are called decimation methods
[Heckbert and Garland (1997)]. In data mining, the algorithm has been
used extensively by two of the current authors to support a variety of time
series data mining tasks [Keogh and Pazzani (1999), Keogh and Pazzani
(1998), Keogh and Smyth (1997)]. In medicine, the algorithm was used
by Hunter and McIntosh to provide the high level representation for their
medical pattern matching system [Hunter and McIntosh (1999)].

i −

Table 4. The generic Bottom-Up algorithm.

Algorithm Algorithm Seg TS = Bottom Up(T, max error)

for fofori=1:2:length(T) // Create initial fine approximation.

Seg TS = concat(Seg TS, create segment(T[i:i+1]));
end; end;

for

end;

fofori=1:length(Seg TS) - 1 // Find merging costs.
merge cost(i) = calculate error([merge(Seg TS(i), Seg TS(i + 1))]);
end; end;

while

end;

while min(merge cost) < max error // While not finished.
p = min(merge cost); // Find ''cheapest'' pair to merge.
Seg TS(p) = merge(Seg TS(p), Seg TS(p + 1)); // Merge them.
delete(Seg TS(p + 1)); // Update records.
merge cost(p) = calculate error(merge(Seg TS(p), Seg TS(p + 1)));
merge cost(p - 1) = calculate error(merge(Seg TS(p - 1), Seg TS(p)));
end;

while

end;