Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data

David Hallac, Sagar Vare, Stephen P. Boyd, Jure Leskovec

TICC (Toeplitz Inverse Covariance-Based Clustering) provides a robust framework for segmenting and clustering multivariate time series data by focusing on the structural dependencies between sensors. Unlike traditional methods that rely on raw value similarity, TICC characterizes clusters as Markov Random Fields (MRFs) with a block-Toeplitz structure, allowing it to identify recurring patterns even when sensor magnitudes vary.

The Challenge of Multivariate Time Series Clustering

Clustering multivariate time series involves two simultaneous challenges: segmentation (dividing a long series into meaningful intervals) and clustering (grouping these intervals into recurring states).

Traditional approaches like K-means or Dynamic Time Warping (DTW) are "distance-based," meaning they group segments where raw sensor values are similar. However, in complex systems like a moving vehicle, raw values often fluctuate based on external factors (e.g., speed), while the underlying physical relationships between components remain stable. TICC addresses this by capturing these time-invariant interdependencies through a model-based approach.

Methodology

The TICC method defines each cluster as a Gaussian Inverse Covariance matrix ($\Theta$), representing a Markov Random Field (MRF). To ensure time-invariance, the model enforces a block-Toeplitz constraint on this matrix. This ensures that the partial correlation between sensors remains consistent regardless of the window's starting position.

Overview of the TICC framework, illustrating how multivariate time series are segmented into clusters defined by distinct Markov Random Field structures.

The optimization process uses an alternating minimization strategy:

  1. Assignment (E-step): Time points are assigned to clusters using Dynamic Programming (similar to the Viterbi algorithm). A temporal consistency penalty ($\beta$) is applied to discourage rapid switching between clusters, ensuring contiguous segments.
  2. Update (M-step): Cluster parameters are updated by solving a Toeplitz Graphical Lasso problem. The authors developed a specialized solver using the Alternating Direction Method of Multipliers (ADMM) for high computational efficiency.

Key Insights: Structure Over Magnitude

TICC's primary innovation is prioritizing correlation structure over data magnitude. In a car sensor study, TICC successfully grouped left and right turns into a single "turning" state because the structural relationship between steering and acceleration was consistent, despite the sensor values having opposite signs.

Furthermore, because each cluster is an MRF, the resulting models are highly interpretable. Researchers can use network metrics like betweenness centrality to identify which sensors "drive" specific states, turning a "black box" cluster into an interpretable physical state (e.g., identifying the gas pedal as the most influential node during acceleration).

Evaluation and Results

The authors evaluated TICC using both synthetic data (generated from random Erdős-Rényi graphs) and a real-world automobile dataset consisting of 36,000 observations from 7 sensors.

Performance comparison of TICC against baseline methods across varying segment lengths, showing significant improvements in Macro-F1 score.

Key findings include:

  • Superior Accuracy: TICC outperformed state-of-the-art baselines like GMM and DTW by over 40% in cluster assignment accuracy on synthetic benchmarks.
  • Structural Recovery: The algorithm successfully recovered hidden network edges with $F_1$ scores between 0.79 and 0.90.
  • Scalability: TICC scales linearly with the number of observations ($T$), capable of processing 10 million data points in approximately 25 minutes per iteration.
  • Real-World Discovery: In the driving dataset, TICC automatically identified five distinct, interpretable states: slowing down, turning, speeding up, cruising, and driving on curvy roads.

Limitations and Future Work

Currently, TICC assumes data follows a Gaussian distribution. Future research aims to extend this to heterogeneous exponential family MRFs to accommodate boolean or categorical data. Additionally, while the model is robust to window size ($w$), selecting the optimal number of clusters ($K$) and the smoothness penalty ($\beta$) still requires methods like the Bayesian Information Criterion (BIC) or cross-validation.

Summary updated

BibTeX
@inproceedings{hallac2018toeplitz,
  author = {David Hallac and Sagar Vare and Stephen P. Boyd and Jure Leskovec},
  title = {{Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/732},
}
Figure