Interactive mining of most interesting rules with population constraints

• US 6,651,048 B1
• Filed: 10/22/1999
• Issued: 11/18/2003
• Est. Priority Date: 10/22/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bayardo, Roberto J., Agrawal, Rakesh
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/422,657
• Time in Patent Office: 1,488 Days
• Field of Search: 707/1-10, 707/102, 707/104, 706/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and structure for identifying database association rules includes mining first database association rules, the first database association rules having ratings with respect to a plurality of metrics and population constraints, selecting second database association rules from the first database association rules, each of the second database association rules having a highest rating with respect to a different metric of the metrics, and interactively changing the metrics and repeating the selecting to identify most important ones of the databases association rules for a given set of metrics.

Claims

1. A method of mining most interesting rules from a database comprising:

generating a set of maximally general and maximally predictive rules from said database, wherein said maximally general and maximally predictive rules exist at upper and lower support-confidence borders of said database association rules;

specifying metrics and population constraints to a query engine; and

selecting most interesting rules from said set of maximally general and maximally predictive rules based on said metrics.

2. The method in claim 1, wherein said generating produces a partial order of said database association rules.

3. The method in claim 1, wherein said generating identifies said upper and lower support-confidence borders of said database association rules.

4. The method in claim 3, wherein said set of maximally general and maximally predictive rules fall within said upper and lower support-confidence borders and only rules at said upper and lower support-confidence borders comprise optimal rules.

5. The method in claim 1, wherein said set of maximally general and maximally predictive rules comprise a plurality of optimal rules from different equivalence classes.

6. The process in claim 1, wherein said set of maximally general and maximally predictive rules comply with a fixed consequent.

7. The process in claim 1, wherein said metrics comprise at least one of confidence, support gain, variance, chi-squared value, entropy gain, gini, laplace, lift, and conviction.

8. A process for identifying database association rules comprising:

mining first database association rules, said first database association rules having ratings with respect to a plurality of metrics and population constraints;

selecting second database association rules from said first database association rules, each of said second database association rules having a highest rating with respect to a different metric of said metrics; and

interactively changing said metrics and said population constraints and repeating said selecting to identify most important ones of said databases association rules for a given set of metrics.

9. The process in claim 8, wherein said mining produces a partial order of said database association rules.

10. The process in claim 8, wherein said mining identifies upper and lower support-confidence borders of said database association rules.

11. The process in claim 10, wherein said database association rules fall within said upper and lower support-confidence borders and only rules at said upper and lower support-confidence borders comprise optimal rules.

12. The process in claim 8, wherein said second database association rules comprise maximally general and maximally predictive rules from said database.

13. The process in claim 8, wherein said second database association rules comprise a plurality of optimal rules from different equivalence classes.

14. The process in claim 8, wherein said first database association rules comply with at least one consequent.

15. The process in claim 8, wherein said metrics comprise at least one of confidence, support gain, variance, chi-squared value, entropy gain, gini, laplace, lift, and conviction.

16. A system for mining optimal association rules comprising:

a mining engine mining first database association rules, said first database association rules having ratings with respect to a plurality of metrics and population constraints; and

a query engine selecting second database association rules from said first database association rules, each of said second database association rules having a highest rating with respect to a different metric of said metrics,

said query engine interactively changing said metrics and population constraints and identifying most important ones of said databases association rules for a given set of metrics.

17. The system in claim 16, wherein said query engine produces a partial order of said database association rules.

18. The system in claim 16, wherein said query engine identifies upper and lower support-confidence borders of said database association rules.

19. The system in claim 18, wherein said database association rules fall within said upper and lower support-confidence borders and only rules at said upper and lower support-confidence borders comprise optimal rules.

20. The system in claim 16,wherein said second database association rules comprise maximally general and maximally predictive rules from said database.

21. The system in claim 16, wherein said second database association rules comprise a plurality of optimal rules from different equivalence classes.

22. The system in claim 16, wherein said first database association rules comply with at least one consequent.

23. The system in claim 16, wherein said metrics comprise at least one of confidence, support gain, variance, chi-squared value, entropy gain, gini, laplace, lift, and conviction.