Let’s consider how to extract Association /rules (ARs) efficiently from a given Frequent Itemset (FI).

Each frequent k-itemset, Y, can produce up to 2^{k-2} ARs, ignoring ARs that have empty antecedents or consequents (Φ → Y or Y → Φ). An AR can be extracted by partitioning the FI Y into two non-empty subsets, X and Y – X, such that X → Y – X satisfies the confidence threshold. Note that all such rules must have already met the support threshold because they are generated from an FI.

## Example

Let X = {1, 2, 3} be an FI. There are six candidate ARs that can be generated from X: {1, 2} → {3}, {1. 3} → {2}, {2, 3} → {1}, {1} → {2, 3}, {2} → {1, 3}, {3} → {1, 2}. As each of their support is identical to the support for X, the rules must satisfy the **support threshold**.

Computing the confidence of an AR does not require additional scans of the **transaction dataset**. Consider the rule {1, 2} → {3}, which is generated from the FI X = {1, 2, 3}. The **confidence** for this AR is σ({1, 2, 3}/σ({1, 2}). Because {1, 2, 3} is frequent, the **anti-monotone** property of support ensures that {1, 2} must be frequent, too. Since the support counts for both FIs were already found during the FI generation, there is no need to read the entire dataset again.

## Confidence-based pruning

Unlike the support measure, confidence does not have a monotone property. For example,the confidence for X → Y can be larger, smaller, or equal to the confidence for another rule X’ → Y’, where X’ ⊆ X and Y’ ⊆ Y. Nevertheless, if we compare rules generated from the same frequent itemset Y, the following theorem holds for the confidence measure:

**Theorem 1.** *If a rule X → Y – X does not satisfy the confidence threshold, then any rule X’ → Y – X’, where X’ is a subset of X, must not satisfy the confidence threshold as well.*

To prove this theorem, consider the following two rules: X’ → Y – X’ and X → Y – X, where X’ ⊂ X. The confidence of the rules are σ(Y)/σ(X’) and σ(Y)/σ(X), respectively. Since X’ is a subset of X, σ(X’)/σ(X). Therefore, the former rule cannot have a higher confidence than the latter rule.

Previous: In general – Generating Association Rules (ARs)

Next: Apriori algorithm – Generating and pruning candidate FIs or Apriori algorithm – Generating Association Rules (ARs)