Skip to the content

Algorithms on This Page

2.4 Apriori Algorithm 2.5 FP-Growth Algorithm
Why this sits under unsupervised learning: there is no target column. The algorithm is handed a set of transactions and asked which items co-occur more than chance would predict — structure discovered from the data alone. The rule \(X \Rightarrow Y\) looks like a prediction, but it is a description of co-occurrence, not a trained mapping, and it carries no notion of a held-out test set.

2.4  Apriori Algorithm

Frequent ItemsetsAssociation Rules
DEFINITION

The Apriori algorithm mines frequent itemsets from transactional data using the anti-monotone property: any subset of a frequent itemset must also be frequent. It iteratively generates candidate itemsets, prunes infrequent ones, and generates association rules of the form \(X \Rightarrow Y\) with metrics for support, confidence, and lift.

2.4.1  Mathematical Foundation

FORMULAE

Support (frequency of itemset \(X\)):

\[\text{supp}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}\]

Confidence (conditional probability \(X \Rightarrow Y\)):

\[\text{conf}(X \Rightarrow Y) = \frac{\text{supp}(X \cup Y)}{\text{supp}(X)}\]

Lift (independence measure):

\[\text{lift}(X \Rightarrow Y) = \frac{\text{conf}(X \Rightarrow Y)}{\text{supp}(Y)} = \frac{\text{supp}(X \cup Y)}{\text{supp}(X)\cdot\text{supp}(Y)}\]

Lift \(>1\) → positive correlation; Lift \(=1\) → independent; Lift \(<1\) → negative correlation

Anti-monotone property: If \(X\) is infrequent, all supersets of \(X\) are also infrequent

2.4.2  How It Works

Apriori makes one database pass per candidate level, so \(k_{\max}+1\) passes in total, where \(k_{\max}\) is the length of the longest frequent itemset — the count is data-dependent, not fixed. Each pass prunes candidates whose subsets are infrequent. This breadth-first approach generates large numbers of candidate itemsets. Setting appropriate minimum support and confidence thresholds controls the output. Multiple testing correction is needed when many rules are generated. Apriori can be slow for large datasets (FP-Growth is faster), but its output is highly interpretable.

2.4.3  Assumptions and Failure Modes

ASSUMES
  • Transactions are independent; support thresholds are meaningful
BREAKS WHEN
  • Minimum support is set low — the candidate set explodes combinatorially
  • Many rules are generated and none is corrected for multiple testing
  • High confidence is read as causation — check lift, and check both directions

2.4.4  Worked Examples

FINANCE

🏦 Cross-Selling Products

Mining bank customer product holdings. Rule: {Savings Account} ⇒ {Debit Card} (sup=0.62, conf=0.88, lift=1.4). Customers with a savings account are 1.4× more likely to hold a debit card — triggering targeted debit card offers.

RuleSuppConfLift
Savings → Debit0.620.881.40
Mortgage → Insurance0.310.742.10
AGRICULTURE

🌿 Crop Rotation Patterns

Mining 5-year crop rotation records from 2,000 farms. Rule: {Wheat, year1} ∧ {Barley, year2} ⇒ {Rapeseed, year3} (sup=0.28, conf=0.71) reflects agronomically optimal rotations for disease break.

Rotation RuleSuppConf
Wheat+Barley→Rape0.280.71
Maize→Soybean0.340.65
MEDICINE

💊 Drug Co-Prescription Patterns

Mining electronic prescription records for 100,000 patients. Rule: {Metformin, Lisinopril} ⇒ {Atorvastatin} (conf=0.82, lift=2.3) reveals a common diabetes-hypertension-dyslipidaemia combination, guiding clinical guidelines.

Drug RuleConfLift
Metf+Lisin→Atorv0.822.30
Aspirin→PPI0.651.85

2.4.5  Code

Apriori
import numpy as np
import pandas as pd
from mlxtend.frequent_patterns import apriori, association_rules
from mlxtend.preprocessing import TransactionEncoder

