Systems and methods for machine learning using classifying, clustering, and grouping time series data

• US 10,169,720 B2
• Filed: 12/16/2016
• Issued: 01/01/2019
• Est. Priority Date: 04/17/2014
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Chien, Yung-Hsin, Wang, Pu, Li, Yue
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): LAMARDO, VIKER ALEJANDRO
• Application Number:
  US15/381,564
• Publication Number:
  US 20170228661A1
• Time in Patent Office: 746 Days
• Field of Search: 706 12
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities

Abstract

Systems and methods are provided for performing data mining and statistical learning techniques on a big data set. More specifically, systems and methods are provided for linear regression using safe screening techniques. Techniques may include receiving a plurality of time series included in a prediction hierarchy for performing statistical learning to develop an improved prediction hierarchy. It may include pre-processing data associated with each of the plurality of time series, wherein the pre-processing includes tasks performed in parallel using a grid-enabled computing environment. For each time series, the system may determine a classification for the individual time series, a pattern group for the individual time series, and a level of the prediction hierarchy at which the each individual time series comprises an need output amount greater than a threshold amount. The computing system may generate an additional prediction hierarchy using the first prediction hierarchy, the classification, the pattern group, and the level.

Claims

1. A system for performing data mining and statistical learning techniques on a data set, the system comprising:

a processor; and

a non-transitory computer-readable storage medium including instructions stored thereon, which when executed by the processor, cause the system to perform operations including;

receiving a plurality of time series included in a prediction hierarchy for performing statistical learning to develop the prediction hierarchy, each individual time series of the plurality of time series comprising one or more need output characteristics and a need output pattern for an object, the one or more need output characteristics including at least one of a need output data, an intermittence, or a time period of a year, the need output pattern indicating one or more time intervals for which need output for the object is greater than a threshold amount;

pre-processing data associated with each of the plurality of time series, wherein the pre-processing includes executing tasks in parallel using a grid-enabled computing environment, the tasks comprising, for each time series of the plurality of time series;

determining a classification for the individual time series based on the one or more need output characteristics;

determining a pattern group for each individual time series by comparing the need output pattern to need output patterns for other time series in the plurality of time series; and

determining a level of the prediction hierarchy at which the each individual time series comprises a need output amount greater than the threshold amount, wherein determining the level further includes, for each time series in each level of the hierarchy and starting with a lowest level of the hierarchy;

determining whether the individual time series includes a sufficient volume of data by determining whether the individual time series includes an amount of need output above the threshold amount; and

based upon the determination, for each time series that does not include an amount of need output above the threshold amount, aggregating multiple time series from a particular level into a node that is one level higher than the particular level in the hierarchy;

generating an additional prediction hierarchy using the prediction hierarchy, the classification, the pattern group, and the determined level, wherein utilizing the additional prediction hierarchy generates more accurate need output predictions than need output predictions generated utilizing the prediction hierarchy; and

transmitting, to one or more nodes in the grid-enabled computing environment, prediction data related to at least one time series of the plurality of time series based on the additional prediction hierarchy.

2. The system of claim 1, further comprising instructions, which when executed by the processor, cause the system to perform operations including:

determining a number of low-demand periods within the individual time series, wherein each of the number of low-demand periods is a time period during which need output for the item is less than a threshold value;

identifying a number of cycles based on the number of low-demand periods; and

determining a preliminary classification for the time series based on the identified number of cycles and the one or more need output characteristics.

3. The system of claim 2, wherein determining the number of low-demand periods within the individual time series include determining an approximate time series utilizing a segmentation algorithm and the individual time series, wherein the number of low-demand periods are determined based on the approximate time series.

4. The system of claim 2, wherein the preliminary classification comprises one of a short-history classification, a low-volume classification, a short time-span non-intermittent classification, a short time-span intermittent classification, a long time-span time period classification, a long time-span non-seasonal classification, a long time-span intermittent classification, an optional long time-span unclassifiable classification, an optional unclassified classification, an inactive classification, or a long time-span unclassifiable classification.

5. The system of claim 1, further comprising instructions, which when executed by the processor, cause the system to perform operations including:

performing a horizontal reclassification of the individual time series using a classification of one or more sibling time series, the one or more sibling time series belonging to a common parent node in the prediction hierarchy as the individual time series when the individual time series is classified as unclassifiable.

6. The system of claim 5, further comprising instructions, which when executed by the processor, cause the system to perform operations including:

determining the horizontal reclassification based on a most frequently used classification among the one or more sibling time series; and

assigning the horizontal reclassification to a subset of the individual time series.

7. The system of claim 1, further comprising instructions, which when executed by the processor, cause the system to perform operations including:

