Home > Research > Publications & Outputs > Optimal detection of changepoints with a linear...
View graph of relations

Optimal detection of changepoints with a linear computational cost

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Optimal detection of changepoints with a linear computational cost. / Killick, Rebecca; Fearnhead, Paul; Eckley, Idris.
In: Journal of the American Statistical Association, Vol. 107, No. 500, 2012, p. 1590-1598.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

APA

Vancouver

Killick R, Fearnhead P, Eckley I. Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association. 2012;107(500):1590-1598. Epub 2012 Oct 17. doi: 10.1080/01621459.2012.737745

Author

Killick, Rebecca ; Fearnhead, Paul ; Eckley, Idris. / Optimal detection of changepoints with a linear computational cost. In: Journal of the American Statistical Association. 2012 ; Vol. 107, No. 500. pp. 1590-1598.

Bibtex

@article{6520cde56f104f4d9df7ce99c5408b3e,
title = "Optimal detection of changepoints with a linear computational cost",
abstract = "We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we analyse 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 minimising a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalised 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 favourably 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.",
keywords = "Structural Change, Dynamic Programming , Segmentation , PELT",
author = "Rebecca Killick and Paul Fearnhead and Idris Eckley",
year = "2012",
doi = "10.1080/01621459.2012.737745",
language = "English",
volume = "107",
pages = "1590--1598",
journal = "Journal of the American Statistical Association",
issn = "0162-1459",
publisher = "Taylor and Francis Ltd.",
number = "500",

}

RIS

TY - JOUR

T1 - Optimal detection of changepoints with a linear computational cost

AU - Killick, Rebecca

AU - Fearnhead, Paul

AU - Eckley, Idris

PY - 2012

Y1 - 2012

N2 - We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we analyse 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 minimising a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalised 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 favourably 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.

AB - We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we analyse 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 minimising a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalised 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 favourably 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.

KW - Structural Change

KW - Dynamic Programming

KW - Segmentation

KW - PELT

U2 - 10.1080/01621459.2012.737745

DO - 10.1080/01621459.2012.737745

M3 - Journal article

VL - 107

SP - 1590

EP - 1598

JO - Journal of the American Statistical Association

JF - Journal of the American Statistical Association

SN - 0162-1459

IS - 500

ER -