Fuzzy-learning-based extraction of time-series behavior

• US 8,001,074 B2
• Filed: 01/31/2008
• Issued: 08/16/2011
• Est. Priority Date: 01/31/2008
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: To, Wai Yip
• Primary Examiner(s): Fernandez Rivas; Omar F
• Assistant Examiner(s): Hill; Stanley K
• Application Number:
  US12/023,920
• Publication Number:
  US 20090198640A1
• Time in Patent Office: 1,293 Days
• Field of Search: None
• US Class Current: 706/52
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

Systems and methods for extracting or analyzing time-series behavior are described. Some embodiments of computer-implemented methods include generating fuzzy rules from time series data. Certain embodiments also include resolving conflicts between fuzzy rules according to how the data is clustered. Some embodiments further include extracting a model of the time-series behavior via defuzzification and making that model accessible. Advantageously, to resolve conflicts between fuzzy rules, some embodiments define Gaussian functions for each conflicting data point, sum the Gaussian functions according to how the conflicting data points are clustered, and resolve the conflict based on the results of summing the Gaussian functions. Some embodiments use both crisp and non-trivially fuzzy regions and/or both crisp and non-trivially fuzzy membership functions.

Claims

1. A computer-implemented method of extracting time-series behavior based on time-series information, the method comprising:

loading into a computer time-series data, wherein the loaded time-series data comprises time-series data points comprising an input-component-part and an output-component-part, the input-component-part comprising one or more input components and the output-component-part comprising one or more output components, the one or more input components collectively representing a value from an input space and the one or more output components collectively representing a value from an output space, wherein loading time-series data further comprises incorporating at least one time-related input component of at least one data point into the loaded time-series data;

dividing into fuzzy regions a range of possible values for each component of the time-series data;

assigning with one or more computer processors a fuzzy membership function to each fuzzy region;

generating with one or more computer processors non-conflicting fuzzy rules that are determined at least in part by the fuzzy membership functions and at least in part by how a plurality of the time-series data points are clustered;

determining a mapping from the input space to the output space based on defuzzification of the fuzzy rules; and

displaying the mapping in a manner that allows a user to perform time-series prediction or time-series-trend recognition.

2. The method of claim 1, wherein the time-series data substantially represents at least in part measurements of input and output operations of a relational database management system.

3. The method of claim 1, wherein loading into a computer time-series data comprises retrieving time-series data from a database and storing the time-series data in memory, in a file or in databases.

4. The method of claim 1, wherein the input-component-part of at least one time-series data point comprises a plurality of input components.

5. The method of claim 1, wherein the input-component-part of at least one time-series data point comprises one or more time-related input components.

6. The method of claim 5, wherein the one or more time-related input components comprise an input component corresponding to the time of day.

7. The method of claim 1, wherein the output-component-part of at least one time-series data point comprises a plurality of output components.

8. The method of claim 1, wherein dividing into fuzzy regions a range of possible values for each component of the time-series data comprises, for at least one component of the time-series data, defining the fuzzy regions based at least in part on user input.

9. The method of claim 1, wherein assigning a fuzzy membership function to each fuzzy region comprises assigning a triangular fuzzy membership function to at least one fuzzy region.

10. The method of claim 1, wherein assigning a fuzzy membership function to each fuzzy region comprises assigning a rectangular fuzzy membership function to at least one fuzzy region.

11. The method of claim 1, wherein generating non-conflicting fuzzy rules that are determined at least in part by the fuzzy membership functions and at least in part by how a plurality of the time-series data points are clustered comprises:

generating a fuzzy rule with an antecedent clause from each of a plurality of the time-series data points, where, for a given time-series data point among the plurality of the time-series data points, the fuzzy rule is based on the degree of membership each component of the given time-series data point has with respect to each fuzzy region of the range of possible values for that component and where the degree of membership of a given component with respect to a given fuzzy region is determined by evaluating the fuzzy membership function assigned to the given fuzzy region at the value of the given component; and

resolving conflicts among the fuzzy rules, wherein, for a given set of conflicting fuzzy rules, the resolving conflicts comprises;

clustering the output-component-parts of the time-series data points giving rise to the fuzzy rules in the given set of conflicting fuzzy rules;

