Pattern recognition using generalized association rules

• US 6,311,173 B1
• Filed: 10/09/1998
• Issued: 10/30/2001
• Est. Priority Date: 01/05/1998
• Status: Expired due to Fees

• Current Assignee: WizSoft Ltd.
• Original Assignee: WizSoft Ltd.
• Inventors: Levin, Boris, Cheskis, Alex, Meidan, Abraham
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/169,723
• Time in Patent Office: 1,117 Days
• Field of Search: 706/21, 706/45, 707/6, 707/1
• US Class Current: 706/21
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and system for predicting an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest. Known attribute values regarding a training sample of items within the population including the attribute of interest are stored in a memory. The stored attribute values are processed to determine association rules regarding the training sample, including at least one generalized association rule, each association rule including one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, and the at least one generalized rule including a logical combination of a plurality of such conditions using at least one logical operation from the group consisting of disjunction and negation. Data are received from an input device, the data including values of at least some of the attributes of the given item. The association rules including the at least one generalized association rule are applied to the values included in the data so as to predict the unknown value of the attribute of interest of the given item.

Claims

1. A method for predicting an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

storing in a memory known attribute values regarding a training sample of items within the population including the attribute of interest; and

processing the stored attribute values to determine association rules regarding the training sample, including at least one generalized association rule, each association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, and the at least one generalized rule comprising a logical combination of a plurality of such conditions using at least one logical operation from a group consisting of disjunction and negation.

2. A method according to claim 1, wherein processing the attribute values comprises finding the at least one generalized rule such that a support of the rule is maximized on the training sample.

3. A method according to claim 2, wherein finding the at least one generalized rule comprises finding a generalized association rule predicting that the attribute of interest has a given value, such that the support of the generalized rule in the training sample comprises at least ten times as many items having the given value of the attribute of interest as having another value, not equal to the given value.

4. A method according to claim 3, wherein finding the generalized association rule comprises finding a rule whose support in the training sample comprises substantially only items having the given value of the attribute of interest.

5. A method according to claim 1, wherein processing the attribute values comprises finding a plurality of generalized association rules such that an overlap of the respective supports of two or more of the plurality of rules on the training sample is minimized.

6. A method according to claim 1, wherein processing the attribute values comprises finding a plurality of generalized association rules such that substantially all of the items in the training sample are included in the support of one or more of the generalized rules.

7. A method according to claim 6, wherein finding the plurality of generalized rules comprises finding first and second groups of generalized rules that are respectively predictive of first and second values of the attribute of interest, such that there is an approximately equal number of rules in each group.

8. A method according to claim 1, wherein the at least one generalized association rule comprises a rule predicting that the attribute of interest has a first value if a condition substantially of a form (C_j1⁽ⁱ⁾vC_j2⁽ⁱ⁾v . . . vC_jk⁽ⁱ⁾) is fulfilled, wherein j1, j2, . . . , jk are indices enumerating conditions represented collectively as C_jm⁽ⁱ⁾, m an arbitrary index running from 1 to k, and i an index representing a conclusion of the conditions, and wherein each C_jm⁽ⁱ⁾ represents a condition on a known attribute value of the item other than the attribute of interest, which is predictive that the attribute of interest will have another value, different from the first value.

9. A method according to claim 1, wherein the at least one generalized association rule comprises a rule predicting that the attribute of interest has a first value if a condition substantially of a form (C_j1^(i₁)vC_j2^(i₁)v . . . vC_jk^(i₁)){circumflex over ( )}(C_jk+1^(i₂)vC_jk+2^(i₂)v . . . vC_jK^(i₂)) is fulfilled, wherein j1, j2, . . . , jk, jk+1, jk+2, . . . , jK are indices enumerating conditions represented collectively as C_jm^(i₁) and C_jm^(i₂) m an arbitrary index running from 1 to K, and i1 and i2 are indices representing conclusions of the conditions, and wherein each C_jm^(i₁) represents a condition on a known attribute value of the item other than the attribute of interest which is predictive that the attribute of interest will have the first value, and each C_jm^(i₂) represents a condition on a known attribute value of the item other than the attribute of interest which is predictive that the attribute of interest will have another value, different from the first value.

10. A method according to claim 9, wherein processing the attribute values comprises finding the set of rules {C_j1^(i₁) . . . C_jk^(i₁)} and then searching for rules in the set {C_jk+1^(i₂) . . . C_jK^(i₂)} on the support of {C_j1^(i₁) . . . C_jk^(i₁)}.

