A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data

Abstract

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 are continually arriving and are 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 αth absolute moment, for some α ∈ (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 the 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. Supplementary materials for this article are available online.

KEY WORDS:

• Cluster analysis
• Multivariate time series
• Permutation tests
• Signal processing
• U-statistics

Additional information

Funding

We would like to thank the three referees and Associate Editor for their careful review of the manuscript and helpful comments. The authors sincerely thank Toronto EMS for sharing their data. The authors are also grateful to Louis C. Segalini for his research assistance in preparing the financial data analysis. This work was partially supported by National Science Foundation Grant Number CMMI-0926814.