np.random.seed(42)

# ── Simulate Bank Product Holdings ────────────────────────────
products = ['Savings','Debit','Credit','Mortgage','Insurance','Investment','Loan']

def simulate_basket(n_customers):
    baskets = []
    for _ in range(n_customers):
        b = []
        if np.random.rand() < 0.80: b.append('Savings')
        if np.random.rand() < 0.70 and 'Savings' in b: b.append('Debit')
        elif np.random.rand() < 0.30: b.append('Debit')
        if np.random.rand() < 0.45: b.append('Credit')
        if np.random.rand() < 0.25: b.append('Mortgage')
        if 'Mortgage' in b and np.random.rand() < 0.70: b.append('Insurance')
        if np.random.rand() < 0.20 and ('Savings' in b or 'Credit' in b): b.append('Investment')
        if np.random.rand() < 0.15: b.append('Loan')
        if b: baskets.append(b)
    return baskets

transactions = simulate_basket(3000)

# ── One-Hot Encode ────────────────────────────────────────────
te = TransactionEncoder()
te_array = te.fit_transform(transactions)
df = pd.DataFrame(te_array, columns=te.columns_)

# ── Frequent Itemsets ─────────────────────────────────────────
frequent_items = apriori(df, min_support=0.10, use_colnames=True)
frequent_items['length'] = frequent_items['itemsets'].apply(len)
print(f"=== Apriori — Bank Products ===")
print(f"Frequent itemsets: {len(frequent_items)}")
print(frequent_items.sort_values('support', ascending=False).head(10).to_string(index=False))

# ── Association Rules ─────────────────────────────────────────
rules = association_rules(frequent_items, metric='confidence', min_threshold=0.5)
rules = rules.sort_values('lift', ascending=False)
print(f"\nTop 10 Rules by Lift:")
print(rules[['antecedents','consequents','support','confidence','lift']].head(10).to_string(index=False))

# ── Strong rules (lift > 1.5) ─────────────────────────────────
strong = rules[rules['lift'] > 1.5]
print(f"\nStrong rules (lift>1.5): {len(strong)}")
library(arules); library(arulesViz); set.seed(42)

# ── Simulate Bank Transactions ────────────────────────────────
n <- 3000
savings    <- runif(n) < 0.80
debit      <- ifelse(savings, runif(n) < 0.70, runif(n) < 0.30)
credit     <- runif(n) < 0.45
mortgage   <- runif(n) < 0.25
insurance  <- ifelse(mortgage, runif(n) < 0.70, runif(n) < 0.05)
investment <- ifelse(savings | credit, runif(n) < 0.20, runif(n) < 0.05)

df <- data.frame(Savings=savings, Debit=debit, Credit=credit,
                 Mortgage=mortgage, Insurance=insurance, Investment=investment)
trans <- as(df, "transactions")
summary(trans)

# ── Apriori ───────────────────────────────────────────────────
rules <- apriori(trans,
                 parameter=list(supp=0.10, conf=0.50, minlen=2))
cat(sprintf("\nTotal rules: %d\n", length(rules)))

# ── Top rules by lift ─────────────────────────────────────────
rules_sorted <- sort(rules, by="lift", decreasing=TRUE)
cat("\nTop 10 rules by lift:\n")
inspect(head(rules_sorted, 10))

# ── Filter strong rules ───────────────────────────────────────
strong <- subset(rules, lift > 1.5)
cat(sprintf("\nStrong rules (lift>1.5): %d\n", length(strong)))
inspect(strong)

2.5  FP-Growth Algorithm

Tree-Based MiningScalable
DEFINITION

FP-Growth (Frequent Pattern Growth) mines frequent itemsets without candidate generation, using a compact FP-Tree data structure. It requires only two database scans — one to find frequent 1-itemsets and one to build the FP-Tree — then mines patterns recursively by dividing the problem into a set of smaller tasks involving conditional FP-Trees. It is substantially faster than Apriori on large databases.

