Temporal clustering of non-stationary data
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. A method comprising:
initializing a plurality of functional centroids, the functional centroids comprising functions, each function in the functions accepting a timestamp as an input and outputting one or more data points based on the timestamp;
partitioning a non-stationary data set, using the functional centroids, into partitions, a 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 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 centroids;
computing a sum of the energies associated with each of the functional centroids
determining that the sum of the energies does not result in a net energy decrease; and
outputting the final functional centroids.
2. The method of claim 1 , the initializing the plurality of functional centroids comprising:
selecting one or more random points for each of the partitions; and
fitting a function based the one or more random points.
3. The method of claim 1 , the partitioning the non-stationary data set comprising:
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.
4. The method of claim 1 , the generating the set of fitted functional centroids comprising:
fitting a function based on data points associated with a partition;
determining if an energy of the fitted function is less than an energy of a corresponding function centroid; and
using the fitted function as the corresponding functional centroid.
5. The method of claim 4 , the fitting a function comprising fitting a function using a fitting algorithm selected from the group consisting of a polynomial, single cosine, or nonequispaced fast Fourier transform (NFFT) fitting algorithm.
6. The method of claim 1 , an energy of a function computed by summing differences between known points at respective times and outputs of the function for corresponding respective times.
7. The method of claim 1 , the determining that the sum of the energies does not result in a net energy decrease comprising:
computing a first energy for the functional centroids prior to generating the set of fitted functional centroids;
computing a second energy for the function 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.
8. The method of claim 1 , further comprising performing a second partitioning of the non-stationary data set using the functional centroids upon determining that the sum of the energies results in a net energy decrease.
9. 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 a plurality of functional centroids, the functional centroids comprising functions, each function in the functions accepting a timestamp as an input and outputting one or more data points based on the timestamp;
partitioning a non-stationary data set, using the functional centroids, into partitions, a 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 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;
computing a sum of the energies associated with each of the functional centroids;
determining that the sum of the energies does not result in a net energy decrease; and
outputting the functional centroids.
10. The non-transitory computer readable storage medium of claim 9 , the initializing the plurality of functional centroids comprising:
selecting one or more random points for each of the partitions; and
fitting a function based the one or more random points.
11. The non-transitory computer readable storage medium of claim 9 , the partitioning the non-stationary data set comprising:
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.
12. The non-transitory computer readable storage medium of claim 9 , the generating the set of fitted functional centroids comprising:
fitting a function based on data points associated with a partition;
determining if an energy of the fitted function is less than an energy of a corresponding function centroid; and
using the fitted function as the corresponding functional centroid.
13. The non-transitory computer readable storage medium of claim 12 , the fitting a function comprising fitting a function using a fitting algorithm selected from the group consisting of a polynomial, single cosine, or nonequispaced fast Fourier transform (NFFT) fitting algorithm.
14. The non-transitory computer readable storage medium of claim 9 , an energy of a function computing by summing a difference between known points at respective times and an output of the function for corresponding respective times.
15. The non-transitory computer readable storage medium of claim 9 , the determining that the sum of the energies does not result in a net energy decrease comprising:
computing a first energy for the functional centroids prior to generating the set of fitted functional centroids;
computing a second energy for the function 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.
16. The non-transitory computer readable storage medium of claim 9 , the computer program instructions further defining the step of performing a second partitioning of the non-stationary data set using the functional centroids upon determining that the sum of the energies results in a net energy decrease.
17. An apparatus comprising:
a processor;
a storage medium for tangibly storing thereon program logic for execution by the processor, the stored program logic comprising:
logic, executed by the processor, for initializing a plurality of functional centroids, the functional centroids comprising functions, each function in the functions accepting a timestamp as an input and outputting one or more data points based on the timestamp;
logic, executed by the processor, for partitioning a non-stationary data set, using the functional centroids, into partitions, a number of partitions being equal to the number of functional centroids;
logic, executed by the processor, for generating a set of fitted functional centroids for each of the partitions;
logic, executed by the processor, for replacing at least one of 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;
logic, executed by the processor, for computing a sum of the energies associated with each of the functional centroids;
logic, executed by the processor, for determining that the sum of the energies does not result in a net energy decrease; and
logic, executed by the processor, for outputting the functional centroids.
18. The apparatus of claim 17 , the logic for initializing the plurality of functional centroids comprising:
logic, executed by the processor, for selecting one or more random points for each of the partitions; and
logic, executed by the processor, for fitting a function based the one or more random points.
19. The apparatus of claim 17 , the logic for partitioning the non-stationary data set comprising:
logic, executed by the processor, for identifying, for each point in the non-stationary data set, a closest functional centroid generating an output value closest to a respective point; and
logic, executed by the processor, for assigning each point to a partition based on the closest functional centroid.
20. The apparatus of claim 17 , the logic for generating the set of fitted functional centroids comprising:
logic, executed by the processor, for fitting a function based on data points associated with a partition;
logic, executed by the processor, for determining if an energy of the fitted function is less than an energy of a corresponding function centroid; and
logic, executed by the processor, for using the fitted function as the corresponding functional centroid.
21. The apparatus of claim 17 , the logic for computing an energy of a function comprising logic, executed by the processor, for summing a difference between known points at respective times and an output of the function for corresponding respective times.
22. The apparatus of claim 17 , the logic for determining that the sum of the energies does not result in a net energy decrease comprising:
logic, executed by the processor, for computing a first energy for the functional centroids prior to generating the set of fitted functional centroids;
logic, executed by the processor, for computing a second energy for the function centroids after replacing at least one of the functional centroids with a corresponding fitted functional centroid; and
logic, executed by the processor, for 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.
23. The apparatus of claim 17 , the stored program logic further comprising logic, executed by the processor, for performing a second partitioning of the non-stationary data set using the functional centroids upon determining that the sum of the energies results in a net energy decrease.