Association rule discovery is a method for identifying meaningful co-occurrence patterns in transaction data. The goal is to find rules that state: when a particular set of items appears in a transaction, another set of items tends to appear as well, with a quantifiable level of confidence. Importantly, these rules should be interpreted as associations, not as evidence of direct causation.

Core Terminology: k-Itemsets

An $k$-itemset is a collection of $k$ distinct items selected from the universal set of items, where $1 \le k \le m$. Formally, a $k$-itemset is a subset of the universal set.

Empty itemsets are excluded by design, so $k \ge 1$.

Although an $m$-itemset (containing every item in the universal set) is mathematically valid, it is not practically interesting in typical market-basket settings. If a transaction contains all items, then every item appears regardless of what is already in the basket, which provides no useful insight about conditional co-occurrence.

---

How Many Itemsets Exist?

Assume the universal set contains $m \ge 1$ unique items.

For a given $k$, the number of possible $k$-itemsets is the binomial coefficient:

$$\binom{m}{k} = \frac{m!}{k!(m-k)!}, \quad k = 1,2,\dots,m.$$

Across all valid sizes $k = 1$ through $m$, the total number of non-empty itemsets is:

$$\binom{m}{1} + \binom{m}{2} + \cdots + \binom{m}{m}.$$

Using the binomial theorem,

$$\binom{m}{0} + \binom{m}{1} + \cdots + \binom{m}{m} = 2^m,$$

so the total number of non-empty itemsets is:

$$2^m – 1.$$

---

How Many Association Rules Exist?

Since each association rule partitions items into an antecedent and a consequent, the number of possible rules grows even faster than the number of itemsets.

Given that the total number of possible non-empty itemsets is $2^m – 1$, the total number of possible association rules can be expressed (as reported by Tan, Steinbach, and Kumar, 2006, Introduction to Data Mining) as:

$$\sum_{k=1}^{m-1} \binom{m}{k}\sum_{j=1}^{m-k}\binom{m-k}{j} = 3^m – 2^{m+1} + 1.$$

The factorial identity $m! = m \times (m-1) \times \cdots \times 2 \times 1$ underlies the binomial coefficient $\binom{m}{k}$.

A numerical perspective makes the growth concrete. Even with $m=20$ items, the number of possible itemsets is $1,048,575$, and the number of possible association rules is $3,484,687,250$. This scale explains why brute-force enumeration becomes infeasible.

---

What an Association Rule Means

An association rule is commonly described as follows:

If a transaction already contains a particular set of item(s), then with a confidence level of $p\%$, where $0 \le p \le 100$, another specific set of item(s) may also be part of that transaction.

This statement is intended to capture co-occurrence tendency, not a cause-and-effect relationship. The correct interpretation is that the rule represents a statistical association between two or more items.

---

Antecedent and Consequent Itemsets

Association rules are conventionally written as:

$$X \rightarrow Y, \quad \text{where } X, Y \subset I.$$

Here:

• $X$ is the Antecedent itemset.
• $Y$ is the Consequent itemset.

The two itemsets must be disjoint, meaning they share no common items.

There is no restriction on the number of items in either itemset. However, neither $X$ nor $Y$ can be an empty itemset, and neither can be an $m$-itemset.

---

Concrete Examples of Association Rules

One rule can be expressed as: 80% of shoppers who buy ice cream also purchase ice cream cones.
In this rule, the antecedent is the 1-itemset $\{ \text{Ice Cream} \}$, and the consequent is the 1-itemset $\{ \text{Ice Cream Cones} \}$.

Another rule can be expressed as: 60% of students who completed Machine Learning and Data Mining will register for Deep Learning in the next quarter.
In this rule, the antecedent is the 2-itemset $\{\text{Machine Learning course}, \text{Data Mining course}\}$, and the consequent is the 1-itemset $\{\text{Deep Learning course}\}$.

---

Measuring Association Rules

Association rules are evaluated using multiple metrics, including Support, Confidence, Lift, Leverage, Expected Confidence, and Zhang’s Metric. These measures quantify how frequently itemsets occur, how strongly the consequent is linked to the antecedent, and how surprising or useful the rule is compared to baseline expectations.

Support of an Itemset $X$

Support measures the occurrence likelihood of an itemset $X$.

Let:

• $N$ be the total number of transactions,
• $N_X$​ be the number of transactions in which itemset $X$ appears.

Then $N_X \le N$, and since empty itemsets are not allowed, $1 \le N_X$​.

Support is defined as:

$$\text{Support}(X) = \frac{N_X}{N}.$$

The lowest possible support is $\frac{1}{N}$​, and the highest possible support is $1$. Support is often reported as a percentage.

---

Support of a Rule $X \rightarrow Y$

A rule $X \rightarrow Y$ combines the antecedent $X$ and the consequent $Y$. The support of the rule is defined as the support of the union itemset $X \cup Y$:

$$\text{Support}(X \rightarrow Y) = \text{Support}(X \cup Y).$$

This is the proportion of all $N$ transactions in which both $X$ and $Y$ appear together.

Operationally, one can first locate the $N_X$​ transactions containing $X$, then count how many of those transactions also contain $Y$. The joint occurrence can range from none of the $N_X$​ transactions to all of them.

This implies the bound:

$$0 \le \text{Support}(X \cup Y) \le \text{Support}(X).$$

---

Confidence of a Rule $X \rightarrow Y$

