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.
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
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.
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.
| Rule | Supp | Conf | Lift |
|---|---|---|---|
| Savings → Debit | 0.62 | 0.88 | 1.40 |
| Mortgage → Insurance | 0.31 | 0.74 | 2.10 |
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 Rule | Supp | Conf |
|---|---|---|
| Wheat+Barley→Rape | 0.28 | 0.71 |
| Maize→Soybean | 0.34 | 0.65 |
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 Rule | Conf | Lift |
|---|---|---|
| Metf+Lisin→Atorv | 0.82 | 2.30 |
| Aspirin→PPI | 0.65 | 1.85 |
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)
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.
FP-Tree construction:
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.
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.
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.
| Pattern | Support |
|---|---|
| Cash+BalCheck | 0.78 |
| Transfer+Receipt | 0.54 |
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.
| Conditions | Supp | Conf |
|---|---|---|
| pH6+N150+Rain700→High | 0.32 | 0.88 |
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 Set | Conf | Lift |
|---|---|---|
| Fever+Cough→Flu | 0.87 | 3.2 |
| Chest pain+SOB→ACS | 0.72 | 4.1 |
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.
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))
The same information as the assumption blocks above, side by side — this is the comparison that decides which method to reach for.
| Algorithm | Assumes | Breaks when |
|---|---|---|
| 2.4 Apriori Algorithm | Transactions are independent; support thresholds are meaningful | Minimum support is set low — the candidate set explodes combinatorially |
| 2.5 FP-Growth Algorithm | The database has enough shared prefixes for the tree to compress | Transactions share few prefixes — the FP-Tree degenerates to one path each |