×

System and method for quickly mining association rules in databases

  • US 5,794,209 A
  • Filed: 03/31/1995
  • Issued: 08/11/1998
  • Est. Priority Date: 03/31/1995
  • Status: Expired due to Term
First Claim
Patent Images

1. A method executable by a computer having a computer program storage device readable by the computer and a program means on the program storage device and including instructions executable by the computer for performing method steps identifying association rules in itemsets in transactions which are stored in a database, each itemset characterized by one or more items, the method comprising:

  • entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value;

    concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets and discarding all candidate large itemsets whose subsets are not large itemsets;

    comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database;

    entering a candidate large itemset into a next forward set of large itemsets only when the number of times the candidate large itemset is present in the database is greater than the minimum support value;

    for at least some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database; and

    outputting an association rule when the ratio of the number of times a selected subset having a plurality of items appears in the database to the number of times the associated itemset appears in the database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×