System and method for identifying conditions leading to a particular result in a multi-variant system

• US 5,694,524 A
• Filed: 02/15/1994
• Issued: 12/02/1997
• Est. Priority Date: 02/15/1994
• Status: Expired due to Term

• Current Assignee: RR Donnelley & Sons Company
• Original Assignee: RR Donnelley & Sons Company
• Inventors: Evans, Robert B.
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/196,707
• Time in Patent Office: 1,386 Days
• Field of Search: 395/10-11, 395/13, 395/20, 395/50, 395/51, 395/61-62, 395/63, 395/75-77, 395/902, 395/906, 395/914, 364/525-526
• US Class Current: 706/12
• CPC Class Codes: G06F 11/25 Testing of logic operation, e.g. by logic analysers
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: Y10S 706/903 Control
• CPC Class Codes: Y10S 706/904 Manufacturing or machine, e.g. agricultural machinery, machine tool
• CPC Class Codes: Y10S 706/906 Process plant

Abstract

A system and method develops an indication of a cause of a particular result of a process from values associated with attributes which arise during runs of the process. The system includes a data entry device which permits a user to enter data indicating the values of the attributes and a class associated with each of the runs of the process, a memory which stores the data, a processing unit which produces an induction tree having multiple nodes and an output device which provides an indication of the induction tree to a user. At each of a plurality of the nodes of the induction tree, the processing unit divides the values associated with the attributes into value groups, allows a user to select any one of the attributes and designates a value group of the selected attribute as an endpoint of an induction tree when the value group satisfies an endpoint criterion and, otherwise, designates the value group of the selected attribute as a branching point of the induction tree.

Claims

1. A system for use in developing an indication of a cause of a particular result of a process from values each associated with one of a first plurality of attributes arising during an associated one of a second plurality of runs of the process, wherein the runs during which the particular result occurred are in a first class and the runs during which the particular result did not occur are in a second class, comprising:

data entry means for permitting a user to enter data indicating the attribute values and the class associated with each of the second plurality of runs;

a memory for storing the data indicating the attribute values and the class associated with each of the second plurality of runs;

a processing unit including,

means for dividing the values associated with each of the attributes into value groups including means for determining whether an actual distribution of classes among the value groups of a certain one of the attributes is consistent with a class heuristic which indicates an expected distribution of classes among the value groups of the certain one of the attributes,

means for selecting any one of the first plurality of attributes,

means for designating a value group of the selected attribute as an endpoint of an induction tree when the value group satisfies an endpoint criterion and, otherwise, designating the value group of the selected attribute as a branching point of the induction tree,

means operative when a value group of the selected attribute is designated as a branching point for redividing the values associated with attributes other than the selected attribute into further value groups,

means operative when a value group of the selected attribute is designated as a branching point and coupled to the redividing means for choosing a further attribute, and

further means coupled to the choosing means for determining whether any further value group of the further attribute satisfies the endpoint criterion and thus comprises an endpoint of the induction tree; and

an output device which develops a representation of the induction tree for the user.

2. The system of claim 1, wherein the designating means comprises means for ascertaining whether a predetermined percentage of the runs during which the values within the value group arose are associated with one of the first and second classes.

3. The system of claim 1, further including means for calculating figures of merit for attributes from the value groups of the attributes and wherein the selecting means includes means for allowing a user to select any one of the first plurality of attributes and means for indicating the figures of merit to the user prior to allowing the user to select any one of the first plurality of attributes.

4. The system of claim 1, wherein a value group designated as a branching point contains a certain number of values which are associated with a certain number of runs and wherein the redividing means redivides the values associated with attributes other than the selected attribute and associated with the certain number of runs.

5. The system of claim 1, wherein the selecting means includes means for allowing a user to select any one of the first plurality of attributes and means for notifying a user when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic.

6. The system of claim 1, wherein the values associated with a particular one of the attributes are in a continuum and wherein the dividing means divides the continuum into a set of ranges such that each value group associated with the particular one of the attributes includes the values within one of the ranges.

