Distributed hierarchical evolutionary modeling and visualization of empirical data

• US 6,941,287 B1
• Filed: 12/17/1999
• Issued: 09/06/2005
• Est. Priority Date: 04/30/1999
• Status: Expired due to Term

• Current Assignee: E. I. du Pont de Nemours and Company (Corteva, Inc.)
• Original Assignee: E. I. du Pont de Nemours and Company (Corteva, Inc.)
• Inventors: Vaidyanathan, Akhileswar Ganesh, Owens, Aaron J., Whitcomb, James Arthur
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Hirl, Joseph P.
• Application Number:
  US09/466,041
• Time in Patent Office: 2,090 Days
• Field of Search: 706/46, 706/12, 706/14, 707/100
• US Class Current: 706/12
• CPC Class Codes: G06F 18/10 Pre-processing; Data cleansing
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A distributed hierarchical evolutionary modeling and visualization of empirical data method and machine readable storage medium for creating an empirical modeling system based upon previously acquired data. The data represents inputs to the systems and corresponding outputs from the system. The method and machine readable storage medium utilize an entropy function based upon information theory and the principles of thermodynamics to accurately predict system outputs from subsequently acquired inputs. The method and machine readable storage medium identify the most information-rich (i.e., optimum) representation of a data set in order to reveal the underlying order, or structure, of what appears to be a disordered system. Evolutionary programming is one method utilized for identifying the optimum representation of data.

Claims

1. A computer-implemented method of selecting a feature set having a global informational content above a predefined threshold, the feature set being selected from an initial feature set of inputs corresponding to inputs to a system having measurable inputs and outputs,

wherein a large number of input data points to the system and corresponding output data points from the system are acquired to define a data set, and

the acquired input and output data points are stored in a storage device,

the method comprising the steps of:

(a) creating a plurality of feature subspaces, each said feature subspace comprising a set of features from the data set,

(b) quantizing the inputs of the data set, the inputs having a range of values, by dividing the range of values into subranges, thereby dividing said feature subspace into a plurality of cells,

(c) determining the global level of informational content of each feature subspace by calculating at least one local cell Nishi-formulated entropy E to define a local entropic weight W as the complement of the Nishi-formulated entropy E (W=1−

E), and

(d) selecting at least one feature set that has a global informational content above the predefined threshold.

2. The method of claim 1 wherein the step of quantizing the inputs of the data set is performed by dividing the range of values of each input into equally sized subranges.

3. The method of claim 1 wherein the step of quantizing the inputs of the data set is performed by adaptively dividing the range of values of the inputs into subranges, such that the population of data points within each subrange approximates the mean population of the subranges, the mean population being defined as the ratio of the overall selected data point population divided by the number of subranges.

4. The method of claim 1,

wherein the step (a) of creating a plurality of feature subspaces is performed using a genetic selection method employing a fitness function which utilizes the global level of informational content of the feature subspaces, wherein the global level of informational content of the feature subspaces is based on a global entropic weight for each subspace, wherein the global entropic weight for a subspace is defined by an output-state-population-weighted sum of local entropic weights W, wherein each output-state-population is based on the total number of data points corresponding to an output state.

5. The method of claim 4, wherein the global entropic weight for each output state is based on the distribution of the population of that output state over the subspace.

6. The method of claim 4, wherein the global entropic weight for a subspace is based on a cell-population-weighted sum of local entropic weights W for each cell within the subspace.

7. The method of claim 6, wherein the local entropic weight W for each cell within the subspace is based on the distribution of the population of the output states over the cell.

8. The method of claim 6, wherein the local entropic weight W for each cell within the subspace is defined by the distribution of a normalized population of the output states over the cell, the normalized population of each output state being defined by the ratio of the population of output states over the cell to the total output state population.

9. The method of claim 4, wherein the global entropic weight for a subspace is defined by a cell-population-weighted sum of local entropic weight W, wherein each cell-population represents the total number of data points in the cell, wherein the local entropic weight W is defined by the distribution of the cell populations over the subspace.

