Decomposing Time Series with Application to Temporal Segmentation

Abstract

We propose a novel univariate time series decomposition algorithm to partition temporal sequences into homogeneous segments. Unlike most existing temporal segmentation approaches, which generally build statistical models of temporal observations and then detect change points using inference or hypothesis testing techniques, our algorithm requires no domain knowledge, is insensitive to the choice of design parameters and has low time complexity. Our algorithm first symbolizes the time series into a string, and then decomposes the string recursively, similar to the construction process of a decision-tree classifier. We extend this univariate decomposition algorithm to multivariate cases by decomposing each dimension as an univariate time series and then searching for temporal transition points in a coarse-to-fine manner. We evaluate and compare our algorithm to two state-of-the-art approaches on synthetic data, CMU motion capture data, and action videos. Experimental results demonstrate the effectiveness of our approach, which yields both significantly higher precision and recall of temporal transition points.