Source-linked AI summary
An Evaluation of Change Point Detection Algorithms
Gerrit J. J. van den Burg, Christopher K. I. Williams
TL;DR
Existing change point detection algorithms have been evaluated mainly on simulations and limited real-world series with unreliable ground truth, leaving comparative real-world performance insufficiently assessed. The paper builds a 37-series human-annotated benchmark, develops metrics for multiple annotations, and evaluates existing methods in two setups. It aims to provide a proving ground for developing and comparing change point detection algorithms.
Problem
Real-world comparative evaluation of change point detection algorithms is limited because studies commonly rely on simulated data and a small number of series with unreliable ground truth.
Method
The paper constructs a human-annotated benchmark dataset, analyzes annotation quality, introduces metrics for multiple annotations, and evaluates existing algorithms in Default and Oracle experiments.
Results
The benchmark study evaluates a large selection of existing change point algorithms on the human-annotated real-world dataset and reports practical performance differences.
Takeaways & Limitations
The dataset and benchmark provide a basis for systematic, quantitative comparison and for identifying failure cases and future research directions.
Takeaways & Limitations
The benchmark excludes uk coal employ results because most methods cannot handle time series with missing values, and future work is needed to bridge Default and Oracle performance.
Abstract
from arXiv · showhide
Change point detection is an important part of time series analysis, as the presence of a change point indicates an abrupt and significant change in the data generating process. While many algorithms for change point detection have been proposed, comparatively little attention has been paid to evaluating their performance on real-world time series. Algorithms are typically evaluated on simulated data and a small number of commonly-used series with unreliable ground truth. Clearly this does not provide sufficient insight into the comparative performance of these algorithms. Therefore, instead of developing yet another change point detection method, we consider it vastly more important to properly evaluate existing algorithms on real-world data. To achieve this, we present a data set specifically designed for the evaluation of change point detection algorithms that consists of 37 time series from various application domains. Each series was annotated by five human annotators to provide ground truth on the presence and location of change points. We analyze the consistency of the human annotators, and describe evaluation metrics that can be used to measure algorithm performance in the presence of multiple ground truth annotations. Next, we present a benchmark study where 14 algorithms are evaluated on each of the time series in the data set. Our aim is that this data set will serve as a proving ground in the development of novel change point detection algorithms.
1 Introduction
Change point detection matters because abrupt changes may signal altered data-generating processes, yet existing evaluations rely heavily on simulations and limited real-world series. The paper addresses this gap with a human-annotated benchmark dataset, evaluation metrics for multiple annotations, and experiments on existing algorithms.
- Abrupt changes in time-series behavior may signal significant alterations to the data-generating process, making change point detection important.
- Existing evaluations often use simulated series and a small set of reused real-world series, producing an unfair or inaccurate basis for comparison.
- The paper argues for a realistic benchmark dataset so researchers can compare new algorithms systematically against existing alternatives on real-world data.
- The dataset contains 37 real-world time series from diverse application domains, with annotations analyzed for quality and consistency.
- The paper presents evaluation metrics that account for multiple annotations per dataset and benchmarks a significant number of existing algorithms using two experimental setups.
2 Related Work
Related work spans online and offline, univariate and multivariate, and model-based and nonparametric change point detection. The overview covers foundational statistical methods, optimization-based offline methods, Bayesian online models, and nonparametric tests.
- Change point detection methods are categorized as online or offline, univariate or multivariate, and model-based or nonparametric.
- Early quality-control work introduced CUSUM, while later approaches tested differences in maximum likelihood across candidate change points.
- Offline multiple-change-point detection includes greedy binary segmentation and exact dynamic programming, with pruning methods reducing complexity under stated conditions.Binary segmentation obtains a solution in O(T log T) time; dynamic programming and pruning provide alternative computational trade-offs.
- Several offline improvements assume an additive segment cost, linking the cost of a full segment to costs of its subsegments.
- Bayesian online methods model the probability distribution of run lengths and use recursive message passing, while nonparametric methods declare changes when test statistics exceed thresholds.
- The paper distinguishes its general-domain benchmark from genomics datasets that evaluate change point methods using labeled regions.
3 Evaluation Metrics
The paper evaluates change point detection from both segmentation and classification perspectives, adapting metrics to multiple human-annotated ground truths. It uses covering and F1-score measures to compare algorithm partitions and detected change points while accounting for location tolerance and annotator diversity.
- Change point evaluation can treat detection as either partitioning a series into regions or classifying observations as change points and non-change points.
- Clustering metrics: The segmentation covering metric averages partition similarity across the ground-truth partitions supplied by human annotators.
- Classification metrics: Precision and recall use a margin M around true locations, while restricting each true change point to one matched detection to prevent double counting.
- Classification metrics: Recall is macro-averaged across annotators so algorithms are encouraged to explain all annotations rather than favoring the annotator with the most change points.
- The benchmark uses both the segmentation covering metric and F1-score, with an allowed location error of M = 5.
4 Change Point Data Set
The authors built a controlled annotation workflow and a diverse real-world data set to obtain human ground truth for change point evaluation. Annotator agreement was generally high, although gradual transitions and periodic or seasonal behavior created ambiguity.
- Annotation Tool: Annotators marked change points in a web application after introductory training covering changes in mean, variance, trend, and seasonality.
- Annotation Tool: The annotation interface withheld dates, values, series names, and contextual information to reduce historical knowledge and other biases.
- Data set: The series were collected from sources including the WorldBank, EuroStat, U.S. Census Bureau, GapMinder, and Wikipedia, spanning events such as financial crises and legislation.
- Data set: The data set contains 37 real time series: 33 univariate and 4 multivariate, with nine series showing seasonal patterns.
- Annotation Collection: Annotators reported difficulty deciding whether gradual transitions or abrupt periodic changes constituted change points, though location uncertainty was partly reduced by the evaluation margin.
- Annotation Collection: Quality-control series showed that annotators usually located known changes accurately, while periodic behavior was particularly difficult to interpret.
- Consistency: Median one-versus-rest agreement was approximately 0.8 for covering and 0.9 for F1-score, with most observed agreements exceeding chance expectations.
5 Benchmark Study
The benchmark evaluates existing change point detection methods on human-annotated real-world series under default and oracle parameter settings, using separate univariate and multivariate analyses. Results show substantial differences across methods, metrics, and series difficulty, while statistical tests and critical-difference diagrams assess significance.
- Experimental Setup: The study benchmarks existing change point detection algorithms using published software, a zero-method baseline, and separate univariate and multivariate analyses.The benchmark uses methods that are frequently used or recently developed, while excluding unsupported data settings from particular analyses.
- Experimental Setup: Two experiments compare documented default settings with oracle performance obtained by grid-searching hyperparameter configurations.The oracle score averages each series’ highest score over the searched configurations, unlike the default experiment’s single run.
- Results: Default results favor binseg on univariate series, while oracle F1 results favor bocpd on both univariate and multivariate series.In the default experiment, amoc and pelt closely follow binseg on different metrics; rfpop slightly leads univariate oracle covering performance.
- Results: The zero method outperforms many alternatives in the Default experiment, partly because the series contain relatively few change points and many methods produce false positives.Oracle tuning substantially improves kcpa and rfpop, but oracle performance is not indicative of practical real-world selection because the best segmentation cannot be automatically identified.
- Results: Performance varies sharply by series: 9 of 14 methods achieve F1 = 1.0 on nile, whereas businv reaches only 0.650 even in the Oracle experiment.The nile series appears to contain a clear single mean shift, while businv has generally agreed-upon three change point locations.
- Results: Evaluation metric choice affects algorithm rankings because F1 compares against combined annotations, whereas covering measures agreement with each individual annotator.Despite this distinction, the best-performing method remains the same across metrics, indicating some stability in relative performance.
6 Discussion
The paper contributes a human-annotated real-world benchmark and evaluates existing change point algorithms, finding different leaders under default settings versus hyperparameter tuning. It also identifies extensions and automated tuning as future directions.
- The study introduces a dedicated data set of human-annotated real-world time series from diverse application domains for evaluating change point algorithms.The benchmark is intended to support algorithm development and evaluation.
- The framework evaluates detection performance against multiple human annotators using two complementary change point metrics.
- Binary segmentation performs best on univariate series with default parameters, although its performance is not statistically significantly different from several alternatives.
- With hyperparameter tuning, bocpd outperforms the other methods on both univariate and multivariate time series.
- Future work includes improving the data set and benchmark and developing automated hyperparameter tuning to narrow the gap between Default and Oracle performance.
Changelog
The changelog records revisions to the benchmark analyses, implementation details, and supporting materials. Changes include corrected F1 results, expanded Oracle searches, revised visualizations, and additional annotator and data summaries.
- The Oracle experiment was expanded with additional grid-search configurations for some methods.
- Rank plots were replaced by critical-difference diagrams and the results section was updated accordingly.
- The paper expanded its analysis of annotator agreement and added summary statistics for series lengths and annotated change-point counts.
- The comparison added the zero method, alongside minor revisions, corrections, clarifications, and updated acknowledgements.
- The F1-score computation was corrected and the results updated, with no major effect on the conclusions.
A Simulation Details
The appendix documents implementations, defaults, and Oracle grid searches for the evaluated algorithms. Invalid configurations and computational errors were excluded, and the repository is recommended for exact reproducibility.
- The experiments used author-provided packages where possible, skipped configurations causing computational errors, and documented the setup for reproducibility.
- The changepoint package implemented amoc, binseg, pelt, and segneigh, with default and grid-searched choices spanning functions, penalties, test statistics, and maximum change points.
- Invalid parameter combinations were ignored during grid searches.
- rfpop varied loss, penalty, and threshold parameters, producing 2,424 Oracle configurations, the largest grid among the methods.
- ecp and kcpa used the ecp package, with grids covering algorithm settings, significance levels, segment sizes, costs, and maximum change points.
- wbs varied penalty, integration, and maximum-change-point settings, while bocpd used Gaussian modeling with a negative inverse gamma prior and tuned intensity and prior parameters.
- bocpdms and rbocpdms applied method-specific run-length pruning and timeouts, while Prophet used supplied dates when available and a daily series otherwise.
B Simulated Annotator Agreement
The simulation study tests whether observed agreement among five human annotators could arise by chance. Under the stated simulation assumptions, agreement is significantly above chance for most series and for the F1-score except centralia.
- For each series, the study simulates annotations for K = 5 annotators and computes average one-vs-rest agreement.
- Each simulated change point location is drawn uniformly from indices 2 through T −1, excluding the first and last observations.
- The simulation generates 100,000 annotation sets per series and estimates p-values as the proportion of simulated agreements at least as large as the observed agreement.
- The Poisson rate η controls the number of simulated change points and is set to the average number declared per annotator, approximately 2.295.
- For most series, observed average one-vs-rest agreement is significantly higher than expected by chance under the simulation assumptions.
- For the F1-score, only centralia has a p-value above 0.05, consistent with its 15 observations and annotator disagreement about change-point presence.
C.1 Tables
The tables report descriptive statistics for the benchmark series and method results under default and oracle settings using covering and F1 metrics.
- Table 4 summarizes each series and reports the minimum, maximum, and average number of annotator-marked change points.Financial series marked with † contain trading-day observations sampled every three days.
- Default-Covering reports covering results for every method and time series, with unavailable values marked by failure, missing-data, or multidimensionality indicators.Bold entries identify the highest value for each time series.
- Default-F1 reports F1-score results for each method and time series under default settings.The supplied passage identifies the experiment and metric but does not provide the table values.
- Oracle-Covering reports each method’s maximum segmentation covering score after grid search, including failure, missing-data, timeout, and multidimensionality markers.Bold entries identify the highest value for each time series.
- Oracle-F1 reports each method’s maximum F1-score after grid search, with unavailable results attributed to failure, missing data, timeout, or multidimensionality.Bold entries identify the highest value for each time series.
C.2 Multivariate Critical Difference Diagrams
The critical difference diagrams compare method ranks across both experiments and both metrics for multivariate time series.
- Methods connected in a diagram are not significantly different at α = 0.05.Lower ranks indicate better performance.
D Data Set Overview
The data set overview explains how annotator judgments are displayed for the included time series.
- Dashed vertical lines mark annotated change points, with triangles indicating how many annotators selected each location.Triangle colors identify the five annotators, and a box at the figure’s left reports an annotator count.
D.1 Real Time Series
The real-series collection spans diverse domains and includes economic, environmental, demographic, transportation, health, behavioral, image, and synthetic examples.
- Other real-world series cover populations, tourism and airports, measles cases, river volume, room occupancy, running behavior, and image scan lines.The room-occupancy data contain temperature, humidity, light, and CO2 dimensions.
- Environmental and policy-related series include global CO2, Canadian per-person emissions, ozone-depleting substances, rail mileage, and legislation-associated outcomes.Examples include the Montreal Protocol, U.K. seatbelt requirements, and automated-call regulation.
- The data set also includes quality-control and synthetic demonstration series illustrating known mean, variance, trend, periodicity, outlier, multidimensional, and no-change cases.The quality-control series have known change points and are distinct from the annotated real series.