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.
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.