Association Analysis

What is Association Analysis?

Association analysis is an unsupervised technique for discovering relationships between items in large datasets.

The classic example is market basket analysis: given millions of shopping transactions, which products tend to be bought together? The output is a set of association rules of the form:

$$\{\text{bread},\text{butter}\}\Rightarrow \{\text{milk}\}$$

NOTE

Read as “customers who buy bread and butter also tend to buy milk”. The left side is the antecedent, the right side the consequent.

Measuring a rule

Three metrics decide whether a rule like $\{\text{bread}\}\Rightarrow \{\text{milk}\}$ is worth keeping. Each answers a different question, and they build on each other:

• Support: is this combo common enough to bother with?
• Confidence: when they buy the antecedent, how often comes the consequent?
• Lift: is that better than milk selling on its own?

For example, let’s say we have 1,000 baskets: bread appears in 300, milk in 500, and both together in 200.

1. Support = 200 / 1,000 = 0.2 → the pattern is frequent enough to keep.
2. Confidence = 200 / 300 ≈ 0.67 → two-thirds of bread buyers also grab milk. (This is just $P(\text{milk}\mid \text{bread})$.)
3. Lift = 0.67 / 0.5 = 1.34 → bread buyers take milk 34% more often than shoppers at large, so the link is real.

Read lift as the payoff:

• If > 1 they go together
• If = 1 unrelated
• If < 1 they repel (substitutes — like {Coke} ⇒ {Pepsi})

A higher lift isn’t automatically better. Trust a rule only when it has enough support behind it (a huge lift on a handful of baskets is coincidence) and survives a “why would this be true?” check — a big lift often just means both items share a cause (same promo, same aisle) or the rule is obvious ({hot dogs} ⇒ {buns}). The math ranks candidates; judgment validates them.

WARNING

High confidence alone is misleading. If milk is in 90% of all baskets, a rule with 90% confidence tells you nothing — the antecedent didn’t help. Always check lift to confirm the association is real and not just a popular consequent.

Support formula

$\text{support}(X)=\frac{\text{baskets with }X}{\text{all baskets}}$

Confidence formula

$\text{confidence}(X\Rightarrow Y)=\frac{\text{support}(X\cup Y)}{\text{support}(X)}$

Lift formula

$\text{lift}(X\Rightarrow Y)=\frac{\text{confidence}(X\Rightarrow Y)}{\text{support}(Y)}$

The Apriori Algorithm

The hard part is finding frequent itemsets: with $n$ items there are $2^n$ possible itemsets, far too many to count by brute force. Apriori prunes this space using one simple observation, the Apriori property (anti-monotonicity):

If an itemset is infrequent, all of its supersets are also infrequent.

If {bread} doesn’t clear the minimum support threshold, then {bread, milk} can’t either — so you never even generate it.

The algorithm works bottom-up, level by level:

1. Count support for all single items; discard those below min_support.
2. Generate candidate pairs only from surviving items, count them, discard the infrequent.
3. Generate candidate triples only from surviving pairs, and so on.
4. Stop when no new frequent itemsets are found.
5. From the frequent itemsets, generate rules that clear min_confidence.

Each level requires a full pass over the dataset, which is Apriori’s main cost.

flowchart TD
    A[Count support for single items] --> B{Any above min_support?}
    B -->|No| G[Generate rules above min_confidence]
    B -->|Yes| C[Keep frequent itemsets of size k]
    C --> D[Generate size k+1 candidates from frequent size k itemsets]
    D --> E[Scan dataset, count support]
    E --> B
    G --> F[Done]

# mlxtend handles both steps: frequent itemsets, then rules
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules
 
transactions = [
    ["bread", "butter", "milk"],
    ["bread", "butter"],
    ["milk", "eggs"],
    ["bread", "milk", "eggs"],
]
 
# one-hot encode into a transactions x items boolean matrix
te = TransactionEncoder()
matrix = te.fit_transform(transactions)
import pandas as pd
df = pd.DataFrame(matrix, columns=te.columns_)
 
frequent = apriori(df, min_support=0.5, use_colnames=True)
rules = association_rules(frequent, metric="lift", min_threshold=1.0)
 
# FP-Growth: same result, usually faster on big datasets. It compresses the data
# into a tree and mines that, skipping Apriori's per-level rescans and candidate
# generation. The tradeoff is memory — the tree lives in RAM.
# from mlxtend.frequent_patterns import fpgrowth
# frequent = fpgrowth(df, min_support=0.5, use_colnames=True)
 
print(rules[["antecedents", "consequents", "support", "confidence", "lift"]])

Where it’s used

Beyond retail baskets: recommender systems (“frequently bought together”), web usage mining (pages visited in the same session), medical diagnosis (symptoms co-occurring with conditions), and fraud detection (combinations of actions that signal risk).

References

• Agrawal, R., & Srikant, R. Fast Algorithms for Mining Association Rules. VLDB, 1994.
• Han, J., Kamber, M., & Pei, J. Data Mining: Concepts and Techniques, 3rd ed. Morgan Kaufmann, 2011.
• Bishop, C. M. Pattern Recognition and Machine Learning. Springer, 2006.
• Thanuja, V. Association Rules Mining: A Recent Overview.