Title of Paper:Dynamic programming-based optimization for segmentation and clustering of hydrometeorological time series

Hits:

Date of Publication:2016-10-01

Journal:STOCHASTIC ENVIRONMENTAL RESEARCH AND RISK ASSESSMENT

Included Journals:SCIE、EI、Scopus

Volume:30

Issue:7

Page Number:1875-1887

ISSN No.:1436-3240

Key Words:Time series segmentation; Fuzzy clustering; Dynamic time warping; Dynamic programming

Abstract:In this study, we propose a new segmentation algorithm to partition univariate and multivariate time series, where fuzzy clustering is realized for the segments formed in this way. The clustering algorithm involves a new objective function, which incorporates an extra variable related to segmentation, while dynamic time warping (DTW) is applied to determine distances between non-equal-length series. As optimizing the introduced objective function is a challenging task, we put forward an effective approach using dynamic programming (DP) algorithm. When calculating the DTW distance, a DP-based method is developed to reduce the computational complexity. In a series of experiments, both synthetic and real-world time series are used to evaluate the performance of the proposed algorithm. The results demonstrate higher effectiveness and advantages of the constructed algorithm when compared with the existing segmentation approaches.