Computer storage capacity forecasting system using cluster-based seasonality analysis

[0001] This application claims the benefit of U.S. provisional applications 60/805,728, filed on Jun. 23, 2006; 60/805,729, filed on Jun. 23, 2006; and 60/945,546, filed on Jun. 21, 2007. Each of the above applications is incorporated by reference herein in its entirety.

[0002] This application is also related to U.S. patent application Ser. No. 11/823,111, titled “Evaluation of Data Models and Forecasts,” filed on Jun. 25, 2007, and incorporated by reference herein in its entirety.

[0003] 1. Field of the Invention

[0004] The present invention pertains in general to modeling and forecasting of data. In particular, the present invention is directed to automatic evaluation of patterns in time-series data.

[0005] 2. Background of the Invention

[0006] A conventional approach to statistical modeling and forecasting is to use pre-existing knowledge of the data's behavior; to determine, using subject-matter experts' knowledge, how trended the data are, what seasonal variations in the data are observable, and what the level shifts and outliers signify. In some cases, mathematical curve-fitting is used to determine the trend; in some cases Fourier analysis is used to determine the frequency of seasonal variation. However, events such as outliers and level-shifts play a very important role in model quality and, if unaccounted for, may offset the uncertainty of the model and forecast, rendering it potentially meaningless. Yet events are typically either not determined or are determined using a subject-matter-expert's subjective opinion.

[0007] A traditional approach used in data analysis and forecasting has been trial and error, i.e., by running a data set through a series of models and determining which model fits best; an iterative approach to model tuning is sometimes also used. That includes, as an example, the so-called ARIMA model, wherein seasonality and trend are determined by fitting different trend and seasonal models until a best fit is found.

[0008] The present invention provides a methodology for automatic a priori data pattern analysis. It enables an algorithm that allows consistent and objective determination of outliers; trend; seasonality; and level shifts; and the production of better models and more accurate forecasts. In addition, it includes a two-step way to automatically determine seasonality and locate possible events in the data set.

[0009] In particular, the present invention enables decomposition of data into seasonal, trend and level components; detection of outliers and level-shift events in the time series based on statistical analysis of the time series; detection of seasonality based on statistical analysis of clusters of data, (cluster-based seasonality analysis, or CBSA); evaluation of the goodness of fit of a model to data, using the existing goodness of fit indicator, R²; and seasonality analysis, using a sequence of cluster-based seasonality analysis (CBSA) and Fourier analysis.

[0010] The described methods for data pattern analysis can be applied for preliminary data analysis prior to running a time-series forecasting model. The user is provided with the necessary objective information with regard to seasonal patterns, trend type, and events (level shifts and outliers) in the data.

[0011] Applications include, but are not limited to, a variety of areas, such as:

• • [0012] Storage capacity modeling and forecasting;
  • [0013] Statistical Process Control;
  • [0014] Market analysis
  • [0015] Supply-chain forecasting and other business applications.
  • [0016] Traffic analysis and planning;
  • [0017] Meteorology;

[0018] and other applications.

[0019] The seasonality and trend information provided according to embodiments of the present invention are used to fine-tune forecasting models. Event information, in order to be used efficiently in forecasting models, may benefit from input from a subject-matter expert as to when these events are likely to occur in the future. Alternatively, some forecasting software can be used to predict the future schedule of such events (the so-called Croston model); however, that may skew the model's perception of the impact of such events. However, even without any knowledge of when an event is expected to happen in the future, knowledge that it did happen in the past greatly improves the usability of the model in forecasting, narrowing down the uncertainty of the forecast.

[0020] The present invention enables objective, consistent and accurate detection of possible events, trend, and seasonal patterns in a time series, allowing a user to minimize or eliminate the human interaction with the modeling and forecasting process.

[0030] The figures depict various embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.

[0031] FIG. 1 illustrates a system 100 for performing data pattern analysis in accordance with an embodiment of the present invention. System 100 receives as input time-series data 102, i.e. a sequence of numbers corresponding to data collected from a system of interest during a time period. Data pattern analysis engine (DPA) 104 analyzes this historical data 102 in order to find and interpolate outliers, identify trends in the data, de-trend the data, and find seasonality in the data, as described further below. DPA 104 then provides this information to modeling engine 108, which in turn generates a forecasting model based on the provided data from DPA engine 104. The model is then provided to forecasting engine 110, in order to generate forecast data 106, which can then be provided to a user. Modeling engine 108 and forecasting engine 110 in one embodiment are the Forecast Pro product, available from Business Forecast Systems, Inc.; in an alternative embodiment they are the Autobox system, available from AFS Inc.

