Abstract
The key to time series clustering is how to characterize the similarity between any two time series. In this paper, we explore a new similarity metric called “cross-predictability”: the degree to which a future value in each time series is predicted by past values of the others. However, it is challenging to estimate such cross-predictability among time series in the high-dimensional regime, where the number of time series is much larger than the length of each time series. We address this challenge with a sparsity assumption: only time series in the same cluster have significant cross-predictability with each other. We demonstrate that this approach is computationally attractive, and provide a theoretical proof that the proposed algorithm will identify the correct clustering structure with high probability under certain conditions. To the best of our knowledge, this is the first practical high-dimensional time series clustering algorithm with a provable guarantee. We evaluate with experiments on both synthetic data and real-world data, and results indicate that our method can achieve more than 80% clustering accuracy on real-world data, which is 20% higher than the state-of-art baselines.
Introduction
Clustering time series is a foundational task in data science, with applications ranging from financial market analysis to neuroscience. However, traditional methods face significant hurdles in the modern data landscape. First, we often operate in the high-dimensional regime ($d \gg T$), where the number of sensors or variables ($d$) far exceeds the number of available time observations ($T$). In such settings, standard regression and similarity metrics become under-constrained and unreliable. Second, most existing metrics, such as Pearson correlation or Euclidean distance, treat time series as static vectors, ignoring the temporal dynamics and the "arrow of time"—the fact that one series might lead or predict changes in another.
This paper addresses these challenges by defining similarity through temporal relationships, specifically "cross-predictability," rather than simultaneous co-occurrence.
Methodology
The proposed framework models the data using a Vector Autoregressive (VAR) model. In this model, the state of the system at time $t+1$ is represented as a linear function of its state at time $t$, governed by a transition matrix $A$. The core innovation lies in estimating this matrix $A$ under high-dimensional constraints.
To solve the $d \gg T$ problem, the authors introduce a Regularized Dantzig Selector based on a sparsity assumption: a sensor is only predicted by other sensors within its own cluster. This implies that the transition matrix $A$ should have a block-diagonal structure. By estimating the rows of $A$ independently and in parallel, the algorithm remains computationally efficient. Once the transition matrix $\hat{A}$ is estimated, it serves as an adjacency matrix for a graph, upon which spectral clustering is applied to identify the final groups.
Experimental Results and Insights
The algorithm was validated on both synthetic and real-world datasets. A striking theoretical and empirical finding is the logarithmic scaling of the method. The number of time series ($d$) can grow exponentially relative to the length of the series ($T$) while still allowing for accurate cluster recovery.
Key results include:
- High Accuracy: On a real-world dataset of 204 building sensors (measuring $CO_2$, temperature, humidity, and light), the Cross-Predictability (CP) method achieved an Adjusted Rand Index of 82.4%.
- Superiority over Baselines: The CP method significantly outperformed traditional approaches; Pearson Correlation achieved 61.7%, and PCA-based clustering reached only 45.6%.
- Robustness: In synthetic tests, the algorithm maintained 100% accuracy even in the challenging regime where $d=T$, where traditional methods typically fail.
Conclusion
By shifting the focus from static correlation to temporal cross-predictability, this research provides a robust framework for high-dimensional time series clustering. The use of sparsity-constrained estimation allows the algorithm to overcome the "curse of dimensionality," backed by a theoretical guarantee of success. While currently based on linear VAR models, future work may extend this approach to non-linear dynamics and overlapping cluster structures, further broadening its applicability to complex real-world systems.
Summary updated