Change-point driven feature selection for multi-variate time series clustering

Abstract

One embodiment provides a method, including: receiving a multi-variate time-series dataset comprising a plurality of time-dependent datasets; for each of the plurality of time-dependent datasets, segmenting each of the plurality of time-dependent datasets at a transition point; clustering segments of the plurality of time-dependent datasets into clusters having similar lengths of segments; for each cluster (i) selecting a representative segment length and (ii) identifying a feature subset in that cluster; identifying, across the feature subsets, subset transition points, wherein each of the subset transition points corresponds to a change in value that meets a predetermined threshold within its corresponding feature subset; and determining, by applying a threshold test to the subset transition points, a segment length to be used in segmenting the entire multi-variate time-series dataset.

What is claimed is: 
     
       1. A method, comprising:
 receiving a multi-variate time-series dataset comprising a plurality of time-dependent datasets; 
 for each of the plurality of time-dependent datasets, segmenting that time-dependent dataset at a transition point, wherein each of the transition points corresponds to a change in value that meets a predetermined threshold and occurs over a period of time, wherein segments of each of the time-dependent dataset resulting from the segmenting have different lengths, wherein a number of segments for each of the plurality of time-dependent datasets differs between the plurality of time-dependent datasets; 
 clustering the segments across the plurality of time-dependent datasets into clusters having similar lengths of segments, wherein at least one of the clusters comprises segments from more than one of the plurality of time-dependent datasets; 
 for each cluster (i) selecting a representative segment length and (ii) identifying a feature subset in that cluster, wherein a feature subset comprises features from the time-dependent datasets that can be represented by the representative segment for the given cluster; 
 generating a new multi-variate time series dataset from the representative segment lengths and the feature subsets of the clusters; 
 identifying, across the new-multi-variate time series dataset, subset transition points, wherein each of the subset transition points corresponds to a change in value that meets a predetermined threshold within its corresponding feature subset; and 
 determining, by applying a threshold test to the subset transition points, a segment length to be used in segmenting the entire multi-variate time-series dataset. 
 
     
     
       2. The method of  claim 1 , wherein the segmenting comprises an iterative segmenting process that results in different numbers of segments across each iteration of the segmenting via modifying the predetermined threshold for each iteration. 
     
     
       3. The method of  claim 2 , comprising selecting a time-dependent dataset segment length by (i) forming a graph of the different numbers of segments produced via the iterative segmenting process and (ii) identifying a knee point within the graph, wherein the knee point of the graph corresponds to a segment length and is selected as the time-dependent dataset segment length, the knee point comprising a local maximum of the graph. 
     
     
       4. The method of  claim 1 , wherein the threshold test comprises a lower threshold boundary and an upper threshold boundary. 
     
     
       5. The method of  claim 4 , wherein the determining comprises (i) identifying that a number of the subset transition points are below the lower threshold boundary and (ii) augmenting the subset transition points with an additional segmentation of the multi-variate time-dependent datasets utilizing the representative segment length. 
     
     
       6. The method of  claim 4 , wherein the determining comprises (i) identifying that a number of the subset transition points are above the upper threshold boundary and (ii) selecting the representative segment length as the segment length. 
     
     
       7. The method of  claim 4 , wherein the determining comprises (i) identifying that a number of the subset transition points are within the lower threshold boundary and the upper threshold boundary and (ii) selecting the subset transition points as the segment change points. 
     
     
       8. The method of  claim 1 , wherein identifying a feature subset comprises mapping a given segment within a cluster to the time-dependent dataset that the given segment occurs within. 
     
     
       9. The method of  claim 1 , wherein the selecting a representative segment length for a given cluster comprises averaging the segment lengths within the given cluster. 
     
     
       10. The method of  claim 1 , wherein the identifying subset transition points comprises identifying a change in value within the feature subset that at least meets a predetermined threshold. 
     
     
       11. An apparatus, comprising:
 at least one processor; and 
 a computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising: 
 computer readable program code configured to receive a multi-variate time-series dataset comprising a plurality of time-dependent datasets; 
 computer readable program code configured to, for each of the plurality of time-dependent datasets, segment that time-dependent dataset at a transition point, wherein each of the transition points corresponds to a change in value that meets a predetermined threshold and occurs over a period of time, wherein segments of each of the time-dependent dataset resulting from the segmenting have different lengths, wherein a number of segments for each of the plurality of time-dependent datasets differs between the plurality of time-dependent datasets; 
 computer readable program code configured to cluster the segments across the plurality of time-dependent datasets into clusters having similar lengths of segments, wherein at least one of the clusters comprises segments from more than one of the plurality of time-dependent datasets; 
 computer readable program code configured to, for each cluster, (i) select a representative segment length and (ii) identify a feature subset, wherein a feature subset comprises features from the time-dependent datasets that can be represented by the representative segment for the given cluster; 
 computer readable program code configured to generate a new multi-variate time series dataset from the representative segment lengths and the feature subsets of the clusters; 
 computer readable program code configured to identify, across the new-multi-variate time series dataset, subset transition points, wherein each of the subset transition points corresponds to a change in value that meets a predetermined threshold within its corresponding feature subset; and 
 computer readable program code configured to determine, by applying a threshold test to the subset transition points, a segment length to be used in segmenting the entire multi-variate time-series dataset. 
 
     
     
       12. A computer program product, comprising:
 a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code executable by a processor and comprising: 
 computer readable program code configured to receive a multi-variate time-series dataset comprising a plurality of time-dependent datasets; 
 computer readable program code configured to, for each of the plurality of time-dependent datasets, segment that time-dependent dataset at a transition point, wherein each of the transition points corresponds to a change in value that meets a predetermined threshold and occurs over a period of time, wherein segments of each of the time-dependent dataset resulting from the segmenting have different lengths, wherein a number of segments for each of the plurality of time-dependent datasets differs between the plurality of time-dependent datasets; 
 computer readable program code configured to cluster the segments across the plurality of time-dependent datasets into clusters having similar lengths of segments, wherein at least one of the clusters comprises segments from more than one of the plurality of time-dependent datasets; 
 computer readable program code configured to, for each cluster, (i) select a representative segment length and (ii) identify a feature subset, wherein a feature subset comprises features from the time-dependent datasets that can be represented by the representative segment for the given cluster; 
 computer readable program code configured to generate a new multi-variate time series dataset from the representative segment lengths and the feature subsets of the clusters; 
 computer readable program code configured to identify, across the new-multi-variate time series dataset, subset transition points, wherein each of the subset transition points corresponds to a change in value that meets a predetermined threshold within its corresponding feature subset; and 
 computer readable program code configured to determine, by applying a threshold test to the subset transition points, a segment length to be used in segmenting the entire multi-variate time-series dataset. 
 
     
     
       13. The computer program product of  claim 12 , wherein the segmenting comprises an iterative segmenting process that results in different numbers of segments across each iteration of the segmenting via modifying the predetermined threshold for each iteration. 
     
     
       14. The computer program product of  claim 13 , comprising selecting a time-dependent dataset segment length by (i) forming a graph of the different numbers of segments produced via the iterative segmenting process and (ii) identifying a knee point within the graph, wherein the knee point of the graph corresponds to a segment length and is selected as the time-dependent dataset segment length, the knee point comprising a local maximum of the graph. 
     
     
       15. The computer program product of  claim 12 , wherein the determining comprises (i) identifying that a number of the subset transition points are below a lower threshold boundary of the threshold test and (ii) augmenting the subset transition points with an additional segmentation of the multi-variate time-dependent datasets utilizing the representative segment length. 
     
     
       16. The computer program product of  claim 12 , wherein the determining comprises (i) identifying that a number of the subset transition points are above an upper threshold boundary of the threshold test and (ii) selecting the representative segment length as the segment length. 
     
     
       17. The computer program product of  claim 12 , wherein the determining comprises (i) identifying that a number of the subset transition points are within a lower threshold boundary and an upper threshold boundary of the threshold test and (ii) selecting the subset transition points as the segment change points. 
     
     
       18. The computer program product of  claim 12 , wherein identifying a feature subset comprises mapping a given segment within a cluster to the time-dependent dataset that the given segment occurs within. 
     
     
       19. The computer program product of  claim 12 , wherein selecting a representative segment length for a given cluster comprises averaging the segment lengths within the given cluster. 
     
     
       20. A method, comprising:
 receiving a time series dataset comprising a plurality of time-dependent features; 
 identifying, for each of the plurality of time-dependent features, change points within a given time-dependent feature, wherein a change point corresponds to an aspect within a given time-dependent feature that has a value change amount that meets a predetermined threshold and occurs over a period of time; 
 segmenting each of the plurality of time-dependent features at the change points identified for a given time-dependent feature, wherein segments of each of the time-dependent feature resulting from the segmenting have different lengths, wherein a number of segments for each of the plurality of time-dependent features differs between the plurality of time-dependent features; 
 clustering the segments across the time series dataset into clusters having similar lengths of segments, wherein at least one of the clusters comprises segments from more than one of the plurality of time-dependent features; 
 for each cluster (i) selecting a representative segment length and (ii) identifying a feature subset in that cluster, wherein a feature subset comprises features from the time-dependent features that can be represented by the representative segment for the given cluster; 
 generating a new multi-variate time series feature from the representative segment lengths and the feature subsets of the clusters; 
 identifying, across the new-multi-variate time series dataset, subset change points, wherein each of the subset change points corresponds to an aspect within a given feature subset that has a value change amount that meets a predetermined threshold and occurs over a period of time; and 
 determining, by applying a threshold test to the subset change points, a segment length to be used in segmenting the time series dataset.