Source-linked AI summary
ecp: An R Package for Nonparametric Multiple Change Point Analysis of Multivariate Data
Nicholas A. James, David S. Matteson
TL;DR
Change point methods often impose restrictive assumptions or focus on univariate data, motivating a more flexible multivariate approach. The ecp package provides divisive and agglomerative nonparametric procedures, with the paper reporting broad distributional-change detection and reasonable E-Divisive estimates, subject to quadratic running times.
Problem
Existing change point methods may be limited to univariate data or marginal changes, motivating methods for multivariate distributional changes with fewer assumptions.
Method
ecp uses an energy-based divergence measure with hierarchical divisive and agglomerative algorithms for multiple change point estimation.
Results
The methods are able to detect any type of distributional change, and E-Divisive obtains reasonable estimates for change point locations.
Takeaways & Limitations
ecp provides nonparametric multiple change point analysis for multivariate data.
Takeaways & Limitations
Both E-Divisive and E-Agglo have running times quadratic in the size of the time series.
Abstract
from arXiv · showhide
There are many different ways in which change point analysis can be performed, from purely parametric methods to those that are distribution free. The ecp package is designed to perform multiple change point analysis while making as few assumptions as possible. While many other change point methods are applicable only for univariate data, this R package is suitable for both univariate and multivariate observations. Estimation can be based upon either a hierarchical divisive or agglomerative algorithm. Divisive estimation sequentially identifies change points via a bisection algorithm. The agglomerative algorithm estimates change point locations by determining an optimal segmentation. Both approaches are able to detect any type of distributional change within the data. This provides an advantage over many existing change point algorithms which are only able to detect changes within the marginal distributions.
1 Introduction
The paper introduces ecp as an R package for nonparametric multiple change point analysis of univariate and multivariate time series. Its methods estimate change point numbers and locations while requiring limited distributional assumptions.
- ecp performs multiple change point analysis for both univariate and multivariate time series.
- The methods can detect arbitrary distributional changes rather than changes restricted to marginal features.
- Change point numbers and locations are estimated simultaneously without requiring prior knowledge of the number of changes.
- The procedures assume independent observations with a finite absolute αth moment for some α ∈(0, 2].
- The package uses the energy statistic as its fundamental divergence measure for identifying distributional changes.
- Existing R packages described in the introduction commonly focus on univariate series or changes in means and variances, while some require user-specified penalties.
2 The ecp package
The ecp package combines a distance-based divergence measure with hierarchical procedures for detecting distributional changes in multivariate data. Its empirical statistic avoids d-dimensional integration and supports consistency under unequal distributions.
- ecp addresses limitations of existing change point packages by analyzing univariate and multivariate series and estimating multiple locations without a priori change-count knowledge.
- The energy-based divergence measure is constructed from characteristic functions or equivalent Euclidean-distance expectations.
- For α ∈(0, 2), the population divergence is zero exactly when the compared distributions are identical, under the stated moment and independence conditions.
- These results support two hierarchical methods for change point analysis, while α = 2 provides only equality of means rather than equality of distributions.
- The sample divergence consistently estimates the population measure without requiring d-dimensional integration.
- Under unequal distributions, the scaled empirical divergence tends to infinity almost surely as sample sizes grow.
3 Hierarchical divisive estimation: E-Divisive
E-Divisive estimates multiple change points through hierarchical divisive splitting. It tests successive candidate changes by permutation and has consistency guarantees under independent observations, but quadratic runtime limits scale.
- E-Divisive sequentially estimates change points by repeatedly splitting existing segments.
- At each iteration, observations are permuted within current segments to obtain an approximate p value for the candidate change point.
- The procedure has complexity O(kT^2), where k is the number of estimated change points and T is the series length.
- Series larger than several thousand observations are not recommended because the procedure is quadratic in series length.
- Under independent observations, E-Divisive generates strongly consistent change point estimates.
- The authors recommend the divisive approach when appropriate because faster alternatives lack a similar consistency guarantee for nonparametric multiple change point analysis.
4 Hierarchical agglomerative estimation: E-Agglo
E-Agglo estimates change points through hierarchical agglomeration of adjacent segments. It maximizes a penalized goodness-of-fit statistic, with quadratic complexity independent of the number of estimated changes.
- E-Agglo begins from an initial segmentation and sequentially merges neighboring segments.
- The selected change point locations correspond to the iteration maximizing the penalized goodness-of-fit statistic.
- The goodness-of-fit statistic is based on between-within distances among adjacent segments.
- A greedy algorithm approximates the optimal segmentation because directly calculating the true maximum is computationally intensive.
- Penalty choices can either penalize every additional change point equally or account for the sizes of newly formed segments.
- E-Agglo has complexity O(T^2), independent of the number of estimated change points, and assumes at least one change point is present.
5 Examples
The examples illustrate ecp’s divisive and agglomerative procedures on univariate, multivariate, tail-behavior, covariance, and spatio-temporal changes. Results show detection of diverse distributional changes, while penalization improves agglomerative segmentation in the covariance example.
- 5.1 Change in univariate normal distribution: The E-Divisive and E-Agglo procedures produce similar results on simulated univariate Gaussian data with changes in mean or variance.The divisive method is illustrated with α = 1, while the agglomerative method is also applied with α = 1.
- 5.2 Multivariate change in covariance: The covariance example changes the joint distribution while leaving marginal distributions unchanged, so univariate procedures applied separately to each margin will not detect it.The data are generated from trivariate normal distributions with a common mean vector and different covariance matrices.
- 5.2 Multivariate change in covariance: The default E-Agglo procedure generates too many change points in the covariance example, whereas penalizing the number of change points yields a more accurate result.The penalized procedure identifies observations 1–300 and 501–750 as identically distributed.
- 5.3 Multivariate change in tails: The tail-behavior example contrasts bivariate Gaussian observations with bivariate Student’s t observations having 2 degrees of freedom.Periods 1 and 3 are Gaussian, while the second period uses the t-distribution; the estimated change-point output is [1] 1 257 504 751.
- 5.4 Inhomogeneous spatio-temporal point process: For the spatio-temporal point process, E-Agglo without a penalty estimates change points at times 0.998, 3.000, and 4.499.The estimated densities provide a reasonable approximation to the true densities, and the goodness-of-fit statistic is compared across penalization schemes.
6 Real data
The ecp procedures are applied to aCGH and financial time series, estimating multiple change points in multivariate and univariate data. On the aCGH data, both methods recover GFL change points, while financial multivariate analysis reveals events missed by E-Agglo on the univariate series.
- Micro-array data: 43 aCGH dimensions produced 14 GFL, 43 MultiRank, 86 E-Divisive, and 28 E-Agglo estimated change points.The E-Divisive and E-Agglo procedures used α = 2 in this comparison.
- Micro-array data: Both ecp methods identified all change points returned by GFL in the full 43-dimensional aCGH series.E-Divisive additionally identified changes in marginal means, and its first 14–20 estimates matched GFL results.
- Financial data: For the DJIA univariate index, E-Divisive estimated 10/21/96, 3/31/03, 10/15/07, and 3/9/09, whereas E-Agglo estimated 8/18/08 and 3/16/09.Several estimated points corresponded to major financial events, including the 2003 Iraq invasion and the 2007–2009 financial crisis period.
- Financial data: In financial data, E-Divisive’s univariate and multivariate results closely corresponded, while multivariate E-Agglo detected significant events missed by its univariate analysis.The authors therefore recommend performing multivariate analysis regardless of the method used.
7 Performance analysis
The paper evaluates change-point segmentations using Rand-based indices across simulated univariate and multivariate time series. These indices summarize agreement with true segmentations, while the Rand Index itself lacks a baseline-adjusted comparison.
- Evaluation metrics: The Rand Index measures segmentation similarity by examining whether pairs of observations share segment membership.The indices compare two segmentations of the same observations.
- Metric limitation: The Rand Index does not measure departure from a baseline model, making comparisons between different estimated segmentations difficult.Adjusted Rand variants address baseline assumptions through alternative expected-index models.
- Evaluation metrics: The simulations compare E-Divisive and E-Agglo using Rand and Adjusted Rand Indices against the true segmentation.Tables 1 and 2 cover univariate series, Table 3 covers multivariate series, and averages use 1,000 simulations.
- Simulation design: Average Rand Index values are reported with standard errors for simulations with T = 150, 300, or 600 observations and three equally sized clusters.The simulations vary mean changes with µ = 1, 2, 4 and variance changes with σ2 = 2, 5, 10.
- Evaluation metrics: Similar results were obtained for the average Adjusted Rand Index, although those results were not reported.The Adjusted Rand implementations use different baseline assumptions and can therefore yield different expected Rand values.
8 Conclusion
The ecp package performs nonparametric change point analysis for multivariate data, automatically determining the number of change points. Under α ∈ (0, 2), its methods can detect any distributional change when the absolute αth moments exist, while E-Divisive is preferred despite quadratic running time.
- The ecp package performs nonparametric change point analysis of multivariate data.
- Both primary methods determine the number of change points without user input; aside from the data, users provide α.The stated user-supplied parameter is α, subject to the method's specified interval.
- For α ∈ (0, 2), the methods detect any type of distributional change when the absolute αth moments exist.
- E-Divisive sequentially tests candidate change points, whereas E-Agglo optimizes a goodness-of-fit statistic; the authors prefer E-Divisive.
- E-Divisive obtains reasonable change-point location estimates in examples, real-data applications, and simulations.
- Both E-Divisive and E-Agglo currently have running times quadratic in the time-series size, motivating future efforts toward linear-time methods.
A Appendix
The appendix introduces additional implementation details for the ecp package's E-Divisive and E-Agglo methods.
- The appendix provides additional implementation details for both the E-Divisive and E-Agglo methods.
A.1 Divisive outline
The divisive procedure estimates multiple change points by repeatedly locating and testing a candidate within the current segmentation, using distance-based statistics and permutation testing.
- E-Divisive estimates change points with a bisection approach.
- Memoization reduces the computational time for maximizing over (τ, κ) to O(T^2) and limits Algorithm 2's loop execution.
- Algorithm 1 takes the time series, significance and resampling parameters, minimum segment size, and α ∈ (0, 2] to output a segmentation.
- The procedure repeatedly locates a candidate change point, tests its statistical significance, and updates the segmentation when significant.
- Algorithm 2 searches candidate locations within segments subject to a minimum segment size and returns the segment, location, and best statistic.
- The permutation test reorders distance-matrix rows and columns within the current segmentation to obtain an approximate p value.
A.2 Agglomerative outline
The agglomerative procedure begins with an initial segmentation and repeatedly merges segments to optimize a goodness-of-fit objective, then selects the best penalized segmentation.
- E-Agglo estimates change points by maximizing a goodness-of-fit statistic.
- The method requires an initial segmentation, then merges segments to maximize the goodness-of-fit statistic.
- Between-within distances are updated as segments merge, with a lemma providing a computational shortcut for merged segments.
- The outline uses neighboring-segment notation in which C_{i+k} and C_{i-k} denote segments k positions to the right and left of C_i.
- Algorithm 4 constructs a distance matrix, evaluates penalized goodness-of-fit statistics across merges, and returns the best segmentation.