2.5.1  Mathematical Foundation

FORMULAE

FP-Tree construction:

  1. Scan DB → find frequent 1-itemsets \(F\); sort by frequency
  2. Scan DB again → insert each transaction (filtered & sorted) into FP-Tree
  3. Compress by sharing common prefixes

Mining (for each item \(a_i\) in header table):

\[\text{conditional pattern base of } a_i = \{\text{prefix paths of } a_i \text{ in FP-Tree}\}\] \[\text{conditional FP-Tree} = \text{FP-Tree}(\text{conditional pattern base}) \]

Recursively mine conditional FP-Trees to find all frequent patterns

Cost: two database scans regardless of pattern length, against Apriori's one scan per level. The FP-Tree holds at most one node per item occurrence, so it never exceeds the size of the filtered database and is usually far smaller through prefix sharing — but it is not \(O(N)\) in general: with no shared prefixes the tree degenerates to one path per transaction. The gain over Apriori is the elimination of candidate generation, which is exponential in the itemset length in the worst case.

2.5.2  How It Works

FP-Growth avoids the expensive candidate generation and repeated database scanning of Apriori. The FP-Tree stores all frequency information in a compressed form. Items in each transaction are sorted by descending frequency before insertion, maximising prefix sharing. The header table provides direct links to all occurrences of each item. FP-Growth is especially faster when the database is large and the minimum support threshold is low, generating the same set of frequent patterns as Apriori.

2.5.3  Assumptions and Failure Modes

ASSUMES
  • The database has enough shared prefixes for the tree to compress
BREAKS WHEN
  • Transactions share few prefixes — the FP-Tree degenerates to one path each
  • The tree does not fit in memory — projection databases are then needed

2.5.4  Worked Examples

FINANCE

🛒 High-Frequency Transaction Mining

Mining 500,000 daily ATM transactions for co-occurrence patterns. FP-Growth's advantage over Apriori widens as the minimum support falls: Apriori's candidate set grows combinatorially while the FP-Tree does not. The code below times both on identical data so the gap can be measured rather than asserted.

PatternSupport
Cash+BalCheck0.78
Transfer+Receipt0.54
AGRICULTURE

🌾 Growing Condition Associations

Mining 10,000 farm season records for co-occurring growing conditions leading to high yield. FP-Growth finds {pH 6.0–6.5, N>150, rain>700} ⇒ {high yield} with support=0.32, confidence=0.88.

ConditionsSuppConf
pH6+N150+Rain700→High0.320.88
MEDICINE

🏥 Symptom-Disease Associations

Mining 200,000 electronic health records for symptom co-occurrence. FP-Growth finds {fever, cough, fatigue} ⇒ {flu diagnosis} with support=0.12 and confidence=0.87, supporting triage protocol design.

Symptom SetConfLift
Fever+Cough→Flu0.873.2
Chest pain+SOB→ACS0.724.1

2.5.5  Code

A note on the R tab: the arules package has no FP-Growth implementation. The R pane below therefore uses eclat(), which is a different algorithm — Eclat mines frequent itemsets by intersecting vertical tid-lists rather than by building an FP-Tree — though it returns the same frequent itemsets for the same minimum support. For a true FP-Growth in R, use rCBA::fpgrowth(). The Python pane is the one that demonstrates FP-Growth itself.
FP-Growth
import numpy as np
import pandas as pd
import time
from mlxtend.frequent_patterns import fpgrowth, apriori, association_rules
from mlxtend.preprocessing import TransactionEncoder

np.random.seed(42)

# ── Simulate Symptom-Disease Records ─────────────────────────
symptoms = ['Fever','Cough','Fatigue','Headache','Nausea','SoreThroat',
            'Dyspnoea','ChestPain','Diarrhoea','Rash']

def gen_record(profile):
    base, extras = profile
    items = list(base) + [s for s in extras if np.random.rand() < 0.4]
    return list(set(items))