11. A method according to claim 1, wherein processing the attribute values comprises finding simple association rules, wherein each simple association rule comprises one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, such that if the simple association rule includes more than one such condition, the conditions are combined using the logical conjunction operation in defining the conditions of the rule.

12. A method according to claim 11, and comprising:

receiving data from an input device, the data including values of at least some of the attributes of the given item; and

applying the association rules including the at least one generalized association rule to the values included in the data so as to predict the unknown value of the attribute of interest of the given item.

13. A method according to claim 12, wherein applying the association rules comprises applying both the simple and the at least one generalized association rules jointly to predict the unknown value.

14. A method according to claim 13, wherein applying the rules jointly comprises computing a weighted sum of values of the attribute of interest predicted by the rules.

15. A method according to claim 14, wherein computing the weighted sum comprises computing probabilities respectively associated with the simple and generalized rules, and weighting the predicted values by the respective probabilities.

16. A method according to claim 11, wherein finding the association rules comprises finding the at least one generalized association rule by combining a plurality of the simple association rules.

17. A method according to claim 16, wherein combining the plurality of the simple association rules comprises combining the rules to find a generalized rule which includes a disjunction of two or more of the simple rules.

18. A method according to claim 16, wherein combining the plurality of the simple association rules comprises combining the rules to find a generalized rule which includes a negation of one or more of the simple rules.

19. A method according to claim 11, wherein determining the simple association rules comprises determining substantially all simple association rules pertaining to the sample having respective probability and support greater than predetermined minimum values thereof.

20. A method according to claim 1, wherein processing the attribute values comprises encoding values of the attributes according to the frequency of their occurrence in the training sample.

21. A method according to claim 20, wherein encoding the values comprises calculating hash functions.

22. A method according to claim 20, wherein encoding the values comprises assigning a distinguishable code to values occurring at less than a predetermined frequency in the training sample, whereby such values are substantially excluded from the determination the of association rules.

23. A method according to claim 1, and comprising:

receiving data from an input device, the data including values of at least some of the attributes of the given item; and

applying the association rules including the at least one generalized association rule to the values included in the data so as to predict the unknown value of the attribute of interest of the given item.

24. A method according to claim 23, wherein applying the association rules comprises applying a subset of the rules consisting of rules whose one or more conditions are fulfilled by known values of attributes of the given item other than the item of interest.

25. A method according to claim 23, wherein processing the attribute values comprises finding probabilities corresponding to the determined association rules, and wherein applying the association rules comprises applying the probabilities to compute a cumulative probability that the attribute of interest has a given value.

26. A method according to claim 25, wherein computing the cumulative probability comprises computing a weighted sum of the probabilities corresponding respectively to the association rules applied in predicting the value.

27. A method according to claim 25, and comprising determining a probability decision point such that when the cumulative probability is greater than the decision point, the attribute of interest is predicted to have a first value, and when the probability of interest is less than the decision point, the attribute of interest is predicted to have a different, second value.

28. A method according to claim 27, wherein determining the decision point comprises defining an ambiguity range of probabilities including the decision point in which the predicted value is ambiguous.

29. A method according to claim 28, wherein defining the ambiguity range comprises comparing the training sample and at least a portion of the overall population from which the given item is taken, and determining an extent of the ambiguity range responsive to a measure of the similarity of the training sample and the at least portion of the overall population.

30. A method according to claim 27, wherein determining the decision point comprises defining a point such that a total number of prediction errors is minimized.

31. A method according to claim 27, wherein an error cost is assigned to each of a plurality of types of prediction errors, and wherein determining the decision point comprises defining a point such that a total cost of prediction errors is minimized.

32. A method according to claim 23, wherein the items comprise records in a database, and the attributes comprise fields in the records, and wherein applying the association rules comprises predicting the unknown value of a database field.

33. A method according to claim 32, wherein predicting the unknown value comprises predicting a Boolean value.

34. A method according to claim 23, wherein the items comprise sounds, and the attribute values comprise characteristics of sound signals corresponding to the sounds, and wherein applying the association rules comprises identifying a sound signal.

35. A method according to claim 34, wherein identifying the sound signal comprises finding a word corresponding to the signal.

36. A method according to claim 34, wherein identifying the sound signal comprises identifying a speaker who generated the sound signal.

37. A method according to claim 34, wherein receiving the data comprises receiving data from a microphone.

38. A method according to claim 23, wherein the items comprise images, and the attribute values comprise image features, and wherein applying the association rules comprises processing an image.

39. A method according to claim 38, wherein processing the image comprises identifying a subject of the image.

40. A method according to claim 38, wherein receiving the data comprises receiving data from a camera.

41. A method according to claim 38, wherein receiving the data comprises receiving data from a scanner.

