Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data

David Hallac; Sagar Vare; Stephen Boyd; Jure Leskovec

Source-linked AI summary

Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data

David Hallac, Sagar Vare, Stephen Boyd, Jure Leskovec

arXiv:1706.03161v2Jun 10, 2017cs.LGcs.SImath.OC

TL;DR

Multivariate time-series subsequence clustering must simultaneously segment data and discover interpretable recurring states, a challenge for distance-based approaches. TICC models each state with a sparse, time-invariant MRF, jointly learns segmentation and clusters through alternating minimization, and outperforms baselines while recovering dependency structure and interpretable automobile states. Its window-size assumption limits the method near segment boundaries when structure is not time-invariant.

Problem
Simultaneous segmentation and clustering is difficult, and distance-based methods may miss interpretable cross-sensor dependency structure in multivariate time series.
Method
TICC defines clusters with sparse Gaussian inverse-covariance MRFs over short subsequences and jointly learns their parameters and segmentation using alternating minimization with dynamic programming and ADMM.
Results
TICC outperformed state-of-the-art baselines by at least 41% in cluster assignment accuracy, recovered MRFs with F1 scores of 0.79–0.90, and identified five automobile states.
Takeaways & Limitations
TICC provides accurate clustering together with interpretable dependency networks and a sequential representation of high-dimensional time series.
Takeaways & Limitations
The Toeplitz model assumes time-invariant structure within each window, which may not hold near segment boundaries; window size therefore depends on the application and expected segment length.

Abstract

from arXiv · show

Subsequence clustering of multivariate time series is a useful tool for discovering repeated patterns in temporal data. Once these patterns have been discovered, seemingly complicated datasets can be interpreted as a temporal sequence of only a small number of states, or clusters. For example, raw sensor data from a fitness-tracking application can be expressed as a timeline of a select few actions (i.e., walking, sitting, running). However, discovering these patterns is challenging because it requires simultaneous segmentation and clustering of the time series. Furthermore, interpreting the resulting clusters is difficult, especially when the data is high-dimensional. Here we propose a new method of model-based clustering, which we call Toeplitz Inverse Covariance-based Clustering (TICC). Each cluster in the TICC method is defined by a correlation network, or Markov random field (MRF), characterizing the interdependencies between different observations in a typical subsequence of that cluster. Based on this graphical representation, TICC simultaneously segments and clusters the time series data. We solve the TICC problem through alternating minimization, using a variation of the expectation maximization (EM) algorithm. We derive closed-form solutions to efficiently solve the two resulting subproblems in a scalable way, through dynamic programming and the alternating direction method of multipliers (ADMM), respectively. We validate our approach by comparing TICC to several state-of-the-art baselines in a series of synthetic experiments, and we then demonstrate on an automobile sensor dataset how TICC can be used to learn interpretable clusters in real-world scenarios.

1 INTRODUCTION

TICC addresses the challenge of simultaneously segmenting and clustering multivariate time series while making the resulting clusters interpretable through dependency networks. It learns sparse, time-invariant MRF structures for subsequences and efficiently optimizes assignments and parameters, outperforming baselines in synthetic experiments and producing interpretable automobile states.

Method: TICC jointly learns the time-series segmentation and cluster MRFs using an EM-like alternating-minimization procedure.Dynamic programming handles temporally consistent assignments, while ADMM with closed-form updates solves the Toeplitz graphical lasso subproblem.
Motivation: Multivariate time series can be represented as recurring sequences of states, but discovering and interpreting those states requires simultaneous segmentation and clustering.Distance-based methods may miss structural similarities such as cross-sensor dependencies.
Method: TICC defines each cluster by an MRF that represents partial dependencies among sensors across a short, time-invariant subsequence.Edges correspond to direct dependencies after controlling for other variables, making the learned clusters interpretable.
Evaluation: TICC recovered the underlying MRF dependency networks with F1 scores between 0.79 and 0.90 and identified five automobile sensor states.The automobile analysis used location data and clustering assignments to validate interpretable real-world patterns.

2 PROBLEM SETUP

The problem setup clusters each observation using a short contextual subsequence and assigns observations to temporally consistent clusters with sparse block-Toeplitz inverse covariances. Window size, sparsity, smoothness, and cluster count govern the model and must be selected with attention to the application.

