Optimal Transport Based Change Point Detection and Time Series Segment Clustering

Kevin C. Cheng, Shuchin Aeron, Michael C. Hughes, Erika Hussey, Eric L. Miller

Abstract

Two common problems in time series analysis are the decomposition of the data stream into disjoint segments that are each in some sense "homogeneous" - a problem known as Change Point Detection (CPD) - and the grouping of similar nonadjacent segments, a problem that we call Time Series Segment Clustering (TSSC). Building upon recent theoretical advances characterizing the limiting distribution-free behavior of the Wasserstein two-sample test (Ramdas et al. 2015), we propose a novel algorithm for unsupervised, distribution-free CPD which is amenable to both offline and online settings. We also introduce a method to mitigate false positives in CPD and address TSSC by using the Wasserstein distance between the detected segments to build an affinity matrix to which we apply spectral clustering. Results on both synthetic and real data sets show the benefits of the approach.

Introduction

Time series analysis often requires two critical steps: Change Point Detection (CPD)—identifying exactly when a process changes (e.g., when a person stops walking and starts running)—and Time Series Segment Clustering (TSSC)—grouping non-adjacent segments that represent the same activity. Traditional parametric methods rely on specific models like ARMA or HMMs, which work well if the data fits the model but fail when the data is complex or unknown.

This paper introduces a non-parametric, "distribution-free" framework for analyzing time series data using Optimal Transport (OT). By leveraging the Wasserstein distance to compare sliding windows of data, the proposed method enables robust CPD and TSSC without requiring a predefined mathematical model of the underlying process.

Methodology

The core of the proposed framework is the use of the Wasserstein distance (also known as the Earth Mover’s Distance) to measure the minimum cost to transform one probability distribution into another.

Conceptual overview of the CPD and TSSC pipeline using Wasserstein distance.

The algorithm proceeds in three main stages:

  1. Wasserstein Two-Sample Test (W2T): The algorithm employs two sliding windows (one before and one after a time point $t$) and calculates the Wasserstein distance between their empirical distributions. A high distance indicates a likely change point.
  2. The Matched Filter: A key contribution is the development of a "matched filter" for post-processing. Raw W2T statistics often create "blurry" signatures around change points. By empirically deriving the shape of this signature and applying a filter, the detection signal is sharpened, significantly reducing false alarms.
  3. Spectral Clustering for TSSC: Once segments are identified, an affinity matrix is constructed using the Wasserstein distance between the entire point clouds of different segments. Spectral clustering is then applied to group similar segments together.

Experimental Evaluation

The approach was evaluated on synthetic data and four real-world benchmarks: HASC-PAC2016 and HASC-2011 (human activity accelerometer data), Beedance (honeybee movement recordings), and ECG200 (electrocardiogram data).

Application of the W2T method to human activity data (HASC), showing ground truth vs. predicted labels and the effect of filtering.

Results indicate superior performance over traditional non-parametric methods. On the HASC-PAC2016 dataset, the W2T method achieved an F1 score of 0.748, outperforming the M-Statistic (0.713). The matched filter proved essential; for the HASC2011 dataset, it improved the F1 score from 0.720 to 0.824 by cleaning up spurious local maxima. In the Beedance task, the unsupervised approach achieved 65% label accuracy, which is highly competitive for a model requiring no prior training.

Discussion and Conclusion

The W2T framework offers significant advantages in flexibility and efficiency. Because it relies on Optimal Transport between empirical distributions, it is distribution-free and does not require assumptions about the data's underlying shape (e.g., Gaussian vs. Laplacian). Furthermore, with a computational complexity of $O(\beta \log \beta)$, it is more efficient than other popular non-parametric tests like the M-Statistic ($O(\beta^2)$).

While the current method assumes data points within a segment are Independent and Identically Distributed (IID), future work will focus on expanding these methods to handle temporal dependencies (autocorrelation). This would enhance robustness for complex dynamical systems where the temporal order of data points carries critical information.

Summary updated

Abstract

Two common problems in time series analysis are the decomposition of the data stream into disjoint segments that are each in some sense "homogeneous" - a problem known as Change Point Detection (CPD) - and the grouping of similar nonadjacent segments, a problem that we call Time Series Segment Clustering (TSSC). Building upon recent theoretical advances characterizing the limiting distribution-free behavior of the Wasserstein two-sample test (Ramdas et al. 2015), we propose a novel algorithm for unsupervised, distribution-free CPD which is amenable to both offline and online settings. We also introduce a method to mitigate false positives in CPD and address TSSC by using the Wasserstein distance between the detected segments to build an affinity matrix to which we apply spectral clustering. Results on both synthetic and real data sets show the benefits of the approach.
BibTeX
@inproceedings{cheng2020optimal,
  author = {Kevin C. Cheng and Shuchin Aeron and Michael C. Hughes and Erika Hussey and Eric L. Miller},
  title = {{Optimal Transport Based Change Point Detection and Time Series Segment Clustering}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=yFc5nUYASyJ},
}

Loading related content...

Figure