42. A method according to claim 23, and comprising outputting an indication of the predicted value to an output device.

43. A method according to claim 42, wherein outputting the indication comprises displaying the predicted value and a probability thereof.

44. A method according to claim 42, wherein outputting the indication comprises controlling an access responsive to the predicted value.

45. A method according to claim 42, wherein outputting the indication comprises sorting the given item responsive to the predicted value.

46. A method for predicting an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

storing in a memory known attribute values regarding a training sample of items within the population including the attribute of interest;

processing the attribute values to determine simple association rules regarding the training sample, each simple association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, such that if the simple association rule includes more than one such condition, the conditions are combined using a logical conjunction operation in defining the conditions of the rule,

wherein substantially all simple association rules applicable to the sample having respective probability and support greater than predetermined minimum values thereof are determined.

47. A method according to claim 46, wherein processing the attribute values comprises constructing a contingency table, each of whose entries corresponds to the number of items in the sample having a given value of the attribute of interest and a given, respective value of another one of the attributes, and wherein the association rules are determined with respect to the contingency table.

48. A method according to claim 46, and comprising:

receiving data from an input device, the data including values of at least some of the attributes of the given item; and

applying the association rules to the values included in the data so as to predict the unknown value of the attribute of interest of the given item.

49. A method for predicting an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

storing in a memory known attribute values regarding a training sample of items within the population including the attribute of interest;

processing the attribute values to determine association rules regarding the training sample, each association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest,

wherein the attribute values are processed by constructing a contingency table, each of whose entries corresponds to the number of items in the sample having a given value of the attribute of interest and satisfying a given, respective condition on one or more of the attributes other than the attribute of interest, and wherein the association rules are determined with respect to the contingency table.

50. A method according to claim 49, wherein constructing the contingency table comprises constructing a table of 1-conditions, characterized in that the condition on the one or more of the attributes comprises a condition on a single one of the attributes.

51. A method according to claim 50, wherein constructing the contingency table comprises constructing a table of 2-conditions, characterized in that the condition on the one or more of the attributes comprises a condition on two of the attributes, using the table of 1-conditions.

52. A method according to claim 51, wherein constructing the contingency table comprises constructing a plurality of respective tables of q-conditions, for a sequence of one or more integers q≧

3, characterized in that for each q, the condition on the one or more of the attributes comprises a condition on a group of q of the attributes, wherein for each q, the corresponding table is constructed using the table of q-1-conditions previously constructed.

53. A method according to claim 52, wherein each of the tables of q-conditions is stored in the memory as it is constructed, and wherein for each q, the corresponding table of q-1-conditions is deleted from the memory after the table of q-conditions is constructed.

54. A method according to claim 49, and comprising:

receiving data from an input device, the data including values of at least some of the attributes of the given item; and

applying the association rules to the values included in the data so as to predict the unknown value of the attribute of interest of the given item.

55. A system for predicting an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

an input device, which receives data indicative of values of at least some of the attributes of the given item;

a memory, which stores association rules regarding the population, the association rules including at least one generalized association rule, each association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, and the at least one generalized rule comprising a logical combination of such conditions using at least one logical operation from a group consisting of disjunction and negation in defining the conditions of the rule; and

a processor, which receives the data from the input device and reads the association rules from the memory, and which applies the association rules including the at least one generalized association rule to the values included in the data so as to predict the unknown value of the attribute of interest and which generates an output responsive to the prediction.

56. A system according to 55, wherein the processor applies a subset of the rules consisting of rules whose one or more conditions are fulfilled by known values of attributes of the given item other than the item of interest.

57. A system according to claim 55, wherein the processor finds probabilities corresponding to the determined association rules and applies the probabilities to compute a cumulative probability that the attribute of interest has a given value.

58. A system according to claim 57, wherein the processor computes a weighted sum of the probabilities corresponding respectively to the association rules applied in predicting the value.

59. A system according to claim 57, wherein the processor determines a probability decision point such that when the cumulative probability is greater than the decision point, the attribute of interest is predicted to have a first value, and when the probability of interest is less than the decision point, the attribute of interest is predicted to have a different, second value.

60. A system according to claim 59, wherein the processor defines an ambiguity range of probabilities including the decision point in which the predicted value is ambiguous.

61. A system according to claim 60, wherein the processor compares the training sample and at least a portion of the overall population from which the given item is taken, and determines an extent of the ambiguity range responsive to a measure of the similarity of the training sample and the at least portion of the overall population.

62. A system according to claim 59, wherein the processor determines the decision point such that a total number of prediction errors is minimized.