[0032] FIG. 2 illustrates a method for performing data pattern analysis. DPA 104 first receives 200 time series data 102, which as noted above is the data to be analyzed. Next, DPA 104 finds and interpolates 202 outliers in the data. Next, DPA 104 identifies 204 trends in the data. Following this, DPA 104 de-trends 206 the data, and finally finds 208 seasonality in the data.

[0033] In one embodiment, after the time series data 102 is received, it is checked for sufficiency by performing a standard T-test-based analysis of desired confidence limits. Confidence limits as well as other parameters are in one embodiment specified by a user at run-time, and alternatively are stored in a database of system 100 (not shown).

Outlier Detection and Processing

[0034] As is known in the art, an outlier is a statistical observation that is markedly different in value from the others of the sample. In time series analysis (TSA), outliers typically correspond to events and should generally be modeled using multivariate analysis methodologies. If, however, a user does not know what event occurred at the data points corresponding to outliers, then the only thing the modeling and forecasting system can do is either interpolate or ignore them. If, on the other hand, the time intervals between outliers are repeatable, that indicates a possible seasonal pattern in data.

[0035] The step of outlier detection 202 is illustrated further with respect to FIG. 3 and FIG. 4. First, DPA 104 calculates 302 the standard deviation and 306 the so-called running mean (RM) of the data 102. In one embodiment, RM is calculated at each data point by calculating the average of all points up to this data point. Next, for each data point in the time series, a T-test is run 308 to determine whether the value of the data point is within a given number of standard deviations of the RM. A user can specify an appropriate T-test confidence level depending on the desired certainty in detecting outliers. If 310 the value of a data point is more than the specified number of standard deviations of the RM, it is added 312 to the list of outliers.

[0036] Next, and referring to FIG. 4, for each outlier on the outlier list, the point is either interpolated or ignored, depending on a preference that in one embodiment is specified by a user. If 402 the user has chosen to interpolate, then each outlier's value is substituted 404 with a value calculated using a standard linear interpolation formula. In one embodiment, if the outlier is the last data point in the time series, it is discarded. Alternatively, if 406 the user has indicated that outliers should be ignored, it is discarded 408.

[0037] Parameters that DPA 104 uses at this point, and which in one embodiment are user-supplied and in another embodiment are defaulted to automatically, are used to set the sensitivity and accuracy of the method, including the standard T-test parameters (confidence levels); the parameters for calculating the RM; as well as decision-making parameters for handling the outliers if detected.

Trend Detection and Detrending

[0038] Trend in data is an important parameter for the modeling engine 108 and forecasting engine 110. The trend information tells modeling engine 108 what to make of the data, and tells forecasting engine 110 what general tendency to expect of the data over the period covered by the forecast.

[0039] It is important to keep in mind that a trend found in data may or may not be the trend that can be used in forecasting, even if it is the trend providing the best-fitted model. This is particularly the case with polynomial trends. Most modeling and forecasting engines that can differentiate one trend type from another classify trends in time series as linear, where the difference in value between two adjacent data points does not change significantly; exponential, where the difference in value between two adjacent data points increases; or damped, also known as decaying-rate, where the difference in value between two adjacent data points decreases.

[0040] In these terms, in one embodiment, a quadratic trend found by the standard mathematical curve-fitting methodology is interpreted in terms of modeling and forecasting as either exponential or damped; exponential trend, too, is interpreted as exponential (if the values grow) or damped (if the values decrease asymptotically); etc.

Quadratic Trend

[0041] Some trends, e.g., polynomial, are not usable in forecasting, but are very useful in detrending data.

[0042] In one embodiment, quadratic trend (second-order polynomial) is added as a contender for detrending, but is interpreted as one of the three trends above, depending on the position of the maximum or minimum of the quadratic curve. Thus, if quadratic is the best-fitting trend, and if the maximum or minimum is towards the last part of the time series, then forecasting engine 110 interprets such data as damped. If the maximum or minimum of the data is at the very start of the quadratic curve, then forecasting engine 110 handles the trend as linear or exponential.

[0043] In either case, when quadratic is the best-fitting trend, data detrending is done using the quadratic trend (and not linear or damped) in one embodiment.

[0044] FIG. 8a shows the foundations of the trend identification methodology that is implemented in one embodiment. The “goodness-of-fit” of the model 8001 is determined by the value of the so called Pearson's correlation coefficient and parameters derived from it, such as the R² (R-squared). It defines the fraction of the total variance in the data that has been explained by the model.

[0045] However, using R² directly to evaluate the model's “goodness-of-fit” is not very accurate, due to it being random, and its distribution not being normal. DPA 104 uses a Fisher transform 8002 to derive another parameter from correlation, which is distributed normally and therefore can be used in standard statistic tests 8003 to quantitatively evaluate the “goodness-of-fit” of the model.

