Discovering frequent episodes in time series

Abstract

Frequent episode discovery is one of the most challenging tasks. An episode is a set of partially ordered occurrences of events in a period of time. However, in real-valued time series mining community, frequent episode discovery has not been addressed well. One of the most difficult problems is that rather than a sequence of discrete events, time series is a sequence of real-valued data. A pattern can be varied in shape of consecutive data points, so that events of the same type are difficult to identify. One can utilize Subsequence Time Series (STS) clustering technique to identify events in the time series, so that frequent episode discovery algorithm can be applied. However, the problem is that output of current STS clustering algorithms cannot be used for the frequent episode discovery because of two main reasons. First, the previously proposed STS clustering algorithms were claimed to be meaningless because the outputs of STS algorithms will always converge to sinusoidal form. Second, some recent STS clustering algorithms that claim to produce meaningful results fail to dispose of trivial subsequences. This leads to inflation and redundancy of the patterns. This thesis approaches the problems by proposing a new STS clustering algorithm to effectively identify interesting events in time series. More importantly, the proposed algorithm also discard trivial or inessential subsequences. As a result of STS clustering, the patterns can be considered as discrete events, similar to those used in general episode discovery algorithms. Moreover, this thesis extends the proposed method to dynamic time warping (DTW) distance, shape-based averaging, and proposes an optimization over the usage of DTW. Experiments show that the proposed framework can perform the episode discovery from time series effectively and efficiently.