Robust PCA for Anomaly Detection and Data Imputation in Seasonal Time Series

Hong-Lan Botterman, Julien Roussel, Thomas Morzadec, Ali Jabbari, Nicolas J.-b. BrunelLod 2022 · DOI

TL;DR

This paper introduces a robust Principal Component Analysis (RPCA) framework designed to handle noisy, incomplete, and anomalous time series data. They propose both batch and online versions of their method, incorporating temporal regularizations to leverage seasonality and improve signal reconstruction and anomaly detection.

What Problem Does This Paper Address?

Modern data collection systems generate vast amounts of time series data, but this data is often imperfect. It can suffer from missing values due to collection issues or privacy concerns, and it can contain anomalies or outliers that distort the underlying patterns. These imperfections make it difficult to use the data for downstream tasks like prediction or analysis. Traditional methods like Principal Component Analysis (PCA) are sensitive to such corruptions. While Robust PCA (RPCA) exists to handle these issues by separating data into a low-rank (smooth) component and a sparse (anomalous) component, existing RPCA methods often struggle with the temporal dependencies inherent in time series, especially those with seasonality. This paper aims to bridge this gap by developing RPCA techniques specifically tailored for seasonal time series, enabling better anomaly detection and data imputation.

Methods

The core of the paper is the development of a Robust Principal Component Analysis (RPCA) framework with temporal regularizations.

  • Batch RPCA with Temporal Regularizations: The authors extend standard RPCA by adding penalty terms that encourage adjacent time series segments (e.g., consecutive days or weeks) to have similar smooth components. This is achieved by incorporating Toeplitz matrices that penalize differences between columns of the low-rank matrix X at specific lags (e.g., daily or weekly lags). This formulation aims to leverage the expected similarity in seasonal time series.
  • Online RPCA with Temporal Regularizations: Recognizing the limitations of batch methods for large or streaming datasets, they propose an online version. This method uses stochastic optimization and a moving window approach to adapt to potential changes in the underlying subspace over time, making it more suitable for non-stationary data. They also introduce a cross-validation strategy for hyperparameter tuning, making the method more adaptive.
  • Algorithms: They detail algorithms for both the batch and online versions, leveraging techniques like the Alternating Direction Method of Multipliers (ADMM) for the batch approach and stochastic optimization with block-coordinate descent for the online version.

Datasets

  • Synthetic Data: The authors generate synthetic time series by combining sine functions with varying frequencies and amplitudes, then intentionally corrupting them with missing data, anomalies (reaching twice the maximum amplitude), and Gaussian noise. This allows for controlled evaluation of their methods.
  • Real Data: They evaluate their framework on the Automatic Ticket Counting data from stations in Ile-de-France. This dataset represents hourly transport ticket validations from January 2015 to June 2018 and exhibits strong weekly and daily seasonality, as well as non-stationary behaviors like local decreases in validation counts.

Key Insights and Ideas

  • Seasonality is Key: Explicitly modeling temporal dependencies, particularly seasonality, significantly improves the ability of RPCA to disentangle the underlying smooth signal from anomalies and noise in time series.
  • Online Adaptation Matters: For real-world time series data that can exhibit non-stationarity (changing underlying patterns), an online approach with a moving window is crucial for maintaining good performance, outperforming batch methods.
  • End-to-End Pipeline: The proposed method offers a complete pipeline, including hyperparameter tuning via cross-validation, making it practical for real-world applications without requiring extensive prior knowledge of the data.
  • Trade-off in Anomaly Detection: There's an inherent trade-off between achieving good anomaly detection (requiring precise reconstruction) and ensuring the low-rank assumption holds. The proposed methods aim to balance these competing objectives.

Key Results

  • Synthetic Data: Both batch and online RPCA versions showed comparable reconstruction quality on synthetic data, but the batch version offered superior anomaly detection performance (higher F1-scores and precision).
  • Real Data: On the ticketing validation data, the online versions (especially the temporal online with window) outperformed the batch versions in terms of reconstruction errors. This highlights the advantage of adaptive methods for non-stationary real-world data.
  • Modal Decomposition: Applying RPCA before PCA for modal decomposition resulted in smaller differences in the first modes, indicating that RPCA effectively recovers more coherent underlying structures compared to direct PCA on corrupted data.

Limitations and Future Work

  • Hyperparameter Sensitivity: While they propose a cross-validation strategy, the choice of hyperparameters (e.g., the rank r and regularization parameters λ) remains critical and can influence performance.
  • Missing Completely at Random Assumption: The current RPCA frameworks are adapted for data with entries missing "completely at random."
  • Future Work: The authors suggest exploring methods to learn the distributions of missing values to improve imputation. They also acknowledge the need to further investigate the trade-off between anomaly detection and reconstruction accuracy, particularly when dealing with data that is not missing completely at random.

Summary updated

BibTeX
@inproceedings{botterman2022robust,
  author = {Hong-Lan Botterman and Julien Roussel and Thomas Morzadec and Ali Jabbari and Nicolas J.-B. Brunel},
  title = {{Robust PCA for Anomaly Detection and Data Imputation in Seasonal Time Series}},
  booktitle = {Lod},
  year = {2022},
  doi = {10.1007/978-3-031-25891-6\_21},
}
Figure