MINING ASSOCIATION RULES

摘要

Discovering probabilistic association rules between items in large databases is becoming an important process as the size and availability of the data increase. Today, the success of mining association rules technology is usually attributed to the a-priori optimization idea. A drawback of a-priori is the implicit assumption that all items have similar prior probabilities, which makes it sensitive to the support threshold and, for a specific threshold, it may miss some rules of higher confidence than the output ones. To catch these rules, a lower support level must be used which in turn makes the a-priori optimization less useful. To avoid these problems, we propose a new technique based on the relative support between items and the notion of association graph that captures the association relationships between the items. We present a necessary and sufficient condition for the existence of a rule with specific confidence. The necessary part of this condition is used to generate candidate itemsets without counting them from the database. Since the degree of any node in the association graph is bounded, generating the maximal itemsets is efficient. We provide a recursive algorithm to generate all maximal itemsets. The new method is suitable for interactive mining.