Method and apparatus for mining association rules having item constraints

Claim 3

The method recited in claim 1, the method further comprising: determining a support value for subsets of large itemsets included in the database where the subsets do not satisfy the defined constraints; determining confidence values using large itemsets which satisfy the defined constraints and itemsets which do not satisfy the defined constraints, where a confidence value comprises a number of times an itemset appears in the database in relation to a number of times an associated itemset appears in the database; and outputting association rules that satisfy a minimum confidence value.

Claim 4

The method recited in claim 1, the method further comprising: generating a set of selected items from the database such that any itemset that satisfies the defined constraints contains at least one selected item; and using only itemsets that contain at least one selected item to find association rules.

Claim 5

A method according to claim 1, wherein the defined constraints involve more than one item of a mining input expression comprising a boolean expression.

Claim 6

A method according to claim 1, wherein the defined constraints are represented by a mining input expression comprising a boolean expression having more than one item.

Claim 9

The method recited in claim 6, further comprising: forming a second itemset by concatenating the large itemset with a set of large items in the database in accordance with a predetermined concatenation regime, where an item is large if the support value of the item is greater than a minimum support value; joining any two elements of the second itemset that have at least one item in common; generating a set of candidate itemsets including itemsets from the second itemset and joined elements; and using the set of candidate itemsets to output the association rules.

Claim 10

The method recited in claim 6, further comprising: determining whether sets contained in the large itemsets satisfy the predefined constraints; generating a set of candidate itemsets including large itemsets which satisfy the predefined constraints; and using the set of candidate itemsets to output the association rules.

Claim 11

The method recited in claim 8, the outputting association rules including pruning non-interesting association rules.

Claim 12

The method recited in claim 6, further comprising: forming a second itemset by concatenating the large itemsets with a set of large items in accordance with a predetermined concatenation regime to generate a set of candidate itemsets, where an item is large if the support value of the item is greater than a minimum support value; arranging the candidate itemsets so that each item within an itemset which is also contained in the set of selected items precedes any item not in the set of selected items; and using the set of candidate itemsets to output the association rules.

Claim 13

The method recited in claim 10, the outputting association rules including pruning non-interesting association rules.

Claim 14

The method recited in claim 6, the generating a selected set of items including pruning non-interesting items from the set.

Claim 19

The method recited in claim 14, further comprising: forming a second itemset by concatenating the large itemsets with a set of large items in accordance with a predetermined concatenation regime, where an item is large if the support value of the item is greater than a minimum support value; joining any two elements of the second itemset that have at least one item in common; generating a set of candidate itemsets from the second itemset and the joined elements; and using the set of candidate itemsets to output the association rules.

Claim 20

The method recited in claim 14, of further comprising: determining whether sets contained in the large itemsets satisfy the predefined constraints; generating a set of candidate itemsets including large itemsets which satisfy the predefined constraints; and using the set of candidate itemsets to output the association rules.

Claim 21

The method recited in claim 16, the outputting association rules including pruning non-interesting association rules.

Claim 22

The method recited in claim 14, further comprising: forming a second itemset by concatenating the large itemsets with a set of large items in accordance with a predetermined concatenation regime to generate a set of candidate itemsets, where an item is large if the support value of the item is greater than a minimum support value; arranging the candidate itemsets so that each item within an itemset which is also contained in the set of selected items precedes any item not in the set of selected items; and using the set of candidate itemsets to output the association rules.

Claim 23

The method recited in claim 14, the outputting association rules including pruning non-interesting association rules.

Claim 28

An article of manufacture tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for discovering association rules using item constraints, the method comprising: generating a set of selected items from a database based on predefined constraints, the predefined constraints involving one or more items of a mining input expression; determining a support value for an itemset based upon the number of times the itemset appears in the database; entering the itemset into a set of large itemsets if the support value of the itemset is greater than a minimum support value and the itemset contains at least one of the selected items; and outputting an association rule when the number of times the entered itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 29

An article of manufacture tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for discovering association rules using item constraints, the method comprising: generating a set of selected items from a database based on predefined constraints, the predefined constraints involving one or more items of a mining input expression; determining a support value for an itemset based upon the number of times the itemset appears in the database; entering the itemset into a set of large itemsets if the support value of the itemset is greater than a minimum support value and the itemset contains at least one of the selected items; and outputting an association rule when the number of times the entered itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 30

The article of manufacture recited in claim 23, the method further comprising: forming a second itemset by concatenating the large itemset with a set of large items in the database in accordance with a predetermined concatenation regime, where an item is large if the support value of the item is greater than a minimum support value; joining any two elements of the second itemset that have at least one item in common; generating a set of candidate itemsets including itemsets from the second itemset and joined elements; and using the set of candidate itemsets to output the association rules.

Claim 31

The article of manufacture recited in claim 23, the method further comprising: determining whether sets contained in the large itemsets satisfy the predetermined constraints; generating a set of candidate itemsets including large itemsets which satisfy the predefined constraints; and using the set of candidate itemsets to output the association rules.

Claim 32

The article of manufacture recited in claim 25, the method further comprising outputting association rules including pruning of non-interesting association rules.

Claim 33

The article of manufacture recited in claim 23, the method further comprising: forming a second itemset by concatenating the large itemsets with a set of large items in accordance with a predetermined concatenation regime to generate a set of candidate itemsets, where an item is large if the support value of the item is greater than a minimum support value; arranging the candidate itemsets so that each item within an itemset which is also contained in the set of selected items precedes any item not in the set of selected items; and using the set of candidate itemsets to output the association rules.

Claim 34

The article of manufacture recited in claim 27, the method further comprising outputting association rules including pruning non-interesting association rules.

Claim 35

