Source-linked AI summary
A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data
David S. Matteson, Nicholas A. James
TL;DR
Existing methods often assume a single or known number of change points. This paper proposes hierarchical procedures for detecting distributional changes in multivariate observations and establishes consistency for its preferred divisive procedure.
Problem
Existing change-point methodologies often assume a single or known number of change points.
Method
The proposed approach uses hierarchical estimation to detect distributional changes in multivariate observations, including multiple change points.
Results
The divisive procedure has established consistency, and the approach can consistently detect distributional changes in multivariate observations.
Takeaways & Limitations
The paper prefers the consistent divisive procedure in practice for multivariate multiple-change-point analysis.
Takeaways & Limitations
The divisive procedure's computation depends on the number of estimated change points.
Abstract
from arXiv · showhide
Change point analysis has applications in a wide variety of fields. The general problem concerns the inference of a change in distribution for a set of time-ordered observations. Sequential detection is an online version in which new data is continually arriving and is analyzed adaptively. We are concerned with the related, but distinct, offline version, in which retrospective analysis of an entire sequence is performed. For a set of multivariate observations of arbitrary dimension, we consider nonparametric estimation of both the number of change points and the positions at which they occur. We do not make any assumptions regarding the nature of the change in distribution or any distribution assumptions beyond the existence of the alpha-th absolute moment, for some alpha in (0,2). Estimation is based on hierarchical clustering and we propose both divisive and agglomerative algorithms. The divisive method is shown to provide consistent estimates of both the number and location of change points under standard regularity assumptions. We compare the proposed approach with competing methods in a simulation study. Methods from cluster analysis are applied to assess performance and to allow simple comparisons of location estimates, even when the estimated number differs. We conclude with applications in genetics, finance and spatio-temporal analysis.
1 Introduction
The paper addresses offline detection of an unknown number of distributional changes in multivariate time series, where existing methods often assume known change-point counts or have limited multivariate applicability. It proposes a nonparametric, clustering-based approach with broad distributional scope and consistent estimation under stated conditions.
- Motivation: Change point analysis detects distributional changes in time-ordered observations and supports applications in finance, bioinformatics, anomaly detection, data mining, and signal processing.Examples include modeling multivariate financial time series, identifying disease-associated genes, detecting credit-card fraud, classifying data, and finding changes in image streams.
- Problem: Many existing methods assume a single or known number of change points, an assumption the paper identifies as often unrealistic.The introduction also notes that traditional methods have limited applicability to multivariate data.
- Method: The method consistently estimates an unknown number of multiple change-point locations for observations in arbitrary fixed dimension.Its distributional assumptions are limited to existence of the αth absolute moment for some α ∈(0, 2).
- Method: The proposed nonparametric approach uses Euclidean distances between sample observations and avoids difficulties associated with multivariate density-based methods.The methodology is motivated by cluster analysis and is designed to be simple to calculate.
- Algorithms: Estimation simultaneously identifies change-point number and locations, using a bisection approach for computational efficiency.The paper presents a divisive procedure and an alternative agglomerative algorithm, with applications to simulated, real, and spatio-temporal data.
2 Methodology
The methodology addresses multiple change points with unknown number and locations using a nonparametric, hierarchical procedure for multivariate observations. It combines Euclidean-distance distributional divergence with iterative bisection and statistical testing.
- Motivation: Unknown numbers and locations make naive concurrent estimation infeasible, motivating hierarchical procedures for multiple change point analysis.For known k, exhaustive location search becomes computationally intractable when k ≥3; the fully unknown case is likewise infeasible.
- E-Divisive: E-Divisive is a nonparametric method for multiple change point analysis of multivariate observations.The method is explicitly introduced for sequences of multivariate observations and combines bisection with a multivariate divergence measure.
- Distributional divergence: The population divergence is nonnegative and equals zero exactly when the two independent random vectors are identically distributed.This property holds for α ∈ (0,2) under finite α-th absolute moments.
- Distributional divergence: The empirical divergence uses Euclidean distances between sample elements and converges almost surely to its population counterpart as sample sizes grow.Its computation has order O(m^2 ∨ n^2), while a characteristic-function counterpart requires d-dimensional integration.
- Hierarchical estimation: E-Divisive iteratively searches within estimated clusters, selecting a change point and associated κ while retaining O(kT^2) running time.Allowing κ to vary helps avoid confounding from mixture distributions spanning multiple change points.
3 Consistency
The consistency analysis establishes that the proposed estimator consistently recovers single and multiple change-point locations under heterogeneous independent observations and regularity conditions.
- Single Change Point: A strongly consistent estimator is obtained for a single change-point location in rescaled time.The result applies when the candidate location stays away from the sequence boundaries through δT → 0 and TδT → ∞.
- Single Change Point: Consistency requires each cluster size to increase, but not necessarily at the same rate.The minimum cluster size is imposed in applications and may need to be larger when E(X, Y; α) is relatively small.
- Limitations: Rates of convergence require additional distributional information because the estimator’s behavior depends on unknown data distributions.The consistency result alone does not determine convergence rates.
- Multiple Change Points: For multiple change points, the divergence measure is maximized at true adjacent change-point boundaries rather than between them.The proof reduces each interval between consecutive changes to a two-change-point problem and uses strict convexity.
- Multiple Change Points: Repeated application of the consistency theorem makes the first k estimated change points converge to their true locations.This extends the single-change-point result to the general multiple-change-point setting.
4 Simulation Study
Simulations compare E-Divisive with rank-based, parametric, and kernel competitors across univariate and multivariate distributional changes. E-Divisive is consistent and competitive, but performance depends on the change type and the presence of noise.
- Design: Each simulation uses 1,000 independent sequences with two change points and evaluates average Rand index with approximate standard errors.The comparisons include E-Divisive, MultiRank, PELT, and KCP across the reported settings.
- Univariate Analysis: E-Divisive compares favorably with PELT for detecting changes in mean and variance.PELT is specifically designed to identify changes in mean or variance, whereas E-Divisive is evaluated more broadly.
- Univariate Analysis: Rand index values for E-Divisive tend toward 1 as sample size increases, consistent with the theoretical result.The simulations vary sample size while assessing clustering agreement with the true segmentation.
- Multivariate Analysis: For simultaneous bivariate mean changes, all methods perform similarly.The comparison uses E-Divisive, KCP, and MultiRank under the specified bivariate simulation design.
- Multivariate Analysis: KCP performs best for correlation changes when the sample size is sufficiently large, while MultiRank is not reliable for detecting correlation changes.KCP requires sufficient sample size to detect the correlation changes in these simulations.
- Multivariate Analysis: E-Divisive improves with dimension when all components are related, but performance worsens when added components are independent and unchanged.The authors conjecture that simultaneous component changes help, while dimension reduction may be necessary in the presence of noise.
5 Applications
Applications illustrate the proposed procedures on genomic, financial, and spatio-temporal data, identifying distributional changes and comparing estimated locations across methods.
- Genetics: The genomic analysis used normalized aCGH signals from 43 individuals after excluding series with more than 7% missing values.The observations were normalized so the modal logarithmic ratio was zero; missing values were imputed by neighboring averages.
- Genetics: 43 change points were found by MultiRank and 97 by E-Divisive in the 43-dimensional joint series.The E-Divisive analysis used α = 1, minimum cluster size 10, R = 499 permutations, and p0 = 0.05.
- Genetics: For individual 10, MultiRank, KCPA, PELT, and E-Divisive estimated 17, 41, 47, and 35 change points, respectively.Reported adjusted Rand values include 0.572 for Kernel CP and 0.631 for PELT under MultiRank, 0.678 for PELT and 0.658 for E-Divisive under KCPA, and 0.853 for E-Divisive under PELT.
- Finance: Two significant change points were estimated in Cisco Systems monthly log returns, at April 2000 and October 2002, with approximate p-values below 0.03.The analysis used 262 monthly returns, α = 1, minimum cluster size 30, and R = 499 permutations.
- Finance: The middle Cisco period was relatively more volatile and skewed than either neighboring period, while within-period returns showed no significant serial correlation or conditional heteroskedasticity.Distributional comparisons used quantile-quantile plots and kernel density estimates with 95% point-wise bootstrap confidence bands.
6 An Agglomerative Algorithm
The agglomerative algorithm preserves temporal ordering while greedily merging adjacent clusters according to a goodness-of-fit statistic, offering practical speed advantages for large series.
- Algorithm: The algorithm permits merging only adjacent clusters, preserving the time ordering of observations.Clusters Ci and Cj can merge when one immediately follows the other.
- Algorithm: Adjacent clusters are greedily merged when the goodness-of-fit statistic increases most or decreases least, until all observations form one cluster.The estimated number of change points is selected from the clustering that maximizes the statistic across the merging sequence.
- Algorithm: The goodness-of-fit statistic measures between-within distance among adjacent clusters.It is calculated for the initial clustering and updated after each merge.
- Computational considerations: The agglomerative approach has overall computational complexity O(T^2) and runs faster in practice than E-Divisive by restricting candidate change-point locations.The statistic can be updated in O(1) after a merge.
- Toronto EMS application: For approximately 200,000 Toronto EMS events, the week was initially partitioned into 672 equally spaced 15-minute periods.The analysis pooled intra-week changes into one weekly period.
- Toronto EMS application: The goodness-of-fit measure was maximized at 31 change points, occurring daily and primarily in the evening, with some rapid spatial-distribution changes.Three adjacent cluster periods showed persistent downtown density and shape changes in outlying regions.
7 Conclusion
The paper presents nonparametric divisive and agglomerative methods for multivariate multiple-change-point analysis, estimating both the number and locations of distributional changes.
- Scope and guarantees: The methods consistently detect any type of distributional change in independent multivariate observations under existence of an αth absolute moment for some α ∈ (0, 2).They estimate both the number and locations of change points.
- Contribution: Both proposed methods estimate the number and locations of change points without requiring prior knowledge or supplementary analysis.This is presented as an advantage relative to several previously mentioned methods.
- Algorithms: The paper provides both divisive and agglomerative versions of the method.The divisive version hierarchically tests statistical significance, whereas the agglomerative version optimizes a goodness-of-fit statistic.
- Practical consideration: The divisive procedure is preferred in practice because its consistency was established, although its computation depends on the estimated number of change points.The computational dependence is identified as a practical constraint.