Confidence measures how likely the consequent itemset $Y$ will appear in a transaction where the antecedent itemset $X$ has already appeared.

Confidence is defined as:

$$\text{Confidence}(X \rightarrow Y) = \frac{\text{Support}(X \rightarrow Y)}{\text{Support}(X)}.$$

Therefore:

$$0 \le \text{Confidence}(X \rightarrow Y) \le 1.$$

Confidence is often used as a proxy for the “credibility” of a rule, in the sense of how consistently the consequent follows the antecedent in the observed data.

---

Expected Confidence

Expected confidence is the baseline likelihood that the consequent $Y$ occurs, regardless of $X$. Numerically, expected confidence equals the support of the consequent itemset:

$$\text{Expected Confidence} = \text{Support}(Y).$$

This baseline is essential because the goal of an association rule is to reveal whether observing $X$ changes the probability of observing $Y$, either upward or downward.

---

Lift

Lift compares the observed confidence of the rule to the baseline likelihood of $Y$. It is defined as the ratio of confidence to expected confidence:

$$\text{Lift}(Y \mid X) = \frac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)} = \frac{\text{Support}(X \rightarrow Y)}{\text{Support}(X)\,\text{Support}(Y)}.$$

Interpretation follows three standard cases:

• Lift = 1 means the rule is not informative: $Y$ occurs regardless of whether $X$ occurs.
• Lift < 1 means the rule indicates a credible negative association: the presence of $X$ reduces the likelihood of $Y$.
• Lift > 1 means the rule indicates a credible positive association: the presence of $X$ increases the likelihood of $Y$.

---

Theoretical Upper Bound on Lift

To maximize a ratio $\frac{A}{B}$​, one can increase $A$ and decrease $B$.

The highest possible lift can be achieved in theory by maximizing $\text{Confidence}(X \rightarrow Y)$ to $1$ while minimizing $\text{Support}(Y)$ to $\frac{1}{N}$​. Under that extreme configuration, the theoretical maximum lift becomes:

$$\frac{1}{\frac{1}{N}} = N.$$

In practice, lift rarely approaches $N$.

---

Leverage

Leverage measures the effectiveness of bundling the antecedent and consequent items by comparing observed joint occurrence with what would be expected under independence:

$$\text{Leverage}(Y \mid X) = \text{Support}(X \rightarrow Y) – \text{Support}(X)\,\text{Support}(Y).$$

It can also be expressed using lift:

$$\text{Leverage}(Y \mid X) = (\text{Lift}(Y \mid X) – 1)\,\text{Support}(X)\,\text{Support}(Y).$$

Interpretation:

• Leverage = 0 means bundling does not affect sales of the consequent.
• Leverage < 0 means bundling decreases sales of the consequent.
• Leverage > 0 means bundling increases sales of the consequent.

---

Zhang’s Metric

Zhang’s metric extends lift and is mainly used to measure dis-association between the antecedent and consequent.

It is defined as:

$$\text{Zhang}(Y \mid X) = \frac{\text{Support}(X \rightarrow Y) – \text{Support}(X)\,\text{Support}(Y)} {1 – \text{Support}(X)\,\text{Support}(Y)}.$$

Its values lie between $-1$ and $1$. Positive values indicate association, while negative values indicate disassociation.

Because the numerator equals leverage, Zhang’s metric can be viewed as leverage rescaled to the closed interval $[-1, +1]$.

---

Why a Smarter Search Algorithm Is Necessary

Brute-force discovery—explicitly listing every possible association rule—is inefficient and infeasible unless $m$ is very small. The search space is too large, and memory and runtime constraints become prohibitive.

A smarter approach is needed because:

• It is not realistic to review all items in all rules.
• Rules with higher support and/or confidence typically have greater practical impact.
• Rules with high lift are especially valuable because they produce “surprising” associations relative to baseline expectations.

---

The Apriori Algorithm: Restricting the Search Space

The Apriori algorithm constrains the search for association rules by:

1. Discovering frequent itemsets, and
2. Examining only rules that are formed from frequent itemsets.

This approach is typically summarized as two major steps: identifying frequent itemsets and then generating and filtering rules from them.

Step 1: Identify Frequent Itemsets

A frequent itemset is any itemset whose support is greater than or equal to a user-specified minimum support threshold.

The algorithm begins by identifying frequent 1-itemsets (individual items that meet the support threshold). Next, it forms candidate 2-itemsets by adding an additional item to frequent 1-itemsets, and then checks which of those 2-itemsets are frequent. The process continues by increasing itemset length until no more frequent itemsets are found.

Step 2: Generate and Filter Rules from Frequent Itemsets

For each frequent itemset $L$ with length $k > 1$, all observable rules that can be formed from $L$ are generated.

For each generated rule, an evaluation measure (such as confidence) is computed. Rules are then retained only if their evaluation measure exceeds a user-specified threshold.

---

Technical References for the Apriori Family of Methods

The foundational work was proposed by Agrawal, Imielinski, and Swami in 1993 in the paper:

• “Mining Association Rules between Sets of Items in Large Databases,” Proceedings of the 1993 ACM SIGMOD Conference, Washington DC, May 1993.
  (ACM SIGMOD stands for the Association for Computing Machinery Special Interest Group on Management of Data.)

The Apriori algorithm itself was developed further in the Agrawal and Srikant 1994 paper:

• “Fast Algorithms for Mining Association Rules,” Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994.
  (VLDB stands for Very Large Data Bases.)