Data representation: Each observation x_t is represented by a preceding window of w observations concatenated into an nw-dimensional subsequence X_t.The window provides temporal context that can distinguish states such as speeding up from driving at a constant speed.
Optimization objective: TICC jointly estimates one Gaussian inverse covariance Θ_i and one assignment set P_i for each of K clusters.Each observation is assigned to exactly one cluster, and Θ_i encodes that cluster’s MRF structure.
Optimization objective: The objective combines log likelihood, sparse inverse-covariance regularization, and a temporal-consistency penalty encouraging neighboring subsequences to share a cluster.The inverse covariances are constrained to be symmetric block Toeplitz matrices.
Toeplitz structure: Block-Toeplitz structure makes within-time and cross-time dependencies repeat across the w-layer window.A(0) represents concurrent sensor relationships, while A(1) and A(2) represent dependencies across one- and two-step time gaps.
Hyperparameters: λ controls MRF sparsity, β encourages adjacent assignments to match, and K determines the number of clusters.BIC, silhouette score, cross-validation, or normalized mutual information can help select these parameters when appropriate.
Hyperparameters: Larger windows capture longer-range cross-time edges but can misclassify segment boundaries when time invariance fails.The window should remain relatively small and may be selected using the application, BIC, or cross-validation.

3 ALTERNATING MINIMIZATION

TICC uses alternating minimization to separate cluster assignment from inverse-covariance estimation. The assignment step enforces temporal consistency, while the parameter step solves a structured sparse graphical-lasso problem.

Problem (1) jointly optimizes cluster assignments P and inverse covariances Θ, making it a highly non-convex mixed combinatorial and continuous problem.
The method alternates between assigning points to clusters and updating cluster parameters using a variation of expectation maximization.The approach is not guaranteed to reach the global optimum.
With fixed Θ, the assignment subproblem jointly maximizes likelihood and temporal consistency, controlled by the switching penalty β.When β = 0, subsequences can be assigned independently; larger β increasingly favors neighboring subsequences sharing a cluster.
Dynamic programming efficiently finds the globally optimal solution to the assignment subproblem.
With fixed assignments, each cluster inverse covariance Θi is updated in parallel using its assigned points’ empirical covariance Si.The likelihood is expressed separately for each cluster, with C independent of Θi.
The Toeplitz graphical lasso minimizes negative log likelihood with sparsity regularization while imposing a block Toeplitz constraint on Θi.The matrix λ can regularize different inverse-covariance sub-blocks differently.

4 TICC ALGORITHM

The TICC algorithm alternates dynamic-programming cluster assignment with ADMM-based Toeplitz graphical-lasso updates. This yields a Viterbi-like temporal assignment procedure and globally optimal solutions for the convex parameter-update subproblem.

TICC ALGORITHM: TICC uses two subroutines: dynamic programming assigns each subsequence to a cluster, and ADMM solves the Toeplitz graphical lasso for parameter updates.
Cluster Assignment: Given cluster parameters, assignment searches among K^T possible labelings while maximizing likelihood and penalizing assignment changes.
Cluster Assignment: The assignment problem is equivalent to a minimum-cost path from timestamp 1 to T, with negative log likelihood as node cost and β for switches.
Cluster Assignment: Dynamic programming implements the assignment procedure, which is equivalent to finding the minimum-cost Viterbi path.
Toeplitz Graphical Lasso: ADMM reformulates the Toeplitz graphical lasso with consensus variable Z, constraint Θ = Z, and Z restricted to the Toeplitz set.
Toeplitz Graphical Lasso: ADMM alternates Θ- and Z-updates with scaled-dual updates until convergence; convexity guarantees the global optimum.Stopping uses primal and dual residuals near zero.
Toeplitz Graphical Lasso: The Z-update decomposes into parallel subproblems across sub-block elements, enabling scalable computation.The decomposition contains (w − 1)n^2 + n(n + 1)/2 independent problems.
Overall Algorithm: The complete algorithm randomly initializes clusters, alternates E- and M-steps, and stops when cluster assignments become stationary.

5 IMPLEMENTATION

The implementation provides a custom Python solver that accepts multivariate time series and problem parameters, then returns assignments and cluster-level MRF structures.