10. The method of claim 1 further comprising, prior to step (a), the step of preprocessing the previously acquired data by applying a transformation function to the acquired data.

11. The method of claim 1,

wherein, before step (a), grouping the acquired input and output data points into at least one training data set and at least one test data set by selecting corresponding combinations of inputs and outputs of the system, and

wherein the step of selecting at least one feature set comprises selecting a plurality of sets of features, and further comprising the step of:

(e) selecting a group of feature sets that most accurately predicts the system outputs from the system inputs of the test data set.

12. The method of claim 11, wherein the step of selecting a group of feature sets is performed using a genetic selection method employing a fitness function, and

wherein the fitness function for the genetic selection method is based on a predictive error parameter for the entire test data set.

13. The method of claim 12,

wherein the predictive error for a system having discrete outputs is the fraction of samples correctly classified in the test data set, and

wherein an output state of each data point is predicted by creation and analysis of an output state probability vector for that data point.

14. The method of claim 13, wherein the output state is predicted by the state having the largest probability in the output state probability vector.

15. The method of claim 13, wherein the output state probability vector is based on a set of probabilities of each possible output state, wherein the probability of each output state is a weighted sum over all feature subspaces of the probability of being in that output state, and wherein the weighted sum is computed using local entropic weights W and global entropic weights.

16. The method of claim 12, wherein the predictive error for a continuous system having quantitative outputs is the normalized mean absolute difference between the predicted and the actual output values of the test data set.

17. The method of claim 16, wherein the output values are artificially quantized into a set of discrete output states to facilitate computing the local entropic weights W and global entropic weights, wherein a mean analog output value is calculated by using a data replication scale factor for balancing the data set over all the artificially quantized output states.

18. The method of claim 17, wherein the output state value for each data point is predicted by calculating a mean analog output value in a cell for a subspace, wherein the mean analog output value is calculated as a weighted sum of the mean analog output values over all the subspaces, wherein the weighted sum is computed using local entropic weights W and global entropic weights.

19. The method of claim 12, wherein the predictive error for a continuous system having quantitative outputs is the normalized median absolute difference between the predicted and the actual output values of the test data set.

20. The method of claim 19, wherein the output values are artificially quantized into a set of discrete output states to facilitate computing the local entropic weights W and global entropic weights, wherein a median analog output value is calculated by using a data replication scale factor for balancing the data set over all the artificially quantized output states.

21. The method of claim 19, wherein the output state value for each data point is predicted by calculating a median analog output value in a cell for a subspace, wherein the median analog output value is calculated as a weighted sum of the median cell analog output values over all the subspaces, wherein the weighted sum is computed using local entropic weights W and global entropic weights.

22. The method of claim 1, further comprising:

(e) creating a histogram representing the frequency of occurrence of each input in the selected feature set.

23. The method of claim 22, wherein a dimensionality of the data set is the number of inputs, further comprising:

(f) retaining the most frequently occurring inputs to define a reduced-dimensionality data set, wherein the reduced-dimensionality is less than or equal to the dimensionality of the data set.

24. The method of claim 23, wherein the retaining step (f) further comprises:

analyzing the histogram to select a subset of the inputs to create a reduced-dimensionality data set, wherein the size of the subset is less than or equal to the number of inputs, wherein the subset of inputs having the highest frequency of occurrence is selected by sorting the histogram.

25. The method of claim 23, wherein the retaining step (f) further comprises creating a visual representation of the histogram and subjectively selecting a subset of the inputs, wherein the size of the selected subset is less than or equal to the number of inputs.

26. The method of claim 23, wherein the retaining step (f) further comprises:

subjectively selecting one or more inputs to represent each peak in the histogram.

27. The method of claim 23,

wherein, before step (a), grouping the acquired input and output data points into at least one training data set and at least one test data set by selecting corresponding combinations of inputs and outputs of the system, and

further comprising the steps of:

(g) defining a reduced-dimensionality group of feature sets by exhaustively searching over a plurality of subsets of the reduced-dimensionality data set under a plurality of quantization conditions to determine an optimum or near-optimum dimensionality and an optimum or near-optimum quantization condition, the combination of which most accurately predicts system outputs from system inputs on the test data set,

(h) using a genetic selection method, selecting a final group of feature sets from the reduced-dimensionality group of feature sets that most accurately predicts system outputs from system inputs on the data set.

39. A machine-readable storage medium containing data generated by the method of one of claims 1, 4, 10, 11, 12, 16, 22, 25, 27, 28, 31, 34, or 37.

67. The method of claim 1 wherein the system relates to a manufacturing, financial services, advertising, marketing, analytical process or any system having large sets of measurable data.

28. A computer-implemented method of defining a model of a system having measurable inputs and outputs from a data set that most accurately predicts system outputs from system inputs,

wherein a large number of input data points to the system and corresponding output data points from the system are acquired,

the input and output data points are stored in a storage device, and

the acquired input and output data points are grouped into at least one training data set and at least one test data set by selecting corresponding combinations of inputs and outputs of the system,

the method comprising the steps of:

(a) creating a plurality of feature subspaces, each said feature subspace comprising a set of features from the training data set, each feature subspace having a dimension, wherein the dimension of a feature subspace is the number of inputs in the subspace,

(b) quantizing the inputs of the training data set, the inputs having a range of values, by dividing the range of values into subranges, thereby dividing said feature subspace into a plurality of cells,

(c) determining the global level of informational content of each feature subspace by calculating at least one local cell Nishi-formulated entropy E to define a local entropic weight W as the complement of the Nishi-formulated entropy E (w=1−

E),

(d) selecting at least one feature set that has a global informational content above a predefined threshold, and

(e) searching over the plurality of feature subspaces of the training data set under a plurality of quantization conditions by repeating steps (b)-(d) to determine an optimum or near-optimum dimensionality and an optimum or near-optimum quantization condition of cells, the combination of which most accurately predicts system outputs from system inputs on the test data set, thereby defining a model.

29. The method of claim 28 further comprising the step of retaining a subset of the cells in the feature subspace having high local entropic weights W above a predefined threshold.

30. The method of claim 29, wherein the informational content of a cell comprises the output value, the local cell entropic weight W and the cell population, further comprising the step of displaying the subset of cells on a display device by mapping the output value, the local cell entropic weight W and the cell population into a color space.

40. A hybrid method of evolving a relationship between inputs and outputs in an empirical data set acquired from a system having measurable inputs and outputs, using the model generating method of one of claim 28 or 31 or 34 or 37, comprising:

(a) generating a first model from a data set;

(b) generating a second model using the same modeling method, by either;

i) creating a plurality of feature subspaces different from the first model generating step, or

ii) dividing the feature subspace into a different plurality of cells by quantizing the inputs differently from the first model generating step;

(c) dividing the data set into two or more subsets and generating a weighting function based upon performance of the first and second models in each subset; and

(d) combining the first and second models using the weighting function, thereby combining advantages of the performance of each of the models.

31. A computer-implemented method of defining a framework by selecting a group of models of a system having measurable inputs and outputs that most accurately predict system outputs from system inputs,

wherein a large number of input data points t to the system and corresponding output data points from the system are acquired,

the acquired input and output data points are stored in a storage device, and

the acquired input and output data points are grouped into at least one training data set and at least one test data set by selecting corresponding combinations of inputs and outputs of the system,

the method comprising the steps of:

(a) defining a feature subspace as a combination of one or more inputs, wherein the dimension of a feature is the number of inputs in the combination;

(b) determining a combination of feature subspaces having a global informational content above a predefined threshold by;

(i) selecting the training data set;

(ii) creating a plurality of feature subspaces from the training data set;

(iii) quantizing the inputs of the training data set with respect to each feature subspace, the inputs having a range of values, by dividing the range of values into subranges

thereby dividing each feature subspace into a plurality of cells, each cell having a cell population being defined as the number of training set data points which occupy each cell,

(iv) determining the local Nishi-formulated informational entropy E of each cell in the subspace,