7. The system of claim 6, wherein the dividing means includes means for separating the values of the particular one of the attributes into first and second sets according to the classes of the runs during which the values arose, first means for measuring a statistical property of the first set, second means for measuring a statistical property of the second set and means for developing the set of ranges from the statistical properties of the first and second sets.

8. The system of claim 7, wherein the developing means includes means for deriving first and second subsets of values from the first and second sets wherein the first subset includes the values of the first set which are greater than the statistical property of the first set and the second subset includes the values of the second set which are less than the statistical property of the second set, means for finding a statistical property of the first and second subsets, means coupled to the deriving means for replacing the statistical properties of the first and second sets with the statistical properties of the first and second subsets, respectively, if the statistical property of the first subset is less than the statistical property of the second subset, and means coupled to the deriving means and operable when the statistical property of the first subset is greater than or equal to the statistical property of the second subset for defining a first range having a region below the statistical property of the first set, a second range having a region between the statistical property of the first set and the statistical property of the second set and a third range having a region above the statistical property of the second set.

9. The system of claim 8, wherein the statistical property of the first set is the same as the statistical property of the second set.

10. The system of claim 8, wherein the statistical property of one of the first and second sets is a median.

11. The system of claim 1, wherein the data entry means is a keyboard.

12. The system of claim 1, wherein the data entry means is a disk drive.

13. The system of claim 8, wherein the certain one of the attributes is different than the particular one of the attributes.

14. The system of claim 1, further including means for calculating figures of merit for attributes from the value groups of the attributes and wherein the selecting means selects the one of the first plurality of attributes based on the figures of merit.

15. The system of claim 1, wherein the selecting means includes means for allowing a user to select any one of the first plurality of attributes and the choosing means includes means for permitting a user to select the further attribute.

16. The system of claim 1, wherein the selecting means inhibits selection of the certain one of the attributes as the selected attribute when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic.

17. An apparatus for constructing an induction tree having a plurality of nodes which is for use in determining a cause of a particular result of a process from a data set including values for each of a first plurality of attributes arising during each of a second plurality of runs of the process and an indication of a class associated with each of the second plurality of runs, wherein the runs during which the particular result occurred are in a first class and the runs during which the particular result did not occur are in a second class, comprising:

data entry means for permitting a user to enter the data set;

a memory for storing the data set;

a processing unit including,

means for dividing the values within the data set and associated with each of the first plurality of attributes into value groups at each of a third plurality of the nodes, wherein a class heuristic defining an expected distribution of classes among value groups of a certain one of the attributes is identified and wherein the dividing means includes means for determining whether an actual distribution of classes among the value groups of the certain one of the attributes is consistent with the class heuristic,

means coupled to the dividing means for allowing a user to select one of the first plurality of attributes at each of the third plurality of the nodes,

means coupled to the allowing means for designating one of the value groups of the selected attribute as an endpoint of the induction tree when the one of the value groups satisfies an endpoint criterion and, otherwise, designating the one of the value groups of the selected attribute as a branching point of the induction tree, wherein the value group designated as a branching point contains a certain number of values associated with a certain number of runs, and

means coupled to the designating means and to the dividing means and operable when a value group of the selected attribute has been designated as a branching point for redefining the data set to include the values associated with the certain number of runs, and

an output device which develops a representation of the induction tree for the user.

18. The apparatus of claim 17, wherein the endpoint criterion is satisfied when a predetermined percentage of the runs during which the values within the value group being designated arose are associated with one of the first and second classes.

19. The apparatus of claim 17, further including means for calculating a figure of merit for attributes at each of the third plurality of the nodes from the value groups of the attributes and wherein the allowing means includes means for indicating the figures of merit to a user.

20. The apparatus of claim 17, further including means for inhibiting the allowing means from allowing a user to select the certain one of the attributes as the selected attribute when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic.

21. The apparatus of claim 17, wherein the allowing means includes means for notifying a user when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic.

