Blind segmentation of time-series

Abstract

Change-point detection is an indispensable tool for awide variety of applications which has been extensively studied in the literature over the years. However, the development of wireless devices and miniature sensors that allows continuous recording of data poses new challenges that cannot be adequately addressed by the vast majority of existing methods. In this work, we aim to balance statistical accuracy with computational efficiency, by developing a hierarchical two-level algorithmthat can significantly reduce the computational burden in the expense of a negligible loss of detection accuracy. Our choice is motivated by the idea that if a simple test was used to quickly select some potential change-points in the first level, then the second level which consists of a computationally more expensive algorithm, would be applied only to a subset of data, leading to a significant run-time improvement. In addition, in order to alleviate the difficulties arising in high-dimensional data, we use a data selection technique which gives more importance to data that are more useful for detecting changes than to others. Using these ideas, we compute a detection measure which is given as the weighted sum of individual dissimilarity measures and we present techniques that can speed up some standard change-point detection methods. Experimental results on both artificial and real-world data demonstrate the effectiveness of developed approaches and provide a useful insight about the suitability of some of the state-of-the-art methods for detecting changes in many different scenarios.