Constraint-based rule miners find all rules in a given dataset meeting user-specified constraints such as minimum support and confidence. We describe a new algorithm that directly exploits all user-specified constraints including minimum support, minimum confidence, and a new constraint that ensures every mined rule offers a predictive advantage over any of its simplifications. Our algorithm maintains efficiency even at low supports on data that is dense (e.g. relational data). Previous approaches such as Apriori and its variants exploit only the minimum support constraint, and as a result are ineffective on dense data due to a combinatorial explosion of "frequent itemsets". Mining rules from data is a problem that has attracted considerable interest because a rule provides a concise statement of potentially useful information that is easily understood by end users. In the database literature, the focus has been on developing association rule [1] algorithms that identify all conjunctive rules meeting user-specified constraints such as minimum support (a statement of generality) and minimum confidence (a statement of predictive ability). These algorithms were initially developed to tackle data-sets primarily from the domain of market-basket analysis, though there has been recent interest in applying these algorithms to other domains including telecommunications data analysis [14] , census data analysis [6] , and classification and predictive modeling tasks in general. Unlike data from market-basket analysis, these data-sets tend to be dense in that they have any or all of the following properties: 1 • many frequently occurring items (e.g. sex=male); • strong correlations between several items; • many items in each record. These data-sets can cause an exponential blow-up in the resource consumption of standard association rule mining algorithms including Apriori [2] and its many variants. The combinatorial explosion is a result of the fact that these algorithms effectively mine all rules that satisfy only the minimum support constraint, the number of which is exorbitant. Though other rule constraints are specifiable, they are typically enforced solely during a post-processing filter step. Our approach to mining on dense data-sets is to instead directly enforce all user-specified rule constraints during mining. For example, most association rule miners allow users to set a minimum on the predictive ability of any mined rule specified as either a minimum confidence [1] or an alternative measure such as lift [5, 8] (also known as interest [6] ) or conviction [6] . Our algorithm can exploit such minimums on predictive ability during mining for vastly improved efficiency. Even given strong minimums on support and predictive ability, the rules satisfying these constraints in a dense dataset are often too numerous to be mined efficiently or comprehended by the end user. To remedy this problem, our algorithm exploits another constraint that eliminates rules that are uninteresting because they contain conditions that do not (strongly) contribute to the predictive ability of the rule. To illustrate this useful concept, first consider the rule below: This rule has a confidence of 80%, which says that 80% of the people who purchase bread and butter also purchase the item in the consequent of the rule, which is milk. Because of its high confidence, one might be inclined to believe that this rule is an interesting finding if the goal is to, say, understand the population of likely milk buyers in order to make better stocking and discounting decisions. However, if 85% of the population under examination purchased milk, this rule is actually quite uninteresting for this purpose since it characterizes a population that is even less likely to buy milk than the average shopper. This point has motivated additional measures for identifying interesting rules including lift and conviction. Both lift and conviction represent the predictive advantage a rule offers over simply guessing based on the frequency of the consequent. But both measures still exhibit another closely related problem illustrated by the next rule. Milk (Confidence = 95%) Because the confidence of this rule (95%) is significantly higher than the frequency with which milk is purchased (85%), this rule will have lift and conviction values that could imply to the end-user that it is interesting for understanding likely milk buyers. But suppose the purchase of cereal alone implies that milk is purchased with 99% confidence. We then have that the above rule actually represents 1 Market-basket data is sometimes dense, particularly when it incorporates information culled from convenience card applications for mining rules that intermix personal attributes with items purchased. → →
Experiments show that a straightforward disk-based implementation results in excessive I/O. Dense-Miner REF applies all of minimum support, minimum confidence, and minimum improvement to constraint the search space.
Constraint-based rule mining in large, dense databases
Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337)
Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337)
Computer Science Mathematics