Temporal clustering of non-stationary data

Abstract

Techniques for clustering non-stationary data are disclosed. In embodiments, a method is disclosed comprising initializing a plurality of functional centroids; partitioning a non-stationary data set, using the functional centroids, into partitions, the number of partitions being equal to the number of functional centroids; generating a set of fitted functional centroids for each of the partitions; replacing at least one of the functional centroids with a corresponding fitted functional centroid if a computed energy of the corresponding fitted functional centroid is less than an energy of the at least one functional centroid; computing a summation of the energies associated with each of the functional centroids; and outputting the functional centroids upon determining that a termination condition is met.

1 - 23 . (canceled) 
     
     
         24 . A method comprising:
 initializing functional centroids, a respective functional centroid in the functional centroids accepting a timestamp as an input and outputting at least one data point based on the timestamp;   replacing at least one functional centroid in the functional centroids with a corresponding fitted functional centroid to obtain final functional centroids if a computed energy of the corresponding fitted functional centroid is less than an energy of the at least one functional centroid; and   outputting the final functional centroids.   
     
     
         25 . The method of  claim 24 , further comprising:
 partitioning a non-stationary data set, using the functional centroids, into partitions, a number of partitions being equal to a number of functional centroids; and   generating a set of fitted functional centroids for each of the partitions, the set of fitted functional centroids including the corresponding fitted functional centroid.   
     
     
         26 . The method of  claim 25 , wherein partitioning the non-stationary data set comprises:
 identifying, for each point in the non-stationary data set, a closest functional centroid generating an output value closest to a respective point; and   assigning each point to a partition based on the closest functional centroid.   
     
     
         27 . The method of  claim 25 , further comprising:
 computing a sum of energies associated with each of the functional centroids; and   determining that the sum does not result in a net energy decrease prior to outputting the final functional centroids.   
     
     
         28 . The method of  claim 27 , an energy of a function computed by summing differences between known points at respective times and outputs of the function for corresponding respective times. 
     
     
         29 . The method of  claim 27 , wherein determining that the sum of the energies does not result in a net energy decrease comprises:
 computing a first energy for the functional centroids prior to generating the set of fitted functional centroids;   computing a second energy for the functional centroids after replacing at least one of the functional centroids with a corresponding fitted functional centroid; and   determining that the sum of the energies does not result in a net energy decrease if the second energy is not less than the first energy.   
     
     
         30 . The method of  claim 27 , further comprising performing a second partitioning of the non-stationary data set using the functional centroids upon determining that the sum represents a net energy decrease. 
     
     
         31 . The method of  claim 25 , wherein generating the set of fitted functional centroids comprises:
 fitting a function based on data points associated with a partition to generate a fitted function;   determining if an energy of the fitted function is less than an energy of a corresponding functional centroid; and   using the fitted function as the corresponding functional centroid.   
     
     
         32 . A non-transitory computer readable storage medium for tangibly storing computer program instructions capable of being executed by a computer processor, the computer program instructions defining steps of:
 initializing functional centroids, a respective functional centroid in the functional centroids accepting a timestamp as an input and outputting at least one data point based on the timestamp;   replacing at least one functional centroid in the functional centroids with a corresponding fitted functional centroid to obtain final functional centroids if a computed energy of the corresponding fitted functional centroid is less than an energy of the at least one functional centroid; and   outputting the final functional centroids.   
     
     
         33 . The non-transitory computer readable storage medium of  claim 32 , further comprising:
 partitioning a non-stationary data set, using the functional centroids, into partitions, a number of partitions being equal to a number of functional centroids; and   generating a set of fitted functional centroids for each of the partitions, the set of fitted functional centroids including the corresponding fitted functional centroid.   
     
     
         34 . The non-transitory computer readable storage medium of  claim 33 , wherein partitioning the non-stationary data set comprises:
 identifying, for each point in the non-stationary data set, a closest functional centroid generating an output value closest to a respective point; and   assigning each point to a partition based on the closest functional centroid.   
     
     
         35 . The non-transitory computer readable storage medium of  claim 33 , further comprising:
 computing a sum of energies associated with each of the functional centroids; and   determining that the sum does not result in a net energy decrease prior to outputting the final functional centroids.   
     
     
         36 . The non-transitory computer readable storage medium of  claim 35 , an energy of a function computed by summing differences between known points at respective times and outputs of the function for corresponding respective times. 
     
     
         37 . The non-transitory computer readable storage medium of  claim 35 , wherein determining that the sum of the energies does not result in a net energy decrease comprises:
 computing a first energy for the functional centroids prior to generating the set of fitted functional centroids;   computing a second energy for the functional centroids after replacing at least one of the functional centroids with a corresponding fitted functional centroid; and   determining that the sum of the energies does not result in a net energy decrease if the second energy is not less than the first energy.   
     
     
         38 . The non-transitory computer readable storage medium of  claim 34 , wherein generating the set of fitted functional centroids comprises:
 fitting a function based on data points associated with a partition to generate a fitted function;   determining if an energy of the fitted function is less than an energy of a corresponding functional centroid; and   using the fitted function as the corresponding functional centroid.   
     
     
         39 . A device comprising:
 a processor configured to:   initialize functional centroids, a respective functional centroid in the functional centroids accepting a timestamp as an input and outputting at least one data point based on the timestamp;   replace at least one functional centroid in the functional centroids with a corresponding fitted functional centroid to obtain final functional centroids if a computed energy of the corresponding fitted functional centroid is less than an energy of the at least one functional centroid; and   output the final functional centroids.   
     
     
         40 . The device of  claim 39 , the processor further configured to:
 partition a non-stationary data set, using the functional centroids, into partitions, a number of partitions being equal to a number of functional centroids; and   generate a set of fitted functional centroids for each of the partitions, the set of fitted functional centroids including the corresponding fitted functional centroid.   
     
     
         41 . The device of  claim 40 , wherein partitioning the non-stationary data set comprises:
 identifying, for each point in the non-stationary data set, a closest functional centroid generating an output value closest to a respective point; and   assigning each point to a partition based on the closest functional centroid.   
     
     
         42 . The device of  claim 40 , the processor further configure to:
 compute a sum of energies associated with each of the functional centroids; and   determine that the sum does not result in a net energy decrease prior to outputting the final functional centroids.   
     
     
         43 . The device of  claim 40 , wherein generating the set of fitted functional centroids comprises:
 fitting a function based on data points associated with a partition to generate a fitted function;   determining if an energy of the fitted function is less than an energy of a corresponding functional centroid; and   using the fitted function as the corresponding functional centroid.