Time Series Synthesis Using the Matrix Profile

This is a complementary website to a short Vision paper submitted to BigData2023. Here, we house extra visualization examples, our code, hyperparameter discussion, and results.

Abstract: Publishing and sharing data is crucial for the data mining community, allowing collaboration and driving open innovation. However, many researchers cannot release their data due to privacy regulations or fear of leaking confidential business information. To alleviate such issues, we propose the Time Series Synthesis Using the Matrix Profile  (TSSUMP) method, where synthesized time series can be released in lieu of the original data. The TSSUMP method synthesizes time series by preserving similarity join information while reducing the correlation between the synthesized and the original time series. As a result, neither the values for the individual time steps nor the local patterns (or shapes) from the original data can be recovered, yet the resulting data can be used for downstream tasks that data analysts are interested in. We concentrate on similarity joins because they are one of the most widely applied time series data mining routines across different data mining tasks. We test our method on a case study of ECG and gender masking prediction. In this case study, the synthesized time series preserves enough information in the original time series such that unmodified data mining tools can obtain near identical performance on the synthesized time series as the original time series.

A note on the importance of preserving information within the Matrix Profile Index (MPI)...

The following text is further discussion most pertinent to Sections 1-3 of our manuscript.

While we believe that our paper is completely self-contained, here we take the liberty of further explaining the importance of the location information contained within the Matrix Profile Index.

We want to reiterate and expand on the text in our paper, because a reader who is not very familiar with time series data mining might baulk at the idea that the actual shape of the subsequences may not be important, but the location of the subsequence’s nearest neighbors is. Gharghabi et. al. showed in [1][2], that for semantic segmentation we only need the location of the subsequence’s nearest neighbors. More generally, there seems to be an emerging realization that such information is sufficient for most time series data mining tasks.

For example, one of the main reasons why the community does motif discovery is to understand the temporal relationship between the motifs. Suppose we compare and contrast the motifs in the New York Taxi demand, and the motifs in New York temperature. An analyst may make the following observations:

• For both datasets, the majority of the subsequence’s motifs are to the day before (or after). This is what forecasters call classic persistence, the assumption that the situation will be the same tomorrow as it was today.

• Uniquely for Taxi, some of the subsequence’s nearest neighbors will be seven days away. This is because of the vagaries of the typical five-day workweek, both Saturday and Sunday are different to typical weekdays, and each other.

• The timing of some motifs across the two different datasets are related. Unusually hot or cold weather does greatly affect taxi demand.

• There are a handful of days in the year when both Taxi and Temperature motifs strongly violate classic persistence, these are usually caused by blizzards. Such events are classic anomalies identified in the Numenta anomaly benchmark [3]

• Finally, if the analyst has access to taxi demand from other cities, she may be able to see interesting differences. For example, Philadelphia, PA is only 80 miles from New York and has similar weather and culture. However, in New York alone, the subsequence’s representing the second Monday of October show much lower persistence. Why is that? It appears that to be caused by Columbus Day, which is celebrated by New York’s Italian-American community but is increasing ignored in the rest of the USA

Note that all the analytics above (and much more) can be conducted with only access to knowledge of the location of the subsequence’s nearest neighbors.

[1] S. Gharghabi, Y. Ding, C. -C. M. Yeh, K. Kamgar, L. Ulanova and E. Keogh, "Matrix Profile VIII: Domain Agnostic Online Semantic Segmentation at Superhuman Performance Levels," 2017 IEEE International Conference on Data Mining (ICDM), New Orleans, LA, USA, 2017, pp. 117-126, doi: 10.1109/ICDM.2017.21.
[2] Gharghabi, S., Yeh, C.-C. M., Ding, Y. et al. Domain agnostic online semantic segmentation for multi-dimensional time series. Data Min Knowl Disc 33, 96–130 (2019). https://doi.org/10.1007/s10618-018-0589-3
[3]  S. Ahmad et al., “Unsupervised Real-Time Anomaly Detection for Streaming Data,” Neurocomputing, vol. 262, 2017, pp. 134-147. Original Source of Numenta anomaly benchmark https://github.com/numenta/NAB/tree/master/data/realKnownCause

Hyperparameter Discussion

The hyperparameters of TSSUMP can be categorized into three groups: 1) a parameter associated with the Matrix Profile, 2) parameters associated with loss function, and 3) parameters associated with the optimization process. The Matrix Profile has just one well-known parameter in window length m, and efforts to deparameterize the Matrix Profile can be found in the Pan-Matrix-Profile (PMP) [1]. The user can set the subsequence length based on their domain knowledge or adopt the PMP method.

Several research efforts have independently shown that for many problems, including segmentation [2] and anomaly detection [3], setting m to about one period (i.e. one heartbeat, one gait cycle) is a strong heuristic. For the loss function, we use $\alpha$, $\beta$, and $\gamma$ to control the relative importance of each term as shown in the following:

We can directly evaluate how well the current solution solves the time series anonymization problem, and can tune these parameters based on how well the current solution performs on each loss term (L_distance, L_identity, L_cosmetic) relative to L_local. We found that setting alpha=1, beta=2, and gamma=1 works well in our experiments.

While L_cosmetic was not discussed in the paper, it is an optional term based on In this case, we decide to model the time series complexity [4] which is defined as: L_comsetic = Complexity(T_{i,m}) - Complexity(\hat{T}_{i,m}))^2. This measure of time series complexity can be understood as the length of a time series after it is "stretched" flat.

The last group of hyperparameters pertain to the optimization process. Similarly to loss function parameters, setting these can be adjusted based on the quality of the current solution. In our experiments, we use the AdamW optimizer with its default parameter settings in Pytorch. We use the ReduceLROnPlateau learning rate scheduler from Pytorch with the initial learning rate set to 10, patience to 5, cooldown to 3, and the rest with default settings. We set the batch size to 512. The number of iterations is set according to the size of the dataset, and more iterations are required to converge on longer time series.

[1] Madrid, Frank, et al. "Matrix profile xx: Finding and visualizing time series motifs of all lengths using the matrix profile." 2019 IEEE International Conf. on Big Knowledge (ICBK). IEEE, 2019.
[2] Gharghabi, Shaghayegh, et al. "Matrix profile VIII: domain agnostic online semantic segmentation at superhuman performance levels." 2017 IEEE international conference on data mining (ICDM). IEEE, 2017.
[3] Lu, Yue, et al. "Matrix profile XXIV: scaling time series anomaly detection to trillions of datapoints and ultra-fast arriving data streams." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.
[4] Batista, Gustavo EAPA, Xiaoyue Wang, and Eamonn J. Keogh. "A complexity-invariant distance measure for time series." Proceedings of the 2011 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2011. 

Further Visualization Examples

Due to submission guideline page restrictions, we did not describe in depth how the time series were anonymized for clustering in lieu of presenting an example for results. We remedy this with a description here, and provide the code in our package.

1. Given several time series to cluster, embed them into a background signal of Gaussian noise. 

2. Record the indices of the background signal where each time series was embedded.

3. TSSUMP-synthesize a proxy time series given the time series described in step #1.

4. Using the recorded indices of each original series from the data in step #2, "cut out" the "anonymized pieces" that serve as our anonymized series.

5. Cluster the original set of time series and the set of TSSUMP-synthesized series.

The Runtime of TSSUMP Method