Apriori Algorithm — Pseudocode & Key Terms

Pseudocode

Algorithm Apriori(D, min_sup):
    Input:  D = transaction database, min_sup = minimum support threshold
    Output: L = all frequent itemsets in D

    L1 = {frequent 1-itemsets found by scanning D}
    k = 2
    while (L(k-1) is not empty):
        Ck = apriori_gen(L(k-1))          // candidate generation
        for each transaction t in D:
            Ct = subset(Ck, t)             // candidates contained in t
            for each candidate c in Ct:
                c.count++
        Lk = { c in Ck | c.count >= min_sup }
        L = L ∪ Lk
        k = k + 1
    return L

Function apriori_gen(L(k-1)):
    Ck = ∅
    // Join step: join L(k-1) with itself
    for each pair (p, q) in L(k-1) x L(k-1):
        if p and q share the first (k-2) items:
            c = p ∪ {last item of q}
            // Prune step: remove candidates with an infrequent subset
            if all (k-1)-subsets of c are in L(k-1):
                Ck = Ck ∪ {c}
    return Ck

Explanation

1. First pass: count individual items to find frequent 1-itemsets (L1).
2. Iterative passes: for k = 2, 3, ..., generate candidate k-itemsets (Ck) by joining frequent (k-1)-itemsets that share a common (k-2)-item prefix.
3. Prune step: discard any candidate whose any (k-1)-subset is not frequent (using the apriori property: all subsets of a frequent itemset must be frequent).
4. Count & filter: scan the database, count support for surviving candidates, keep only those meeting min_sup → Lk.
5. Repeat until no new frequent itemsets are found.

Key Terms

(i) Support Count
The number of transactions in the database that contain a given itemset:
$$support\_count(X) = |\{t \in D : X \subseteq t\}|$$
Support (as a fraction) = support_count / |D|. It measures how frequently an itemset appears.

(ii) Confidence
For a rule $A \Rightarrow B$, confidence measures how reliably B follows when A is present:
$$confidence(A \Rightarrow B) = \frac{support\_count(A \cup B)}{support\_count(A)}$$
It is the conditional probability $P(B \mid A)$ — the fraction of transactions containing A that also contain B.

Support: "How often does this itemset occur overall?"
Confidence: "Given the antecedent occurred, how often does the consequent follow?"