[0046] FIG. 8b illustrates the R² scoring system as may be implemented in accordance with an embodiment of the present invention. After using the statistical algorithms to obtain the distribution of Fisher-transformed R² 8053, it is superimposed with the segment (0 . . . 1) and its placement is compared with Fisher-transformed values of R_sqMin1 8051 and R_sqMin2 8052, which can be set as parameters. Typical industry values are 0.25 and 0.81, respectively. This placement is then quantified by assigning the maximum score to the case 8060 when the entire significant section of the distribution 8053 is to the right of R_sqMin2 8052, the minimum score to the case 8080 when the entire significant section of the distribution 8053 is to the left of R_sqMin1 8051, and a proportionally distributed score for cases 8070 when the distribution 8053 is anywhere in between the two extremes, the score then depending on the placement of the distribution's mean and the width of its standard deviation. Using such a scoring system, system 100 can then formally evaluate the trends and find the best-fitting trend for the data.

[0047] FIG. 5 illustrates a method for trend goodness-of-fit analysis in accordance with an embodiment of the present invention. After the outliers have been accounted for (see FIG. 3 and FIG. 4 above), the R² is calculated 504 for each of the possible relevant trends and, after Fisher Transform 506, evaluated 508 using statistical methods, and the best-fitted trend model is selected 510.

[0048] Once the best-fitting trend has been detected, it is saved in memory or on disk to notify modeling engine 108 and forecasting engine 110 and also is used to de-trend the data in order to ensure an accurate seasonality analysis.

[0049] In one embodiment, parameters provided to DPA engine 104 at this point are related to setting the preferred sensitivity and accuracy of the algorithm, including the standard T-test parameters (confidence levels) for R²; the critical values of the Fisher-transformed R²(R_sqMin1, R_sqMin2); trend preferences for cases where two or more trends fit so closely that there is no statistical difference in the R² score.

[0050] Additional parameters related to the interpretation of trend for forecasting engine 110 include such factors as the critical values of the curve parameters when an exponential trend may be considered linear; quadratic linear or exponential; etc.

[0051] These values help DPA engine 104 to identify the trend that is most suitable for detrending the data, as well as the trend that will provide a more reasonable forecast.

Seasonality Analysis

[0052] Seasonality is any pattern in the data that is periodic. The number of data points after which the pattern becomes repetitious is called the period of the seasonality, or seasonality for short.

[0053] In one embodiment, DPA 104 performs 208 seasonality analysis in two stages. The first stage is cluster-based seasonality analysis (CBSA), and the second stage is Fourier analysis. Depending on the user's preference, the stages can operate independently or in sequence. In one embodiment, DPA 104 includes three modes of operation with regard to Fourier analysis:

[0054] Never—the seasonality is the one that was found using CBSA, even if CBSA did not find any.

[0055] Sequentially—only if CBSA did not find a seasonality, e.g., if the data are changing seasonally, but in a very smooth pattern, CBSA will not find a seasonality (no outliers—no clusters—no seasonality). For such cases, Fourier analysis is used as a backup.

[0056] Always—this is the most all-embracing mode of operation. If CBSA and Fourier analysis both returned seasonality, then, if modeling engine 108 allows multiple seasonalities to be entered, then DPA engine 104 passes them all into modeling engine 108; if it is a single-seasonality engine, then DPA engine 104 picks one that has the highest impact on the data.

[0057] Other sequences are possible as well, including, but not limited to, using CBSA only if Fourier analysis did not find seasonality. Note that this may not be a very efficient proposition, since Fourier analysis is much more sensitive to deviations from the pattern.

Cluster-Based Seasonality Analysis (CBSA)

[0058] A cluster is an uninterrupted group of data points displaying similar behavior over a period of time. We refer to a cluster as a time interval between two consecutive events.

[0059] The CBSA method in one embodiment uses the clusters to detect seasonality in data. There are two types of events that can be found in time series data: outliers and level shifts. For level shifts, the same methodology as outlined above with respect to FIG. 3 and FIG. 4 is used in one embodiment. It is made possible by the mathematical principles summarized in FIG. 6: level shifts 3004 in actual data (FIG. 6a) correspond to outliers 3005 in rate-of-change data FIG. 6b. Thus, the problem of finding the points of transition from cluster to cluster are solved using the outlier-detection algorithm presented in FIG. 3 and FIG. 4.

[0060] This methodology in one embodiment uses the algorithm outlined in FIG. 7. Data are grouped 702 into clusters using the methods shown in FIG. 3 and FIG. 4 and FIG. 9. In FIG. 9, the data's standard deviation is calculated 902, and then for each data point in the series, its corresponding rate of change (Rate) is calculated 904 and added to the time series of rates. All outliers in the Rate time series are detected 906, and then for each Rate outlier on the list, a new cluster is created 908 in the original time series starting at that Rate outlier.

