Modified dynamic programming approach for offline segmentation of long hydrometeorological time series

Springer Science and Business Media LLC - Tập 24 - Trang 547-557 - 2009
Abdullah Gedikli1, Hafzullah Aksoy1,2, N. Erdem Unal1, Athanasios Kehagias3
1Department of Civil Engineering, Istanbul Technical University, Maslak, Istanbul, Turkey
2Fakultät III, Umwelt und Technik, Hydrologie und Wasserwirtschaft, Leuphana Universität Lüneburg, Suderburg, Germany
3School of Engineering, Aristotle University of Thessaloniki, Thessaloniki, Greece

Tóm tắt

For the offline segmentation of long hydrometeological time series, a new algorithm which combines the dynamic programming with the recently introduced remaining cost concept of branch-and-bound approach is developed. The algorithm is called modified dynamic programming (mDP) and segments the time series based on the first-order statistical moment. Experiments are performed to test the algorithm on both real world and artificial time series comprising of hundreds or even thousands of terms. The experiments show that the mDP algorithm produces accurate segmentations in much shorter time than previously proposed segmentation algorithms.

Tài liệu tham khảo

Aksoy H (2007) Hydrological variability of the European part of Turkey. Iran J Sci Technol Trans B 31(B2):225–236 Aksoy H, Unal NE, Gedikli A (2007) Letter to the editor. Stoch Environ Res Risk Assess 21(4):447–449 Aksoy H, Unal NE, Alexandrov V, Dakova S, Yoon J (2008a) Hydrometeorological analysis of northwestern Turkey with links to climate change. Int J Climatol 28(8):1047–1060 Aksoy H, Gedikli A, Unal NE, Kehagias A (2008b) Fast segmentation algorithms for long hydrometeorological time series. Hydrol Process 22:4600–4608 Basseville M, Nikiforov IV (1993) Detection of abrupt changes: theory and application. PRT Prentice Hall, Englewood Cliffs, NJ Buishand TA (1982) Some methods for testing the homogeneity of rainfall records. J Hydrol 58:11–27 Dahamsheh A, Aksoy H (2007) Structural characteristics of annual precipitation data in Jordan. Theor Appl Climatol 88(3–4):201–212 Dobigeon N, Tourneret JY (2007) Joint segmentation of wind speed and direction using a hierarchical model. Comput Stat Data Anal 51:5603–5621 Fortin V, Perreault L, Salas JD (2004) Restropective analysis and forecasting of streamflows using a shifting level models. J Hydrol 296:135–163 Gedikli A, Aksoy H, Unal NE (2008) Segmentation algorithm for long time series analysis. Stoch Environ Res Risk Assess 22(3):291–302 Gedikli A, Aksoy H, Unal NE (2009) AUG-Segmenter: a user-friendly tool for segmentation of long time series. J Hydroinformatics (in press) Hipel KW, McLeod AI (1994) Time series modelling of water resources and environmental systems. Elsevier, Amsterdam Hubert P (2000) The segmentation procedure as a tool for discrete modeling of hydrometeorological regimes. Stoch Environ Res Risk Assess 14:297–304 Hubert P, Carbonnel JP, Chaouche A (1989) Segmentation des series hydrométéorologiques—application à des séries de précipitations et de débits de l’afrique de l’ouest. J Hydrol 110(3–4):349–367 Hubert P, Bader J-C, Bendjoudi H (2007) Un siècle de débits annuels du fleuve Sénégal. J Hydrol Sci 52(1):68–73 Hughes MK, Graumlich LJ (1996) Climatic variations and forcing mechanisms of the last 2000 years, vol 141. Multi-millenial dendroclimatic studies from the western United States. NATO ASI Series, pp 109–124 Kehagias A (2004) A hidden Markov model segmentation procedure for hydrological and environmental time series. Stoch Environ Res Risk Assess 18:117–130 Kehagias A, Fortin V (2006) Time series segmentation with shifting means hidden Markov models, Nonlin. Process Geophys 13:339–352 Kehagias A, Nidelkou E, Petridis V (2006) A dynamic programming segmentation procedure for hydrological and environmental time series. Stoch Environ Res Risk Assess 20:77–94 Kehagias A, Petridis V, Nidelkou E (2007) Reply by the authors to the letter by Aksoy et al. Stoch Environ Res Ris Assess 21:451–455 Koutsoyiannis D (2006) Nonstationarity versus scaling in hydrology. J Hydrol 324:239–254 Kundzewicz ZW, Robson AJ (2004) Change detection in hydrological records—a review of the methodology. J Hydrol Sci 49(1):7–19 Labbé C, Labbé D, Hubert P (2004) Automatic segmentation of texts and corpora. J Quant Linguist 11(3):193–213 Morettin PA, Mesquita AR, Rocha JGC (1987) Rainfall at Fortaleza in Brazil revisited. Time Ser Anal Theory Pract 6:67–85 Editor: O.D. Anderson Radziejewski M, Kundzewicz ZW (2004) Detectability of changes in hydrological records. J Hydrol Sci 49(1):39–51 Scheffe M (1959) The analysis of variance. Wiley, New York Tsakalias G, Koutsoyiannis D (1999) A comprehensive system for the exploration and analysis of hydrological data. Water Resour Manag 13:269–302 Xiong L, Guo S (2004) Trend test and change-point detection for the annual discharge series of the Yangtze River at the Yichang hydrological station. J Hydrol Sci 49(1):99–112