performing a top-down reclassification of the individual time series using a parent time series of the individual time series as indicated in the prediction hierarchy when the determined classification for the individual time series is long time-span intermittent.

8. The system of claim 1, further comprising instructions, which when executed by the processor, cause the system to perform operations including:

generating an initial set of time-series clusters using a first number of clusters, a k-means clustering algorithm, and the plurality of time series;

determining an optimal number of clusters using a hierarchical clustering technique applied to the initial set of time-series clusters; and

determining an optimal set of time-series clusters using the optimal number of clusters, the k-means clustering algorithm, and the plurality of time series.

9. The system of claim 1, further comprising instructions, which when executed by the processor, cause the system to perform operations including:

determining a lowest grouping level of the prediction hierarchy;

determining a user-defined grouping level of the prediction hierarchy; and

for each level of the prediction hierarchy between, and including, the user-defined grouping level and the lowest grouping level;

determining a need output volume amount for one or more sibling time series in the prediction hierarchy; and

aggregating the one or more sibling time series in the prediction hierarchy based on the need output volume amount.

10. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, including instructions configured to cause a data processing apparatus to perform operations including:

receiving a plurality of time series included in a prediction hierarchy for performing statistical learning to develop the prediction hierarchy, each individual time series of the plurality of time series comprising one or more need output characteristics and a need output pattern for an object, the one or more need output characteristics including at least one of a need output data, an intermittence, or a time period of a year, the need output pattern indicating one or more time intervals for which need output for the object is greater than a threshold value amount;

pre-processing data associated with each of the plurality of time series, wherein the pre-processing includes executing tasks in parallel using a grid-enabled computing environment, the tasks comprising, for each time series of the plurality of time series;

determining a classification for the individual time series based on the one or more need output characteristics;

determining a pattern group for each individual time series by comparing the need output pattern to need output patterns for other time series in the plurality of time series; and

determining a level of the prediction hierarchy at which the each individual time series comprises a need output amount greater than the threshold amount, wherein determining the level further includes, for each time series in each level of the hierarchy and starting with a lowest level of the hierarchy;

determining whether the individual time series includes a sufficient volume of data by determining whether the individual time series includes an amount of need output above the threshold amount; and

based upon the determination, for each time series that does not include an amount of need output above the threshold amount, aggregating multiple time series from a particular level into a node that is one level higher than the particular level in the hierarchy;

generating an additional prediction hierarchy using the prediction hierarchy, the classification, the pattern group, and the determined level, wherein utilizing the additional prediction hierarchy generates more accurate need output predictions than need output predictions generated utilizing the prediction hierarchy; and

transmitting, to one or more nodes in the grid-enabled computing environment, prediction data related to at least one time series of the plurality of time series based on the additional prediction hierarchy.

11. The computer-program product of claim 10, further comprising instructions configured to cause the data processing apparatus to:

determine a number of low-demand periods within the individual time series, wherein each of the number of low-demand periods is a time period during which need output for the item is less than a threshold value;

identify a number of cycles based on the number of low-demand periods; and

determine a preliminary classification for the time series based on the identified number of cycles and the one or more need output characteristics.

12. The computer-program product of claim 11, wherein determining the number of low-demand periods within the individual time series include determining an approximate time series utilizing a segmentation algorithm and the individual time series, wherein the number of low-demand periods are determined based on the approximate time series.

13. The computer-program product of claim 11, wherein the preliminary classification comprises one of a short-history classification, a low-volume classification, a short time-span non-intermittent classification, a short time-span intermittent classification, a long time-span time period classification, a long time-span non-seasonal classification, a long time-span intermittent classification, an optional long time-span unclassifiable classification, an optional unclassified classification, an inactive classification, or a long time-span unclassifiable classification.

14. The computer-program product of claim 10, further comprising instructions configured to cause the data processing apparatus to:

perform a horizontal reclassification of the individual time series using a classification of one or more sibling time series, the one or more sibling time series belonging to a common parent node in the prediction hierarchy as the individual time series when the individual time series is classified as unclassifiable.

15. The computer-program product of claim 14, further comprising instructions configured to cause the data processing apparatus to:

determine the horizontal reclassification based on a most frequently used classification among the one or more sibling time series; and

assign the horizontal reclassification to a subset of the individual time series.

16. The computer-program product of claim 10, further comprising instructions configured to cause the data processing apparatus to:

perform a top-down reclassification of the individual time series using a parent time series of the individual time series as indicated in the prediction hierarchy when the determined classification for the individual time series is long time-span intermittent.

17. The computer-program product of claim 10, further comprising instructions configured to cause the data processing apparatus to:

generate an initial set of time-series clusters using a first number of clusters, a k-means clustering algorithm, and the plurality of time series;

