Optimal Detection of Changepoints With a Linear Computational Cost. Killick, R., Fearnhead, P., & Eckley, I. A. Journal of the American Statistical Association, 107(500):1590–1598, December, 2012. Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/01621459.2012.737745![Optimal Detection of Changepoints With a Linear Computational Cost [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex In this article, we consider the problem of detecting multiple changepoints in large datasets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example, in genetics as we analyze larger regions of the genome, or in finance as we observe time series over longer periods. We consider the common approach of detecting changepoints through minimizing a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies, we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the binary segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data. This article has supplementary materials available online.
@article{killick_optimal_2012,
title = {Optimal {Detection} of {Changepoints} {With} a {Linear} {Computational} {Cost}},
volume = {107},
issn = {0162-1459},
url = {https://doi.org/10.1080/01621459.2012.737745},
doi = {10.1080/01621459.2012.737745},
abstract = {In this article, we consider the problem of detecting multiple changepoints in large datasets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example, in genetics as we analyze larger regions of the genome, or in finance as we observe time series over longer periods. We consider the common approach of detecting changepoints through minimizing a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies, we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the binary segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data. This article has supplementary materials available online.},
number = {500},
urldate = {2022-08-25},
journal = {Journal of the American Statistical Association},
author = {Killick, R. and Fearnhead, P. and Eckley, I. A.},
month = dec,
year = {2012},
note = {Publisher: Taylor \& Francis
\_eprint: https://doi.org/10.1080/01621459.2012.737745},
keywords = {Dynamic programming, PELT, Segmentation, Structural change},
pages = {1590--1598},
}
Downloads: 0
{"_id":"FhSCcb65GoGJwoE2c","bibbaseid":"killick-fearnhead-eckley-optimaldetectionofchangepointswithalinearcomputationalcost-2012","author_short":["Killick, R.","Fearnhead, P.","Eckley, I. A."],"bibdata":{"bibtype":"article","type":"article","title":"Optimal Detection of Changepoints With a Linear Computational Cost","volume":"107","issn":"0162-1459","url":"https://doi.org/10.1080/01621459.2012.737745","doi":"10.1080/01621459.2012.737745","abstract":"In this article, we consider the problem of detecting multiple changepoints in large datasets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example, in genetics as we analyze larger regions of the genome, or in finance as we observe time series over longer periods. We consider the common approach of detecting changepoints through minimizing a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies, we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the binary segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data. This article has supplementary materials available online.","number":"500","urldate":"2022-08-25","journal":"Journal of the American Statistical Association","author":[{"propositions":[],"lastnames":["Killick"],"firstnames":["R."],"suffixes":[]},{"propositions":[],"lastnames":["Fearnhead"],"firstnames":["P."],"suffixes":[]},{"propositions":[],"lastnames":["Eckley"],"firstnames":["I.","A."],"suffixes":[]}],"month":"December","year":"2012","note":"Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/01621459.2012.737745","keywords":"Dynamic programming, PELT, Segmentation, Structural change","pages":"1590–1598","bibtex":"@article{killick_optimal_2012,\n\ttitle = {Optimal {Detection} of {Changepoints} {With} a {Linear} {Computational} {Cost}},\n\tvolume = {107},\n\tissn = {0162-1459},\n\turl = {https://doi.org/10.1080/01621459.2012.737745},\n\tdoi = {10.1080/01621459.2012.737745},\n\tabstract = {In this article, we consider the problem of detecting multiple changepoints in large datasets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example, in genetics as we analyze larger regions of the genome, or in finance as we observe time series over longer periods. We consider the common approach of detecting changepoints through minimizing a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies, we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the binary segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data. This article has supplementary materials available online.},\n\tnumber = {500},\n\turldate = {2022-08-25},\n\tjournal = {Journal of the American Statistical Association},\n\tauthor = {Killick, R. and Fearnhead, P. and Eckley, I. A.},\n\tmonth = dec,\n\tyear = {2012},\n\tnote = {Publisher: Taylor \\& Francis\n\\_eprint: https://doi.org/10.1080/01621459.2012.737745},\n\tkeywords = {Dynamic programming, PELT, Segmentation, Structural change},\n\tpages = {1590--1598},\n}\n\n","author_short":["Killick, R.","Fearnhead, P.","Eckley, I. A."],"key":"killick_optimal_2012","id":"killick_optimal_2012","bibbaseid":"killick-fearnhead-eckley-optimaldetectionofchangepointswithalinearcomputationalcost-2012","role":"author","urls":{"Paper":"https://doi.org/10.1080/01621459.2012.737745"},"keyword":["Dynamic programming","PELT","Segmentation","Structural change"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://bibbase.org/zotero/mh_lenguyen","dataSources":["iwKepCrWBps7ojhDx"],"keywords":["dynamic programming","pelt","segmentation","structural change"],"search_terms":["optimal","detection","changepoints","linear","computational","cost","killick","fearnhead","eckley"],"title":"Optimal Detection of Changepoints With a Linear Computational Cost","year":2012}