63. A system according to claim 59, wherein an error cost is assigned to each of a plurality of types of prediction errors, and wherein the processor determines the decision point such that a total cost of prediction errors is minimized.

64. A system according to claim 55, wherein the items comprise records in a database, and the attributes comprise fields in the records, and wherein the processor applies the association rules to predict the unknown value of a database field.

65. A system according to claim 64, wherein the unknown value comprises predicting a Boolean value.

66. A system according to claim 55, wherein the items comprise sounds, and the attribute values comprise characteristics of sound signals corresponding to the sounds, and wherein the processor applies the association rules to identify a sound signal.

67. A system according to claim 66, wherein the processor finds a word corresponding to the signal.

68. A system according to claim 66, wherein the processor identifies a speaker who generated the sound signal.

69. A system according to claim 66, wherein the input device comprises a microphone.

70. A system according to claim 55, wherein the items comprise images, and the attribute values comprise image features, and wherein the processor applies the association rules to process an image.

71. A system according to claim 70, wherein the processor identifies a subject of the image.

72. A system according to claim 70, wherein the input device comprises a camera.

73. A system according to claim 70, wherein the input device comprises a scanner.

74. A system according to claim 55, and comprising an output device, which receives the output from the processor and performs an action responsive thereto.

75. A system according to claim 74, wherein the output device comprises a display, which displays the predicted value.

76. A system according to claim 75, wherein the display displays a probability associated with the predicted value.

77. A system according to claim 74, wherein the output device comprises an access controller, which controls an access responsive to the predicted value.

78. A system according to claim 74, wherein the output device comprises a sorter, which sorts the given item responsive to the predicted value.

79. A system according to claim 55, and comprising a computer, which receives a training sample of items within the population having known respective attribute values including the attribute of interest, and which determines the association rules and finds the at least one generalized association rule by processing the known attribute values.

80. A system according to claim 79, wherein the computer includes the processor.

81. A system for determining association rules for prediction of an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

an input device, which receives data indicative of values of attributes of a training sample of items within the population including the attribute of interest;

a memory, which stores the values of the attributes; and

a computer, which reads the values from the memory and determines association rules regarding the population, the association rules including at least one generalized association rule, each association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, and the at least one generalized rule comprising a logical combination of such conditions using at least one logical operation from a group consisting of disjunction and negation in defining the conditions of the rule, and which stores the association rules in the memory.

82. A method according to claim 81, wherein the computer finds the at least one generalized rule such that a support of the rule is maximized on the training sample.

83. A system according to claim 82, wherein the at least one generalized association rule predicts that the attribute of interest has a given value, and the support of the generalized rule in the training sample comprises at least ten times as many items having the given value of the attribute of interest as having another value, not equal to the given value.

84. A system according to claim 83, wherein the support of the generalized rule in the training sample comprises substantially only items having the given value of the attribute of interest.

85. A system according to claim 81, wherein the computer finds a plurality of generalized association rules such that an overlap of the respective supports of two or more of the plurality of rules on the training sample is minimized.

86. A system according to claim 81, wherein the computer finds a plurality of generalized association rules such that substantially all of the items in the training sample are included in the support of one or more of the generalized rules.

87. A system according to claim 86, wherein the plurality of generalized rules comprises first and second groups of generalized rules that are respectively predictive of first and second values of the attribute of interest, such that there is an approximately equal number of rules in each group.