(v) using the local informational entropy (E) to define a local entropic weight W as the complement of the Nishi-formulated entropy E (W=1−

E), and using the local entropic weight W to determine the global informational content of each feature subspace,

(vi) determining a set of feature subspaces that have a global informational content above the predefined threshold;

(c) selecting a model comprising a set of feature subspaces that most accurately predicts system outputs from system inputs on the test data set;

(d) repeating steps (a)-(c) on different training and test data sets to define a group of models;

(e) creating a new training data set and a new test data set using individual model output-predicted values as inputs and actual output values as outputs; and

(f) selecting a subset group of optimum models from the group of models that most accurately predict system outputs from system inputs on the new test data set to define the framework.

32. The method of claim 31, wherein the selecting step (f) is performed using a genetic selection method employing a fitness function, wherein the fitness function for the genetic selection method is defined by a predictive error parameter for the entire new test data set of step (f).

33. The method of claim 31, wherein the step (b) (vi) of determining a set of feature subspaces that have a global informational entropy above the predefined threshold is performed using a genetic method employing a fitness function.

34. A computer-implemented method of defining a super-framework of a system having measurable inputs and outputs by selecting a group of frameworks that most accurately predict system outputs from system inputs,

wherein a large number of input data points to the system and corresponding output data points from the system are acquired,

the acquired input and output data points are stored in a storage device, and

the acquired input and output data points are grouped into at least one training data set and at least one test data set by selecting corresponding combinations of inputs and outputs of the system,

the method comprising the steps of:

(a) defining a feature subspace as a combination of one or more inputs, wherein the dimension of a feature subspace is the number of inputs in the combination;

(b) determining a combination of feature subspaces of a global informational content above a predefined threshold by;

(i) selecting the training data set,

(ii) creating an initial set of features from the training data set,

(iii) quantizing the inputs of the training data set, the inputs having a range of values, by dividing the range of values into subranges,

thereby dividing each feature subspace into a plurality of cells, the cells being defined by combinations of subranges of inputs, each cell having a cell population being defined as the number of training data set data points which occupy each cell,

(iv) determining the local Nishi-formulated informational entropy E of each cell in the subspace,

(v) using the local informational entropy E to define a local entropic weight W as the complement of the Nishi-formulated entropy E (W=1−

E), and using the local entropic weight W to determine the global informational content of each feature subspace,

(vi) determining a set of feature subspaces that have a global informational content above a predefined threshold;

(c) selecting a model comprising a combination of features subspaces that most accurately predicts system outputs from system inputs on the test data set;

(d) repeating steps (a)-(c) on different training data sets and test data sets to define a group of models;

(e) creating a new training data set and a new test data set using individual model output-predicted values as inputs and actual output values as outputs;

(f) defining a framework by selecting a subset group of optimum models from the group of models that most accurately predict system outputs from system inputs on the new test data set;

(g) repeating steps (a)-(f) on different training data sets and test data sets to define a group of optimum frameworks;

(h) creating a new training data set and a new test data set using individual framework output-predicted values as inputs and actual output values as the outputs; and

(i) defining a super-framework by selecting a subset group of frameworks from the group of optimum frameworks that most accurately predict system outputs from system inputs on the new test data set.

35. The method of claim 34, wherein the step (f) of selecting the subset group of frameworks from the group of optimum frameworks that most accurately predict system outputs from system inputs is performed using a genetic selection method employing a fitness function, wherein the fitness function for the genetic selection method is defined by a predictive error parameter for the entire new test data set of step (i).

36. The method of claim 34, wherein the step (b)(vi) of determining a set of feature subspaces that have high global informational entropy is performed using a genetic selection method employing a fitness function.

37. A computer-implemented method of evolving a mathematical relationship between inputs and outputs in an empirical data set acquired from a system having measurable inputs and outputs,

wherein a large number of input data points to the system and corresponding output data points from the system are acquired,

the acquired input and output data points are stored in a storage device, and

