Optimal Transport Based Change Point Detection and Time Series Segment Clustering

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

TL;DR

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 authors developed a robust method for detecting change points (CPD) and clustering similar segments (TSSC) without requiring a predefined mathematical model of the underlying process.

What Problem Does This Paper Address?

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). These work well if the data fits the model, but they fail when the data is complex or unknown. Existing "non-parametric" methods, which don't assume a specific model, often struggle with "noise" in the detection signal, leading to false positives and poor localization of the actual change point. The authors aim to provide a more flexible, statistically grounded approach that works across diverse data types.

Methods

The core of the paper is the use of the Wasserstein distance (also known as the Earth Mover’s Distance). This metric measures the minimum "cost" to transform one probability distribution into another.

  1. Wasserstein Two-Sample Test (W2T): The algorithm uses two sliding windows (one before and one after a time point $t$). It calculates the Wasserstein distance between the empirical distributions of these windows. A high distance suggests a change point.
  2. The Matched Filter: A key contribution is the development of a "matched filter" for post-processing. The raw W2T statistic tends to create "blurry" or extended signatures around a change point. By empirically deriving the shape of this signature and applying a filter, the authors "sharpen" the detection signal, significantly reducing false alarms.
  3. Spectral Clustering for TSSC: Once segments are identified, the authors build an affinity matrix using the Wasserstein distance between the entire point clouds of different segments. They then apply spectral clustering to group similar segments (e.g., all "walking" segments) together.

Datasets

The authors evaluated their approach on both synthetic data and four real-world benchmarks:

  • HASC-PAC2016 & HASC-2011: Large-scale human pedestrian activity data (accelerometer readings for actions like walking, jogging, and climbing stairs).
  • Beedance: Recordings of honeybee movements (turn left, turn right, and "waggle" dance).
  • ECG200: Electrocardiogram data used for detecting abnormal heartbeats.
  • Synthetic IID Data: Used to characterize the matched filter and visualize clustering performance.

Key Insights and Ideas

  • Distribution-Free Flexibility: Because the method relies on Optimal Transport between empirical distributions, it doesn't care if the data is Gaussian, Laplacian, or something entirely different. It simply measures how the "shape" of the data changes.
  • Computational Efficiency: The authors note that the W2T statistic has a computational complexity of $O(\beta \log \beta)$ (where $\beta$ is window size), making it more efficient than other popular non-parametric tests like the M-Statistic ($O(\beta^2)$).
  • The "Matched Filter" Breakthrough: The observation that change points create a predictable "signature" in the W2T statistic allowed the authors to treat CPD as a signal processing problem. This filtering step is what makes the method viable for real-world, noisy data.
  • Better Clustering Geometry: Using t-SNE visualizations, the authors show that Wasserstein distance provides much tighter, more distinct clusters for different distributions compared to other two-sample tests like MMD or Kolmogorov-Smirnov.

Key Results

  • Superior Accuracy: On the HASC-PAC2016 dataset, the W2T method achieved an F1 score of 0.748, outperforming the M-Statistic (0.713).
  • Robustness to Noise: 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.
  • Competitive Unsupervised Clustering: In the Beedance task, their unsupervised approach achieved 65% label accuracy. While lower than state-of-the-art supervised models (87.7%), it is highly competitive for a model that requires no prior training or labels.

Limitations and Future Work

The primary limitation acknowledged by the authors is the IID (Independent and Identically Distributed) assumption. Their theoretical framework assumes that data points within a single segment are independent. In reality, time series data often has temporal dependencies (autocorrelation).

Future work will focus on expanding these Optimal Transport methods to handle non-IID data, which would make the system even more robust for complex dynamical systems where the "order" of data points within a window carries significant information. Additionally, in an online (real-time) setting, the method currently has a minimum detection delay of $2\beta$ (two window lengths).

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