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 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Change Point DetectionClusteringTime SeriesTime Series AnalysisMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Optimal Transport for Change Detection on LiDAR Point Clouds
Unsupervised change detection between airborne LiDAR data points, taken at separate times over the same location, can be difficult due to unmatching spatial support and noise from the acquisition system. Most current app…
Change DetectionMulti-class ClassificationSemantic SegmentationOn Rank Energy Statistics via Optimal Transport: Continuity, Convergence, and Change Point Detection
This paper considers the use of recently proposed optimal transport-based multivariate test statistics, namely rank energy and its variant the soft rank energy derived from entropically regularized optimal transport, for…
Change Point DetectionMerging Embedded Topics with Optimal Transport for Online Topic Modeling on Data Streams
Topic modeling is a key component in unsupervised learning, employed to identify topics within a corpus of textual data. The rapid growth of social media generates an ever-growing volume of textual data daily, making onl…
Change Point DetectionSoft and subspace robust multivariate rank tests based on entropy regularized optimal transport
In this paper, we extend the recently proposed multivariate rank energy distance, based on the theory of optimal transport, for statistical testing of distributional similarity, to soft rank energy distance. Being differ…
Change Point DetectionTime SeriesTime Series AnalysisA Novel Skip Orthogonal List for Dynamic Optimal Transport Problem
Optimal transport is a fundamental topic that has attracted a great amount of attention from the optimization community in the past decades. In this paper, we consider an interesting discrete dynamic optimal transport pr…