Method and apparatus for discovering association rules

• US 6,385,608 B1
• Filed: 11/05/1998
• Issued: 05/07/2002
• Est. Priority Date: 11/11/1997
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Mitsuishi, Akitoshi, Obata, Yasushi
• Primary Examiner(s): Homere, Jean R.
• Assistant Examiner(s): Wassum, Luke S
• Application Number:
  US09/186,356
• Time in Patent Office: 1,279 Days
• Field of Search: 707/1-3, 707/5-6, 706/47, 705/10
• US Class Current: 1/1
• 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: G06F 2216/03 Data mining
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A candidate-itemset generating unit generates a candidate-itemset composed of at least one candidate item to be included in the left hand side or the right hand side of the association rule. A candidate-itemset verifying unit selects itemsets having frequencies (appearing times in the database) more than the minimum frequency out of the candidate-itemsets, as large-itemsets. A candidate rule generating unit generates candidate association rules based on a large-itemset of k−1 long and a large-itemset of 1 long. A chi-square testing unit generates an association rule set based on the candidate association rules by performing a chi-square test in which a χ² statistics and a significant level are used as parameters.

Claims

1. A method for discovering an association rule existing between itemsets composed of one or more items, from a database storing a plurality of records composed of one or more items,

where k is an integer greater than or equal to 2, and n indicates an integer from 1 to k,

when an itemset is composed of n items and a frequency, meaning a number of records including the n items, of the itemset has not been checked, the itemset is defined as a candidate-itemset Cn, and

when a frequency of the candidate-itemset Cn is greater than or equal to a lower limit value Smin, the candidate-itemset Cn is defined as a large-itemset Ln,

the method comprising the steps of:

(a) generating a large-itemset, this step including the steps of;

(a1) generating a large-itemset L1 by counting a frequency meaning a number of records including each item, and defining an itemset composed of items made of the each item having a frequency greater than or equal to than the lower limit value Smin as the large-itemset L1;

(a2) generating a candidate-itemset Ck by using a large-itemset Lk−

1 and the large-itemset L1; and

(a3) generating a large-itemset Lk by selecting the large-itemset Lk from the candidate-itemset Ck; and

(b) generating and testing a hypothesis, this step including the steps of;

(b1) generating a candidate association rule by using the large-itemset Lk−

1 and the large-itemset L1, where the large-itemset Lk−

1 is defined as a condition itemset called a left hand side (LHS) and the large-itemset L1 is defined as a conclusion itemset called a right hand side (RHS); and

(b2) testing whether or not the candidate association rule is to be applied as the association rule; and

(c) inputting at least a significance level used for a chi-square test, and the step of testing the rule includes processes of calculating x² statistics (chi-squared statistics) based on a frequency of LHS, a frequency of RHS, a frequency of BS (both right and left hand sides) and a total number of records, and performing the chi-square test in which the x² statistics and the significance level are used as parameters.

2. The method for discovering an association rule of claim 1, wherein the step of generating and testing the hypothesis includes the step of discriminating the association rule to be one of a positive association rule and a negative association rule.

3. The method for discovering an association rule of claim 1, wherein the step of generating the large-itemset includes the step of deciding a limit frequency for calculating the lower limit value Smin based on a frequency of each item.

4. The method of discovering an association rule of claim 1, wherein the step of generating the large-itemset includes the step of deciding a minimum frequency by defining a smallest frequency in frequencies calculated for the each item, as the lower limit value of Smin.

5. The method for discovering an association rule of claim 1, wherein the step of generating and testing the hypothesis further includes the step of deciding a boundary for calculating a frequency limit value of the large-itemset L1 used in the step of generating the candidate association rule, by using a frequency of the large-itemset Lk−

1, being a pair to the large-itemset L1 and used in the step of generating the candidate association rule, and wherein the step of testing the rule includes the process of performing the chi-square test only for a candidate association rule generated based on the large-itemset L1 having a frequency within the boundary and the large-itemset Lk−

1 being a pair to the large-itemset L1.

6. The method for discovering an association rule of claim 1, said method further comprising inputting a parameter necessary for obtaining the association rule;

wherein the step of inputting includes the process of user'"'"'s inputting at least a condition regarding an item in one of the LHS and RHS.

7. The method for discovering an association rule of claim 1, said method further comprising inputting a parameter necessary for obtaining the association rule;

wherein the step of inputting includes the process of inputting at least an item, as the condition, at least one of which is necessarily included in the LHS of the association rule, and inputting at least an item, as the condition, at least one of which is included in the RHS of the association rule.

8. The method of discovering an association rule of claim 1, said method further comprising inputting a parameter necessary for obtaining the association rule;

