The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection
American Journal of Theoretical and Applied Statistics
Volume 4, Issue 6, November 2015, Pages: 581-586
Received: Nov. 5, 2015; Accepted: Nov. 11, 2015; Published: Dec. 2, 2015
Views 6356      Downloads 339
Authors
Gachomo Dorcas Wambui, Department of Statistics and Actuarial Science, Jomo Kenyatta University of Agriculture and Technology (JKUAT), Nairobi, Kenya
Gichuhi Anthony Waititu, Department of Statistics and Actuarial Science, Jomo Kenyatta University of Agriculture and Technology (JKUAT), Nairobi, Kenya
Anthony Wanjoya, Department of Statistics and Actuarial Science, Jomo Kenyatta University of Agriculture and Technology (JKUAT), Nairobi, Kenya
Article Tools
Follow on us
Abstract
Changepoint detection is the problem of estimating the point at which the statistical properties of a sequence of observations change. Over the years several multiple changepoint search algorithms have been proposed to overcome this challenge. They include binary segmentation algorithm, the Segment neighbourhood algorithm and the Pruned Exact Linear Time (PELT) algorithm. The PELT algorithm is exact and under mild conditions has a computational cost that is linear in the number of data points. PELT is more accurate than binary segmentation and faster as than other exact search methods. However, there is scanty literature on the sensitivity/power of PELT algorithm as the changepoints approach the extremes and as the size of change increases. In this paper, we implemented the PELT algorithm which uses a common approach of detecting changepoints through minimising a cost function over possible numbers and locations of changepoints. The study used simulated data to determine the power of the PELT test. The study investigated the power of the PELT algorithm in relation to the size of the change and the location of changepoints. It was observed that the power of the test, for a given size of change, is almost the same at all changepoints location. Also, the power of the test increases with the increase in size of change.
Keywords
Changepoint, Computational Cost, Detection, Segmentation, Power of the Test
To cite this article
Gachomo Dorcas Wambui, Gichuhi Anthony Waititu, Anthony Wanjoya, The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection, American Journal of Theoretical and Applied Statistics. Vol. 4, No. 6, 2015, pp. 581-586. doi: 10.11648/j.ajtas.20150406.30
Copyright
Copyright © 2015 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
References
[1]
Reeves Jaxk, Chen Jien, Wang, Xiaolan L., lund Robert & Lu Qiqi (2007). A review of comparison of changepoint detection techniques for climate data. Journal of Applied Meteorology and Climatology , 46, 900-915.
[2]
Erdman, C., & Emerson, J. W. (2008). A fast bayesian change point analysis for the segmentation of microarray data. Bioinformatics, 24(19), 2143-2148
[3]
Zeileis, A., Shah, A., & Patnaik, I. (2010). Testing,monitoring and dating structural changes in exchange rate regimes. Computational Statistics & Data Analysis , 54 (6), 1696-1706.
[4]
Killick, R., Eckley, I. A., Jonathan, P., & Eswans, K. (2010). Detection of changes in the characteristics of oceanographic time-series using statistical change point analysis. Ocean Engineering, 37 (13), 1120-1126.
[5]
Nam, C., Aston, J., & Johansen, A. M. (2012). Quantifying the uncertainity in change points. Journal of Timeseries Analysis, 33(5), 807-823.
[6]
Scott, A. J., & Knott, M. (1974). Acluster analysis method for grouping means in the analysis of variance. Biometrics , 30, 507-512.
[7]
Auger Iran E., & Lawrence,Charles E. (1989). Algorithms for the optimal identification of segment neighborhoods. Bulletin of Mathematical Biology, 51, 39-54.
[8]
Killick Rebecca, Fearnhead P, Eckley Idris A(2012). Optimal detection of change points with a linear computational costs. JASA, 107, 1590-1598
[9]
Page, E. S. (1954). Continous inspection shemes. Biometrica, 41, 100-116.
[10]
Page, E. S. (1955). A test for change in a parameter occuring at an unknown point. Biometrica, 42, 523-526.
[11]
Chernoff, H., & Zacks, S. (1964). Estimating the current mean of normal distribution which is subjected to changes in time. Annals of Mathematical Statistics, 35, 999-1018.
[12]
Gichuhi Antony Waititu, Franke, Jurgen, & Weizsacker, Heinrich Von (2008). Nonparametric changepoint analysis for bernoulli random variables based on neural networks. KLUEDO.
[13]
Bai Jushan, & Perron Pierre. (1998). Estimating and testing linear models with multiple structural changes. Econometrica, 66, 47-78.
[14]
Pan Jianmin, & Chen Jiahua (2006). Application of modified information criterion to multiple change point problems. Journal of Multivariate Analysis , 97, 2221-2241.
[15]
Yao Yi-Ching (1984). Estimation of a noisy discrete-time step function:Bayes and emperical bayes approaches. The Annals of Statistics , 12, 1434-1447.
[16]
Barry Daniel, & Hartigan, J. A. (1992). Product partition models for change point problems. The Annals of statistics, 20, 260-279.
[17]
Lee Chung-Bow (1998). Bayesian estimation of the number of change points. Statistica Sinica, 8, 923-939.
[18]
Lavielle Marc (1999). Detection of multiple changes in a sequence of dependent variables. Stochastic Processes and their Applications, 83, 79-102.
[19]
Lai Tze Leung, Liu Haiyan, Xing Haipeng(2005). Autoregressive models with piecewise constant volatility and regression parameters. Statistica Sinica, 15, 279-301.
[20]
Jackson Brad, Sargle Jeffrey D, Barnes David, Arabhi Sundararajan, Alt Alina, Gioumousis Peter, Gwin Elyus, Sangtrakulcharoen Paungkaew, Tan Linda, Tsai Tun Tao(2005). An algorithm for optimal partitioning of data on an interval. IEEE, Signal Processing Letters, 12(2), 105-108.
[21]
Killick Rebecca, Eckley Idris A., & Jonathan P. (2011). Efficient Detection of Multiple Changepoints Within An Oceanographic Time Series. In proceedings of the 58th session of ISI. ISI.
[22]
Madon, Benedicte & Hingrat Yves (2014). Deciphering behavioral changes in animal movement with a "multiple change point algorithm-classification tree" framework. Frontiers in Ecology and Evolution, 2, 1-9.
[23]
Gombay Edit, & Horvath Lajos (1996). On the Rate of Approximation for Maximum Likelihood tests in Change-point Models. Journal of Multivariate Analysis, 56, 120-152.
ADDRESS
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
U.S.A.
Tel: (001)347-983-5186