The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection

Gachomo Dorcas Wambui; Gichuhi Anthony Waititu; Anthony Wanjoya

doi:doi:10.11648/j.ajtas.20150406.30

| Peer-Reviewed |

The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection

Gachomo Dorcas Wambui, Gichuhi Anthony Waititu, Anthony Wanjoya

Received: 5 November 2015 Accepted: 11 November 2015 Published: 2 December 2015

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

DOI	10.11648/j.ajtas.20150406.30
Published in	American Journal of Theoretical and Applied Statistics (Volume 4, Issue 6, November 2015)
Page(s)	581-586
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Changepoint, Computational Cost, Detection, Segmentation, Power of the Test

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.

Cite This Article

Plain Text BibTeX RIS

APA Style

Gachomo Dorcas Wambui, Gichuhi Anthony Waititu, Anthony Wanjoya. (2015). The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection. American Journal of Theoretical and Applied Statistics, 4(6), 581-586. https://doi.org/10.11648/j.ajtas.20150406.30

Copy | Download

ACS Style

Gachomo Dorcas Wambui; Gichuhi Anthony Waititu; Anthony Wanjoya. The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection. Am. J. Theor. Appl. Stat. 2015, 4(6), 581-586. doi: 10.11648/j.ajtas.20150406.30

Copy | Download

AMA Style

Gachomo Dorcas Wambui, Gichuhi Anthony Waititu, Anthony Wanjoya. The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection. Am J Theor Appl Stat. 2015;4(6):581-586. doi: 10.11648/j.ajtas.20150406.30

Copy | Download

@article{10.11648/j.ajtas.20150406.30,
  author = {Gachomo Dorcas Wambui and Gichuhi Anthony Waititu and Anthony Wanjoya},
  title = {The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection},
  journal = {American Journal of Theoretical and Applied Statistics},
  volume = {4},
  number = {6},
  pages = {581-586},
  doi = {10.11648/j.ajtas.20150406.30},
  url = {https://doi.org/10.11648/j.ajtas.20150406.30},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtas.20150406.30},
  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.},
 year = {2015}
}

Copy | Download

TY - JOUR
T1 - The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection
AU - Gachomo Dorcas Wambui
AU - Gichuhi Anthony Waititu
AU - Anthony Wanjoya
Y1 - 2015/12/02
PY - 2015
N1 - https://doi.org/10.11648/j.ajtas.20150406.30
DO - 10.11648/j.ajtas.20150406.30
T2 - American Journal of Theoretical and Applied Statistics
JF - American Journal of Theoretical and Applied Statistics
JO - American Journal of Theoretical and Applied Statistics
SP - 581
EP - 586
PB - Science Publishing Group
SN - 2326-9006
UR - https://doi.org/10.11648/j.ajtas.20150406.30
AB - 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.
VL - 4
IS - 6
ER -

Copy | Download

Author Information

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

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Gachomo Dorcas Wambui, Gichuhi Anthony Waititu, Anthony Wanjoya. (2015). The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection. American Journal of Theoretical and Applied Statistics, 4(6), 581-586. https://doi.org/10.11648/j.ajtas.20150406.30

Copy | Download

ACS Style

Gachomo Dorcas Wambui; Gichuhi Anthony Waititu; Anthony Wanjoya. The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection. Am. J. Theor. Appl. Stat. 2015, 4(6), 581-586. doi: 10.11648/j.ajtas.20150406.30

Copy | Download

AMA Style

Gachomo Dorcas Wambui, Gichuhi Anthony Waititu, Anthony Wanjoya. The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection. Am J Theor Appl Stat. 2015;4(6):581-586. doi: 10.11648/j.ajtas.20150406.30

Copy | Download

@article{10.11648/j.ajtas.20150406.30,
  author = {Gachomo Dorcas Wambui and Gichuhi Anthony Waititu and Anthony Wanjoya},
  title = {The Power of the Pruned Exact Linear Time(PELT) Test in Multiple Changepoint Detection},
  journal = {American Journal of Theoretical and Applied Statistics},
  volume = {4},
  number = {6},
  pages = {581-586},
  doi = {10.11648/j.ajtas.20150406.30},
  url = {https://doi.org/10.11648/j.ajtas.20150406.30},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtas.20150406.30},
  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.},
 year = {2015}
}

Copy | Download