US5615341A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for mining generalized association rules in databases
Assignee: SAP SE
•
Filing: 1995-05-08
•
Granted: 1997-03-25
•
Expires: 2015-05-08
Abstract
Abstract A system and method for discovering consumer purchasing tendencies includes a computer-implemented program which identifies consumer transaction itemsets that are stored in a database and which appear in the database a user-defined minimum number of times, referred to as minimum support. The itemsets contain items that are characterized by a hierarchical taxonomy. Then, the system discovers association rules, potentially across different levels of the taxonomy, in the itemsets by comparing the number of times each of the large itemsets appears in the database to the number of times particular subsets of the itemset appear in the database. When the relationship exceeds a predetermined minimum confidence value, the system outputs a generalized association rule which is representative of purchasing tendencies of consumers. The set of generalized association rules can be pruned of uninteresting rules, i.e., association rules which do not occur at a frequency that is significantly different than what is expected based upon the frequency of occurrence of the rule's ancestors.
Inventors
- 👤 Rakesh Agrawal
- 👤 Ramakrishnan Srikant
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 06:45
CPC Classifications
G; G06; G06Q; G06Q30/00; G06Q30/02; G06Q30/0201; G06Q30/0202; G06F; G06F2216/00; G06F2216/03
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
171 words
A computer program device comprising: a computer program storage device readable by a digital processing apparatus; and a program means on the program storage device and including instructions executable by the digital processing apparatus for performing method steps for identifying association rules in itemsets with a hierarchical taxonomy on items of the itemsets, the taxonomy defining descendant and ancestor relationships between the items, the method steps comprising: entering an itemset into a set of large itemsets when the number of times the itemset is present in a database of transactions establishes a support value that exceeds a predefined minimum support value; for at least some of the itemsets in the set of large itemsets, determining the number of times selected subsets of the itemsets appear in transactions in the database; and (d) outputting an association rule when the number of times a selected subset appears in the database bears a predetermined relationship to the number of times the associated itemset appears in the database and thereby satisfies a minimum confidence constraint.
Claim 2
Dependent Claim
171 words
A computer program device comprising: a computer program storage device readable by a digital processing apparatus; and a program means on the program storage device and including instructions executable by the digital processing apparatus for performing method steps for identifying association rules in itemsets with a hierarchical taxonomy on items of the itemsets, the taxonomy defining descendant and ancestor relationships between the items, the method steps comprising: entering an itemset into a set of large itemsets when the number of times the itemset is present in a database of transactions establishes a support value that exceeds a predefined minimum support value; for at least some of the itemsets in the set of large itemsets, determining the number of times selected subsets of the itemsets appear in transactions in the database; and (d) outputting an association rule when the number of times a selected subset appears in the database bears a predetermined relationship to the number of times the associated itemset appears in the database and thereby satisfies a minimum confidence constraint.
Claim 3
Dependent Claim
116 words
The computer program device of claim 1, further comprising the steps of: 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: and 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.
Claim 4
Dependent Claim
37 words
The computer program device of claim 2, wherein the taxonomy is a directed acyclic graph (DAG) taxonomy, and at least some of the itemsets contain items that are descendant items and ancestor items in the DAG taxonomy.
Claim 5
Dependent Claim
100 words
The computer program device of claim 3, wherein ancestors of an item are entered into transactions that include the item only when the ancestor appears in one of the itemsets in the next set of candidate large itemsets, and the method further comprises the steps of: accessing the DAG taxonomy to predetermine the ancestors of each item prior to entering the ancestors into the set of large itemsets; and when an itemset in the next set of candidate large itemsets contains an item and an ancestor of the item deleting the itemset from the next set of candidate large itemsets.
Claim 6
Dependent Claim
46 words
The computer program device of claim 4, further comprising the steps of entering ancestors of an item into transactions that include the item and deleting duplicate item entries from the transactions, prior to determining the number of times the associated itemset is present in the database.
Claim 7
Dependent Claim
64 words
The computer program device of claim 4, wherein the taxonomy is derived on the itemsets and is characterized by a hierarchical order of levels, the levels ranging from highest level to lowest level successively represented by integers 0 through n, and itemsets containing items at level 0 are accessed for entry into the set of large itemsets before itemsets containing items at other levels.
Claim 8
Dependent Claim
69 words
The computer program device of claim 6, wherein an itemset at level 1 is deleted if the itemset is a descendant of an ancestor itemset in level 0 when the number of times the ancestor itemset is present in the database does not exceed the predefined minimum support value, the deleting step being performed before itemsets at level 1 are accessed for entry into the set of large itemsets.
Claim 9
Dependent Claim
96 words
The computer program device of claim 4, wherein the taxonomy is characterized by a hierarchical order of levels, the levels ranging from highest level to lowest level successively represented by integers 0 through n, the method further comprising the steps of: accessing a selected sample portion of the database to estimate candidate large itemsets; entering itemsets estimated to be large into the next set of candidate large itemsets: and entering itemsets not estimated to be large but having ancestor itemsets all of which are estimated to be large into the next set of candidate large itemsets.
Claim 10
Dependent Claim
44 words
The computer program device of claim 8, further comprising the step of determining the number of times descendant itemsets of an itemset that was not estimated to be large are present in the database when the next set of candidate large itemsets is counted.
Claim 11
Dependent Claim
64 words
The computer program storage device of claim 1, further comprising the steps of: determining expected confidence and support values for an association rule based upon the confidence and support of an ancestor of the association rule; and identifying the association rule as interesting when the confidence and support values of the association rule exceeds the expected confidence and support values by a predetermined factor.
Claim 12
Dependent Claim
206 words
A computer program product for use with a computer system, a central processing unit and means coupled to the central processing unit for storing a database to identify association rules in itemsets of transactions which are stored in the database, the itemsets being characterized by items in a hierarchical taxonomy, comprising: a data storage device including a computer usable medium having computer readable program means for identifying association rules in itemsets having items anywhere in the hierarchy of the taxonomy, the computer usable code means having: computer readable code means for accessing an itemset; computer readable code means for entering the 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: computer readable code means for determining for at least some of the itemsets in the set of large itemsets, the number of times selected subsets of the itemsets appear in transactions in the database: and computer readable code means for outputting an association rule when the number of times a selected subset appears in the database bears a predetermined minimum confidence relationship to the number of times the associated itemset appears in the database, thereby satisfying a minimum confidence constraint.
Claim 13
Dependent Claim
206 words
A computer program product for use with a computer system, a central processing unit and means coupled to the central processing unit for storing a database to identify association rules in itemsets of transactions which are stored in the database, the itemsets being characterized by items in a hierarchical taxonomy, comprising: a data storage device including a computer usable medium having computer readable program means for identifying association rules in itemsets having items anywhere in the hierarchy of the taxonomy, the computer usable code means having: computer readable code means for accessing an itemset; computer readable code means for entering the 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: computer readable code means for determining for at least some of the itemsets in the set of large itemsets, the number of times selected subsets of the itemsets appear in transactions in the database: and computer readable code means for outputting an association rule when the number of times a selected subset appears in the database bears a predetermined minimum confidence relationship to the number of times the associated itemset appears in the database, thereby satisfying a minimum confidence constraint.
Claim 14
Dependent Claim
37 words
The computer program product of claim 11, wherein the taxonomy is a directed acyclic graph (DAG) taxonomy, and at least some of the itemsets contain items that are descendant items or ancestor items in the DAG taxonomy.
Claim 15
Dependent Claim
109 words
The computer program product of claim 12, wherein ancestors of an item are entered into transactions that include the item only when the ancestor appears in one of the itemsets in the next set of candidate large itemsets, and the computer program product further comprises: computer readable code means for accessing the DAG taxonomy to predetermine the ancestors of each item prior to entering the ancestors into the set of large itemsets; and computer readable code means for deleting, when an itemset in the next set of candidate large itemsets contains an item and an ancestor of the item, the itemset from the next set of candidate large itemsets.
Claim 16
Dependent Claim
49 words
The computer program product of claim 13, further comprising computer readable code means for entering ancestors of an item into a transaction that includes the item and deleting duplicate item entries from the transaction, prior to determining the number of times the associated itemset is present in the database.
Claim 17
Dependent Claim
65 words
The computer program product of claim 13, wherein the taxonomy derived on the candidate itemsets is characterized by a hierarchical order of levels, the levels ranging from highest level to lowest level successively represented by integers 0 through n, and the computer readable code means accesses itemsets at level 0 for entry into the set of large itemsets before itemsets at other levels are accessed.
Claim 18
Dependent Claim
68 words
The computer program product of claim 15, wherein the computer readable code means deletes an itemset at level 1 if the itemset is a descendant of an ancestor itemset in level 0. When the number of times the ancestor itemset is present in the database does not exceed the predefined minimum support value, before itemsets at level 1 are accessed for entry into the set of large itemsets.
Claim 19
Dependent Claim
108 words
The computer program product of claim 13, wherein the taxonomy is characterized by a hierarchical order of levels, the levels ranging from highest level to lowest level successively represented by integers 0 through n, and the computer program product further comprises: computer readable code means for accessing a selected sample portion of the database to estimate candidate large itemsets; computer readable code means for entering itemsets estimated to be large into the next set of candidate large itemsets; and computer readable code means for entering itemsets not estimated to be large but having all ancestor itemsets estimated to be large into the next set of candidate large itemsets.
Claim 20
Dependent Claim
46 words
The computer program product of claim 17, further comprising computer readable code means for determining the number of times descendant itemsets of an itemset that was not estimated to be large are present in the database when the next set of candidate large itemsets is counted.
Claim 21
Dependent Claim
71 words
The computer program storage device of claim 11, further comprising: computer readable code means for determining expected confidence and support values for an association rule based upon the confidence and support of an ancestor of the association rule; and computer readable code means for identifying the association rule as interesting when the confidence and support values of the association rule exceeds the expected confidence and support values by a predetermined factor.
Claim 22
Dependent Claim
120 words
A program storage device readable by a digital processing apparatus and tangibly embodying a program of instructions executable by the digital processing apparatus to perform method steps for identifying generalized association rules of itemsets in transactions stored in a database and having more than one item, the items being characterized by a taxonomic structure, so as to discover customer purchasing tendencies, the method steps comprising: identifying as large itemsets those itemsets having items located anywhere in the taxonomic structure and recurring with at least a user-defined minimum support; discovering association rules between the large itemsets and subsets thereof when the subset recurrence bears a predetermined relationship to itemset recurrence; and outputting the association rules as representative of customer purchasing tendencies.
Claim 23
Dependent Claim
120 words
A program storage device readable by a digital processing apparatus and tangibly embodying a program of instructions executable by the digital processing apparatus to perform method steps for identifying generalized association rules of itemsets in transactions stored in a database and having more than one item, the items being characterized by a taxonomic structure, so as to discover customer purchasing tendencies, the method steps comprising: identifying as large itemsets those itemsets having items located anywhere in the taxonomic structure and recurring with at least a user-defined minimum support; discovering association rules between the large itemsets and subsets thereof when the subset recurrence bears a predetermined relationship to itemset recurrence; and outputting the association rules as representative of customer purchasing tendencies.
Claim 24
Dependent Claim
112 words
The program storage device of claim 20, comprising the step of generating a next set of candidate large itemsets, wherein ancestors of an item are entered into at least one transaction that includes the item only when the ancestor appears in one of the itemsets in the next set of candidate large itemsets, and the method steps further comprise: accessing the taxonomic structure to predetermine ancestors of each item prior to entering the ancestors into the set of large itemsets; and when an itemset in the next set of candidate large itemsets contains an item and an ancestor of the item, deleting the itemset from the next set of candidate large itemsets.
Claim 25
Dependent Claim
63 words
The program storage device of claim 21, further comprising the steps of: determining expected confidence and support values for an association rule based upon the confidence and support of an ancestor of the association rule; and identifying the association rule as interesting when the confidence and support values of the association rule exceeds the expected confidence and support values by a predetermined factor.
Claim 26
Dependent Claim
115 words
A database mining system for discovering association rules in itemsets having items stored in a taxonomically structured database, comprising: a large itemset generator for generating large itemsets when the itemsets have a support in a transaction database at least equal to a user-defined minimum support value; an association rule generator for receiving the large itemsets and outputting an association rule when an itemset bears a confidence relationship to at least one of its subsets equal to or greater than a predetermined confidence relationship; and a rule pruner for identifying an association rule as interesting when the support and the confidence relationship respectively exceed an expected support and an expected confidence relationship by a preselected factor.
Claim 27
Dependent Claim
115 words
A database mining system for discovering association rules in itemsets having items stored in a taxonomically structured database, comprising: a large itemset generator for generating large itemsets when the itemsets have a support in a transaction database at least equal to a user-defined minimum support value; an association rule generator for receiving the large itemsets and outputting an association rule when an itemset bears a confidence relationship to at least one of its subsets equal to or greater than a predetermined confidence relationship; and a rule pruner for identifying an association rule as interesting when the support and the confidence relationship respectively exceed an expected support and an expected confidence relationship by a preselected factor.
Claim 28
Dependent Claim
150 words
A computer-based system for discovering purchasing tendencies of consumers by identifying association rules between itemsets of transactions and subsets of the itemsets, the subsets including one or more items, comprising: a multi-level taxonomic structure accessible by the computer for storing the items in a hierarchical relationship; a large itemset generator accessing the taxonomic structure and the transactions for determining a first number of times an itemset appears in the transactions and for designating the itemset as a large itemset when the first number of times exceeds a minimum support value; and an association rule discoverer accessing the large itemset generator for determining a second number of times at least one subset of an itemset appears in the transactions, the association rule discoverer outputting an association rule representative of purchasing tendencies of consumers when the first number of times bears a predetermined minimum confidence relationship to the second number of times.
Claim 29
Dependent Claim
150 words
A computer-based system for discovering purchasing tendencies of consumers by identifying association rules between itemsets of transactions and subsets of the itemsets, the subsets including one or more items, comprising: a multi-level taxonomic structure accessible by the computer for storing the items in a hierarchical relationship; a large itemset generator accessing the taxonomic structure and the transactions for determining a first number of times an itemset appears in the transactions and for designating the itemset as a large itemset when the first number of times exceeds a minimum support value; and an association rule discoverer accessing the large itemset generator for determining a second number of times at least one subset of an itemset appears in the transactions, the association rule discoverer outputting an association rule representative of purchasing tendencies of consumers when the first number of times bears a predetermined minimum confidence relationship to the second number of times.
References Cited (Backward Citations)
US5173851A
Cited
US4949256A
Cited
US5430644A
Cited
US5056019A
Cited
US5515270A
Cited
US5369571A
Cited
US5459306A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-24 | 2000-09-23 | 2001-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-24 | 2004-09-23 | 2005-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-24 | 2008-09-23 | 2009-03-25 | $7700.00 | Window Closed / Lapsed |