Univariate time series segmentation using proxy variables and sparse graph recovery algorithms
This disclosure relates to a time series segmentation system that efficiently and accurately segments univariate time series data. For example, the time series segmentation system utilizes proxy variable time series to identify distinct segments in a univariate time series. To illustrate, the time series segmentation system generates proxy variables that approximate a univariate time series and combine with the time series to generate a supplemented multivariate time series. The time series segmentation system then divides the supplemented multivariate time series into portions using time-based windows, converts the windowed subsequences into graph objects using a sparse graph recovery model, utilizes a conditional similarity model to determine segmentation timestamps from the graph objects, and generates a segmented univariate time series from the segmentation timestamps.
1. A computer-implemented method for segmenting univariate time series data comprising:
generating multiple proxy variable time series for a univariate time series, wherein a first proxy variable time series of the multiple proxy variable time series is based on the univariate time series;
generating a supplemented multivariate time series by supplementing the univariate time series with the multiple proxy variable time series;
grouping portions of the supplemented multivariate time series by a window size to generate windowed subsequences of the supplemented multivariate time series;
generating graph objects from the windowed subsequences utilizing a sparse graph recovery model, wherein the graph objects indicate correlation values between nodes; and
determining one or more segmentation timestamps indicating one or more segment changes in the supplemented multivariate time series utilizing a conditional similarity model conditioned on the univariate time series that determines when changes between correlation values in graph objects meet or exceed a difference threshold.
2. The computer-implemented method of claim 1 , further comprising generating the first proxy variable time series by interpolating the univariate time series at a first sampling rate.
3. The computer-implemented method of claim 1 , further comprising generating a segmented univariate time series by segmenting the supplemented multivariate time series based on the one or more segmentation timestamps.
4. The computer-implemented method of claim 1 , further comprising:
determining a data type of the univariate time series; and
determining the multiple proxy variable time series based on the data type.
5. The computer-implemented method of claim 1 , further comprising:
determining a constant correlation between two proxy variable time series of the multiple proxy variable time series across the univariate time series; and
removing one of the two proxy variable time series.
6. The computer-implemented method of claim 1 , further comprising:
generating additional graph objects from the windowed subsequences utilizing an additional sparse graph recovery model that is different from the sparse graph recovery model; and
determining that the graph objects and the additional graph objects are within a threshold similarity.
7. The computer-implemented method of claim 1 , wherein generating the graph objects from the windowed subsequences includes generating a visual graph of nodes and edges, where the edges indicate a positive or negative partial correlation between connected nodes.
8. The computer-implemented method of claim 1 , further comprising generating multiple graph objects from the windowed subsequences at a same time as part of a batch operation that utilizes one instance of the sparse graph recovery model and shared parameters.
9. The computer-implemented method of claim 1 , wherein the sparse graph recovery model generates conditional independence graph objects that exhibit partial correlation between variables.
10. The computer-implemented method of claim 1 , further comprising:
comparing a first graph object to a second graph object utilizing the conditional similarity model to determine that a difference between the first graph object and the second graph object satisfies a difference threshold; and
determining a first segmentation timestamp based on a segmentation timestamp of the first graph object.
11. The computer-implemented method of claim 1 , wherein the conditional similarity model conditioned on the univariate time series ignores graph object connections between two of the multiple proxy variable time series.
12. A system comprising:
a univariate time series;
a first sparse graph recovery model that generates graph objects from multiple portions of time series data;
a first conditional similarity model that determines differences between two or more graph objects;
a processor; and
a computer memory comprising instructions that, when executed by the processor, cause the system to carry out operations comprising:
generating multiple proxy variable time series for the univariate time series;
generating a first supplemented multivariate time series by supplementing the univariate time series with the multiple proxy variable time series;
grouping portions of the first supplemented multivariate time series by a first window size to generate windowed subsequences of the first supplemented multivariate time series;
generating graph objects from the windowed subsequences utilizing the first sparse graph recovery model, wherein the graph objects indicate correlation values between nodes; and
determining one or more segmentation timestamps indicating one or more segment changes in the first supplemented multivariate time series utilizing the first conditional similarity model conditioned on the univariate time series that determines when changes between correlation values in graph objects meet or exceed a difference threshold.
13. The system of claim 12 , further comprising additional instructions that, when executed by the processor, cause the system to carry out an operation comprising:
generating an additional proxy variable time series for the univariate time series based on the one or more segmentation timestamps;
generating a second supplemented multivariate time series by supplementing the univariate time series with the additional proxy variable time series and the multiple proxy variable time series;
generating additional windowed subsequences from the second supplemented multivariate time series;
generating additional graph objects from the additional windowed subsequences utilizing a second sparse graph recovery model; and
determining one or more refined segmentation timestamps from the additional graph objects utilizing a second conditional similarity model conditioned on the univariate time series.
14. The system of claim 13 , wherein the additional windowed subsequences utilize a second window size that has a smaller window size than the first window size.
15. The system of claim 14 , wherein the additional windowed subsequences are fewer in number than the windowed subsequences.
16. The system of claim 13 , wherein the first sparse graph recovery model is a general sparse graph recovery model, and the second sparse graph recovery model is a specialized sparse graph recovery model.
17. A computer-implemented method for segmenting univariate time comprising:
generating a proxy variable time series for a univariate time series;
generating a supplemented multivariate time series by supplementing the univariate time series with the proxy variable time series;
grouping portions of the supplemented multivariate time series by a window size to generate windowed subsequences of the supplemented multivariate time series;
generating graph objects from the windowed subsequences utilizing a sparse graph recovery model, wherein the graph objects indicate correlation values between nodes;
determining one or more segmentation timestamps indicating one or more segment changes in the supplemented multivariate time series utilizing a conditional similarity model conditioned on the univariate time series that determines when changes between correlation values in graph objects meet or exceed a difference threshold; and
generating a segmented univariate time series by segmenting the supplemented multivariate time series based on the one or more segmentation timestamps.
18. The computer-implemented method of claim 17 , further comprising:
generating a first proxy variable time series by interpolating the univariate time series at a first sampling rate; and
generating a second proxy variable time series by interpolating the univariate time series at a second sampling rate that is different from the first sampling rate.
19. The computer-implemented method of claim 17 , further comprising generating an additional proxy variable time series by interpolating the univariate time series.
20. The computer-implemented method of claim 17 , wherein the proxy variable time series is a polynomial proxy variable.