US5943667A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Eliminating redundancy in generation of association rules for on-line mining
Assignee: International Business Machines Corp
•
Filing: 1997-06-03
•
Granted: 1999-08-24
•
Expires: 2017-06-03
Abstract
Abstract A computer method of removing simple and strict redundant association rules generated from large collections of data. A compact set of rules is presented to an end user which is devoid of many redundancies in the discovery of data patterns. The method is directed primarily to on-line applications such as the Internet and Intranet. Given a number of large itemsets as input, simple redundancies are removed by generating all maximal ancestors, the frontier set, for each large itemset. The set of maximal ancestors share a hierarchical relationship with the large itemset from which they were derived and further satisfy an inequality whereby the ratio of respective support values is less than the reciprocal of some user defined confidence value. The resulting compact rule set is displayed to an end user at some specified level of support and confidence. The method is also able to generate the full set of rules from the compact set.
Inventors
- 👤 Charu Chandra Aggarwal
- 👤 Philip Shi-lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 12:10
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2465; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
101 words
A computer performed process for generating a compact subset of non-redundant association rules from large item sets, comprising the steps of: inputting to the computer, data including a plurality of large item sets, a minimum support level, and a minimum confidence level; and generating a frontier itemset corresponding to each large item set to remove simple redundancies of said large itemsets, a frontier itemset comprising a set of all maximal ancestors of said large item set; and pruning each set of frontier itemsets to eliminate strict redundancies; and generating a compact subset of non-redundant association rules from said pruned frontier itemsets.
Claim 2
Dependent Claim
101 words
A computer performed process for generating a compact subset of non-redundant association rules from large item sets, comprising the steps of: inputting to the computer, data including a plurality of large item sets, a minimum support level, and a minimum confidence level; and generating a frontier itemset corresponding to each large item set to remove simple redundancies of said large itemsets, a frontier itemset comprising a set of all maximal ancestors of said large item set; and pruning each set of frontier itemsets to eliminate strict redundancies; and generating a compact subset of non-redundant association rules from said pruned frontier itemsets.
Claim 3
Dependent Claim
29 words
The method of claim 1, wherein the step of generating a frontier itemset from each large item set further includes finding minimum antecedent sets contained in each large itemset.
Claim 4
Dependent Claim
51 words
The method of claim 1, wherein the step of pruning the frontier itemset from each large item set further includes generating the frontier itemsets for each child of said frontier itemset; and eliminating from said frontier itemset any itemset also contained in the frontier itemset of any child of said frontierset.
Claim 5
Dependent Claim
56 words
The method as claimed in claim 1, wherein a maximal ancestor (Y) of a large itemset (X) is defined as an itemset meeting a criteria: s(Y)/s(X)<1/c where s(Y) is a minimum support value of said itemset (Y), s(X) is a minimum support value of said large itemset (X), and c is a minimum specified confidence value.
Claim 6
Dependent Claim
63 words
The method as claimed in claim 4, wherein said maximal ancestor (Y) of a large itemset (X) is defined as an itemset meeting a criteria: s(Z)/s(X)<=1/c where s(X) is a minimum support value of said itemset (X), Z is an immediate parent of itemset Y, s(Z) is a minimum support value of said itemset (Z), and c is a minimum specified confidence value.
Claim 7
Dependent Claim
185 words
A computer performed process for determining whether an input association rule is valid from a generated set of compact rules comprising: identifying a subset of association rules from the compact set of rules, where said subset contains only those rules whose antecedents are subsets of the antecedent of said input association rule; and deleting from said compact set of rules those association rules whose antecedents are not subsets of said input association rule; and identifying from said subset of association rules a further subset of association rules containing only those rules whose consequents are supersets of the consequent of said input association rule; and deleting those association rules from said subset of association rules whose consequents are not supersets of the consequent of said input association rule; and determining whether said further subset of association rules is the empty set including; displaying a message to the user that said input association rule is invalid when said further subset is the empty set; otherwise displaying a message to the user that said input association rule is valid when said further subset is not the empty set.
Claim 8
Dependent Claim
185 words
A computer performed process for determining whether an input association rule is valid from a generated set of compact rules comprising: identifying a subset of association rules from the compact set of rules, where said subset contains only those rules whose antecedents are subsets of the antecedent of said input association rule; and deleting from said compact set of rules those association rules whose antecedents are not subsets of said input association rule; and identifying from said subset of association rules a further subset of association rules containing only those rules whose consequents are supersets of the consequent of said input association rule; and deleting those association rules from said subset of association rules whose consequents are not supersets of the consequent of said input association rule; and determining whether said further subset of association rules is the empty set including; displaying a message to the user that said input association rule is invalid when said further subset is the empty set; otherwise displaying a message to the user that said input association rule is valid when said further subset is not the empty set.
Claim 9
Dependent Claim
194 words
A computer performed process for generating all valid association rules from a compact subset of non-redundant association rules comprising: selecting an input rule from the compact subset of association rules; and calculating the union of the antecedent and consequent of said input rule; and calculating a plurality of subsets of said union where each subset is a superset of the antecedent of said input rule; and generating a plurality of rules whereby the generation of each individual rule includes; generating the antecedent of said generated rule where said antecedent comprises one of said plurality of subsets; and generating the consequent of said generated rule where said consequent comprises the difference between said union of the antecedent and consequent of said input rule and one of said subsets; and adding the generated rule to the set of all valid association rules; and deleting said input rule from the compact subset of association rules; and determining whether said compact subset of association rules is the empty set including; outputting the set of all association rules when said compact subset is the empty set otherwise selecting the next input rule from the compact subset of association rules.
Claim 10
Dependent Claim
194 words
A computer performed process for generating all valid association rules from a compact subset of non-redundant association rules comprising: selecting an input rule from the compact subset of association rules; and calculating the union of the antecedent and consequent of said input rule; and calculating a plurality of subsets of said union where each subset is a superset of the antecedent of said input rule; and generating a plurality of rules whereby the generation of each individual rule includes; generating the antecedent of said generated rule where said antecedent comprises one of said plurality of subsets; and generating the consequent of said generated rule where said consequent comprises the difference between said union of the antecedent and consequent of said input rule and one of said subsets; and adding the generated rule to the set of all valid association rules; and deleting said input rule from the compact subset of association rules; and determining whether said compact subset of association rules is the empty set including; outputting the set of all association rules when said compact subset is the empty set otherwise selecting the next input rule from the compact subset of association rules.
References Cited (Backward Citations)
US5819266A
Cited
US5764975A
Cited
US5794209A
Cited
US5842200A
Cited
US5615341A
Cited
US5727199A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-23 | 2003-02-22 | 2003-08-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-23 | 2007-02-22 | 2007-08-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-23 | 2011-02-22 | 2011-08-24 | $7700.00 | Window Closed / Lapsed |