Association analysis and Apriori pruning

Association analysis

Association analysis (association rule mining) discovers interesting relations, in the form of rules X → Y, among items in large transaction data. Example: {bread, butter} → {milk} [support 5%, confidence 80%] means 80% of customers who buy bread and butter also buy milk.

• Support(X → Y) = (transactions containing X ∪ Y)/(total transactions)
• Confidence(X → Y) = support(X ∪ Y)/support(X)

The task has two steps: (1) find all frequent itemsets (support ≥ minsup), (2) generate strong rules from them (confidence ≥ minconf). Step 1 is the expensive one, as N items give 2ᴺ − 1 candidate itemsets.

Apriori principle

If an itemset is frequent, then all of its subsets must also be frequent.

Equivalently, if an itemset is infrequent, all its supersets are infrequent. This follows from the anti-monotone property of support: s(X) ≥ s(Y) whenever X ⊆ Y.

Pruning

If {A, B} is infrequent, then {A, B, C}, {A, B, D}, {A, B, C, D} … are not counted at all. During candidate generation, any (k+1)-itemset that has a k-subset not in L_k is removed before the database is scanned. This greatly reduces the search space.

Apriori algorithm

L1 = frequent 1-itemsets                  (scan database)
for (k = 2; L(k-1) not empty; k++):
    Ck = join L(k-1) with itself          (join step)
    remove from Ck every candidate having an
        infrequent (k-1)-subset           (prune step)
    scan database; count support of each candidate in Ck
    Lk = candidates in Ck with support >= minsup
answer = union of all Lk

Join step: two frequent (k−1)-itemsets that share the first (k−2) items are joined: {A, B} and {A, C} give {A, B, C}.

Small example (minsup = 2 transactions)

T: {A, C, D}, {B, C, E}, {A, B, C, E}, {B, E}.

• L₁ = {A:2, B:3, C:3, E:3}; D (1) is dropped.
• C₂ counts: AB 1, AC 2, AE 1, BC 2, BE 3, CE 2 → L₂ = {AC, BC, BE, CE}.
• Joining BC and BE gives {B, C, E}; all its 2-subsets are in L₂, so it is kept; count = 2 → L₃ = {BCE}. {A, B, C} is never counted: the join does not produce it, and it would be pruned anyway because {A, B} is infrequent.