Association Rule Mining — Definition, Example & Constraint-Based Mining

Definition

Association rule mining searches for interesting co-occurrence relationships among items in a large transactional (or relational) database. The discovered rules have the form

$$A \Rightarrow B \quad [\text{support } s,\; \text{confidence } c]$$

where $A$ and $B$ are disjoint itemsets. Support measures how frequently the rule applies, and confidence measures how reliably $B$ appears whenever $A$ appears:

$$\text{support}(A \Rightarrow B) = P(A \cup B) = \frac{\text{no. of transactions containing } A \cup B}{\text{total transactions}}$$

$$\text{confidence}(A \Rightarrow B) = P(B \mid A) = \frac{\text{support}(A \cup B)}{\text{support}(A)}$$

Example

From a supermarket's transaction database:

TID	Items bought
1	Bread, Butter, Milk
2	Bread, Butter
3	Beer, Diaper
4	Bread, Milk
5	Butter, Milk

The rule {Bread} ⇒ {Butter}:

• $\text{support} = \frac{2}{5} = 40\%$ (Bread and Butter appear together in T1, T2)
• $\text{confidence} = \frac{2}{3} \approx 66.7\%$ (of the 3 transactions containing Bread, 2 also contain Butter)

A rule is strong if it exceeds user-specified minimum support ($\text{minsup}$) and minimum confidence ($\text{minconf}$).

Constraint-Based Association Mining

In large databases, plain Apriori/FP-growth can generate an overwhelming number of rules, many of which are uninteresting. Constraint-based mining lets the analyst push user-specified constraints into the mining process so that only rules satisfying the constraints are discovered — this both prunes the search space (better efficiency) and focuses the results to what the user wants.

Kinds of constraints:

1. Rule constraints — limit the form of the rule, e.g., only rules of the form $\text{Sugar} \Rightarrow X$ or rules with 3 or more items in the antecedent.
2. Itemset constraints — require specific items to be present or absent, e.g., only itemsets containing snacks or only itemsets that exclude expensive-items.
3. Support/confidence (interestingness) thresholds — standard minsup/minconf or other measures like lift, e.g., support ≥ 2% AND lift ≥ 1.5.
4. Aggregate constraints — conditions on aggregated values. e.g., "rules for which the average price of items in the rule exceeds $10".

Example:

"Find association rules involving at least one item from the 'Dairy' category whose support is at least 10%."

If the constraint is anti-monotone (e.g., $min(price) \ge 10$), the Apriori pruning property applies — once an itemset violates it, all supersets violate it too, so entire subtrees of the search can be pruned.

Benefit: mining on the constrained space returns far fewer but highly targeted rules, and does so much faster than mining everything and filtering afterwards. Constraint checking is usually pushed inside the candidate-generation step of Apriori or the FP-tree construction step, so only constrained-valid candidates are counted.