Optimal Transport Based Change Point Detection and Time Series Segment Clustering

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 Seg...

Full description

Saved in:
Bibliographic Details
Main Authors: Cheng, Kevin C., Aeron, Shuchin, Hughes, Michael C., Hussey, Erika, Miller, Eric L.
Format: Conference Proceeding
Language:English
Subjects:
Buildings
change point detection
Clustering algorithms
Conferences
Limiting
optimal transport
Signal processing algorithms
Speech processing
Time series analysis
time series segment clustering
Wasserstein two-sample
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2379-190X
DOI:10.1109/ICASSP40776.2020.9053344