Rule discovery system, method, apparatus, and program

Patent metadata

Field	Value
Publication number	US-9767411-B2
Application number	US-201314401019-A
Country	US
Kind code	B2
Filing date	May 13, 2013
Priority date	May 14, 2012
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

A system includes a free itemset generation unit to generate a set of free itemsets, each having a frequency in the database greater than or equal to a predetermined threshold value set in advance, a valid rule candidate generation unit to generate rule candidates and store the generated rule candidates, and a rule minimality decision unit to check minimality of each of the generated rule candidates and output the generated rule candidate to an output apparatus when the generated rule candidate is determined to be minimal.

First claim

The invention claimed is:

1. A rule discovery system comprising:
a storage apparatus configured to store a database;
a data processing apparatus; and
an output apparatus, wherein
the data processing apparatus includes;
a free itemset generation unit to generate a free itemset including a set of items of attribute-value pairs in the database, the free itemset having a frequency in the database greater than or equal to a predetermined threshold value set in advance;
a valid rule candidate generation unit to generate a rule candidate including a condition part having the generated free itemset set thereto and a consequent part having an item that does not share an attribute with the free itemset set thereto, the rule candidate having a confidence greater than or equal to a confidence threshold value set in advance, and to store the generated rule candidate in a storage unit, when a ratio of a frequency of the itemset obtained by adding one item x to a free itemset α to a frequency of the free itemset α is greater than or equal to the confidence threshold value, the valid rule candidate generation unit adding to a list of a rule candidate group including a plurality of the rule candidates a rule including a condition part having a free itemset α set thereto and a consequent part having the one item x set thereto; and
a rule minimality decision unit to check minimality of the rule candidate generated by the valid rule candidate generation unit and to output the rule candidate to the output apparatus when the rule candidate is determined to be minimal.

2. The rule discovery system according to claim 1 , wherein the rule minimality decision unit sorts the list of the rule candidate group generated by the valid rule candidate generation unit in an ascending order of sizes of the rule candidates,
the rule minimality decision unit sequentially extracts, from a head of the list, a minimal one or more of the rule candidates and outputs the extracted minimal one or more of the rule candidates to the output apparatus, and
the rule minimality decision unit removes, from the list, one or more of the remaining rule candidates in the list that are redundant with respect to the output minimal one or more of the rule candidates.

3. The rule discovery system according to claim 1 , comprising
an input apparatus configured to receive a threshold value of the frequency and the threshold value of the confidence as setting parameters.

4. The rule discovery system according to claim 1 , wherein the rule is a rule expressed as a CFD (Conditional Functional Dependency).

5. A rule discovery system comprising:
a storage apparatus configured to store a database;
a data processing apparatus; and
an output apparatus, wherein
the data processing apparatus includes;
a free itemset generation unit to generate a free itemset including a set of items of attribute-value pairs in the database, the free itemset having a frequency in the database greater than or equal to a predetermined threshold value set in advance;
a valid rule candidate generation unit to generate a rule candidate including a condition part having the generated free itemset set thereto and a consequent part having an item that does not share an attribute with the free itemset set thereto, the rule candidate having a confidence greater than or equal to a confidence threshold value set in advance, and to store the generated rule candidate in a storage unit; and
a rule minimality decision unit to check minimality of the rule candidate generated by the valid rule candidate generation unit and to output the rule candidate to the output apparatus when the rule candidate is determined to be minimal, wherein the valid rule candidate generation unit calculates a frequency of an itemset obtained by adding one item x to each free itemset α, and
when a ratio of a frequency of the itemset obtained by adding the one item x to the free itemset α to a frequency of the free itemset α is greater than or equal to the confidence threshold value, the valid rule candidate generation unit repeatedly performs a process of adding to a list of a rule candidate group including a plurality of the rule candidates a rule including a condition part having the free itemset α set thereto and a consequent part having the one item x set thereto, as a rule candidate, until the checking for all combinations of the free itemsets α generated by the free itemset generation unit and the item x is finished.

6. A method of discovering a rule from a database by a data processing apparatus, the method comprising:
(a) reading the database, generating a free itemset that includes a set of items of attribute-value pairs in the database and that has a frequency in the database greater than or equal to a predetermined threshold value set in advance, and storing the generated free itemset in a storage unit;
(b) generating a rule candidate that includes a condition part having the generated free itemset set thereto and a consequent part having an item that does not share an attribute with the free itemset set thereto, and that has a confidence greater than or equal to a confidence threshold value set in advance, and storing the generated rule candidate in a storage unit, when a ratio of a frequency of the itemset obtained by adding one item x to a free itemset α to a frequency of the free itemset α is greater than or equal to the confidence threshold value, adding to a list of a rule candidate group including a plurality of the rule candidates a rule including a condition part having a free itemset α set thereto and a consequent part having the one item x set thereto; and
(c) checking minimality of the rule candidate generated and outputting the rule candidate to an output apparatus when the rule candidate is determined to be minimal.

7. The rule discovery method according to claim 6 , comprising:
sorting the list of the rule candidate group including the generated rule candidates in an ascending order of sizes of the rule candidates;
sequentially extracting a minimal one or more of the rule candidates from a head of the list and outputting the extracted minimal one or more of the rule candidates to the output apparatus; and
removing, from the list, one or more of the remaining rule candidates in the list that are redundant with respect to the output minimal one or more of the rule candidates.

8. A non-transitory computer readable recording medium storing a program to cause a computer to execute the processing including:
(a) reading a database to generate a free itemset that includes a set of items of attribute-value pairs in the database, and that has a frequency in the database greater than or equal to a predetermined threshold value set in advance, and storing the generated free itemset in a storage unit;
(b) generating a rule candidate that includes a condition part having the generated free itemset set thereto and a consequent part having an item that does not share an attribute with the free itemset set thereto and that has a confidence greater than or equal to a confidence threshold value set in advance, and storing the generated rule candidate in a storage unit, when a ratio of a frequency of the itemset obtained by adding one item x to a free itemset α to a frequency of the free itemset α is greater than or equal to the confidence threshold value, adding to a list of a rule candidate group including a plurality of the rule candidates a rule including a condition part having a free itemset α set thereto and a consequent part having the one item x set thereto; and
(c) checking minimality of each of the generated rule candidates and outputting the rule candidate to an output apparatus when the rule candidate is determined to be minimal.

Assignees

• Nec Corp

Inventors

• Nakayama Hiroki

Classifications

• G06N3/043

  based on fuzzy logic, fuzzy membership or fuzzy inference, e.g. adaptive neuro-fuzzy inference systems [ANFIS] · CPC title

• G06N5/025 Primary

  Extracting rules from data · CPC title

• G06F17/30943

  Physics · mapped topic

• G06N3/004

  Artificial life, i.e. computing arrangements simulating life · CPC title

• G06Q30/02

  Marketing; Price estimation or determination; Fundraising · CPC title