[0061] Continuing with FIG. 7, DPA engine 104 checks 704 whether the distribution of cluster sizes can be fitted reasonably well with a Poisson distribution, where “reasonably well” in one embodiment refers to the Chi-Square test used in statistics to analyze the distribution's “goodness of fit”. If 706 it can—then 708 the number of points in the cluster (cluster size) that has been observed more frequently is likely to be the periodicity of the seasonal pattern. The likelihood of that is defined by the likelihood of it being a Poisson distribution. If, conversely, the distribution is not Poisson, then 710 nothing can be said with regard to seasonality in the data, so a Fourier analysis should be used.

[0062] In addition, in one embodiment, a flexible seasonality detection is used, wherein clusters whose sizes are similar, but not exactly the same, are still considered same size for the intents and purposes of the seasonality detection.

[0063] Other parameters related to the CBSA are related to the Chi-Square test, which in one embodiment is used to determine if the cluster sizes follow the Poisson distribution.

Fourier Analysis

[0064] In one embodiment, as illustrated in FIG. 10, a Fourier analysis is performed as described below to detect hidden seasonalities that may or may not be detectable by CBSA. The following steps illustrated in FIG. 10 are based on the assumption that the data have been de-trended 1002.

[0065] First, a Fourier transform is executed 1004 to shift data from the time domain into the frequency domain. Next, the frequencies are analyzed 1006 to find those that produce the largest magnitude. Then, a reverse Fourier transform is executed 1008 to obtain the seasonal component of the time-series data.

[0066] Next DPA 104 finds a correlation between the seasonal component and the de-trended data. In one embodiment, the R² scoring methodology is used as outlined above. A separate set of values for the same R²-related parameters as were used for the trend analysis is used in one embodiment to analyze the seasonality for goodness of fit.

[0067] If 1010 the correlation is statistically significant, then 1014 the highest-magnitude period is the seasonal period in data; otherwise, the conclusion is 1012 that the data are non-seasonal.

[0068] Once the seasonality has been found 208, modeling engine 108 creates a model as described above. In one embodiment, the model can be evaluated to determine its strength. Techniques for obtaining a model quality index (MQI) are described further in U.S. patent application Ser. No. 11/823,111, titled “Evaluation of Data Models and Forecasts,” filed on even date herewith and incorporated by reference herein in its entirety.

[0069] Embodiments in addition to those described above are also possible. For example:

• • [0070] The Running-Mean (RM) may be calculated using a different methodology.
  • [0071] The Fourier analysis may be expanded to return multiple seasonalities.
  • [0072] The cluster-based seasonality analysis (CBSA) algorithm may be expanded to group two or more consecutive clusters into one if the cluster-size pattern is repeatable.
  • [0073] For trend and seasonality, the R² scoring system may use different scales (non-proportional) for scoring the model's goodness-of-fit, which may or may not be beneficial, depending on the data behavior.

[0074] System 100 therefore provides an integrated, robust, and flexible combination of tools that can be used in data analysis as part of data preparation in forecasting models.

[0075] The algorithms described herein can be expanded as outlined above to further improve the models produced by using this methodology. The process flow shown in FIG. 2 may be altered to include only part of the data analysis, if the user of this algorithm is only interested in some aspects of the data set. That ensures the flexibility uniquely integrated into this approach. Furthermore, the scope of the invention can be expanded beyond being used as a tool for preliminary data analysis in forecasting models, and also as a standalone tool for any time-series data decomposition and cluster analysis.

[0076] The present invention has been described in particular detail with respect to a limited number of embodiments. Those of skill in the art will appreciate that the invention may additionally be practiced in other embodiments. First, the particular naming of the components, capitalization of terms, the attributes, data structures, or any other programming or structural aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names, formats, or protocols. Further, the system may be implemented via a combination of hardware and software, as described, or entirely in hardware elements. Also, the particular division of functionality between the various system components described herein is merely exemplary, and not mandatory; functions performed by a single system component may instead be performed by multiple components, and functions performed by multiple components may instead performed by a single component. For example, the particular functions of the modeling engine 108 and forecasting engine 110, and so forth may be provided in many or one module.

[0077] Some portions of the above description present the feature of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the art of data modeling and forecasting to most effectively convey the substance of their work to others skilled in the art. These operations, while described functionally or logically, are understood to be implemented by computer programs. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules or code devices, without loss of generality.

[0078] It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the present discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0079] Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by real time network operating systems.

[0080] The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.

[0081] The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description above. In addition, the present invention is not described with reference to any particular programming language. It is appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references to specific languages are provided for disclosure of enablement and best mode of the present invention.

[0082] Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention.