A dynamic programming segmentation procedure for hydrological and environmental time series

We present a procedure for the segmentation of hydrological and environmental time series. The procedure is based on the minimization of Hubert's segmentation cost or various generalizations of this cost. This is achieved through a dynamic programming algorithm, which is guaranteed to find the globally optimal segmentations with K=1, 2, ..., K (max) segments. Various enhancements can be used to speed up the basic dynamic programming algorithm, for example recursive computation of segment errors and "block segmentation". The "true" value of K is selected through the use of the Bayesian information criterion. We evaluate the segmentation procedure with experiments which involve artificial as well as temperature and river discharge time series.