22. The apparatus of claim 17, wherein the values associated with a particular one of the attributes are in a continuum and the dividing means divides the continuum into a set of ranges such that each value group associated with the particular one of the attributes includes the values within one of the ranges.

23. The apparatus of claim 22, wherein the dividing means includes means for separating the values associated with the particular one of the attributes into first and second sets according to the classes of the runs during which the values arose, means for finding statistical properties of the first and second sets and means for developing the set of ranges from the statistical properties of the first and second sets.

24. The apparatus of claim 23, wherein the developing means includes means for deriving first and second subsets of values from the first and second sets, wherein the first subset includes the values of the first set which are greater than the statistical property of the first set and the second subset includes the values of the second set which are less than the statistical property of the second set, means for measuring statistical properties of the first and second subsets, means for replacing the statistical properties of the first and second sets with the statistical properties of the first and second subsets, respectively, if the statistical property of the first subset is less than the statistical property of the second subset, and means coupled to the deriving means and operable when the statistical property of the first subset is greater than or equal to the statistical property of the second subset for defining a first range having a region below the statistical property of the first set, a second range having a region between the statistical property of the first set and the statistical property of the second set and a third range having a region above the statistical property of the second set.

25. The apparatus of claim 24, wherein the statistical property of one of the first and second sets is a median.

26. The apparatus of claim 24, wherein the certain one of the attributes is different than the particular one of the attributes.

27. The system of claim 17, wherein the data entry means is a keyboard.

28. The system of claim 17, wherein the data entry means is a disk drive.

29. A method of forcing a repetitively-executed process toward a particular outcome, comprising the steps of:

determining attributes which potentially affect the outcome;

collecting attribute data indicative of each attribute during a number of prior runs of the process;

obtaining outcome data indicative of the outcome of each prior process run;

building an induction tree from the collected attribute data and the obtained outcome data including dividing the attribute data into value groups and determining whether an actual distribution of outcomes associated with the attribute data in the value groups of a certain one of the attributes is consistent with a class heuristic defining an expected distribution of outcomes among the attribute data of the values groups of the certain one of the attributes;

finding a path in the induction tree which indicates that the particular outcome is more likely to occur than not; and

using the found path to specify attribute values for a subsequent run of the process.

30. The method of claim 29, wherein the induction tree comprises a plurality of nodes and the step of building the induction tree comprises the step of allowing the user to select a branch at multiple nodes.

31. The method of claim 29, wherein the attribute data of a particular one of the attributes are in a continuum, the runs during which the outcome occurred are in a first class and the runs during which the outcome did not occur are in a second class, and wherein the step of building the induction tree comprises the steps of dividing the attribute data associated with the particular one of the attributes into first and second sets according to the classes of the runs during which the attribute data was collected, determining a statistical property of the first set, determining a statistical property of the second set and developing value groups for the particular one of the attributes from the statistical properties of the first and second sets.

32. The method of claim 31, wherein the step of developing the value groups includes the steps of (a) developing first and second subsets of attribute data from the first and second sets wherein the first subset includes the attribute data of the first set which are greater than the statistical property of the first set and the second subset includes the attribute data of the second set which are less than the statistical property of the second set, (b) determining a statistical property of the first subset, (c) determining a statistical property of the second subset, (d) replacing the statistical properties of the first and second sets with the statistical properties of the first and second subsets, respectively, if the statistical property of the first subset is less than the statistical property of the second subset, (e) repeating the steps (a) through (d) until the statistical property of the first subset is greater than or equal to the statistical property of the second subset and (f) defining a first value group having attribute data in a region below the statistical property of the first set, a second value group having attribute data in a region between the statistical property of the first set and the statistical property of the second set and a third value group having attribute data in a region above the statistical property of the second set.

33. The method of claim 32, wherein the statistical property of the first set is the same as the statistical property of the second set.

34. The method of claim 32, wherein the statistical property of one of the first and second sets is a median.