profiles = [
    (['Fever','Cough'], ['Fatigue','SoreThroat','Headache']) for _ in range(4000)
] + [
    (['ChestPain','Dyspnoea'], ['Fatigue','Nausea']) for _ in range(1200)
] + [
    (['Diarrhoea','Nausea'], ['Fatigue','Fever']) for _ in range(1500)
] + [
    ([s],['Headache','Rash']) for s in np.random.choice(symptoms, 3300)
]

transactions = [gen_record(p) for p in profiles]
valid = [t for t in transactions if len(t) >= 1]

te = TransactionEncoder()
df = pd.DataFrame(te.fit_transform(valid), columns=te.columns_)

# ── FP-Growth vs Apriori timing ───────────────────────────────
min_sup = 0.05
t0 = time.time()
freq_fp = fpgrowth(df, min_support=min_sup, use_colnames=True)
t_fp = time.time() - t0

t0 = time.time()
freq_ap = apriori(df, min_support=min_sup, use_colnames=True)
t_ap = time.time() - t0

print("=== FP-Growth vs Apriori ===")
print(f"FP-Growth : {len(freq_fp):4d} itemsets in {t_fp:.4f}s")
print(f"Apriori   : {len(freq_ap):4d} itemsets in {t_ap:.4f}s")
print(f"Speedup   : {t_ap/max(t_fp,1e-6):.2f}x")

# ── Association Rules from FP-Growth ─────────────────────────
rules = association_rules(freq_fp, metric='confidence', min_threshold=0.6)
rules = rules.sort_values('lift', ascending=False)
print("\nTop 8 Rules (Symptom-Disease Patterns):")
print(rules[['antecedents','consequents','support','confidence','lift']].head(8).to_string(index=False))
library(arules); set.seed(42)

# ── Simulate Medical Symptom Data ─────────────────────────────
symptoms <- c("Fever","Cough","Fatigue","Headache","Nausea",
              "SoreThroat","Dyspnoea","ChestPain","Diarrhoea","Rash")
n <- 10000

gen_trans <- function(n) {
  lapply(1:n, function(i) {
    r <- runif(1)
    if(r < 0.40) base <- c("Fever","Cough")
    else if(r < 0.55) base <- c("ChestPain","Dyspnoea")
    else if(r < 0.70) base <- c("Diarrhoea","Nausea")
    else base <- sample(symptoms, 1)
    extra <- symptoms[runif(length(symptoms)) < 0.15]
    unique(c(base, extra))
  })
}

trans_list <- gen_trans(n)
trans <- as(trans_list, "transactions")
cat(sprintf("Transactions: %d, Items: %d\n", length(trans), nitems(trans)))

# ── NOTE: arules has no FP-Growth. Eclat is a DIFFERENT algorithm ────
# (vertical tid-list intersection, not FP-Tree prefix sharing). It yields
# the same frequent itemsets at the same support. For real FP-Growth in R
# use rCBA::fpgrowth(). Shown here as the closest available vertical miner.
freq_items <- eclat(trans, parameter=list(supp=0.05, maxlen=4))
cat(sprintf("Frequent itemsets: %d\n", length(freq_items)))
inspect(sort(freq_items, by="support")[1:10])

# ── Association Rules ─────────────────────────────────────────
rules <- ruleInduction(freq_items, trans, confidence=0.6)
rules <- sort(rules, by="lift", decreasing=TRUE)
cat("\nTop 10 rules:\n")
inspect(head(rules, 10))

At a Glance

The same information as the assumption blocks above, side by side — this is the comparison that decides which method to reach for.

AlgorithmAssumesBreaks when
2.4 Apriori AlgorithmTransactions are independent; support thresholds are meaningfulMinimum support is set low — the candidate set explodes combinatorially
2.5 FP-Growth AlgorithmThe database has enough shared prefixes for the tree to compressTransactions share few prefixes — the FP-Tree degenerates to one path each