Apriori Algorithm Theory Guide

Rules & Common Mistakes

• Exam Trap: $X\rightarrow Y$ is NOT the Same as $Y\rightarrow X$

  Confidence is strictly directional. The confidence of 'Apple $\rightarrow$ Milk' divides the pair's count by the count of Apple. The confidence of 'Milk $\rightarrow$ Apple' divides by the count of Milk instead. They yield completely different percentages every time. Students constantly calculate one direction, assume the reverse is identical, write it down, and lose massive points. Always double-check the denominator before submitting an answer.
• The Subset Trap: Check All Pairs Before Counting Triplets

  When building a triplet like $\{Apple,Milk,Bread\}$ ($C_3$), rushing straight to the receipts to start counting wastes valuable time. Stop first. Check the $L_2$ list. Did the pair $\{Milk,Bread\}$ actually survive? Did $\{Apple,Bread\}$ survive? If even one of those internal pairs was eliminated earlier, the entire triplet is instantly dead. Skip counting it entirely and move straight to the next candidate.
• Exam Trap: Support Always Divides by Total Transactions ($N$)

  When asked for the Support of a rule like $X\rightarrow Y$, panicking and dividing by the count of $X$ is a common mistake — that calculation is Confidence, not Support. The Support of a rule is mathematically identical to the Support of the itemset itself ($X\cup Y$). Always divide the count of the pair by the total number of transactions ($N$), regardless of which direction the arrow points.
• Pro Tip: A Lift Below 1 Means They Are Substitutes

  Everyone knows a Lift above $1$ means items are bought together, and exactly $1$ means independence. Professors love asking what a Lift of $0.5$ actually means. It doesn't signal a 'weak' connection — it signals a negative connection. Customers buying the first item are actively avoiding the second. Think Coke and Pepsi: buying one drastically reduces the likelihood of buying the other one too.

Strengths, Weaknesses & When To Use It

When to use it:Apriori is the foundational algorithm for Market Basket Analysis — perfect for finding 'Frequently Bought Together' patterns in retail or basic recommendation engines. On an exam, if a question asks for a more modern, memory-efficient alternative that doesn't generate massive candidate tables or scan the database repeatedly, the answer is always the FP-Growth algorithm. Apriori is easy to teach and trace by hand, but FP-Growth is what companies actually deploy in production for big data.

Apriori Algorithm vs. FP-Growth

Apriori and FP-Growth are not trying to solve different problems — they are two different vehicles driving to the exact same destination. Given identical datasets and thresholds, both output identical frequent itemsets and association rules. Apriori is the pioneer, relying on brute-force candidate generation and repeated database scans to get there. FP-Growth is the modern upgrade, compressing the entire database into a memory-efficient tree structure that entirely eliminates the need to generate candidates at all.

• Candidate Generation — Generate and Test vs. Zero Candidates: Apriori is a 'generate and test' algorithm. It builds massive $C_k$ tables of hypothetical combinations in memory before checking whether they actually exist in the data. FP-Growth generates exactly zero candidates. It extracts patterns directly from a compressed tree structure, completely bypassing the single most memory-intensive step of the entire process.
• Database Scans — Repeated vs. Just Twice: Apriori must physically scan the entire transaction database from scratch on every single iteration, scanning it $k$ times where $k$ is the size of the largest itemset. FP-Growth scans the database exactly twice — once to count individual items, and once to build the FP-Tree. After that, it never touches the original database again.
• Memory Usage — Exponential vs. Compressed: Apriori consumes memory exponentially. With a wide dataset containing thousands of items, generating pairs and triplets will instantly overwhelm system RAM. FP-Growth stays highly memory-efficient because it compresses the original data — overlapping transactions share the same branches within the FP-Tree, massively shrinking the dataset's overall memory footprint.
• Real-World Use — Classroom Tool vs. Production Workhorse: Apriori is perfect for the classroom because it is mathematically intuitive and easy to trace by hand on an exam paper. It completely chokes on Big Data, however. FP-Growth is vastly faster and infinitely more scalable, making it the algorithm companies actually deploy in production for large-scale recommendation engines.

Implementation Pseudocode

// APRIORI ALGORITHM — Generate, Test, and Prune
// Builds frequent itemsets level by level, pruning early using the
// Downward Closure Property to avoid testing combinations doomed to fail.

