Comparison of change-point detection algorithms for vector time series
Independent thesis Advanced level (degree of Master (Two Years)), 30 credits / 45 HE creditsStudent thesis
Change-point detection aims to reveal sudden changes in sequences of data. Special attention has been paid to the detection of abrupt level shifts, and applications of such techniques can be found in a great variety of fields, such as monitoring of climate change, examination of gene expressions and quality control in the manufacturing industry. In this work, we compared the performance of two methods representing frequentist and Bayesian approaches, respectively. The frequentist approach involved a preliminary search for level shifts using a tree algorithm followed by a dynamic programming algorithm for optimizing the locations and sizes of the level shifts. The Bayesian approach involved an MCMC (Markov chain Monte Carlo) implementation of a method originally proposed by Barry and Hartigan. The two approaches were implemented in R and extensive simulations were carried out to assess both their computational efficiency and ability to detect abrupt level shifts. Our study showed that the overall performance regarding the estimated location and size of change-points was comparable for the Bayesian and frequentist approach. However, the Bayesian approach performed better when the number of change-points was small; whereas the frequentist became stronger when the change-point proportion increased. The latter method was also better at detecting simultaneous change-points in vector time series. Theoretically, the Bayesian approach has a lower computational complexity than the frequentist approach, but suitable settings for the combined tree and dynamic programming can greatly reduce the processing time.
Place, publisher, year, edition, pages
2010. , 42 p.
change-point detection, time series, tree, dynamic programming, Bayesian, MCMC
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-59925ISRN: LIU-IDA/STAT-A--10/003--SEOAI: oai:DiVA.org:liu-59925DiVA: diva2:356285
2010-06-07, Alan Turing, E building, Linköping University, Linköping, 09:00 (English)
UppsokPhysics, Chemistry, Mathematics
Nordgaard, Anders, Universitetslektor
Grimvall, Anders, Professor