the acquired input and output data points are grouped into at least one training data set and at least one test data set by selecting corresponding combinations of inputs and outputs of the system,

the method comprising the steps of:

(a) defining a feature subspace as a combination of one or more inputs, wherein the dimension of a feature subspace is the number of inputs in the combination;

(b) determining a combination of feature subspaces having a global informational entropy above a predefined threshold by;

(i) selecting the training data set,

(ii) creating an initial set of feature subspaces from the training data set,

(iii) quantizing the inputs of the training data set, the inputs having a range of values, by dividing the range of values into subranges,

thereby dividing each feature subspace into a plurality of cells, each cell having a cell population being defined as the number of training set data points which occupy each cell,

(iv) determining the local Nishi-formulated informational entropy E of each cell in the subspace relative to each output of the subspace,

(v) using the local informational entropy E to define a local entropic weight W as the complement of the Nishi-formulated entropy E (W=1−

E), and using the local entropic weight W to determine the global informational entropy of each feature subspace,

(vi) selecting a set of feature subspaces that have a global informational entropy above the predefined threshold;

(c) selecting the feature subspace with the highest global informational entropy from the feature data set;

(d) creating a reduced-dimensionality data set by selecting only those inputs from the data set that are contained in the selected feature subspace; and

(e) applying a genetic programming method to evolve a mathematical relationship between the inputs and outputs of the reduced-dimensionality data set.

38. A hybrid method of evolving a relationship between inputs and outputs in an empirical data set acquired from a system having measurable inputs and outputs, using the model generating method of one of claim, comprising the steps of:

(a) generating a first model from a data set;

(b) generating a second model using the same modeling method, by either;

i) creating a plurality of feature subspaces different from the first model generating step, or

ii) dividing the feature subspace into a different plurality of cells by quantizing the inputs differently from the first model generating step;

(c) dividing the data set into subsets and determining a local performance of each model in each subset;

(d) generating a weighting function based upon the local performance of the first and second models in each subset; and

(e) combining the first and second models using the weighting function, thereby combining the local performance advantages of each of the models.

41. A machine-readable storage medium containing a set of instructions for causing a computing device to generate a model of a system using measurable inputs and measurable outputs of the system, said instructions causing the computing device to execute the steps of:

creating a plurality of feature subspaces, each said feature subspace comprising a set of features from data acquired from the system;

determining the global level of informational content of each feature subspace by calculating at least one local cell Nishi-formulated entropy E to define a local entropic weight W as the complement of the Nishi-formulated entropy E (W=1−

E)

searching the plurality of feature subspaces to locate feature subspaces having informational content above a predefined threshold, said located feature subspaces comprising combinations of one or more inputs;

searching a plurality of models, said models comprising one or more of said located feature subspaces, each of said models having an associated output prediction; and

selecting one of said models having an output prediction accuracy that is greater than that of at least one other model.

42. The storage medium of claim 41 wherein said step of searching a plurality of subspaces is performed by examining substantially all possible subspaces.

43. The storage medium of claim 41 wherein said step of searching a plurality of subspaces is performed by a genetic evolution algorithm employing a measure of informational content as a fitness function, wherein said fitness function is a measure of global subspace entropy,

further comprising the step of eliminating one or more inputs having the lowest frequency of occurrence in the plurality of models, and thereafter repeating the step of searching, wherein the feature subspaces comprise combinations of one or more of the remaining inputs.

44. The storage medium of claim 41 wherein said step of searching a plurality of models is performed by a genetic evolution algorithm which uses a measure of prediction accuracy as a fitness function, wherein said measure of prediction accuracy is based on predictions comprising a weighted combination of predictions of localized cellular regions within said one or more informational feature subspaces.

45. The storage medium of claim 41 wherein said searching includes dividing each said subspace into cells.

46. The storage medium of claim 45 wherein the number of cells is varied to identify a cell division that provides a higher informational content than at least one other cell division.

47. The storage medium of claim 45 wherein the number of cells is determined based on the number of available data points.

48. The storage medium of claim 45 wherein the cells are determined by dividing each dimension into equally sized subranges.