35. A method of determining a cause of a particular result of a process from values each associated with one of a first plurality of attributes arising during each of a second plurality of runs of the process, comprising the steps of:

(a) defining a data set to include the plurality of values;

(b) dividing the values associated with each of the first plurality of attributes within the data set into value groups wherein the values associated with a certain one of the attributes are in a continuum and the step of dividing includes the steps of;

(1) grouping the runs during which the particular result occurred into a first class and grouping the runs during which the particular result did not occur into a second class,

(2) dividing the continuum into a set of ranges wherein each value group associated with the certain one of the attributes includes the values within one of the ranges including the steps of;

(i) dividing the values associated with the certain one of the attributes into first and second sets according to the classes of the runs during which the values arose,

(ii) determining a statistical property of the first set,

(iii) determining a statistical property of the second set,

(iv) developing first and second subsets of values from the first and second sets wherein the first subset includes the values of the first set which are greater than the statistical property of the first set and the second subset includes the values of the second set which are less than the statistical property of the second set,

(v) determining a statistical property of the first subset,

(vi) determining a statistical property of the second subset,

(vii) replacing the statistical properties of the first and second sets with the statistical properties of the first and second subsets, respectively, if the statistical property of the first subset is less than the statistical property of the second subset,

(viii) repeating the steps (iv) through (vii) until the statistical property of the first subset is greater than or equal to the statistical property of the second subset, and

(ix) defining a first range having a region below the statistical property of the first set, a second range having a region between the statistical property of the first set and the statistical property of the second set and a third range having a region above the statistical property of the second set;

(c) allowing a user to select one of the attributes;

(d) designating a value group of the selected attribute as an endpoint of an induction tree when the value group satisfies an endpoint criterion and, otherwise, designating the value group of the selected attribute as a branching point of the induction tree, wherein the value group designated as a branching point contains a certain number of values which are associated with a certain number of runs;

(e) redefining the data set to include only the values associated with the certain number of runs;

(f) repeating steps (b) through (e) until a value group is designated as an endpoint in step (d); and

(g) identifying one or more of the value groups designated as one of the endpoints and the value groups designated as branching points within a path to one of the endpoints as a cause of the particular result.

36. The method of claim 35, further including the step of calculating a figure of merit for a particular number of the attributes from the value groups for the particular number of the attributes and indicating the figures of merit for the particular number of the attributes to a user prior to the step of selecting one of the attributes.

37. The method of claim 35, wherein the runs during which the particular result occurred are in a first class and the runs during which the particular result did not occur are in a second class and wherein the endpoint criterion is satisfied when a predetermined percentage of the runs during which the values within the value group being designated arose are in one of the first and second classes.

38. The method of claim 35, further including the steps of generating a solution including ranges of values for a third plurality of the attributes from the value groups identified as the cause of the particular result and forcing each of the values of the third plurality of the attributes of a run of the process to be within the ranges of the third plurality of the attributes in the solution.

39. The method of claim 35, further including the steps of generating a solution including ranges of values for a third plurality of the attributes from the value groups identified as the cause of the particular result and forcing each of the values of the third plurality of the attributes of a run of the process to be outside of the ranges of the third plurality of the attributes in the solution.

40. The method of claim 35, further including the steps of identifying the first plurality of attributes arising during each run of the process and obtaining the values each associated with one of the first plurality of attributes arising during the second plurality of runs of the process.

41. The method of claim 35, wherein the runs during which the particular result occurred are in a first class and the runs during which the particular result did not occur are in a second class and further including the steps of identifying a class heuristic defining an expected distribution of classes among value groups of one of the attributes and determining whether an actual distribution of classes among the value groups of the one of the attributes is consistent with the class heuristic.

42. The method of claim 41, further including the step of inhibiting the selection of the one of the attributes as the selected attribute when the actual distribution of classes among the value groups of the one of the attributes is inconsistent with the class heuristic.