88. A system according to claim 81, wherein the at least one generalized association rule comprises a rule predicting that the attribute of interest has a first value if a condition substantially of a form (C_j1⁽ⁱ⁾vC_j2⁽ⁱ⁾v . . . vC_jk⁽ⁱ⁾ is fulfilled, wherein j1, j2, . . . , jk are indices enumerating conditions represented collectively as C_jm⁽ⁱ⁾, m an arbitrary index running from 1 to k, and i an index representing a conclusion of the conditions, and wherein each C_jm⁽ⁱ⁾ represents a condition on a known attribute value of the item other than the attribute of interest which is predictive that the attribute of interest will have another value, different from the first value.

89. A system according to claim 81, wherein the at least one generalized association rule comprises a rule predicting that the attribute of interest has a first value if a condition substantially of a form (C_j1^(i₁)vC_j2^(i₁)v . . . vC_jk^(i₁)){circumflex over ( )} (C_jk+1^(i₂)vC_jk+2^(i₂)v . . . vC_jK^(i₂) is fulfilled, wherein j1, j2, . . . , jk, jk+1, jk+2, . . . , jK are indices enumerating conditions represented collectively as C_jm^(i₁) and C_jm^(i₂), m an arbitrary index running from 1 to K, and i1 and i2 are indices representing conclusions of the conditions, and wherein each C_jm^(i₁) represents a condition on a known attribute value of the item other than the attribute of interest which is predictive that the attribute of interest will have the first value, and each C_jm^(i₂) represents a condition on a known attribute value of the item other than the attribute of interest which is predictive that the attribute of interest will have another value, different from the first value.

90. A system according to claim 89, wherein the computer finds the set of rules {C_j1^(i₁) . . . C_jk^(i₁)} and then searches for rules in the set {C_jk+1^(i₂) . . . C_jK^(i₂)} on the support of {C_j1^(i₁) . . . C_jk^(i₁)}.

91. A system according to claim 81, wherein the computer finds simple association rules, wherein each simple association rule comprises one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, such that if the simple association rule includes more than one such condition, the conditions are combined using the logical conjunction operation in defining the conditions of the rule.

92. A system according to claim 91, wherein the simple and the at least one generalized association rules are applied jointly to predict the unknown value.

93. A system according to claim 92, wherein a weighted sum of values of the attribute of interest predicted by the rules is used by the computer to predict the unknown value.

94. A system according to claim 93, wherein the computer computes probabilities respectively associated with the simple and generalized rules, which are used to weight the predicted values in computing the weighted sum.

95. A system according to claim 93, wherein the computer finds the at least one generalized association rule by combining a plurality of the simple association rules.

96. A system according to claim 95, wherein the at least one generalized rule includes a disjunction of two or more of the simple rules.

97. A system according to claim 95, wherein the at least one generalized rule includes a negation of one or more of the simple rules.

98. A system according to claim 91, wherein the computer determines substantially all simple association rules pertaining to the sample having respective probability and support greater than predetermined minimum values thereof.

99. A system according to claim 81, wherein the computer encodes values of the attributes according to the frequency of their occurrence in the training sample.

100. A system according to claim 99, wherein the computer encodes the values by calculating hash functions.

101. A system according to claim 99, wherein the computer assigns a distinguishable code to values occurring at less than a predetermined frequency in the training, sample, whereby such values are substantially excluded from the determination the of association rules.

102. A system for determining association rules for prediction of an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

an input device, which receives data indicative of values of attributes of a training sample of items within the population including the attribute of interest;

a memory, which stores the values of the attributes; and

a computer, which reads the values from the memory and determines simple association rules regarding the population, each simple association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, such that if the simple association rule includes more than one such condition, the conditions are combined using a logical conjunction operation in defining the conditions of the rule, and which stores the association rules in the memory,

wherein substantially all simple association rules applicable to the sample having respective probability and support greater than predetermined minimum values thereof are determined.

103. A system according to claim 102, wherein the computer determines the association rules by constructing a contingency table, each of whose entries corresponds to the number of items in the sample having a given value of the attribute of interest and a given, respective value of another one of the attributes.

104. A system for determining association rules for prediction of an unknown value of an attribute of interest of a given item from a population of items, each item in the population having a plurality of variable attributes including the attribute of interest, comprising:

an input device, which receives data indicative of values of attributes of a training sample of items within the population including the attribute of interest;

a memory, which stores the values of the attributes; and

a computer, which reads the values from the memory and determines association rules regarding the population, each association rule comprising one or more conditions on one or more respective attribute values of the items predictive of the value of the attribute of interest, and which stores the association rules in the memory,

wherein the computer determines the association rules by constructing one or more contingency tables, each of whose entries corresponds to the number of items in the sample having a given value of the attribute of interest and satisfying a given, respective condition on one or more of the attributes other than the attribute of interest.

105. A system according to claim 104, wherein the one or more contingency tables comprise a table of 1-conditions, characterized in that the condition on the one or more of the attributes comprises a condition on a single one of the attributes.

106. A system according to claim 105, wherein the one or more contingency tables comprise a table of 2-conditions, characterized in that the condition on the one or more of the attributes comprises a condition on two of the attributes, which is constructed by the computer using the table of 1-conditions.

107. A system according to claim 106, wherein the one or more contingency tables comprise a plurality of respective tables of q-conditions, for a sequence of one or more integers q≧

3, characterized in that for each q, the condition on the one or more of the attributes comprises a condition on a group of q of the attributes, wherein for each q, the computer constructs the corresponding table using the table of q-1-conditions previously constructed.

108. A system according to claim 107, wherein the computer stores each of the tables of q-conditions in the memory as it is constructed, and wherein for each q, the computer deletes the corresponding table of q-1-conditions from the memory after the table of q-conditions is constructed.