Computer-Implemented Systems And Methods For Flexible Definition Of Time Intervals

• US 20110208701A1
• Filed: 02/22/2011
• Published: 08/25/2011
• Est. Priority Date: 02/23/2010
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Jackson, Wilma Stainback, Crowe, Keith Eugene, Leonard, Michael J.
• Granted Patent: US 8,631,040 B2
• Time in Patent Office: Days
• US Class Current: 707/687
• CPC Class Codes: G06F 16/2445 Data retrieval commands; View definitions
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

Systems and methods are provided for segmenting time-series data stored in data segments containing one or more data records. A combined segment error measure is determined based on a proposed combination of two candidate segments. An error cost to merge the two candidate segments is determined based on a difference between the combined segment error measure and a segment error measure of one of the segments. The two candidate segments are combined when the error cost to merge meets a merge threshold to generate a combined segment.

Claims

1. A computer-implemented method of clustering time-series data stored in data segments containing one or more data records, comprising:

determining a combined segment error measure based on a proposed combination of two candidate segments;

determining an error cost to merge the two candidate segments based on a difference between the combined segment error measure and a segment error measure of one of the segments; and

combining the two candidate segments when the error cost to merge meets a merge threshold to generate a combined segment.

2. The method of claim 1, wherein the two candidate segments are combined when the error cost to merge is greater than the merge threshold or greater than or equal to the merge threshold.

3. The method of claim 1, wherein the two candidate segments are combined when the error cost to merge is less than the merge threshold or less than or equal to the merge threshold.

4. The method of claim 1, wherein determining the error cost to merge the two candidate segments includes calculating a combined segment function based on the data records in the proposed combination, wherein the combined segment error measure is based on a quality of fit measurement of the combined segment function to the data records of the candidate segments.

5. The method of claim 1, wherein the segment error measure is based on a quality of fit of a segment function to the data records of one of the segments.

6. The method of claim 1, further comprising generating a predictive data model based on the combined segment containing the two candidate segments and at least one other segment.

7. The method of claim 6, further comprising generating a forecast based on the predictive model.

8. The method of claim 1, further comprising:

receiving a plurality of time series data records, a time series data record including a measure of a parameter over a particular length of time; and

assigning the time series data records to segments;

9. The method of claim 1, wherein the error cost to merge is a percentage change from the segment error measure of one of the segments to the combined segment error measure.

10. The method of claim 1, wherein the error cost to merge is calculated according to:

11. The method of claim 1, further comprising generating a forecast model based on the combined segment.

12. The method of claim 1, wherein the two candidate segments have variances that differ by less than 10%, and wherein the two candidate segments have trends that differ by less than 10%.

13. The method of claim 1, wherein clustering the time-series data transforms the time-series data from non-stationary to stationary.

14. The method of claim 1, wherein the cost to merge, p_i, is calculated according to:

15. The method of claim 1, wherein the clustering is used in decomposing a time series, customizing discrete time intervals, a turning point analysis, comparing time series, or visualizing a time series.

16. A computer-implemented system for clustering time-series data into data segments containing one or more data records, comprising:

one or more data processors;

a computer-readable medium encoded with instructions for commanding the data processor to execute steps that include;

determining a combined segment error measure based on a proposed combination of two candidate segments;

determining an error cost to merge the two candidate segments based on a difference between the combined segment error measure and a segment error measure of one of the segments; and

combining the two candidate segments when the error cost to merge meets a merge threshold to generate a combined segment.

17. The system of claim 16, wherein the two candidate segments are combined when the error cost to merge is greater than the merge threshold or greater than or equal to the merge threshold.

18. The system of claim 16, wherein the two candidate segments are combined when the error cost to merge is less than the merge threshold or less than or equal to the merge threshold.

19. The system of claim 16, wherein determining the error cost to merge the two candidate segments includes calculating a combined segment function based on the data records in the proposed combination, wherein the combined segment error measure is based on a quality of fit measurement of the combined segment function to the data records of the candidate segments.

20. The system of claim 16, wherein the segment error measure is based on a quality of fit of a segment function to the data records of one of the segments.

21. The system of claim 16, wherein the steps further include generating a predictive data model based on the combined segment containing the two candidate segments and at least one other segment.

22. The system of claim 21, wherein the steps further include generating a forecast based on the predictive model.

23. The system of claim 16, wherein the steps further include:

receiving a plurality of time series data records, a time series data record including a measure of a parameter over a particular length of time; and

assigning the time series data records to segments;

24. The system of claim 16, wherein the error cost to merge is a percentage change from the segment error measure of one of the segments to the combined segment error measure.

25. The system of claim 16, wherein the error cost to merge is calculated according to:

26. The system of claim 16, wherein the steps further include generating a forecast model based on the combined segment.

27. The system of claim 16, wherein the two candidate segments have variances that differ by less than 10%, and wherein the two candidate segments have trends that differ by less than 10%.

28. The system of claim 16, wherein clustering the time-series data transforms the time-series data from non-stationary to stationary.

29. The system of claim 16, wherein the cost to merge, p_i, is calculated according to:

30. The system of claim 16, wherein the clustering is used in decomposing a time series, customizing discrete time intervals, a turning point analysis, comparing time series, or visualizing a time series.

31. A computer-readable medium encoded instructions for clustering time-series data into segments containing one or more data records, the method comprising:

determining a combined segment error measure based on a proposed combination of two candidate segments;

determining an error cost to merge the two candidate segments based on a difference between the combined segment error measure and a segment error measure of one of the segments;

combining the two candidate segments when the error cost to merge meets a merge threshold to generate a combined segment.