FUNCTION apriori(transactions, min_support):

    // ── INITIALIZATION ──
    // Find every individual item and count how often it appears.
    L1 = []
    itemCounts = countEachUniqueItem(transactions)
    // Helper: countEachUniqueItem() simply tallies every item across every row.

    FOR EACH item IN itemCounts:
        IF itemCounts[item] >= min_support:
            L1.add(item)
    END FOR
    // L1 holds every item that survives the very first popularity filter.
    // Anything missing here is permanently dead for the rest of the algorithm.

    allFrequentSets = [L1]
    k = 2

    // ── THE MAIN LOOP ──
    WHILE L_(k-1) is NOT empty:

        // ── STEP 1: CANDIDATE GENERATION (Ck) ──
        Ck = joinWithItself(L_(k-1))
        // Helper: joinWithItself() combines surviving (k-1)-itemsets into
        // new k-sized candidate combinations. This step can explode in size
        // if L_(k-1) is large, which is exactly why pruning happens next.

        // ── STEP 2: DOWNWARD CLOSURE PRUNING ──
        FOR EACH candidate IN Ck:
            subsets = get_subsets(candidate, k-1)
            // Helper: get_subsets() returns every possible (k-1)-sized
            // subset contained inside this candidate.

            FOR EACH subset IN subsets:
                IF subset NOT IN L_(k-1):
                    REMOVE candidate FROM Ck
                    // Exam Gold: this is the Downward Closure Property in
                    // action. If even one smaller piece of a candidate already
                    // failed the support test, the whole candidate is
                    // mathematically guaranteed to fail too. Deleting it now
                    // means it never gets counted in Step 3 — pure time saved.
                    BREAK
                END IF
            END FOR
        END FOR

        // ── STEP 3: DATABASE SCAN (THE BOTTLENECK) ──
        FOR EACH transaction IN transactions:
            FOR EACH candidate IN Ck:
                IF candidate IS SUBSET OF transaction:
                    increment candidate's count
                END IF
            END FOR
        END FOR
        // Exam Trap: this loop re-reads the ENTIRE transaction database
        // from scratch, every single iteration of k. This repeated disk
        // scanning is the exact reason Apriori becomes painfully slow on
        // large datasets — and exactly why FP-Growth was invented to avoid it.

        // ── STEP 4: FILTER TO BUILD Lk ──
        Lk = []
        FOR EACH candidate IN Ck:
            IF candidate.count >= min_support:
                Lk.add(candidate)
            END IF
        END FOR

        allFrequentSets.add(Lk)
        k = k + 1

    END WHILE

    RETURN allFrequentSets

END FUNCTION

Time & Space Complexity

Apriori Exam Questions Students Always Get Wrong

• Does the order of items matter? Is {Apple, Milk} different from {Milk, Apple}?

  No. Itemsets are mathematically unordered collections. Treating them as different combinations instantly doubles the workload, bloats the $C_2$ table, and ruins the support calculations. Always write pairs in alphabetical order to ensure the same combination never gets counted twice by accident.

• The exam asks for 60% Support, but counts are whole numbers. Convert every row to a percentage?

  Never convert row by row. Doing fraction math for every single candidate wastes time and invites careless errors. Multiply the required percentage by the total number of transactions ($N$) immediately. This gives a raw target number — just check if each count hits that target directly.

• What if {Apple, Milk} has support 3, and {Apple} also has support 3? Drop one?

  Keep both. This simply means every person who bought an Apple also bought Milk — perfect correlation. As long as a combination meets the minimum support threshold, it survives. Never drop a smaller itemset just because a larger one happens to share the exact same count.

• When building $C_3$ triplets, pull items from the original receipts or from $L_2$?

  Always build new candidates strictly by joining the survivors from the previous step, $L_2$. Looking back at the original receipts to guess triplets defeats the entire purpose of the algorithm. The original transaction database only gets touched again when it is time to count support.

• If a triplet exists in the database, do subsets still need to survive $L_2$ first?

  Yes, if the exam asks for pruning steps to be shown. The downward closure property dictates candidates are pruned before scanning the database. If a subset failed earlier, the triplet is invalid even if it physically appears somewhere. Skipping the subset check usually loses points for incorrect execution.