The article of manufacture recited in claim 23, the method further comprising the generating a selected set of items including pruning non-interesting items from the set.

Claim 36

An article of manufacture tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for discovering rules using item constraints, the method comprising: determining a set of large items, where an item is large if the support value of the item is greater than a minimum support value; generating a set of large itemsets where the large itemsets satisfy a predetermined constraint, the predetermined constraint involving one or more items of a mining input expression; forming a second itemset by concatenating the large itemsets with the set of large items in accordance with a predetermined concatenation regime; dropping any set of large items from the second itemset that does not satisfy the predetermined constraint; dropping any set of large items in the second itemset that satisfies the predetermined constraint but does not have a support value greater than the minimum support value; adding an itemset to the second itemset if all non-negated elements of the second itemset are large; and outputting an association rule when the number of times an itemset in the second itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 37

An article of manufacture tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for discovering rules using item constraints, the method comprising: determining a set of large items, where an item is large if the support value of the item is greater than a minimum support value; generating a set of large itemsets where the large itemsets satisfy a predetermined constraint, the predetermined constraint involving one or more items of a mining input expression; forming a second itemset by concatenating the large itemsets with the set of large items in accordance with a predetermined concatenation regime; dropping any set of large items from the second itemset that does not satisfy the predetermined constraint; dropping any set of large items in the second itemset that satisfies the predetermined constraint but does not have a support value greater than the minimum support value; adding an itemset to the second itemset if all non-negated elements of the second itemset are large; and outputting an association rule when the number of times an itemset in the second itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 38

A digital processing machine used to discover trends in a database, the device comprising: a database; a digital processing apparatus, the digital processing apparatus configured to receive data and commands from a signal-bearing medium tangibly embodying a program of machine-readable instructions executable by the digital processing apparatus and used to perform a method for discovering trends in a database, said method comprising: generating a set of selected items from a database based on predefined constraints, the predefined constraints involving one or more items of a mining input expression; determining a support value for an itemset based upon the number of times the itemset appears in the database; entering the itemset into a set of large itemsets if the support value of the itemset is greater than a minimum support value and the itemset contains at least one of the selected items; and outputting an association rule when the number of times the entered itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 39

A digital processing machine used to discover trends in a database, the device comprising: a database; a digital processing apparatus, the digital processing apparatus configured to receive data and commands from a signal-bearing medium tangibly embodying a program of machine-readable instructions executable by the digital processing apparatus and used to perform a method for discovering trends in a database, said method comprising: generating a set of selected items from a database based on predefined constraints, the predefined constraints involving one or more items of a mining input expression; determining a support value for an itemset based upon the number of times the itemset appears in the database; entering the itemset into a set of large itemsets if the support value of the itemset is greater than a minimum support value and the itemset contains at least one of the selected items; and outputting an association rule when the number of times the entered itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 40

The machine recited in claim 31, where the method for discovering trends in a database further comprises: forming a second itemset by concatenating the large itemset with a set of large items in the database in accordance with a predetermined concatenation regime, where an item is large if the support value of the item is greater than a minimum support value; joining any two elements of the second itemset that have at least one item in common; generating a set of candidate itemsets including itemsets from the second itemset and joined elements; and using the set of candidate itemsets to output the association rules.

Claim 41

The machine recited in claim 31, where the method for discovering trends in a database further comprises: determining whether sets contained in the large itemsets satisfy the predefined constraints; generating a set of candidate itemsets including large itemsets which satisfy the predefined constraints; and using the set of candidate itemsets to output the association rules.

Claim 42

The machine recited in claim 33, where the generating a selected set of items includes pruning non-interesting items from the set.

Claim 43

The machine recited in claim 31, where the method for discovering trends in a database further comprises: forming a second itemset by concatenating the large itemsets with a set of large items in accordance with a predetermined concatenation regime to generate a set of candidate itemsets, where an item is large if the support value of the item is greater than a minimum support value; arranging the candidate itemsets so that each item within an itemset which is also contained in the set of selected items precedes any item not in the set of selected items; and using the set of candidate itemsets to output the association rules.

Claim 44

The machine recited in claim 35, where the generating a selected set of items includes pruning non-interesting items from the set.

Claim 45

The machine recited in claim 31, where the generating a selected set of items includes pruning non-interesting items from the set.

Claim 46

A digital processing machine used to discover trends in a database, the device comprising: determining a set of large items, where an item is large if the support value of the item is greater than a minimum support value; generating a set of large itemsets where the large itemsets satisfy a predetermined constraint, the predetermined constraint represented by a boolean expression including items; forming a second itemset by concatenating the large itemsets with the set of large items in accordance with a predetermined concatenation regime; dropping any set of large items from the second itemset that does not satisfy the predetermined constraint; dropping any set of large items in the second itemset that satisfies the predetermined constraint but does not have a support value greater than the minimum support value; adding an itemset to the second itemset if all non-negated elements of the second itemset are large; and outputting an association rule when the number of times an itemset in the second itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.

Claim 47

A digital processing machine used to discover trends in a database, the device comprising: determining a set of large items, where an item is large if the support value of the item is greater than a minimum support value; generating a set of large itemsets where the large itemsets satisfy a predetermined constraint, the predetermined constraint represented by a boolean expression including items; forming a second itemset by concatenating the large itemsets with the set of large items in accordance with a predetermined concatenation regime; dropping any set of large items from the second itemset that does not satisfy the predetermined constraint; dropping any set of large items in the second itemset that satisfies the predetermined constraint but does not have a support value greater than the minimum support value; adding an itemset to the second itemset if all non-negated elements of the second itemset are large; and outputting an association rule when the number of times an itemset in the second itemset appears in the database bears a predetermined relationship to a number of times an associated itemset appears in the database and thereby satisfies a minimum confidence constraint.