49. The storage medium of claim 45 wherein the cells are determined by dividing each dimension of a given subspace into subranges such that each subrange has approximately the same number of data points.

50. The storage medium of claim 41 wherein the informational content of a subspace is a weighted sum of cell informational content.

51. The storage medium of claim 50 wherein the cell informational content is based on the probabilities of an output being in a given output state for that cell.

52. The storage medium of claim 50 wherein the cell informational content is based on output state entropy.

53. The storage medium of claim 50 wherein the weight of a cell is based on number of points in the cell.

54. The storage medium of claim 41 wherein the informational content is a weighted sum of output-specific probabilities.

55. The storage medium of claim 54 wherein the output-specific probabilities are based on the probabilities of inputs being in individual cells for a given output state, wherein the output-specific probabilities are based on the entropy of the cell distribution for a given output state.

56. The storage medium of claim 54 wherein the weight of a subspace is based on the number of points in that subspace for a given output state.

57. The storage medium of claim 41 wherein the located informational subspaces are identified by a heuristic algorithm utilizing the number of cells within a subspace having a clustering of output states.

58. The storage medium of claim 41 wherein each subspace is divided into cells and each cell in each subspace has a cell probability vector, and wherein elements of the probability vector correspond to the probability of each output state, wherein each model has an associated probability vector containing a weighted sum of cell probability vectors, and wherein the weight is a combination of local entropic weights W and global entropic weights.

59. The storage medium of claim 41 wherein the output prediction accuracy is based on predictions having a value equal to the output having the highest probability of occurrence.

60. The storage medium of claim 41 further including instructions comprising the steps of:

selecting a plurality of models; and

grouping subsets of the selected models into a framework.

61. A machine-readable storage medium containing data structures, said data structures comprising:

a feature subspace data structure containing data representing a plurality of input combinations corresponding to a plurality of feature subspaces;

a model data structure containing data representing a plurality of feature subspace combinations;

a data structure containing data used to specify cell regions for each feature subspace; and

a training data structure containing data representing the training data set needed to populate the feature subspaces; and

further containing a data structure containing entropic weights for each subspace, each entropic weight being based upon at least one local cell Nishi-formulated entropy E, each local entropic weight W being defined as the complement of the Nishi-formulated entropy E (W=1−

E).

62. The storage medium of claim 61 further containing a data structure containing entropic weights for each cell region.

63. The storage medium of claim 61 further containing a data structure containing prediction values for each cell region.

64. The storage medium of claim 61 further containing a framework data structure containing data representing a plurality of model combinations.

65. A machine-readable storage medium containing a plurality of data structures, said plurality of data structures being used to determine a system output prediction response to system input data points, said data structures comprising:

a mapping data structure containing data used to map an input data point to a cell prediction value, wherein the prediction values are weighted probability vectors;

a model data structure containing data representing a plurality of feature subspace combinations, and,

further comprising a weighting data structure containing data representing local entropic weights w and global entropic weights, each entropic weight being based upon at least one local cell Nishi-formulated entropy E,

each local entropic weight W being defined as the complement of the Nishi-formulated entropy E (W=1−

E).

66. The storage medium of claim 65 further containing a framework data structure containing data representing a plurality of model combinations.

68. A machine-readable storage medium containing a set of instructions for causing a computing device to generate a model of a system using measurable inputs and measurable outputs of the system, wherein a large number of input data points to the system and corresponding output data points from the system are acquired to define a data set, said instructions causing the computing device to execute the steps of:

(a) creating a plurality of feature subspaces, each said feature subspace comprising a set of features from the data set,

(b) quantizing the inputs of the data set, the inputs having a range of values, by dividing the range of values into subranges, thereby dividing said feature subspace into a plurality of cells,

(c) determining the global level of informational content of each feature subspace by calculating at least one local cell Nishi-formulated entropy E to define a local entropic weight W as the complement of the Nishi-formulated entropy E (W=1−

E), and

(d) selecting at least one feature set that has a global informational content above a predefined threshold.