determine an optimal number of clusters using a hierarchical clustering technique applied to the initial set of time-series clusters; and

determine an optimal set of time-series clusters using the optimal number of clusters, the k-means clustering algorithm, and the plurality of time series.

18. The computer-program product of claim 10, further comprising instructions configured to cause the data processing apparatus to:

determine a lowest grouping level of the prediction hierarchy;

determine a user-defined grouping level of the prediction hierarchy; and

for each level of the prediction hierarchy between, and including, the user-defined grouping level and the lowest grouping level;

determine a need output volume amount for one or more sibling time series in the prediction hierarchy; and

aggregate the one or more sibling time series in the prediction hierarchy based on the need output volume amount.

19. The method of claim 10, further comprising:

performing a top-down reclassification of the individual time series using a parent time series of the individual time series as indicated in the prediction hierarchy when the determined classification for the individual time series is long time-span intermittent.

20. A method for performing data mining and statistical learning techniques on a data set, the method comprising:

receiving a plurality of time series included in a prediction hierarchy for performing statistical learning to develop the prediction hierarchy, each individual time series of the plurality of time series comprising one or more need output characteristics and a need output pattern for an object, the one or more need output characteristics including at least one of a need output data, an intermittence, or a time period of a year, the need output pattern indicating one or more time intervals for which need output for the object is greater than a threshold amount;

pre-processing data associated with each of the plurality of time series, wherein the pre-processing includes executing tasks in parallel using a grid-enabled computing environment, the tasks comprising, for each time series of the plurality of time series;

determining a classification for the individual time series based on the one or more need output characteristics;

determining a pattern group for each individual time series by comparing the need output pattern to need output patterns for other time series in the plurality of time series; and

determining a level of the prediction hierarchy at which the each individual time series comprises a need output amount greater than the threshold amount, wherein determining the level further includes, for each time series in each level of the hierarchy and starting with a lowest level of the hierarchy;

determining whether the individual time series includes a sufficient volume of data by determining whether the individual time series includes an amount of need output above the threshold amount; and

based upon the determination, for each time series that does not include an amount of need output above the threshold amount, aggregating multiple time series from a particular level into a node that is one level higher than the particular level in the hierarchy;

generating an additional prediction hierarchy using the prediction hierarchy, the classification, the pattern group, and the determined level, wherein utilizing the additional prediction hierarchy generates more accurate need output predictions than need output predictions generated utilizing the prediction hierarchy; and

transmitting, to one or more nodes in the grid-enabled computing environment, prediction data related to at least one time series of the plurality of time series based on the additional prediction hierarchy.

21. The method of claim 20, further comprising:

determining a number of low-demand periods within the individual time series, wherein each of the number of low-demand periods is a time period during which need output for the item is less than a threshold value;

identifying a number of cycles based on the number of low-demand periods; and

determining a preliminary classification for the time series based on the identified number of cycles and the one or more need output characteristics.

22. The method of claim 21, wherein determining the number of low-demand periods within the individual time series include determining an approximate time series utilizing a segmentation algorithm and the individual time series, wherein the number of low-demand periods are determined based on the approximate time series.

23. The method of claim 21, wherein the preliminary classification comprises one of a short-history classification, a low-volume classification, a short time-span non-intermittent classification, a short time-span intermittent classification, a long time-span time period classification, a long time-span non-seasonal classification, a long time-span intermittent classification, an optional long time-span unclassifiable classification, an optional unclassified classification, an inactive classification, or a long time-span unclassifiable classification.

24. The method of claim 20, further comprising:

performing a horizontal reclassification of the individual time series using a classification of one or more sibling time series, the one or more sibling time series belonging to a common parent node in the prediction hierarchy as the individual time series when the individual time series is classified as unclassifiable.

25. The method of claim 24, further comprising:

determining the horizontal reclassification based on a most frequently used classification among the one or more sibling time series; and

assigning the horizontal reclassification to a subset of the individual time series.

26. The method of claim 20, further comprising:

generating an initial set of time-series clusters using a first number of clusters, a k-means clustering algorithm, and the plurality of time series;

determining an optimal number of clusters using a hierarchical clustering technique applied to the initial set of time-series clusters; and

determining an optimal set of time-series clusters using the optimal number of clusters, the k-means clustering algorithm, and the plurality of time series.

27. The method of claim 20, further comprising:

determining a lowest grouping level of the prediction hierarchy;

determining a user-defined grouping level of the prediction hierarchy; and

for each level of the prediction hierarchy between, and including, the user-defined grouping level and the lowest grouping level;

determining a need output volume amount for one or more sibling time series in the prediction hierarchy; and

aggregating the one or more sibling time series in the prediction hierarchy based on the need output volume amount.