Method and apparatus for knowledge-driven data mining used for predictions

• US 20030041042A1
• Filed: 08/21/2002
• Published: 02/27/2003
• Est. Priority Date: 08/22/2001
• Status: Abandoned Application

• Current Assignee: Insyst, Ltd. (Advanced Emissions Solutions, Inc.)
• Original Assignee: Insyst, Ltd. (Advanced Emissions Solutions, Inc.)
• Inventors: Cohen, Inon, Fisher, Yossi, Hartman, Jehuda
• Application Number:
  US10/226,693
• Publication Number:
  US 20030041042A1
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and apparatus is provided for constructing a predictive model for a system based on a priori qualitative modeling of the system and on historical database collected from past activity of the system or past events in the system. An expert provides grouping of parameters and qualitative dependencies between parameters and attributes, wherein some of the attributes may be conceptual or virtual attributes. The present invention extends existing methods of ‘evolutionary algorithms’ in order to build successive sets of quantitative predictive models for the system, wherein parts of each model are evolved by the evolutionary algorithm and parts of each model are derived using the historical database. According to the present invention a model constructed by this method can be incorporated as a predictive model into a diagnosis or control apparatus without the need for human inspection, as the model complies with the expert'"'"'s knowledge about the system. The present invention also provides a method to update the constructed model when new data is delivered, thus adjusting the model to changes in the environment.

Claims

1. A method for constructing a model for predicting values of at least one output parameter of a system from input parameters and attributes of the system, the method comprising the steps of:

a) defining dependencies between the input parameters, the attributes and the at least one output parameter of the system, wherein at least a portion of said dependencies are quantitatively unknown and at least a portion of said attributes are unmeasured;

b) building a plurality of initial predictive models for the system, said initial predictive models having quantitative functions representing said dependencies, wherein at least one of said quantitative functions is derived using a first historical database of the system;

c) building additional predictive models with increasing accuracy in a process of an iterative evolutionary algorithm, said additional predictive models having quantitative functions representing said dependencies, and marking some of said additional predictive models; and

d) selecting the most reliable of said marked models based on prediction of values of output parameters in a historical database.

2. The method of claim 1 wherein the step of defining dependencies further comprises the steps of:

assigning the at least one output parameter and at least a portion of said input parameters and attributes of the system to be relevant parameters of the system;

grouping said relevant parameters into groups of at least two, wherein any one of said relevant parameters is a member of at least one of said groups; and

associating a qualitative dependency to each group of said groups wherein a single relevant parameter of said group is assigned to be a dependent parameter, and all of remaining relevant parameters of said group are assigned to be independent parameters.

3. The method of claim 2 wherein said grouping said relevant parameters and said associating a qualitative dependency to each group is complying with the conditions that:

each of said relevant parameters is a dependent parameter of at most one of said groups;

the at least one output parameter of the system is a dependent parameter of one of said groups;

any one of said relevant parameters which is a dependent parameter of one of said groups and is not the output parameter of the system is an independent parameter of at least one of said groups;

any one of said relevant parameters which is not measured and is an independent parameter of at least one of said groups, is a dependent parameter of one of said groups; and

the group whose dependent parameter is the output parameter of the system has at least one independent parameter which is unmeasured.

4. The method of claim 3 wherein said assigning and said grouping and said associating is based on expert knowledge of the system.

5. The method of claim 1, wherein the step of building a plurality of initial predictive models further comprises the steps of:

assigning the at least one output parameter and at least a portion of the input parameters and attributes of the system to be relevant parameters of the system;

to each one of said dependencies, associating one of said relevant parameters to be a dependent parameter, and at least one of remaining relevant parameters to be independent parameters;

representing a portion of said dependencies for which quantitative functions are known beforehand by said quantitative functions;

representing by randomly built quantitative functions a portion of said dependencies whose dependent parameter is unmeasured; and

representing by quantitative functions derived using said first historical database a portion of said dependencies whose dependent parameter is measured.

6. The method of claim 4, wherein the step of representing by randomly built quantitative functions further comprises the steps of:

selecting random values of parameters for a portion of said dependencies whose functional form is known beforehand and substituting said random values for free parameters of said functional form, and;

building random expressions for a portion of said dependencies whose functional form is unknown, where said random expressions follow a recursive syntax and said random expressions refer to independent parameters of said dependencies.

7. The method of claim 4, wherein the step of representing by quantitative functions derived using said first historical database further comprises the steps of:

calculating values of independent parameters of said dependencies for all records in said historical database, wherein a portion, if any, of said independent parameters are measured, and reminder of said independent parameters are dependent parameters of known quantitative functions or randomly built quantitative functions; and

deriving a quantitative function by relating said independent parameters and said dependent parameter using a known statistical method to relate dependent parameter to at least one independent parameters.

8. The method of claim 1 wherein the step of building additional predictive models further comprises the steps of:

assigning the at least one output parameter and at least a portion of the input parameters and attributes of the system to be relevant parameters of the system;

to each one of said dependencies, associating one of said relevant parameters to be a dependent parameter, and at least one of remaining relevant parameters to be independent parameters;

assigning said initial predictive models to be current set of models; and

iterating an evolutionary procedure until a stopping criteria is met.

9. The method of claim 8 wherein the step of iterating an evolutionary procedure further comprises the steps of:

calculating a fitness score for each model in said current set of models, said fitness score is based on said model prediction of values in said first historical database of the system of the at least one output parameter of the system, wherein a higher fitness score indicates better predictive accuracy and reliability;

marking at most one of the models in said current set of models, wherein a model is marked if said model has a highest fitness score in said current set of models and said modal has a fitness score higher than the fitness score of all previously marked models;

checking said stopping criteria and continuing only if said stopping criteria is not met, wherein said stopping criteria is based on said fitness score of the models in said current set of models and on the number of iterations iterated by said evolutionary procedure;

selecting from said current set of models a set of founders for a new set of models, wherein said selecting is a probabilistic process based on said fitness score of models in said current set of models;

building from said set of founders a new set of models, wherein each model in said new set is at least one item selected from the group consisting of duplicating a model from said founders set, mutating a model from said founders set, and recombining at least two models from said founders set;

re-deriving said quantitative functions that represent a portion of said dependencies whose dependent parameter is measured, said re-deriving is done by using said first historical database; and

assigning said new set of models to be current set of models.

10. The method of claim 9 wherein the step of mutating a model from said founders set further comprises the step of performing minor change in each function of said functions with unmeasured dependent parameter, wherein said minor change does not change functional form of a portion of said functions whose functional form is known beforehand.

11. The method of claim 9 wherein the step of recombining at least two models from said founders set further comprises the steps of:

selecting a first model from said at least two models to be a recipient model and remaining models from said at least two models to be donor models; and

recombining each function of a portion of said functions of said recipient model, said function'"'"'s dependent parameter is unmeasured, with functions of said donor models representing dependency same as dependency represented by said function of said recipient model, wherein recombining further comprises the step of replacing a portion of said function of said recipient model with portions of said functions of said donor models.

12. The method of claim 9 wherein the step of re-deriving said quantitative functions that represent a portion of said dependencies whose dependent parameter is measured further comprises the steps of:

calculating values of independent parameters of said dependencies for all records in said historical database, wherein a portion, if any, of said independent parameters are measured, and reminder of said independent parameters are dependent parameters of quantitative functions; and

deriving a quantitative function by relating said independent parameters and said dependent parameter using a known statistical method to relate dependent parameter to at least one independent parameters.

13. The method of claim 1 wherein selecting the most reliable of said marked models is based on predictive accuracy and reliability on said first historical database of the system.

14. The method of claim 1 wherein selecting the most reliable of said marked models is based on predictive accuracy on a second historical database of the system.

15. An apparatus for constructing a model for predicting values of at least one output parameter of a system from input parameters and attributes of the system, the apparatus comprising:

a) a knowledge engineering tool for defining dependencies between the input parameters, the attributes and the at least one output parameter of the system, wherein at least a portion of said dependencies are quantitatively unknown and at least a portion of said attributes are unmeasured;

