|
ACM Special Interest Group on Knowledge
Discovery & Data Mining
|
KDD-2000
Sixth ACM SIGKDD International Conference on
Knowledge Discovery & Data Mining
August 20-23, 2000
Boston, MA, USA
KDD-2000
Runner-Up Best Research Paper
Deformable
Markov Model Templates for Time-Series Pattern Matching
Xianping
Ge (University of California, Irvine)
Padhraic
Smyth (University of California, Irvine)
Abstract:
This
paper addresses the problem of automatically detecting specific patterns or
shapes in time-series data. A novel and flexible approach is proposed based on
segmental semi-Markov models. Unlike dynamic time-warping or
template-matching, the proposed framework provides a principled and coherent
framework for leveraging both prior knowledge and training data. The pattern
of interest is modeled as a K-state segmental hidden Markov model where each
state is responsible for the generation of a component of the overall shape
using a state-based regression function. The distance (in time) between
segments is modeled as a semi-Markov process, allowing flexible deformation of
time. The model can be constructed from a single training example. Recognition
of a pattern in a new time series is achieved by a recursive Viterbi-like
algorithm which scales linearly in the length of the sequence. The method is
successfully demonstrated on real data sets, including an application to
end-point detection in semiconductor manufacturing.
|
|