A custom Python solver runs TICC using the original multivariate time series and problem parameters as inputs.
The solver returns each time point’s clustering assignment and the structural MRF representation of every cluster.
The code and solver are available at the cited TICC project URL.

6 EXPERIMENTS

Experiments on synthetic multivariate time series show that TICC accurately clusters temporal sequences, recovers their dependency networks, remains robust to window-size choices, and scales to large datasets.

Experimental Setup: The synthetic experiments generate zero-mean clusters distinguished by Toeplitz inverse-covariance structure and evaluate clustering with macro-F1 against known ground truth.Each observation is modeled in the context of a short window of predecessors, and the experiments use four temporal cluster sequences.
Clustering Accuracy: TICC achieves an average macro-F1 score of 0.95 across four synthetic sequences, 41% higher than GMM’s 0.67.All methods use identical synthetic data and the true number of clusters; TICC scores range from 0.90 to 0.98.
Effect of the Total Number of Samples: With 200 samples per segment, TICC exceeds macro-F1 0.9, while its temporal-consistency variant ultimately reaches 1.0 as sample size grows.At 100 samples, no method accurately clusters the data; the temporal consistency constraint contributes mainly at larger sample sizes.
Network Recovery Accuracy: TICC recovers the underlying network structure with macro-F1 scores between 0.79 and 0.90 across the four synthetic sequences.The learned multilayer MRF represents cluster-specific dependency networks that competing baselines do not explicitly reconstruct.
Window Size Robustness: Window sizes from 4 to 15 yield clustering macro-F1 scores of 0.95–0.98, while sizes from 5 to 14 yield network-recovery macro-F1 scores of 0.87–0.89.Performance worsens only when the window size falls below 4 or exceeds 15, with similar patterns in the other examples.
Scalability of TICC: TICC’s per-iteration runtime scales linearly with the number of observations, clustering 10 million R50 points in approximately 25 minutes per iteration.The ADMM solver takes under 4 seconds per 150×150 inverse covariance, independently of the number of observations.

7 CASE STUDY

TICC is applied to a one-hour, seven-sensor driving session to identify five interpretable driving-state clusters. Network centrality and spatial cluster assignments support interpretations such as turning, slowing down, and repeated turn sequences.

Dataset and setup: The dataset contains 36,000 observations from seven automobile sensors collected every 0.1 seconds during a one-hour real driving session.TICC uses a 1-second window, and Bayesian information criterion selects K = 5 clusters.
Cluster interpretation: Each TICC cluster is represented by a multilayer MRF network, whose node centralities help characterize sensor importance within that driving state.The analysis uses betweenness centrality to compare the relative importance of sensors across clusters.
Cluster interpretation: The five clusters have distinct sensor signatures that support interpretations including turning, slowing down, and straight driving.Y-Acceleration is important in clusters #2 and #5, while cluster #1 has the largest Brake Pedal score and no Gas Pedal importance.
Observed driving patterns: Driving turns follow a repeated sequence of going straight, slowing down, turning, speeding up, then going straight again.The five clusters’ real-world interpretations align closely with estimates based on betweenness scores.
Observed driving patterns: TICC assigns both left and right turns to the same underlying cluster because it groups structural similarities rather than raw-value proximity.Distance-based approaches would treat the two turn directions differently because several sensor values have opposite signs.

8 CONCLUSION AND FUTURE WORK

TICC is a model-based method that simultaneously segments and clusters multivariate time-series subsequences using interpretable multilayer MRFs. Its alternating optimization combines temporally consistent assignment with MRF updates, while future work extends the framework beyond Gaussian observations.

Conclusion: TICC simultaneously segments and clusters high-dimensional multivariate time series into a sequential timeline of interpretable states.Clusters are defined by correlation structure and multilayer Markov random fields.
Conclusion: Each cluster is defined by a multilayer MRF that represents correlation structure, making the resulting clusters interpretable.The method clusters subsequences by structural relationships rather than only by raw values.
Optimization: TICC alternates temporally consistent cluster assignment through dynamic programming with cluster-MRF updates through ADMM.These are the two optimization steps used to discover the clusters.
Future work: Future work could extend TICC to heterogeneous exponential-family MRFs for datasets containing boolean or categorical readings.The proposed extension would broaden the types of datasets incorporated into the framework.