43. The method of claim 41, further including the step of changing the class heuristic for the one of the attributes when the actual distribution of classes among the value groups of the one of the attributes is inconsistent with the class heuristic.

44. The method of claim 35, further including the step of allowing termination of branching from a branching point interactively.

45. The method of claim 35, wherein the statistical property of the first set is the same as the statistical property of the second set.

46. The method of claim 35, wherein the statistical property of one of the first and second sets is a median.

47. A method of controlling the incidence of a particular result which arises during a run of a process using values each associated with one of a first plurality of attributes arising during each of a second plurality of runs of the process, wherein the values associated with one of the attributes fall within a continuum, and wherein a certain number of runs are grouped into a plurality of classes based on the occurrence of the particular result within each of the certain number of runs, comprising the steps of:

(A) constructing an induction tree from the plurality of values including the steps of,

(a) dividing the values associated with the one of the attributes into first and second sets according to the classes of the runs during which the values arose,

(b) determining a statistical property of the first set,

(c) determining a statistical property of the second set, and

(d) dividing the values associated with the one of the attributes into ranges defined in accordance with the statistical properties of the first and second sets including the steps of,

(i) developing first and second subsets of values from the first and second sets wherein the first subset includes the values of the first set which are greater than the statistical property of the first set and the second subset includes the values of the second set which are less than the statistical property of the second set,

(ii) determining a statistical property of the first subset,

(iii) determining a statistical property of the second subset,

(iv) replacing the statistical properties of the first and second sets with the statistical properties of the first and second subsets, respectively, if the statistical property of the first subset is less than the statistical property of the second subset,

(v) repeating the steps (i) through (iv) until the statistical property of the first subset is greater than or equal to the statistical property of the second subset, and

(vi) defining a first range having a region below the statistical property of the first set, a second range having a region between the statistical property of the first set and the statistical property of the second set and a third range having a region above the statistical property of the second set;

(B) determining a cause of the particular result from the induction tree; and

(C) controlling a run of the process in accordance with the determined cause to either reduce or increase the probability of incidence of the particular result.

48. The method of claim 47, wherein the statistical property of the first set and the statistical property of the second set are the same statistical property.

49. The method of claim 47, wherein the statistical property of one of the first and second sets is a median.

50. The method of claim 47, wherein the step of building an induction tree further comprises the steps of dividing the values associated with each of the first plurality of attributes into value groups, wherein each of the value groups associated with the one of the attributes comprises one of the ranges, selecting a particular one of the attributes, designating one of the value groups of the selected attribute as an endpoint of an induction tree when the one of the value groups satisfies an endpoint criterion and, otherwise, designating the one of the value groups as a branching point of the induction tree.

51. The method of claim 50, wherein the step of selecting a particular one of the attributes comprises interactively selecting the particular one of the attributes.

52. The method of claim 50, including the step of identifying a class heuristic defining an expected distribution of classes among value groups of a certain one of the attributes and wherein the step of building the induction tree comprises the step of determining whether an actual distribution of classes among the value groups of the certain one of the attributes is consistent with the class heuristic.

53. The method of claim 52, wherein the step of selecting a particular one of the attributes comprises interactively selecting the particular one of the attributes.

54. The method of claim 52, wherein the one of the attributes, the particular one of the attributes and the certain one of the attributes comprise a different one of the first plurality of attributes.

55. A method of controlling the incidence of a particular result which arises during a run of a process using a plurality of values each associated with one of a first plurality of attributes arising during each of a second plurality of runs of the process, wherein a class heuristic which defines an expected distribution of classes among value groups of a certain one of the attributes is identified, comprising the steps of:

(a) defining a data set to include the plurality of values;

(b) dividing the values within the data set and which are associated with each of the attributes into value groups;

(c) comparing an actual distribution of classes among value groups of the certain one of the attributes with the class heuristic;

(d) selecting one of the attributes based on the step of comparing;

