In general – Generating Association Rules (ARs)

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 2k-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)