defining a function for each resulting cluster, the characteristics of each cluster determining at least one relative maximum value of its associated function;

selecting a cluster whose associated function has a relative maximum value equal to the greatest relative maximum value of all the functions associated with a cluster; and

creating a fuzzy rule using the antecedent clauses of the fuzzy rules in the given set of conflicting fuzzy rules and a consequent clause determined by an output space value substantially representing the center of the selected cluster.

12. The method of claim 11, wherein defining a function for each resulting cluster, the characteristics of each cluster determining at least one relative maximum value of its associated function, comprises:

defining a Gaussian function for each time-series data point giving rise to a fuzzy rule in the given set of conflicting fuzzy rules, where, for each such time-series data point, the output-component-part of the time-series data point determines the position of the center of the Gaussian function'"'"'s peak, the height of each Gaussian function'"'"'s peak is the same for each time-series data point giving rise to a fuzzy rule in the given set of conflicting fuzzy rules, and the full width at half maximum of each Gaussian function is the same for each time-series data point giving rise to a fuzzy rule in the given set of conflicting fuzzy rules; and

defining an aggregate function for each resulting cluster based on the sum of the Gaussian functions for each time-series data point whose output-component-part is in the cluster.

13. The method of claim 11, wherein defining a function for each resulting cluster, the characteristics of each cluster determining at least one relative maximum value of its associated function, comprises, for each given cluster, defining a constant function whose constant value is equal to the number of output-component-parts in the given cluster.

14. The method of claim 11, wherein the function defined for each given resulting cluster achieves a relative maximum at an output space value that falls substantially within a neighborhood of output space values that includes, for each given output-component-part belonging to the given cluster, the output space value represented by the one or more output components of the given output-component-part, and wherein the output space value substantially representing the center of the selected cluster is a value at which the function associated with the selected cluster attains a relative maximum and that falls substantially within a neighborhood of output space values that includes, for each given output-component-part belonging to the selected cluster, the output space value represented by the one or more output components of the given output-component-part.

15. The method of claim 11, wherein the output space value substantially representing the center of the selected cluster is a value that substantially incorporates a weighted average of output space values that comprise each output space value that is represented by the one or more output components of any one of the output-component-parts belonging to the selected cluster, where the weight of a given output space value is determined at least in part by the density of a neighborhood of the given output space value.

16. The method of claim 1, wherein generating non-conflicting fuzzy rules that are determined at least in part by the fuzzy membership functions and at least in part by how a plurality of the time-series data points are clustered comprises:

generating a fuzzy rule with an antecedent clause from each of a plurality of the time-series data points, where, for a given time-series data point among the plurality of the time-series data points, the fuzzy rule is based on the degree of membership each component of the given time-series data point has with respect to each fuzzy region of the range of possible values for that component and where the degree of membership of a given component with respect to a given fuzzy region is determined by evaluating the fuzzy membership function assigned to the given fuzzy region at the value of the given component; and

resolving conflicts among the fuzzy rules, wherein, for a given set of conflicting fuzzy rules, the resolving conflicts comprises;

clustering the output-component-parts of the time-series data points giving rise to the fuzzy rules in the given set of conflicting fuzzy rules;

defining a function for each resulting cluster, the characteristics of each cluster determining at least one relative maximum value of its associated function;

selecting a cluster whose associated function has a relative maximum value equal to the greatest relative maximum value of all the functions associated with a cluster; and

creating a fuzzy rule using the antecedent clauses of the fuzzy rules in the given set of conflicting fuzzy rules and a consequent clause determined by an output space value substantially reflecting properties of the selected cluster that are determined at least in part by the output-component-parts belonging to the selected cluster.

17. The method of claim 1, wherein the plurality of the time-series data points are clustered according to clusters substantially complying with the following properties:

if a first point is in a cluster and a second point is reachable from the first point, then the second point is in the cluster, where the second point is reachable from the first point if there exists a chain of points beginning with the first point and ending with the second point such that, for a given point in the chain of points, except possibly the second point, there is a pre-defined minimum number of other points within a neighborhood of the given point and one of those other points is the next point in the chain; and