wherein the step of inputting includes the process of inputting at least an item, as the condition, all of which are necessarily included in the LHS of the association rule, and inputting at least an item, as the condition, all of which are necessarily included in the RHS of the association rule.

9. The method for discovering an association rule of claim 1, said method further comprising inputting a parameter necessary for obtaining the association rule;

wherein the step of inputting includes the process of inputting at least a specific item in the plurality of records in the database in order to specify a domain which is a set of records including the specific item, and the step of generating the large-itemset includes the step of restricting the domain in order to select only the records included in a specified domain, and in order to use a total number of the records included in the specified domain hereinafter instead of a total number of the plurality of records in the database.

10. An apparatus for generating an association rule existing between itemsets composed of one or more items, from a database storing a plurality of records composed of one or more items,

where k is an integer greater than or equal to 2, and n indicates an integer from 1 to k,

when an itemset is composed of n items and a frequency, meaning a number of records including the n items, of the itemset has not been checked, the itemset is defined as a candidate-itemset Cn, and

when a frequency of the candidate-itemset Cn is greater than or equal to a lower limit value Smin, the candidate-itemset Cn is defined as a large-itemset Ln,

the apparatus comprising:

a memory; and

a processor coupled to the memory, the processor configured to;

(a) generate a large-itemset, the processor further configured to;

(a1) generate a large-itemset L1 by counting a frequency meaning a number of records including each item, and defining an itemset composed of items made of the each item having a frequency greater than or equal to the lower limit value Smin as the large-itemset L1;

(a2) generate a candidate-itemset Ck by using a large-itemset Lk−

1 and the large-itemset L1; and

(a3) generate a large-itemset Lk by selecting the large-itemset Lk from the candidate-itemset Ck; and

(b) generate and test a hypothesis, the processor further configured to;

(b1) generate a candidate association rule by using the large-itemset Lk−

1 and the large-itemset L1, where the large-itemset Lk−

1 is defined as a condition itemset called a left hand side (LHS) and the large-itemset L1 is defined as a conclusion itemset called a right hand side (RHS); and

(b2) test a rule for testing whether or not the candidate association rule is to be one of applied and not-applied as the association rule; and

(c) input at least a significance level used for a chi-square test,

wherein the processor in testing the rule is further configured to calculate chi-squared statistics based on a frequency of LHS, a frequency of RHS, a frequency of both RHS and LHS, and a total number of records, and performing the chi-square test in which the chi-squared statistics and the significance level are used as parameters.

11. The apparatus for discovering an association rule according to claim 10, wherein the processor in generating and testing the hypothesis is further configured to discriminate the association rule to be one of a positive association rule and a negative association rule.

12. The apparatus for discovering an association rule according to claim 10, wherein the processor in generating the large-itemset is further configured to decide a limit frequency for calculating the lower limit value Smin based on a frequency of each item.

13. The apparatus for discovering an association rule according to claim 10, wherein the processor in generating the large-itemset is further configured to decide a minimum frequency by defining a smallest frequency in frequencies calculated for the each item, as the lower limit value of Smin.

14. The apparatus for discovering an association rule according to claim 10, wherein the processor in inputting at least a significance level is further configured to input at least a condition regarding an item in one of the LHS and RHS.

15. The apparatus for discovering an association rule according to claim 10, wherein the processor in generating and testing the hypothesis is further configured to decide a boundary for calculating a frequency limit value of the large-itemset L1 used in generating the candidate association rule, by using a frequency of the large-itemset Lk−

1, being a pair to the large-itemset L1 and used in the step of generating the candidate association rule, and wherein the processor in testing the rule is further configured to perform the chi-square test only for a candidate association rule generated based on the large-itemset L1 having a frequency within the boundary and the large-itemset Lk−

1 being a pair to the large-itemset L1.

16. The apparatus for discovering an association rule according to claim 10, wherein the processor in inputting at least a significance level is further configured to input at least an item, as the condition, at least one of which is necessarily included in the LHS of the association rule, and input at least an item, as the condition, at least one of which is included in the RHS of the association rule.

17. The apparatus for discovering an association rule according to claim 10, wherein the processor in inputting at least a significance level is further configured to input at least an item, as the condition, all of which are necessarily included in the LHS of the association rule, and input at least an item, as the condition, all of which are necessarily included in the RHS of the association rule.

18. The apparatus for discovering an association rule according to claim 10, wherein the processor in inputting at least a significance level is further configured to input at least a specific item in the plurality of records in the database in order to specify a domain which is a set of records including the specific item, and in generating the large-itemset is further configured to restrict the domain in order to select only the records included in a specified domain, and in order to use a total number of the records included in the specified domain hereinafter instead of a total number of the plurality of records in the database.