Association Rules, Apriori and FP-Growth

Measure both frequency and surprise

You will calculate four rule metrics from transactions and use the downward-closure property to understand why Apriori can prune candidate itemsets.

• Calculate itemset support and directional rule confidence.
• Interpret lift against the consequent’s base rate and conviction with care.
• Explain Apriori join, prune and downward closure.
• Describe how FP-growth compresses transactions into an FP-tree.

A frequent rule is not necessarily informative

Support is the fraction of transactions containing an itemset. Confidence for A to B is support of A and B divided by support of A. A popular B can create high confidence even when A adds no information.

Lift divides confidence by support of B. Lift above one means co-occurrence is higher than under an independence baseline, below one means lower, and one indicates no association under that baseline. Sampling, store layout, promotions and customer mix can all explain the result.

Conviction compares the expected frequency of A occurring without B under independence with the observed frequency. It approaches infinity when confidence is one. Small samples and zero denominators require careful handling. Report counts beside every metric.

Apriori uses downward closure: if an itemset is frequent, all its subsets must be frequent. Therefore, any candidate containing an infrequent subset can be pruned. It repeatedly joins frequent itemsets into larger candidates and scans transactions for support.

FP-growth avoids generating the full candidate list. It compresses transactions into a prefix tree ordered by item frequency and mines conditional pattern bases. It can be much faster on dense data, but output volume can still explode when support is low. Constraints and closed or maximal itemsets help focus the search. A metarule can require a rule shape, such as a product category in the antecedent and a service in the consequent. Anti-monotonic constraints, including maximum itemset size or excluding a forbidden item, let the miner prune a whole branch as soon as it fails. Monotonic constraints, such as requiring a minimum total value, become guaranteed only after enough qualifying items enter the set. Classify each constraint before using it for pruning, because the wrong assumption can silently discard valid rules.

Calculate a rule from transparent transactions

The code uses sets so every item counts at most once per basket. Quantity-aware mining is a different problem.

Measure bread to milk

transactions = [
    {"bread", "milk"},
    {"bread", "eggs"},
    {"milk", "eggs"},
    {"bread", "milk", "eggs"},
    {"bread", "milk"},
]

def support(items):
    items = set(items)
    return sum(items <= basket for basket in transactions) / len(transactions)

antecedent = {"bread"}
consequent = {"milk"}
joint = support(antecedent | consequent)
confidence = joint / support(antecedent)
lift = confidence / support(consequent)
denominator = 1 - confidence
conviction = float("inf") if denominator == 0 else (1 - support(consequent)) / denominator

print(f"support: {joint:.3f}")
print(f"confidence: {confidence:.3f}")
print(f"lift: {lift:.3f}")
print(f"conviction: {conviction:.3f}")
print("joint count:", int(joint * len(transactions)))

Expected rule metrics

support: 0.600
confidence: 0.750
lift: 0.937
conviction: 0.800
joint count: 3

Confidence is 75 percent, but lift is below one because milk is already very common. The rule is not positive surprise under the independence baseline.

Rule-mining traps

The more rules you search, the easier it is to find an impressive one by chance. Treat discovery and confirmation as separate stages.

• Very low support produces unstable ratios from a few baskets.
• Duplicate item lines can inflate counts if a basket is not converted to a set.
• Using confidence alone promotes rules whose consequent is simply popular.
• Mining across a promotion and ordinary period can mix two different processes.

Build a filtered rule table

Use a synthetic transaction file or a source with clear rights. Generate frequent itemsets and rules, then apply declared support, lift and minimum-count gates.

• Split discovery and later confirmation periods.
• Include antecedent count, consequent count and joint count.
• Compare Apriori and FP-growth outputs at the same support threshold.
• Investigate one high-lift rule and one high-confidence, low-lift rule.

Evidence to retain

• Threshold rationale.
• Rule table with counts and metrics.
• Confirmation result and non-causal interpretation.

Official references and further reading

• mlxtend association_rules (Primary project documentation for rule metrics)
• mlxtend apriori (Primary project documentation for frequent itemsets)
• mlxtend fpgrowth (Primary project documentation for FP-growth)

Review note for Association Rules, Apriori and FP-Growth: recheck the linked documentation after a dependency changes the relevant API, metric or modelling assumption, then record the tested version beside your result.