for any two points in a cluster, there is a third point from which each of the two points is reachable.

18. The method of claim 1, wherein generating non-conflicting fuzzy rules that are determined at least in part by the fuzzy membership functions and at least in part by how a plurality of the time-series data points are clustered comprises:

processing a plurality of the time-series data points, the processing for a given time-series data point of the plurality of the time-series data points comprising;

defining a Gaussian function on the output space, where the output-component-part of the given time-series data point determines the position of the center of the Gaussian function'"'"'s peak; and

updating a sum of functions associated with an antecedent clause of a fuzzy rule generated by the given time-series data point, wherein the updating comprises adding the defined Gaussian function to the sum of functions; and

generating fuzzy rules each with an antecedent clause and a consequent clause, the consequent clause of a given fuzzy rule being determined by an output space value at which the sum of functions associated with the antecedent clause of the given fuzzy rule achieves a greatest relative maximum.

19. A computer-implemented method of extracting time-series behavior based on time-series information, the method comprising:

loading into a computer time-series data, wherein the loaded time-series data comprises time-series data points comprising an input-component-part and an output-component-part, the input-component-part comprising one or more input components and the output-component-part comprising one or more output components, the one or more input components collectively representing a value from an input space, the one or more output components collectively representing a value from an output space, and the one or more input components comprising at least one time-related input component;

dividing into fuzzy regions a range of possible values for each component of the time-series data;

assigning with one or more computer processors a fuzzy membership function to each fuzzy region, wherein assigning a fuzzy membership function to each fuzzy region comprises assigning a triangular fuzzy membership function to at least one fuzzy region;

constructing with one or more computer processors a Fuzzy Associated Memory (FAM) bank comprising fuzzy rules each having an antecedent clause and a consequent clause, wherein the consequent clause of a given fuzzy rule of the FAM bank is determined by the output space value at which a sum of functions associated with the antecedent clause of the given fuzzy rule achieves a greatest relative maximum, wherein the sum of functions associated with the antecedent clause of the given fuzzy rule comprises a sum of Gaussian functions on the output space, each such Gaussian function achieving a greatest relative maximum at an output space value determined by a time-series data point whose input-component-part corresponds to the antecedent clause of the given fuzzy rule;

determining a mapping from the input space to the output space based on defuzzification of the FAM bank; and

displaying the mapping in a manner that allows a user to perform time-series prediction or time-series-trend recognition.

20. A computer-implemented method of extracting time-series behavior based on time-series information, the method comprising:

loading into a computer a first increment of time-series data, wherein the loaded first increment of time-series data comprises time-series data points comprising an input-component-part and an output-component-part, the input-component-part comprising one or more input components and the output-component-part comprising one or more output components, the one or more input components collectively representing a value from an input space and the one or more output components collectively representing a value from an output space;

dividing with one or more computer processors into fuzzy regions a range of possible values for each component of the time-series data;

assigning with one or more computer processors a fuzzy membership function to each fuzzy region;

using the first increment of time-series data to build a Fuzzy Associated Memory (FAM) bank comprising fuzzy rules, the fuzzy rules of the FAM bank being determined at least in part by the fuzzy membership functions and at least in part by the way a plurality of the time-series data points of the first increment of time-series data are clustered; and

providing with one or more computer processors a model of the behavior of the first increment of time-series data in a manner that allows a user to perform time-series prediction or time-series-trend recognition.

21. The method of claim 20, wherein the model comprises a mapping from the input space to the output space determined at least in part by defuzzification of the fuzzy rules of the FAM bank.

22. The method of claim 20, further comprising updating the model based on at least a second increment of time-series data, wherein updating the model does not require reexamining the time-series data points of the first increment of time-series data.

23. The method of claim 20, wherein using the first increment of time-series data to build a Fuzzy Associated Memory (FAM) bank comprising fuzzy rules, the fuzzy rules of the FAM bank being determined at least in part by the fuzzy membership functions and at least in part by the way a plurality of the time-series data points of the first increment of time-series data are clustered, comprises:

processing a plurality of the time-series data points of the first increment of time-series data, the processing for a given time-series data point of the plurality of the time-series data points comprising;

