Consistent Algorithms for Clustering Time Series

Azadeh Khaleghi, Daniil Ryabko, Jérémie Mary, Philippe PreuxJMLR 2016 · OpenReview

TL;DR

This paper introduces a novel definition of "consistent clustering" for time series, where time series from the same underlying distribution are grouped together. They propose computationally efficient algorithms that achieve this consistency under very general assumptions, even for highly dependent time series, and demonstrate their effectiveness on synthetic and real-world motion capture data.

What Problem Does This Paper Address?

Clustering is a fundamental task in machine learning, aiming to group similar data points. When the data points are time series, the challenge is to group them based on the underlying generative process, not just their observed values. Traditional clustering methods often struggle with the complex dependencies and unknown structures inherent in time series data. Furthermore, defining what "consistent" clustering means for time series, especially in dynamic (online) settings where new data arrives continuously, is a significant challenge. The authors aim to bridge this gap by proposing a rigorous definition of consistency and developing algorithms that meet this standard under minimal assumptions.

Methods

The core of the paper lies in defining and achieving consistent clustering for time series. The authors propose that a clustering algorithm is consistent if it places two time series into the same cluster if and only if they are generated by the same underlying probability distribution. This is a powerful notion, as it directly links clustering to the generative process.

They introduce the distributional distance as a key tool. This distance metric quantifies the difference between two probability distributions, allowing them to measure how distinct the underlying processes generating time series are. They then develop empirically consistent estimators for this distance.

Based on these tools, they propose two main algorithms:

  • Offline (Batch) Clustering Algorithm: This algorithm, when given a fixed set of time series, uses farthest-point initialization to select initial cluster centers and then assigns remaining series to the nearest center based on the estimated distributional distance.
  • Online Clustering Algorithm: This algorithm handles growing datasets by combining multiple clusterings from different time windows, weighted to account for the reliability of distance estimates and the presence of all cluster types.

Crucially, these algorithms are designed to be asymptotically consistent, meaning they will eventually achieve the correct clustering with probability 1 as the length of the time series tends to infinity. They also explore scenarios where the number of clusters is unknown, requiring stronger assumptions like mixing rates.

Datasets

  • Synthetic Data: The authors generate synthetic time series from "rotation processes." These are chosen to be stationary ergodic but not easily approximated by simpler models like finite-state hidden Markov models, reflecting the generality of their approach.
  • Real Data: Motion capture sequences from the MOCAP database are used. These sequences represent human locomotion (walking, running, jumping) and are used to evaluate the algorithms' performance on real-world, complex time-series data.

Key Insights and Ideas

  • Clustering by Distribution, Not Just Observation: The fundamental insight is that true clustering of time series should be based on the underlying generative process, not just superficial similarities in observed data. This is a more robust and interpretable goal.
  • Distributional Distance as a Universal Metric: The distributional distance provides a theoretically sound way to compare any two stationary ergodic distributions, making it suitable for a wide range of time series without strong parametric assumptions.
  • Online Consistency is Tricky: The authors highlight that a naive application of offline algorithms to online data doesn't work. "Bad" sequences (those with insufficient data) can mislead the entire clustering process. Their online algorithm addresses this by intelligently combining information from different time windows.
  • Asymptotic Consistency is Achievable Under Weak Assumptions: The paper demonstrates that even with highly dependent time series and unknown distributions, consistent clustering is possible under surprisingly mild conditions (stationarity and ergodicity).

Key Results

  • Theoretical Consistency: The proposed offline and online algorithms are proven to be strongly asymptotically consistent for clustering time series when the number of clusters is known and the underlying distributions are stationary ergodic.
  • Empirical Performance: Experiments on synthetic data show that both offline and online algorithms achieve decreasing error rates as sequence lengths increase.
  • Real-World Efficacy: On motion capture data, Algorithm 1 (offline) consistently outperforms a previous method (Li and Prakash, 2011) on ergodic motions and performs competitively on non-ergodic motions. The online algorithm demonstrates its robustness by converging to zero error in a simulated online setting, unlike the offline algorithm which remains confused by new data.

Limitations and Future Work

  • Unknown Number of Clusters: While the paper presents some results for the unknown-κ case under stronger mixing assumptions, the general framework primarily assumes known κ. Extending consistent clustering to unknown κ under minimal assumptions remains an open challenge.
  • Rates and Optimality: The paper focuses on asymptotic consistency, meaning performance guarantees as data length goes to infinity. Obtaining finite-sample performance guarantees and understanding the optimal rates of convergence for different classes of time series (e.g., i.i.d. series) is an open area.
  • Growing Sequences Assumption: The online setting assumes sequences grow indefinitely. The authors suggest exploring scenarios where sequences stop growing or are not representative, which would significantly increase the difficulty.
  • Alternative Metrics: The current work relies on the distributional distance. Investigating other distances or compression-based methods for clustering time series within their consistency framework is a promising future direction.
  • Non-stationarity and Gradual Changes: The paper briefly touches upon extending results to Asymptotically Mean Stationary (AMS) ergodic processes and scenarios with slightly different distributions within the same cluster, indicating avenues for further research.

Summary updated

Abstract

The problem of clustering is considered for the case where every point is a time series. The time series are either given in one batch (offline setting), or they are allowed to grow with time and new time series can be added along the way (online setting). We propose a natural notion of consistency for this problem, and show that there are simple, computationally efficient algorithms that are asymptotically consistent under extremely weak assumptions on the distributions that generate the data. The notion of consistency is as follows. A clustering algorithm is called consistent if it places two time series into the same cluster if and only if the distribution that generates them is the same. In the considered framework the time series are allowed to be highly dependent, and the dependence can have arbitrary form. If the number of clusters is known, the only assumption we make is that the (marginal) distribution of each time series is stationary ergodic. No parametric, memory or mixing assumptions are made. When the number of clusters is unknown, stronger assumptions are provably necessary, but it is still possible to devise nonparametric algorithms that are consistent under very general conditions. The theoretical findings of this work are illustrated with experiments on both synthetic and real data.
BibTeX
@article{khaleghi2016consistent,
  author = {Azadeh Khaleghi and Daniil Ryabko and Jérémie Mary and Philippe Preux},
  title = {{Consistent Algorithms for Clustering Time Series}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=KgWarN3bE5C},
}
Figure