b) a first model generator for building a plurality of initial predictive models for the system, said initial predictive models having quantitative functions representing said dependencies, wherein at least one of said quantitative functions is derived using a first historical database of the system; and

c) a second model generator for building additional predictive models with increasing accuracy in a process of an iterative evolutionary algorithm, said additional predictive models having quantitative functions representing said dependencies, and said second model generator marking some of said additional predictive models; and

d) a selector for selecting the most reliable of said marked models based on prediction of values of output parameters in a historical database.

16. An apparatus for predicting and controlling values of at least one output of a system, said apparatus comprises:

a) a modeler unit for constructing a model for predicting values of the least one output parameter of a system from input parameters and attributes of the system, the apparatus comprising;

(i) a knowledge engineering tool for defining dependencies between said input parameters, said attributes and the at least one output parameter of the system, wherein at least a portion of said dependencies are quantitatively unknown and at least a portion of said attributes are unmeasured;

(ii) a first model generator for building a plurality of initial predictive models for the system, said initial predictive models having quantitative functions representing said dependencies, wherein at least one of said quantitative functions is derived using a first historical database of the system; and

(iii) a second model generator for building additional predictive models with increasing accuracy in a process of an iterative evolutionary algorithm, said additional predictive models having quantitative functions representing said dependencies, and said second model generator marking some of said additional predictive models; and

(iv) a selector for selecting the most reliable of said marked models based on prediction of values of output parameters in a historical database, said selected model is assigned to be a working model; and

b) a diagnosis unit for predicting the at least one output value of the system.

17. The apparatus of claim 16 wherein the diagnosis unit further comprises:

a first data collector for collecting values of a portion of said input parameters;

a predictor for predicting value of said at least one output parameter of the system, said prediction unit uses said working model for prediction; and

an output device for reporting the predicted value of the at least one output of the system.

18. The apparatus of claim 17 wherein the diagnosis unit further comprises:

a second data collector for collecting actual output values of said at least one output parameter;

a data storage unit for storing said collected data and said collected actual output values and maintaining a updated historical database; and

a model maintainer for re-deriving a portion of said functions of said working model based on said updated historical database.

19. An apparatus for controlling values of at least one output of a system, said apparatus comprises:

a) a modeler unit for constructing a model for predicting values of the least one output parameter of a system from input parameters and attributes of the system, the apparatus comprising;

(i) a knowledge engineering tool for defining dependencies between said input parameters, said attributes and the at least one output parameter of the system, wherein at least a portion of said dependencies are quantitatively unknown and at least a portion of said attributes are unmeasured;

(ii) a first model generator for building a plurality of initial predictive models for the system, said initial predictive models having quantitative functions representing said dependencies, wherein at least one of said quantitative functions is derived using a first historical database of the system; and

(iii) a second model generator for building additional predictive models with increasing accuracy in a process of an iterative evolutionary algorithm, said additional predictive models having quantitative functions representing said dependencies, and said second model generator marking some of said additional predictive models; and

(iv) a selector for selecting the most reliable of said marked models based on prediction of values of output parameters in a historical database, said selected model is assigned to be a working model; and

b) a control unit for manipulating parameters of the system and controlling the at least one output value of the system.

20. The apparatus of claim 19 wherein the control unit further comprises the

a data collector for collecting values of a portion of said input parameters, wherein a portion of remaining said input parameters are assigned to be controllable parameters;

a goal input device for indicating to said control unit desired values of the at least one output parameter;

an optimizer for finding the values of said controllable parameters for which predicted values of said at least one output parameter of the system are similar to said desired values of the at least one output parameter, said optimizer using said working model for predicting values of said at least one output parameter of the system; and

an output device for reporting said found values of said controllable parameters.

21. The apparatus of claim 20 wherein the control unit further comprises:

a second data collector for collecting actual output values of said at least one output parameter;

a data storage unit for storing said collected data and said collected actual output values and maintaining a updated historical database; and

a model maintainer for re-deriving a portion of said functions of said working model based on said updated historical database.