defining a Gaussian function on the output space, where the output-component-part of the given time-series data point determines the position of the center of the Gaussian function'"'"'s peak; and

updating a sum of functions associated with an antecedent clause of a fuzzy rule generated by the given time-series data point, wherein the updating comprises adding the defined Gaussian function to the sum of functions; and

generating a FAM bank comprising fuzzy rules each having an antecedent clause and a consequent clause, the consequent clause of a given fuzzy rule being determined by an output space value at which the sum of functions associated with the antecedent clause of the given fuzzy rule achieves a greatest relative maximum.

24. The method of claim 23, further comprising:

maintaining a record of the sums of functions associated with antecedent clauses; and

updating the model based on one or more additional increments of time-series data, the updating the model comprising;

using a plurality of time-series data points of the one or more additional increments of time-series data to update the record of the sums of functions; and

updating the FAM bank based on output space values at which the sums of functions of the updated record achieve greatest relative maxima.

25. The method of claim 20, wherein at least one fuzzy region is a crisp region and at least one fuzzy region is a non-trivially fuzzy region.

26. An apparatus for analyzing time-series behavior comprising:

a first computer system; and

a second computer system, wherein a first code module that is loaded into a memory of the first computer system communicates with a database and a second code module that is loaded into a memory of the second computer system communicates with the first code module so as to retrieve from the database data relating to a time series, extracts a model of the behavior of the time series via fuzzy learning based in part on how conflicting data points of the retrieved data are clustered, where two data points conflict if they give rise to conflicting fuzzy rules, and makes the extracted model accessible to a user such that the user can use the model to perform time-series analysis,

wherein the second code module further incorporates at least one time-related input component of at least one data point into the retrieved time-series data.

27. The apparatus of claim 26, wherein the time series is at least in part substantially a time series reflecting measurements of input and output operations of a relational database management system.

28. An apparatus for analyzing time-series behavior comprising:

a first computer system; and

a second computer system, wherein a first code module that is loaded into a memory of the first computer system communicates with a database and a second code module that is loaded into a memory of the second computer system communicates with the first code module so as to retrieve from the database data relating to a time series, extracts a model of the behavior of the time series via fuzzy learning based in part on how conflicting data points of the retrieved data are clustered, where two data points conflict if they give rise to conflicting fuzzy rules, and makes the extracted model accessible to a user such that the user can use the model to perform time-series analysis,

wherein each data point of the retrieved data has one or more output components that collectively represent a value from an output space and, for each set of conflicting data points, the second code module further clusters output components of the conflicting data points;

defines a function for each resulting cluster, the characteristics of each cluster determining at least one relative maximum value of its associated function;

selects a cluster whose associated function has a relative maximum value equal to the greatest relative maximum value of all the functions associated with a cluster; and

creates a fuzzy rule using the antecedent clauses of the fuzzy rules generated by the data points in the set of conflicting data points and the consequent clause corresponding to the fuzzy region for which an output value substantially representing the center of the selected cluster has the highest degree of membership.

29. The apparatus of claim 28, wherein the second code module defines a function for each resulting cluster by defining a Gaussian function for each data point in the set of conflicting data points, where, for each such data point, the one or more output components of the data point determine the position of the center of the Gaussian function'"'"'s peak, the height of each Gaussian function'"'"'s peak is the same for each data point in the set of conflicting data points, and the full width at half maximum of each Gaussian function is the same for each data point in the set of conflicting data points;

and defining an aggregate function for each resulting cluster based on the sum of the Gaussian functions for each data point whose one or more output components are in the cluster.

30. A system for analyzing time-series behavior comprising:

a computer system, wherein a first code module that is loaded into and is executable on the computer system, and that is in communication with a training database, comprises;

a second code module that reads data based on a time series from the training database, the data being comprised of data points, and

a third code module that communicates with the second code module and that extracts via fuzzy learning a model of the behavior of the time series based in part on how conflicting data points are clustered; and

a user interface in communication with the third code module, the user interface providing a user with access to models extracted by the third code module such that the user can perform time-series analysis,

wherein the third code module resolves conflicts between data points based on summing Gaussian functions that are substantially determined by the output values of conflicting data points, where the sums are calculated according to how the output values are clustered.