(e) designating one of the value groups of the selected attribute as an endpoint when an endpoint criterion is satisfied and, otherwise, designating the one of the value groups of the selected attribute as a branching point, wherein a value group designated as a branching point contains a certain number of values associated with a certain number of runs;

(f) redefining the data set to include only the values associated with the certain number of runs;

(g) repeating steps (b) through (f) until a value group is designated as an endpoint in step (e);

(i) identifying one of the value groups designated as the endpoint and the value groups designated as branching points within a path to the endpoint as a cause of the particular result; and

(j) controlling a run of the process in accordance with the identified cause to either reduce or increase the probability of incidence of the particular result.

56. The method of claim 55, wherein the step of selecting one of the attributes includes the step of calculating a figure of merit for attributes from the value groups of the attributes.

57. The method of claim 55, wherein the step of selecting one of the attributes includes the step of inhibiting the selection of the certain one of the attributes as the selected attribute when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic.

58. The method of claim 55, further including the step of identifying the certain one of the attributes to the user when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic for the certain one the of attributes.

59. The method of claim 58, further including the step of changing the class heuristic when the actual distribution of classes among the value groups of the certain one of the attributes is inconsistent with the class heuristic.

60. The method of claim 58, wherein the step of selecting one of the attributes comprises allowing a user to interactively select one of the attributes.

61. A system for use in developing an indication of a cause of a particular result of a process from values each associated with one of a first plurality of attributes arising during an associated one of a second plurality of runs of the process, wherein the runs during which the particular result occurred are in a first class and the runs during which the particular result did not occur are in a second class, comprising:

data entry means for permitting a user to enter data indicating the attribute values and the class associated with each of the second plurality of runs;

a memory for storing the data indicating the plurality of attribute values and the class associated with each of the second plurality of runs;

a processing unit including,

means for dividing the values associated with each of the attributes into value groups wherein the values associated with a particular one of the attributes are in a continuum and wherein the dividing means divides the continuum into a set of ranges such that each value group associated with the particular one of the attributes includes the values within one of the ranges, the dividing means including;

(1) means for separating the values of the particular one of the attributes into first and second sets according to the classes of the runs during which the values arose,

(2) first means for measuring a statistical property of the first set,

(3) second means for measuring a statistical property of the second set, and

(4) means for developing the set of ranges from the statistical properties of the first and second sets including (a) means for deriving first and second subsets of values from the first and second sets wherein the first subset includes the values of the first set which are greater than the statistical property of the first set and the second subset includes the values of the second set which are less than the statistical property of the second set, (b) means for finding a statistical property of the first and second subsets, (c) means coupled to the deriving means for replacing the statistical properties of the first and second sets with the statistical properties of the first and second subsets, respectively, if the statistical property of the first subset is less than the statistical property of the second subset and (d) means coupled to the deriving means and operable when the statistical property of the first subset is greater than or equal to the statistical property of the second subset for defining a first range having a region below the statistical property of the first set, a second range having a region between the statistical property of the first set and the statistical property of the second set and a third range having a region above the statistical property of the second set,

means for selecting any one of the first plurality of attributes,

means for designating a value group of the selected attribute as an endpoint of an induction tree when the value group satisfies an endpoint criteria and, otherwise, designating the value group of the selected attribute as a branching point of the induction tree,

means operative when a value group of the selected attribute is designated as a branching point for redividing the values associated with attributes other than the selected attribute into further value groups,

means operative when a value group of the selected attribute is designated as a branching point and coupled to the redividing means for choosing a further attribute, and

further means coupled to the choosing means for determining whether any further value group of the further attribute satisfies the endpoint criterion and thus comprises an endpoint of the induction tree; and

an output device which develops a representation of the induction tree for the user.

62. The system of claim 61, wherein the statistical property of the first set is the same as the statistical property of the second set.

63. The system of claim 61, wherein the statistical property of one of the first and second sets is a median.

64. The system of claim 61, wherein the selecting means includes means for allowing a user to select any one of the first plurality of attributes and the choosing means includes means for permitting a user to select the further attribute.