—

Data Mining

Association Rule Mining: Apriori and FP-Growth

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Association rules, support, and confidence as conditional probability — covered in Lectures 2 and 11 (Data Mining Fundamentals; Association Rule Mining)
Itemsets, k-itemsets, support count, and minimum support — covered in Lecture 11 (Association Rule Mining)
The Apriori principle and the 2^D candidate explosion — covered in Lecture 11 (Association Rule Mining)
Transaction data and market basket analysis — covered in Lectures 2, 3, and 11 (Data Mining Fundamentals; Data and Data Preprocessing; Association Rule Mining)

This session recaps association rule mining from the previous session and then builds two methods for mining frequent itemsets efficiently: the Apriori algorithm, which prunes candidate itemsets using the Apriori principle, and FP-Growth, which compresses the whole transaction log into a single tree and mines patterns from that tree.

The story of the session runs like this. First we remember what association rule mining is and why retailers care about it (Section 12.1), then we fix the vocabulary â€” itemsets, support count, frequent itemsets (Section 12.2) â€” and the two quality measures for rules, support and confidence (Section 12.3). That vocabulary is enough to see why the naive approach fails: the number of candidate itemsets and rules grows exponentially, and every candidate must be counted against a log that may hold millions of transactions (Section 12.4). The Apriori principle (Section 12.5) gives us the first pruning weapon, and the Apriori algorithm (Sections 12.6â€“12.8) turns it into a practical loop. But Apriori still scans the whole log once per level, and that cost motivates the tree-based alternative: FP-growth (Sections 12.10â€“12.12), which compresses the log into a single FP-tree in one pass and mines it bottom-up without regenerating candidates.

12.1 Association Rule Mining — Recap

12.1.1 The Task

Hook. A customer walks out of a grocery store with a cart containing milk, bread, and eggs. How many other customers walked out with the exact same trio — and what does that pattern tell the store about what to stock, what to discount, and what to advertise? That is the question association rule mining answers from a simple transaction log.

Given a set of transactions — a log generated by a mall, a shopping mall, or a grocery shop — we want to mine frequent patterns and rules from it. Association rules are essentially conditional dependencies: they say that when one thing happens, another thing is likely to happen too. For example, if a person has bought a diaper, they are also likely to buy beer; if a person has bought milk and bread, they are also likely to buy egg and Coke; if a person has bought beer and bread, they are also likely to buy milk. These are the sorts of rules we want to dig out of a transaction log.

Intuition + analogy. Think of the transaction log as a diary of shopping trips. Each row is one trip — one basket. Association rule mining reads the diary and looks for habits: "whenever the basket has X, it almost always also has Y." The famous real example is diapers and beer: a chain store discovered that shoppers buying diapers were unusually likely to buy beer too. There is no physical reason for the two to be linked; the pattern is simply in the data. The store used it to decide shelf placement and promotions.

Mining association rules is a two-step process. First we find frequent patterns (frequent itemsets), and second, within those frequent patterns, we find association rules. So the first step is to find frequent patterns and the second step is to find association rules. This is a theory-heavy topic, though the previous session worked some examples as well.

The reason for the split is practical. Support (how often a pattern appears) depends only on the itemset itself, while confidence (how reliable a rule is) depends on which side of the rule each item goes to. So we first find every itemset that appears often enough — a small fraction of all possible itemsets — and then only inside those few itemsets do we hunt for high-confidence rules. This two-step decomposition is the strategy behind every algorithm in this lecture, and it saves an enormous amount of computation, because itemsets that fail the first test never even reach the second one.

12.1.2 Where It Is Used

Real-world: supermarket self-management, sales promotion, and inventory management are the main application areas named in the previous session. The general principle is that wherever you need to find an association between two items, this style of algorithm applies. The example used in class: an advertisement was able to link two soft-drink brands (Thanda and Coke) to each other because a pattern of co-purchase was found, and that is exactly why the advertisement exists.

Scope — where association mining applies and where it does not. The general principle is: wherever you need to find an association between two items, this style of algorithm applies. In retail that means shelf layout, promotions, and inventory planning — if customers who buy computers also buy antivirus software, the store can place the displays near each other, or run a sale on printers to pull computer sales. Outside retail, the same machinery is used for medical diagnosis (sets of symptoms), web mining (pages visited together), bioinformatics (genes co-expressed), and scientific data analysis (linked atmospheric, ocean, and land processes). What the algorithm does not do is decide causality: "diapers → beer" is a co-occurrence pattern, not proof that diapers cause beer purchases. The rule tells you what happens together; it never tells you why.

Q: What is the application area of this algorithm other than what we discussed? A: We are finding association between two items, so wherever you think you need to find an association between two items, this algorithm is useful. The Thanda–Coke case is a simple example: they were able to find an association between the two brands, and that is why the advertisement exists.

Recap + bridge. Association rule mining turns a transaction log into conditional statements of the form "if X is bought, then Y is often bought too", through two stages: find frequent patterns first, then mine rules inside them. Next we pin down the exact vocabulary — itemset, support count, frequent itemset — because every formula in the rest of the lecture is built from these three words.

12.2 Core Definitions: Itemset, Support Count, Frequent Itemset

12.2.1 Itemsets

Given a transaction log, an itemset (a collection of zero or more items treated as one unit) is a collection of one or more items. If the store's items are bread, milk, diaper, and so on, then any combination of one or more of these items forms an itemset. A k-itemset (an itemset containing exactly $k$ items) is an itemset whose cardinality is $k$ — that is, a set with $k$ items in it. So a 3-itemset is a set that contains three items. For example, ${beer, diapers, milk}$ is a 3-itemset, while ${bread, milk}$ is a 2-itemset. A transaction is said to contain an itemset $X$ whenever every item of $X$ appears in that transaction.

Intuition. An itemset is just a group of items you want to study together — the "shopping list" the algorithm asks about. The size of the group is its cardinality, written $k$ . Nothing else about the items matters at this point: not the price, not the quantity bought, only whether the whole set appears in a transaction. One subtle but important special case: the null (empty) itemset is an itemset too — it is contained in every transaction — but it carries no information, so every algorithm in this lecture silently ignores it.

12.2.2 Support Count

The support count (how many transactions contain the whole itemset), written $σ (X)$ , is the frequency of that itemset in the entire transaction log. To compute it, we look through every transaction and count how many transactions contain the whole set. Worked example: take the itemset ${milk, bread, diaper}$ . Scanning the five-transaction log, milk + bread + diaper was bought in transaction one and in transaction two, and in no other transaction. That gives a support count of two.

$support count ({milk, bread, diaper}) = 2$

Worked example — support count of a 3-itemset. Suppose the log is the classic five-transaction market basket below.

TID	Items
1	Bread, Milk
2	Bread, Diapers, Beer, Eggs
3	Milk, Diapers, Beer, Coke
4	Bread, Milk, Diapers, Beer
5	Bread, Milk, Diapers, Coke

For $X = {milk, bread, diaper}$ , walk through each transaction and ask: does it contain all three items at once?

TID 1: milk ✓, bread ✓, diaper ✗ → no.
TID 2: bread ✓, diaper ✓, milk ✗ → no.
TID 3: milk ✓, diaper ✓, bread ✗ → no.
TID 4: milk ✓, bread ✓, diaper ✓ → yes.
TID 5: milk ✓, bread ✓, diaper ✓ → yes.

So $σ ({milk, bread, diaper}) = 2$ . Compare with $σ ({milk, bread})$ : TIDs 1, 4, 5 all contain both, so its support count is 3. The smaller the set, the more transactions can contain it — this monotonicity is the engine behind the Apriori principle in Section 12.5.

In symbols, for a transaction log $T = {t_{1}, t_{2}, \dots, t_{N}}$ and an itemset $X$ :

$σ (X) = ∣ {t_{i} : X \subseteq t_{i}, t_{i} \in T} ∣$

where the vertical bars $∣ \cdot ∣$ mean "the number of elements in the set". So $σ (X)$ counts the transactions that contain $X$ .

12.2.3 Frequent Itemsets and Minimum Support

A frequent itemset (an itemset whose support count clears the threshold) is an itemset that satisfies a minimum support threshold. We call an itemset frequent when it has been purchased at least the required number of times — maybe 10 times, 50 times, 500 times, or 1,000,000 times. That threshold, the minimum support (min sup), is a tunable parameter that we, as domain experts, pass to the algorithm.

Scope — the meaning of the threshold. The minimum support is a knob, not a law of nature. The analyst chooses it, and the choice changes the answer: a low min sup (say 1 in a million transactions) returns many patterns, most of them rare and possibly spurious; a high min sup returns only the most common patterns. Rules with very low support may occur simply by chance, and a low-support rule is also usually uninteresting in business — promoting items that customers seldom buy together does not pay. So the threshold is the analyst's trade-off between completeness and reliability. It is the same knob in every algorithm in this lecture: Apriori, and later FP-growth, both take min sup as input and never question it.

Recap + bridge. The vocabulary is now fixed: an itemset is a group of items studied as one unit (with size $k$ for a $k$ -itemset), its support count $σ (X)$ is the number of transactions containing the whole set, and an itemset is frequent when $σ (X)$ clears the analyst-chosen minimum support. Next, we attach the same two ideas — support and a threshold — to rules, which are directional statements $X \to Y$ .

12.3 Association Rules: Support and Confidence

12.3.1 Writing a Rule

Once we have the frequent itemsets, we can write association rules from them. A rule looks like $X \to Y$ , read "X tends to Y": if X is done, there is a high chance that Y will also be done. For example, if milk and diaper are bought, then beer will also be bought — that is an association rule we can write from the transaction log. In the rule $X \to Y$ , the left-hand side X is the condition (the antecedent) and the right-hand side Y is the consequent.

Intuition. A rule is a direction: it points from what we observe (X) to what we expect (Y). The same pair of sides flipped — $Y \to X$ — is a different rule with a different confidence, which is why the arrow matters. Both $X$ and $Y$ are itemsets, and for a well-formed rule they must be disjoint: the same item cannot sit on both sides. Notice also that Y itself may contain several items — ${mi l k, d ia p er} \to {b eer, b r e a d}$ is perfectly legal — the "if X, then Y" phrasing carries no restriction that Y be a single item.

12.3.2 Support of a Rule

The support of a rule $X \to Y$ is the fraction of transactions that contain both X and Y. Written as a formula:

$support (X \to Y) = \frac{support count ( X \cup Y )}{N}$

where $N$ is the number of transactions in the log and $support count (X \cup Y)$ counts transactions containing the combined itemset. Note the difference between support count (a raw count) and support (a fraction). For the rule ${milk, diaper} \to {beer}$ , the itemset ${milk, diaper, beer}$ appears two times in the five-transaction log, so:

$support ({milk, diaper} \to {beer}) = \frac{2}{5}$

Why support is a fraction, not a count. Support answers "how big is this pattern in my data?" — so it must be comparable across stores and logs of different sizes. A pattern in 200 out of 400 transactions (support 0.5) is enormous; the same 200 out of 40,000 (support 0.005) is negligible. The fraction $σ (X \cup Y) / N$ is also exactly the empirical probability $P (X \cup Y)$ that a random transaction contains the whole combined itemset. A rule with very low support is likely to have appeared by chance, so support acts as a first filter for meaningful rules.

12.3.3 Confidence of a Rule

The confidence of a rule measures how often Y will happen when X is happening: given X, what is the chance that Y also happens? The formula:

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

Since support and support count differ only by the same constant $N$ in numerator and denominator, the counts version is equivalent:

$confidence (X \to Y) = \frac{support count ( X \cup Y )}{support count ( X )}$

In probability language, confidence is the conditional probability $P (Y ∣ X)$ — the estimate of "Y given X" read directly from the log.

Worked example: for the rule ${milk, diaper} \to {beer}$ , the support of the combined itemset $X \cup Y = {milk, diaper, beer}$ was already computed as $\frac{2}{5}$ . The support of X alone, ${milk, diaper}$ , is $\frac{3}{5}$ , because milk and diaper were bought together three times in the five transactions. So:

$confidence ({milk, diaper} \to {beer}) = \frac{2/5}{3/5} = \frac{2}{3} \approx 0.67$

Worked example — full computation on the five-transaction log. Reuse the log from Section 12.2:

TID	Items
1	Bread, Milk
2	Bread, Diapers, Beer, Eggs
3	Milk, Diapers, Beer, Coke
4	Bread, Milk, Diapers, Beer
5	Bread, Milk, Diapers, Coke

Step 1 — count the union. $X \cup Y = {milk, diapers, beer}$ . Scanning: TID 3 has all three (milk ✓, diapers ✓, beer ✓); TID 4 has all three (milk ✓, diapers ✓, beer ✓); TIDs 1, 2, 5 each miss at least one. So $σ (X \cup Y) = 2$ .

Step 2 — count the left side. $X = {milk, diapers}$ . TIDs 3, 4, 5 contain both; TIDs 1, 2 miss one. So $σ (X) = 3$ .

Step 3 — divide. $confidence = \frac{2}{3} \approx 0.67$ .

Sense-check. Of the three transactions that contain milk and diapers, two also contain beer — so "about two-thirds of the time, milk+diapers is accompanied by beer" matches the arithmetic exactly.

In words: if X is happening, there is a 67% chance that Y will also happen. That 0.67 (two-thirds) is the confidence of the rule. The higher the confidence, the better the rule. If we can say with 100% confidence that whenever X happens, Y always happens, the confidence of the rule is extremely high.

12.3.4 Rules from the Same Itemset

Look at the rules written on the right-hand side of the screen example. The item sets behind all of them are the same — milk, diaper, and butter/beer depending on the version of the table — and because the itemset is the same, the support is the same for every rule. The support of a rule only depends on $X \cup Y$ , and when $X \cup Y$ is the same set, the support cannot change. Confidence, however, is different for each rule, because the denominator $support (X)$ changes when the left-hand side changes. In the example, the confidence of the first rule is 67% while the confidence of the second rule is 100%. That is why support and confidence are two different performance measures: rules originating from the same itemset have identical support but may have different confidence.

Worked example — six rules from one 3-itemset. Take the frequent itemset ${B, D, M} = {beer, diapers, milk}$ , with $σ ({B, D, M}) = 2$ , $σ ({B, D}) = 2$ , $σ ({B, M}) = 2$ , $σ ({D, M}) = 3$ in the five-transaction log. Splitting the three items between left and right sides gives six distinct rules, all with the same support:

Rule	$σ (X \cup Y)$	$σ (X)$	Confidence
${B, D} \to {M}$	2	2	$2/2 = 1.0$ (100%)
${B, M} \to {D}$	2	2	$2/2 = 1.0$ (100%)
${D, M} \to {B}$	2	3	$2/3 \approx 0.67$ (67%)
${B} \to {D, M}$	2	2	$2/2 = 1.0$ (100%)
${M} \to {B, D}$	2	3	$2/3 \approx 0.67$ (67%)
${D} \to {B, M}$	2	3	$2/3 \approx 0.67$ (67%)

Every row has support $\frac{2}{5}$ , yet confidence ranges from 67% to 100%. The reason is visible in the table: the numerator never changes, but the denominator $σ (X)$ changes with the left side. This is why a single itemset produces rules of very different quality — and why both measures are reported together.

Formalize — the two measures, side by side. For a rule $X \to Y$ in a log of $N$ transactions:

$support (X \to Y) = \frac{σ ( X \cup Y )}{N}, confidence (X \to Y) = \frac{σ ( X \cup Y )}{σ ( X )}$

with $σ$ denoting support count. Support says how often the rule is applicable to the data; confidence says how reliable it is when it is applicable. In probability terms: $support = P (X \cup Y)$ and $confidence = P (Y ∣ X)$ . A rule is called strong when it satisfies both a minimum support and a minimum confidence threshold. The whole mining problem is then: given the thresholds $min sup$ and $min conf$ , find all strong rules.

12.3.5 Student Questions and Answers

Q: Why is the confidence 100% for the second rule? A: Put the formula to work. Confidence is support of X and Y divided by support of X. The support of the combined itemset (milk, butter, diaper) goes in the numerator and the support of the left-hand side (milk and butter) goes in the denominator. Plug in the numbers and you get the confidence. The screen table did not match the example — there is no butter in the stated item list, so the instructor conceded the table was wrong — but the formula itself is the takeaway: plug the correct counts in and you get the answer.

Q: Why is the confidence of the second rule higher than the first — both come from the same itemset? A: Because only the numerator is shared. The numerator $σ (X \cup Y)$ is fixed by the combined itemset, but the denominator $σ (X)$ belongs to the left-hand side, and the left-hand side differs between rules. Whenever $σ (X)$ happens to equal $σ (X \cup Y)$ — meaning every transaction that contains X already contains the whole union — the rule gets confidence 1.0. That is precisely the second rule's situation: milk and butter never appear without diaper, so given milk and butter, diaper is guaranteed. Confidence is not a property of the itemset; it is a property of the split you choose.

Recap + bridge. A rule $X \to Y$ is scored twice: support $\frac{σ ( X \cup Y )}{N}$ (how common the pattern is) and confidence $\frac{σ ( X \cup Y )}{σ ( X )}$ (how reliably Y follows X, the conditional probability $P (Y ∣ X)$ ). Rules from one itemset share support but not confidence. Now that the measures exist, we can ask the cost question: how many rules and itemsets are there to score, and can we afford to score them all?

12.4 Why the Brute-Force Approach Is Too Expensive

12.4.1 The Brute-Force Recipe

Given a set of transactions, a brute-force approach works like this: generate every possible association rule, then compute support and confidence for each rule, then prune (delete) the rules whose support or confidence falls below the thresholds, and finally keep only the rules that are relevant. The problem: first we generate all possible combinations, then we prune. That can be an extremely expensive exercise.

Why do we need the thresholds at all? Because thousands of rules can be derived from a transaction log, and we are only interested in rules that happen very frequently — those are the ones we can market or take business benefit from. So we select rules based on minimum support and minimum confidence.

Scope — the two costs of brute force. The naive recipe pays twice. First, it generates every combination of items — most of which are infrequent and useless — and second, for each candidate it scans the transaction log to count support. Both costs explode with the number of items: generating combinations grows exponentially with $D$ , and counting each candidate costs one comparison against every transaction. Even for the small five-transaction log used in class, Tan's analysis of a six-item example shows that more than 80% of all rules are discarded after applying the thresholds — meaning more than 80% of the computation was wasted work. The whole point of this lecture is to stop doing that wasted work.

12.4.2 Counting the Candidates and Rules

To see how bad brute force is, count the possibilities. If a store sells $D$ unique items, then the number of possible candidate itemsets is:

$candidate itemsets = 2^{D}$

Every item is either in the set or not, so all subsets of the item universe are candidates. If the store sells five items, $2^{5} = 32$ candidate itemsets are possible.

The number of possible association rules is:

$R = 3^{D} - 2^{D + 1} + 1$

Where the rule-count formula comes from. A rule $X \to Y$ splits the $D$ items into three groups: items in $X$ (left side), items in $Y$ (right side), and items in neither. Every item independently chooses one of the three groups, giving $3^{D}$ raw assignments. Two corrections are needed: the empty left side $X = \emptyset$ is not a legal rule (there are $2^{D}$ of those — every choice of $Y$ ), and so is the empty right side $Y = \emptyset$ (another $2^{D}$ , every choice of $X$ ). But the case where both sides are empty was subtracted twice, so we add it back once:

$R = 3^{D} - 2^{D} - 2^{D} + 1 = 3^{D} - 2^{D + 1} + 1$

This is the standard formula (Eq. 6.3 in the reference book), and it matches the form stated in class exactly.

For five items that already means 32 candidate itemsets to check and on the order of 180 potential rules. And every one of these candidates has to be counted against the transaction log, which itself might run into millions of transactions.

Worked example — the numbers for $D = 5$ and $D = 6$ .

Candidate itemsets, $D = 5$ : $2^{5} = 32$ (one per subset of the five items, including the empty set, which we ignore in practice).
Association rules, $D = 5$ : $R = 3^{5} - 2^{6} + 1 = 243 - 64 + 1 = 180$ .
Association rules, $D = 6$ : $R = 3^{6} - 2^{7} + 1 = 729 - 128 + 1 = 602$ — the value quoted in the class discussion ("601", with the components 64 and 62 floating around) is a misreading of this standard example from the reference book, which uses a six-item store. For the five-item store the true count is 180: 243 minus 64 plus 1.

Sense-check. The formula must always exceed the number of candidate itemsets' worth of rules; and indeed $3^{D} - 2^{D + 1} + 1 > 2^{D}$ for $D \geq 2$ (180 > 32 at $D = 5$ ). Also, since every rule needs a nonempty $X \cup Y$ , $R$ can never exceed the $2^{D}$ itemsets times the rule splits of each — the formula's value of 180 is comfortably below that loose bound.

12.4.3 The Scale Problem in Real Stores

Real-world: a typical mall — like Lance mall or D-Mart — sells thousands of items, not five. If a store sells 5,000 items, the number of candidate itemsets and candidate rules explodes into astronomically large numbers, and each candidate must be matched against a transaction log with millions of rows. Generating the candidates is a challenging task, and counting the support is also a challenging task. This is exactly why we do not follow a brute-force approach; we want an efficient method that is quick, fast, and effective.

Pitfalls.

Underestimating $2^{D}$ . "It is only exponential" hides the truth: $2^{5000}$ is a number with about 1,505 digits — every atom-in-the-universe-style comparison fails. No amount of clever counting code fixes an exponential candidate set.
Confusing the two formulas. $2^{D}$ counts itemsets (subsets); $3^{D} - 2^{D + 1} + 1$ counts rules (directional splits). Students routinely plug the rule formula in when counting itemsets, or vice versa.
Forgetting the counting cost per candidate. The number of candidates is only half the problem — each surviving candidate must be matched against the entire transaction log. With $M = 2^{D} - 1$ candidate itemsets and $N$ transactions of width $w$ , the brute-force count costs $O (N M w)$ comparisons, and even the matching step alone is infeasible at real-store scale.

Recap + bridge. Brute force is a two-stage disaster: it enumerates $2^{D}$ itemsets and $3^{D} - 2^{D + 1} + 1$ rules, then counts every survivor against millions of transactions. At D-Mart scale both stages are impossible. The escape route is the observation that itemsets are not independent: if an itemset is frequent, its subsets must be frequent too — and that single fact, the Apriori principle, is the next topic.

12.5 The Apriori Principle

12.5.1 The Principle

The Apriori principle (the anti-monotone property: support never increases when an itemset grows) helps us reduce the number of candidate itemsets we have to consider. It says: if an itemset is frequent, then all its subsets must also be frequent. Formally, if $X \subseteq Y$ , then:

$support (X) \geq support (Y)$

The reason is mechanical: any transaction that contains Y also contains X, because X is a subset of Y, so Y can never appear in more transactions than X does. This property is also called the anti-monotone property, and we can exploit it like anything. If an itemset is frequent — say $A B$ is frequent — then all its subsets ( $A$ and $B$ individually) are also frequent.

Analogy — the school that can only shrink. Imagine a school where you collect the set of students who take all three of physics, chemistry, and math. That set can never be bigger than the set who take just physics, or just chemistry — an extra requirement can only shrink a group, never grow it. Support behaves the same way: every extra item added to an itemset can only remove transactions from its count. Formally, "if $X \subseteq Y$ then $σ (X) \geq σ (Y)$ " — a superset can never out-frequent its subset. This is called anti-monotone because support falls as the set grows: the measure is monotonically decreasing in the subset order.

12.5.2 The Inverted Use: Pruning Supersets

The same property, read backwards, gives us the pruning power. If $A B$ is infrequent, then every superset of $A B$ will also be infrequent. Why? Because if any superset of $A B$ were frequent, then by the principle its subset $A B$ would have to be frequent — a contradiction. So the moment we find that $A B$ is infrequent, we do not have to generate its supersets, we do not have to count their support, and they will not contribute any rules either. The complexity of the whole calculation drops, because we can discard an infrequent itemset and all its supersets in one shot.

Formalize — the two directions of the same statement.

Forward (frequency travels down): if $Y$ is frequent, every subset $X \subseteq Y$ is frequent. This is the anti-monotone property in its positive form.
Backward (infrequency travels up): if $X$ is infrequent, every superset $Y \supseteq X$ is infrequent. This is the same statement by contraposition: $frequent (Y) \Rightarrow frequent (X)$ is logically equivalent to $\neg frequent (X) \Rightarrow \neg frequent (Y)$ .

Both directions are used in Apriori: the forward form is how the algorithm proves candidate subsets need no checking, and the backward form is the pruning engine — an infrequent itemset kills its entire upward branch of supersets in the itemset lattice at once, without generating or counting any of them.

Worked example — the chain of supersets. Suppose, in a five-item world ${A, B, C, D, E}$ , we count supports and find $σ (A B) = 1$ below min sup. The Apriori principle then guarantees, with no further counting:

$A B C$ is infrequent (it contains $A B$ ),
$A B C D$ is infrequent (it contains $A B C$ ),
$A B C D E$ is infrequent (it contains $A B C D$ ).

That is the full pruning chain: one support count of $A B$ eliminates $A B C$ , $A B D$ , $A B E$ , $A B C D$ , $A B C E$ , $A B D E$ , $A B C D E$ , and every other superset of ${A, B}$ — all in one shot. Contrast with what we know about $C D$ or $D E$ : neither contains $A B$ , so the principle says nothing about them; they must each be counted on their own.

12.5.3 Student Questions and Answers

The class probed the principle from several directions, and each question sharpened one boundary of the statement.

Q: The screen mentions DE. Is DE frequent then? Or CD? If AB is infrequent, what about DE? A: We are not commenting on DE or CD at all. What was said is this: if AB is infrequent, then all its supersets — ABC, ABCD, ABCDE — will also be infrequent. ABC contains AB, so ABC is infrequent; ABCD contains ABC, so ABCD is infrequent; and so on. But CD and DE are not supersets of AB, so we know nothing about them. We cannot say they are frequent and we cannot say they are infrequent until we check. If ABC is infrequent, we can discard ABCD as well, and then ABCDE too — whether it would also become infrequent through some other part of the diagram does not matter; some part of it is infrequent for sure, so the whole set is infrequent.

Q: If AB is infrequent, can we say with 100% surety that ABCD will be infrequent? A: Yes. If AB is infrequent, then ABC is infrequent with 100% confidence; and from ABC we can say ABCD is infrequent; and from ABCD we can say ABCDE is infrequent. CD might still be frequent — we are not commenting on CD. The chain only flows upward through supersets. Invert the picture: if ABCDE is frequent, then all its subsets are frequent — ABCD, ABCE, ABC, AB, A — every one of them. That is the same principle from the other side.

Q: If A is frequent and B is frequent, will AB be frequent? A: The Apriori principle does not say anything on this question. It says that the subsets of a frequent set are frequent, not that combining two frequent items produces a frequent pair. Still, we can understand that AB will be frequent in practice: both items occur often, so the pair will usually clear the threshold too. But that is our intuition, not the principle. The principle only guarantees the subset direction.

The instructor then caught a slip of his own wording and corrected the direction of the principle on the spot.

Q: One student kept flipping the direction: if an item set is infrequent, does that make every subset (the "children") infrequent too? A: No — that claim is backwards, and the instructor corrected it on the spot after misspeaking it once; the correction means: read the Apriori principle again — if an itemset is frequent, then all its subsets will also be frequent. So if ABCD is frequent, then ABC, ABE, and so on are frequent; if ABC is frequent then AB is frequent. Infrequency goes the other way: if an itemset is infrequent, all its supersets are infrequent. The reliable memory aid: whenever we talk about infrequency, we talk about supersets; whenever we talk about frequency, we talk about subsets. Do not merge these two statements — if we try to overlap them, we cannot conclude anything. Whichever direction the question asks, check which side of the principle it is on.

Q: Several students asked the same follow-up: if A is frequent and B is frequent, is AB guaranteed frequent? A: No guarantee — and it matters for the exam. The principle is one-directional: frequent sets imply frequent subsets; two frequent items do not imply a frequent pair, because the two items may co-occur far less often than each appears alone. The test to remember: a rule about supersets can only ever be concluded from an infrequent starting point; a rule about subsets only from a frequent starting point. Crossing the directions is exactly where the marks are lost.

Pitfalls.

Reversing the direction. "AB infrequent ⇒ A or B infrequent" is false — the infrequent pair can easily be made of two very frequent singles (their co-occurrence is what is rare). Infrequency only propagates up to supersets.
Claiming certainty about unrelated sets. If $A B$ is infrequent, $C D$ 's status is unknown until counted. Students who declare $C D$ infrequent "by the principle" are misapplying it.
Merging the two statements. "Frequent ⇒ subsets frequent" and "infrequent ⇒ supersets infrequent" are contrapositives of the same fact, not two facts — but reasoning as though either direction can be freely flipped is the classic error the professor flagged in class.

Recap + bridge. The Apriori principle (anti-monotonicity of support) gives a free pruning oracle: count one infrequent itemset and its whole family of supersets dies without a single further scan. This principle is the fuel for the Apriori algorithm's four-step loop, which we now run on a real transaction log.

12.6 The Apriori Algorithm

12.6.1 The Notation

The Apriori algorithm uses two kinds of item sets. The class calls them $F_{k}$ , the frequent itemsets of size $k$ , and $L_{k}$ , the candidate itemsets of size $k$ . (Standard textbook notation usually writes $C_{k}$ for candidates and $F_{k}$ for frequent; here the class labels the candidates $L_{k}$ .) First we generate all the candidates, and then those candidates whose support is greater than or equal to the minimum support (min sup) are called frequent itemsets.

Notation. The reference books write $C_{k}$ for the candidate $k$ -itemsets and $L_{k}$ for the frequent $k$ -itemsets (the $L$ standing for "large", the historical name for frequent sets). This lecture swaps the second symbol: $L_{k}$ is the candidate set and $F_{k}$ the frequent set. Whatever the letters, the pipeline is identical: candidates → count → keep the frequent ones. Use the lecture's letters on the exam, and note the equivalence so a textbook page does not confuse you.

12.6.2 The Four Steps in a Loop

The algorithm is simple. Start with $k = 1$ : generate the candidate one-itemsets $L_{1}$ (all single items), count their support in the log, and keep the ones that meet min sup as $F_{1}$ , discarding the rest. Then enter a loop that repeats until $F_{k}$ becomes empty:

Candidate generation. Generate the next-level candidates $L_{k + 1}$ — for example, from $F_{1}$ we generate two-itemsets, so $L_{2}$ . The next candidates are built from the previous frequent itemsets, as described in Section 12.8.
Candidate pruning. Prune candidates using the Apriori principle: if an item was infrequent at the previous level, then every superset containing it will also be infrequent, so we can drop those candidates immediately — we do not even generate or explore them.
Support counting. For the candidates that remain, count the support (the frequency) in the transaction log.
Candidate elimination. Based on the support counts, remove the candidates whose support is below min sup, keeping only the frequent ones.

Then repeat the same four steps for three-itemsets, four-itemsets, five-itemsets, and so on, until the final itemset becomes empty — that is when $F_{k} = \emptyset$ and the loop stops.

Formalize — the loop in pseudocode.

L1 = all single items                 # candidate 1-itemsets
F1 = {X in L1 : sigma(X) >= min sup}  # frequent 1-itemsets
k = 1
while Fk is not empty:
    L(k+1) = candidates from Fk       # step 1: generate (Section 12.8)
    prune L(k+1) by Apriori principle # step 2: prune
    count sigma(X) for X in L(k+1)    # step 3: scan the log once
    F(k+1) = {X in L(k+1) : sigma(X) >= min sup}  # step 4: eliminate
    k = k + 1
return F1 U F2 U ... U Fk

Each pass through the loop needs exactly one scan of the transaction log, and every level is built only on the frequent sets of the previous level — infrequent sets never breed children. That is the entire trick of Apriori: the candidate set at level $k + 1$ comes from $F_{k}$ , so the exponential space of Section 12.4 is never materialized.

Scope — when the loop stops. The loop ends when no frequent $k$ -itemset exists, and from then on nothing larger can ever be frequent (Apriori principle). There is a hard ceiling anyway: an itemset can be at most as large as the widest transaction. In a store with 5,000 items, you will rarely see transactions wider than a few dozen items — but the number of candidates at each level, not the ceiling, is what dominates the cost.

12.6.3 Worked Example: Four Transactions, Minimum Support 2

Take this simple log with four transactions:

Transaction	Items
1	1, 3, 4
2	2, 3, 5
3	1, 2, 3, 5
4	2, 5

The minimum support is given as 2.

Level 1 ( $L_{1} \to F_{1}$ ). Generate all one-itemsets: ${1}, {2}, {3}, {4}, {5}$ . Count support in the log:

Itemset	Support
${1}$	2
${2}$	3
${3}$	3
${4}$	1
${5}$	3

Item 4 has support 1, less than the minimum support 2. By the Apriori principle, any superset containing 4 will be infrequent, so we do not even explore it: no generation of candidates with 4, no support counting for them, and no rule generation later. The frequent one-itemsets are $F_{1} = {{1}, {2}, {3}, {5}}$ .

Level 2 ( $L_{2} \to F_{2}$ ). Candidate generation: all two-itemsets that avoid item 4 — ${1, 2}, {1, 3}, {1, 5}, {2, 3}, {2, 5}, {3, 5}$ . Candidate pruning: none of these contains an infrequent single item, so all six survive. Support counting:

Itemset	Support	Where it appears
${1, 2}$	1	transaction 3 only
${1, 3}$	2	transactions 1, 3
${1, 5}$	1	transaction 3 only
${2, 3}$	2	transactions 2, 3
${2, 5}$	3	transactions 2, 3, 4
${3, 5}$	2	transactions 2, 3

Candidate elimination: ${1, 2}$ has support 1 and ${1, 5}$ has support 1, both below 2, so both are dropped. Note the in-class correction on ${1, 5}$ : its support count is 1, not 2 — the instructor first wrote a wrong value, then corrected it ("one five will be one... my bad. Yeah, one. So this will also be removed"). The frequent two-itemsets are $F_{2} = {{1, 3}, {2, 3}, {2, 5}, {3, 5}}$ .

Level 3 ( $L_{3} \to F_{3}$ ). Going back to the top of the loop, generate three-itemsets by merging two frequent two-itemsets that share a common first element (the prefix rule from Section 12.8). ${2, 3}$ and ${2, 5}$ share the prefix 2, so they merge into ${2, 3, 5}$ ; the other pairs do not share a prefix. Pruning: by the Apriori principle, supersets of the infrequent pairs ${1, 2}$ and ${1, 5}$ are also infrequent, so nothing with 1–2 or 1–5 is generated. Support counting: ${2, 3, 5}$ appears in transactions 2 and 3, so its support count is 2, equal to min sup, and it is frequent. All other three-itemsets have support below 2 and are not considered.

Level 4. With only one frequent three-itemset, no four-itemset can be generated — $L_{4}$ is the null set — and the loop stops. The final frequent itemsets are ${1, 3}, {2, 3}, {2, 5}, {3, 5}$ and ${2, 3, 5}$ , from which the association rules are then written.

Worked example — the full trace, with every count verified. Let us re-verify each number directly from the four transactions (T1 = {1,3,4}, T2 = {2,3,5}, T3 = {1,2,3,5}, T4 = {2,5}).

Level 1. $σ ({1})$ : T1 ✓, T3 ✓ → 2. $σ ({2})$ : T2, T3, T4 → 3. $σ ({3})$ : T1, T2, T3 → 3. $σ ({4})$ : T1 only → 1 (below 2 → dropped). $σ ({5})$ : T2, T3, T4 → 3. So $F_{1} = {{1}, {2}, {3}, {5}}$ .

Level 2. All six pairs from $F_{1}$ . ${1, 2}$ : appears in T3 only → 1 (dropped). ${1, 3}$ : T1, T3 → 2 (kept). ${1, 5}$ : T3 only → 1 (dropped — the in-class corrected count). ${2, 3}$ : T2, T3 → 2 (kept). ${2, 5}$ : T2, T3, T4 → 3 (kept). ${3, 5}$ : T2, T3 → 2 (kept). So $F_{2} = {{1, 3}, {2, 3}, {2, 5}, {3, 5}}$ .

Level 3. Merge pairs sharing the first element: only ${2, 3}$ and ${2, 5}$ share prefix 2 → candidate ${2, 3, 5}$ . Pruning check: its 2-subsets ${2, 3}$ , ${2, 5}$ , ${3, 5}$ are all in $F_{2}$ → survives. Count: T2 has all of 2, 3, 5 ✓; T3 has all ✓; T1 and T4 miss items → $σ ({2, 3, 5}) = 2$ → kept. $F_{3} = {{2, 3, 5}}$ .

Level 4. One frequent 3-itemset cannot form a pair with a shared 2-prefix → $L_{4} = \emptyset$ → stop.

Final answer: frequent itemsets ${1, 3}$ , ${2, 3}$ , ${2, 5}$ , ${3, 5}$ , ${2, 3, 5}$ .

Sense-check. Every frequent itemset must have all its subsets frequent: check ${2, 3, 5}$ — its three pairs ${2, 3}, {2, 5}, {3, 5}$ are all in $F_{2}$ ✓, and its singles are all in $F_{1}$ ✓. No itemset containing item 4 survived — matching the Level-1 prune ✓.

12.6.4 Student Questions and Answers

Two students asked to recheck the loop's internal machinery, so the professor compared the two steps directly.

Q: How are candidate pruning and candidate elimination different? A: Candidate pruning is done using the Apriori principle. If an item is infrequent, every superset will also be infrequent, so we do not want to consider them — we do not even generate them as candidate sets. That is pruning: it happens before support counting. Candidate elimination is done with the help of the support count: we calculate the support of the candidates we did generate, and those whose support is less than minimum support are discarded. Pruning works on the subset theory before counting; elimination works on counted support values after counting.

Q: Can you explain step number four, candidate elimination again? A: It is simple. You have the support counts you computed. Remove those candidates whose support is less than the minimum support — eliminate the infrequent candidates, leaving only those that are frequent. For example, a candidate whose support was 1 with a minimum support of 2 is infrequent, so we drop it. That is step four: candidate elimination using the counted supports.

Pitfalls.

Pruning and elimination are different steps. Pruning happens before counting and uses only the Apriori principle (no counts needed — it kills candidates whose subsets are infrequent). Elimination happens after counting and uses the measured support. Doing elimination twice or pruning twice changes nothing; swapping their order does not work, because pruning needs no counts while elimination is impossible without them.
Counting candidates that could not survive. At level 2, a candidate containing an infrequent item (here, item 4) is guaranteed infrequent — counting it wastes a scan pass. This is the most common efficiency mistake when running Apriori by hand.
Generating level- $k + 1$ candidates from non-frequent sets. Only $F_{k}$ feeds candidate generation. Merging from $L_{k}$ (which still contains dropped items) resurrects supersets the principle already killed.

Recap + bridge. Apriori climbs the itemset sizes one level at a time; at each level it generates candidates only from the previous frequent set, prunes with the principle, counts support in one scan, and eliminates below-threshold sets — stopping when a level produces nothing. We have now seen the loop on paper with four transactions. The next section runs the identical loop on a bigger, item-named example to see how the pruning cascade looks in practice.

12.7 The Apriori Algorithm in Pictures: Five Transactions, Minimum Support 3

12.7.1 The Setup

The screen version of the same process uses a log of five transactions and the items beer, bread, diaper, egg, coke, and milk. The minimum support is 3. The purpose is to visualize the four steps at each level, because writing everything out by hand gets clumsy.

Visual intuition — the itemset lattice. Draw all subsets of the six items as a lattice: the empty set at the top, the six singles beneath it, then all 15 pairs, all 20 triples, and so on down to the full 6-item set. Apriori moves through this diagram level by level, top to bottom. The anti-monotone property cuts whole branches: when an itemset is crossed out as infrequent, the entire subtree hanging beneath it (all its supersets) is dead on arrival. In the picture, the infrequent items egg and coke mark two branches at the very top of the lattice, and no candidate anywhere below them is ever examined. That is what "in pictures" means here — the lattice shows you the pruned region at a glance, and the four-step loop is the machine that sweeps across it.

12.7.2 Level 1: Egg and Coke Are Infrequent

Generate $L_{1}$ , all one-itemsets, and count support from the log. Egg is infrequent (its support count is below 3), so by the Apriori principle every superset containing egg is infrequent — for example, the set {beer, bread, diaper, egg} will also be infrequent. Coke is infrequent because its support count is 2, less than the minimum support of 3, so any set containing coke is also infrequent — for example, {beer, coke, diaper, milk}. The rest of the one-itemsets are fine, so $F_{1}$ keeps the frequent singles and drops egg and coke.

Scope — the choice of min sup changes the outcome. With min sup = 3 here, the two least common items (egg at 2, coke at 2) vanish at level 1 and take every superset with them. Had we set min sup = 2, both would have survived and the whole lattice below them would remain alive — the final answer set grows dramatically. Apriori's efficiency and its answer both depend on this one number, which is why it is the analyst's responsibility, not the algorithm's.

12.7.3 Level 2 and Beyond

Inside the loop, generate two-itemsets. Because egg and coke were infrequent, no two-itemset contains egg or coke — the candidate generation and the candidate pruning happen together, and we never even explore those combinations. After support counting, two of the two-itemsets fall below minimum support: one pair transcribed as "bread and butter" (though the stated item list has no butter) with support 2, and {beer, milk} with support 2. Candidate elimination removes both, leaving four candidate two-itemsets. The loop then repeats: three-itemsets, four-itemsets, and so on, running all four steps at each level until a level produces the null set.

A correction (screen label). The class's stated item list — beer, bread, diaper, egg, coke, milk — contains no butter. The pair "bread and butter" spoken in class is therefore a mishearing of some pair from the real list (the professor's table), and what matters for the method is the pattern, not the label: it is a 2-itemset whose support is 2, below min sup 3, so it is eliminated alongside {beer, milk}. Treat every dropped pair with support < 3 the same way — eliminated, and every superset of it pruned.

Worked example — the level-2 arithmetic (supports reconstructed from the five-transaction log). The pair table used in class reports two pairs at support 2 (one is {beer, milk}, the other the mislabeled pair) and four pairs at support ≥ 3. Counting any candidate pair works exactly like Section 12.6: scan each of the five transactions, tick the ones containing both items, and compare the total with 3. For example, if {bread, milk} appeared in transactions 1, 3, and 5, its support would be 3 — kept; a pair seen only twice — dropped. The four surviving pairs then become the source set for level 3, exactly as in the four-transaction example.

12.7.4 Student Questions and Answers

One student was looking at a different table on the screen, and the confusion resolved into a useful rule of thumb.

Q: Why will item five be infrequent? Its support is 4. And this row — TID 5 — will it also be infrequent? A: Two tables are on screen, so the instructor asked which one the student meant: the TID-and-item table. In that table, the TID-five row contains coke, and since coke is infrequent, this set will also be infrequent. Yes, you are correct: any row that contains an infrequent item is itself infrequent, because it is a superset of that infrequent item.

Recap + bridge. In the lattice picture, the four-step loop sweeps downward level by level; infrequent items like egg and coke prune entire branches so their supersets are never generated or counted. This example also shows the loop running on a natural-language item set — and how a single min sup choice governs the whole search. Now we zoom into step 1 of the loop: exactly which pairs of frequent sets may be merged into the next level's candidates?

12.8 Candidate Generation by Merging: $F_{k - 1} \times F_{k - 1}$

12.8.1 The Merging Rule

Candidate generation has a fixed way of working. To generate four-itemsets, for example, we use the frequent three-itemsets: we merge pairs of frequent $k - 1$ itemsets to form candidate $k$ -itemsets. The step is called $F_{k - 1} \times F_{k - 1}$ . While merging, we can merge only those two itemsets whose first $k - 2$ elements are common — the prefix must match. At $k = 4$ , $k - 2 = 2$ , so the two-itemset prefix (the first two elements) must be the same. For example, $A B C$ and $A B D$ have the same prefix $A B$ , so we can merge them into the four-itemset $A B C D$ . Likewise $A B C$ and $A B E$ merge into $A B C E$ , and $A B D$ and $A B E$ merge into $A B D E$ . But $A B D$ and $C D E$ cannot be merged, because their two-prefix parts ( $A B$ versus $C D$ ) do not match — and the same for any pair whose prefixes differ. We have to try all possible combinations, but only matching-prefix pairs produce candidates.

Formalize — the merge condition. Let $A = {a_{1}, a_{2}, \dots, a_{k - 1}}$ and $B = {b_{1}, b_{2}, \dots, b_{k - 1}}$ be two frequent $(k - 1)$ -itemsets, each written in sorted order. They may be merged into the candidate $k$ -itemset $A \cup B$ if and only if:

$a_{i} = b_{i} for i = 1, 2, \dots, k - 2 and a_{k - 1} \neq = b_{k - 1}$

That is: the first $k - 2$ elements (the prefix) are identical, and the last elements differ. The differing last element is what keeps the merged set of size $k$ rather than $k - 1$ . At $k = 4$ , the prefix has length $2$ : $A B C$ and $A B D$ share prefix $A B$ and differ in the third position, so the merge $A B C D$ is legal; $A B D$ and $C D E$ share no 2-prefix, so no candidate is produced.

Why the prefix rule exists. Without it, the same candidate would be generated many times over — ${B r e a d, D ia p er s, M i l k}$ could arise by merging ${B r e a d, D ia p er s}$ with ${M i l k}$ , or ${B r e a d, M i l k}$ with ${D ia p er s}$ , or ${D ia p er s, M i l k}$ with ${B r e a d}$ . Requiring a matching sorted prefix makes the merge deterministic: every candidate is produced exactly once. This is the standard rule in the reference books (the "join step" of Apriori), and the completeness argument is: if $A B C D$ is truly frequent, then its $(k - 1)$ -subsets $A B C$ and $A B D$ are frequent (Apriori principle), they share the 2-prefix $A B$ , and the merge will find it — no frequent itemset is ever missed.

Worked example — the full merge table for $k = 4$ from $F_{3}$ . Suppose the frequent 3-itemsets are ${A, B, C}, {A, B, D}, {A, B, E}$ . Sort each (already sorted here), then pair them up and test the 2-prefix:

Pair	Prefixes	Merge legal?	Candidate
$A B C, A B D$	$A B = A B$	✓ (differ in 3rd: C vs D)	$A B C D$
$A B C, A B E$	$A B = A B$	✓ (C vs E)	$A B C E$
$A B D, A B E$	$A B = A B$	✓ (D vs E)	$A B D E$
$A B D, C D E$	$A B \neq = C D$	✗	—
$A B C, C D E$	$A B \neq = C D$	✗	—
$A B E, C D E$	$A B \neq = C D$	✗	—

Sense-check. Each candidate has size 4 and contains two frequent 3-subsets (e.g., $A B C D \supset A B C, A B D$ ✓); each frequent pair produced at most one candidate; and no candidate repeats. Note the candidates then still face the Apriori pruning step — every $(k - 1)$ -subset must be frequent — so after merging, $A B C D$ 's other two subsets ( $A C D, B C D$ ) would need checking against $F_{3}$ before it is counted.

12.8.2 Student Questions and Answers

Two student questions probed the merge rule's boundary conditions.

Q: BD and DE both contain D — BD is common to BC... does the order matter? Can we merge them? A: Yes, the order matters. To merge two itemsets we need the prefix part — the first $k - 2$ elements — to be the same. ${B, D}$ has prefix $B$ , while ${D, E}$ has prefix $D$ ; they do not match, so you cannot merge them. If the first two elements are not identical, no four-itemset comes out of that pair, even if the sets share some element in the middle.

Q: How do we actually generate $L_{4}$ from $F_{3}$ ? A: For generating four-itemsets, you would have already completed the three-itemset level and you would have the frequent three-itemsets. Candidate generation for level 4 is done with the help of those frequent three-itemsets: merge multiple of them to come up with four-itemsets, but merge only those pairs whose prefix of length $k - 2 = 2$ matches. $A B C$ and $A B D$ merge into $A B C D$ ; $A B D$ and $A B E$ merge into $A B D E$ ; and so on. Pairs with different two-prefixes are not merged.

Pitfalls.

Order matters. ${B, D}$ and ${D, E}$ share the item $D$ but not the first element — with sorted items, the prefix of a 2-itemset is just its first item, and $B \neq = D$ . Shared middle elements never count.
Merging without pruning afterwards. The prefix rule guarantees each candidate appears once, but a merged candidate may still have an infrequent $(k - 1)$ -subset other than the two that formed it. The Apriori pruning step after merging is mandatory — in the lecture's loop it is exactly step 2.
Merging itemsets that are not frequent. The merge pool is $F_{k - 1}$ , the frequent $(k - 1)$ -itemsets only. Merging from the candidate set $L_{k - 1}$ regenerates supersets that the principle already condemned.

Recap + bridge. Candidate generation is a fixed, deterministic procedure: merge pairs from $F_{k - 1}$ whose first $k - 2$ elements match, then prune by the principle. The lecture has now covered the full Apriori loop, and we can see where it will ultimately strain: every level needs a fresh scan of the whole log. Sections 12.9 and 12.10 close that story — first, how rules come out of the final frequent itemsets, then the cost problem that motivates a tree.

12.9 From Frequent Itemsets to Rules

12.9.1 The Last Step

Once the frequent itemsets are found, we generate the rules out of them. Suppose we have the frequent itemset {beer, diaper, milk}. From it we can generate rules like {beer, diaper} → {milk} or {beer} → {diaper, milk}. We do not take all possible rules from the frequent itemsets, though — from a single itemset there can be many rules. We only want the rules that have a high confidence, say a 75% chance or more: if X is done, there is at least a 75% chance that Y will also happen. We can define such a confidence threshold, because a lesser-confidence rule might not be very significant. The two-stage picture, then, is: first find the itemsets with support greater than or equal to min sup, then within those itemsets find the rules with high confidence.

Formalize — rule generation from one frequent itemset. For a frequent itemset $l$ with support count $σ (l)$ :

Enumerate every nonempty proper subset $s$ of $l$ .
For each $s$ , form the rule $s \to (l - s)$ .
Compute its confidence:

$confidence (s \to (l - s)) = \frac{σ ( l )}{σ ( s )}$

Keep the rule only if $confidence \geq min conf$ .

Because $l$ is frequent, every rule produced this way automatically satisfies minimum support — support was already guaranteed at the itemset stage. That is why the rule stage only checks confidence. A strong rule is one that passes both thresholds, and the set of strong rules is the final deliverable of the whole lecture.

Worked example — six rules from {beer, diaper, milk}, then the threshold filter. Take the log of Section 12.3 with $σ ({B, D, M}) = 2$ . All six splits are candidates; their confidences (computed in Section 12.3) are:

Rule	Confidence
${B, D} \to {M}$	100%
${B, M} \to {D}$	100%
${D, M} \to {B}$	67%
${B} \to {D, M}$	100%
${M} \to {B, D}$	67%
${D} \to {B, M}$	67%

With min conf = 75%, only the three 100% rules survive as strong rules; the three 67% rules are discarded as not significant enough.

Sense-check. Note the two-stage ordering in action: all six rules share support $\frac{2}{5} \geq$ min sup (passed at the itemset stage), and only the confidence test filters anything here.

Pitfalls.

Generating rules from infrequent itemsets. A rule built from an infrequent itemset can never be strong — skip it. The entire reason the lecture is split into two stages is that rule generation only ever touches the frequent itemsets.
Confusing which threshold kills what. Minimum support is checked at the itemset stage; minimum confidence at the rule stage. A rule is strong only if it passes both, and they are checked at different points in the pipeline.
Counting support for each rule from scratch. The confidence of $s \to (l - s)$ reuses counts already computed at the itemset stage — $σ (l)$ and $σ (s)$ — so rule generation costs almost nothing compared with itemset mining.

Recap + bridge. The second stage is light: enumerate splits of each frequent itemset, divide the same two counts, and keep rules whose confidence clears min conf. With the algorithm complete end to end, we return to the worry from Section 12.4: Apriori still scans the full log once per level — and that is where the cost of the whole approach lives. That cost is the motivation for FP-growth.

12.10 The Cost of Repeated Scanning

12.10.1 The Pain

Think about the Apriori approach on a realistic log: millions of transactions and thousands of items (say 500 or 5,000). For the one-itemset level we scan through the complete log; for two-itemsets we generate candidates, then go back and scan again for support counting; for three-itemsets we generate candidates, count support again; for four-itemsets we go through the transaction log again. Every level means another full pass over a log of millions of rows. This becomes an extremely tedious and computationally expensive exercise. The question of this session is how to reduce that cost.

The idea: what if we traverse the transaction log only once, from top to bottom, and create a data structure — a tree-like data structure — that stores everything, and that tree then helps us find all the frequent itemsets without counting support again and again and again? That is what the FP-growth method does, using a data structure called the FP-tree (frequent pattern tree).

Scope — how bad the repeated scanning really is. Two costs compound in Apriori. First, the candidate sets themselves can explode: with just $1 0^{4}$ frequent 1-itemsets, the join step produces more than $1 0^{7}$ candidate 2-itemsets — the candidate explosion of Section 12.4 never fully disappears. Second, every level walks the whole database again, pattern-matching each candidate against each transaction. Both costs grow with every level, so a long frequent itemset means many full scans. The FP-tree idea attacks the second cost directly — one traversal, one tree — and stores the frequency information so that no later level ever needs the log again. Keep in mind what the tree must therefore contain: not just the item names, but the counts on every path, since those counts are the supports for all future levels.

12.10.2 Student Questions and Answers

Q: I am confused — are we doing prediction here, or finding the patterns? A: We are not doing any prediction here. We are just finding the frequent patterns. The FP-tree method mines the frequent itemsets from the log; prediction is a different task.

Q: Apriori already finds the frequent itemsets — why would a tree be better? A: Same output, different cost. Apriori finds the identical frequent itemsets but pays for them with one database scan per level and a candidate-generation step at every level. The FP-tree pays once: a single pass builds the tree, and mining then reads only the tree, never the log. On large logs the tree-based approach is typically about an order of magnitude faster, though the exact win depends on how well the log compresses — highly repetitive baskets give a small, dense tree; all-distinct baskets give a wide, bushy tree that saves little.

Recap + bridge. Apriori's weakness is structural: every level re-scans a log of millions of rows, and candidate sets can explode even after pruning. The proposed cure is to compress the whole log into one tree in a single pass — the FP-tree — and to mine the tree instead of the log. The next two sections build that tree node by node and then mine it bottom-up.

12.11 FP-Growth: Building the Frequent Pattern Tree

12.11.1 The Idea

FP-growth compresses the transaction log into a single tree. If we can build the tree with one pass over the log, the tree itself contains all the frequency information we need, and we can mine frequent itemsets from it directly.

Purpose, inputs and outputs. Apriori's pain (Section 12.10) is that every level re-reads the log. FP-growth removes the log from the inner loop: the input is the transaction log plus min sup, and the output is a compact tree called the FP-tree (frequent pattern tree) that encodes every frequent itemset's occurrence structure — plus a header table with one entry per frequent item, each carrying its support and a chain of pointers to every node of that item in the tree. The tree is built in exactly two passes: pass one counts single-item supports (and discards items below min sup); pass two inserts the surviving items of each transaction into the tree. From that point on, the log is never touched again.

12.11.2 Step 1: One-Item Supports and Ordering

First, generate the one-itemsets and find their support. The example uses nine transactions over five items, $I_{1}, I_{2}, I_{3}, I_{4}, I_{5}$ . The support counts are:

Item	Support
$I_{1}$	6
$I_{2}$	7
$I_{3}$	6
$I_{4}$	2
$I_{5}$	2

With minimum support 2, every one-itemset is frequent, so none is discarded. Next, arrange the one-itemsets in descending order of support: $I_{2}$ (7) comes first, then $I_{1}$ (6) and $I_{3}$ (6), then $I_{4}$ (2) and $I_{5}$ (2). When two items have the same support — $I_{1}$ and $I_{3}$ both at 6, $I_{4}$ and $I_{5}$ both at 2 — we use a tie-breaker: the lower index gets the higher priority. So $I_{1}$ precedes $I_{3}$ , and $I_{4}$ precedes $I_{5}$ . Whether you put one or the other first does not matter much, but whatever choice you make must be uniform throughout the problem. The global order is:

$I_{2} ≻ I_{1} ≻ I_{3} ≻ I_{4} ≻ I_{5}$

Scope — why the ordering matters. The tree's shape — and therefore its size — depends on the ordering. Sorting by descending support puts frequent items early in every transaction, so many transactions share long common prefixes and the tree merges them into single paths. If you instead sorted by ascending support, shared prefixes would be rarer and the tree would blow up toward one path per transaction. The tie-break rule (lower index first) is a pure convention; its only requirement is that it is applied identically in step 1, in every rearranged transaction, and throughout the mining in Section 12.12.

12.11.3 Step 2: Rearranging Every Transaction

Rearrange the items inside each transaction into this descending order, so that higher-frequency items come first and lower-frequency items come later:

Transaction	Original items	Rearranged
T1	${I_{1}, I_{2}, I_{5}}$	$I_{2}, I_{1}, I_{5}$
T2	${I_{2}, I_{4}}$	$I_{2}, I_{4}$
T3	${I_{2}, I_{3}}$	$I_{2}, I_{3}$
T4	${I_{1}, I_{2}, I_{4}}$	$I_{2}, I_{1}, I_{4}$
T5	${I_{1}, I_{3}}$	$I_{1}, I_{3}$
T6	${I_{2}, I_{3}}$	$I_{2}, I_{3}$
T7	${I_{1}, I_{3}}$	$I_{1}, I_{3}$
T8	${I_{1}, I_{2}, I_{3}, I_{5}}$	$I_{2}, I_{1}, I_{3}, I_{5}$
T9	${I_{1}, I_{2}, I_{3}}$	$I_{2}, I_{1}, I_{3}$

A correction (the last two transactions were misread in class). In class the last two transactions were read as "I2 I1 I3 I5" and "I2 I1 I5", but that reading cannot be right: it would give $I_{5}$ three occurrences (T1, T8, T9) while the stated support table says $I_{5} = 2$ . The reference book's version of exactly this nine-transaction example has T9 = ${I_{1}, I_{2}, I_{3}}$ (and T8 = ${I_{1}, I_{2}, I_{3}, I_{5}}$ ), which reproduces all five stated supports perfectly — $I_{1} = 6, I_{2} = 7, I_{3} = 6, I_{4} = 2, I_{5} = 2$ . That is the table used here, and every count below follows from it.

12.11.4 Step 3: Building the Tree Node by Node

Start with a null root node. Process each transaction in order. For the first item, look at the children of the null node: if a child with that item already exists, go to it; otherwise create a new node. Every time we visit a node, we increase its count by one. Then move to the next item and repeat from the current node.

T1 = I2, I1, I5. From null we cannot see I2, so create node I2 with count 1. From I2 we cannot see I1, so create I1 with count 1. From I1 we cannot see I5, so create I5 with count 1.
T2 = I2, I4. From null we can see I2, so go to it and increase its count to 2. From I2 we cannot see I4, so create I4 with count 1.
T3 = I2, I3. I2 count goes to 3. From I2 we cannot see I3, so create I3 with count 1.
T4 = I2, I1, I4. I2 count goes to 4. From I2 we can see I1, so increase its count to 2. From I1 we cannot see I4, so create I4 with count 1.
T5 = I1, I3. From null we cannot see I1, so create a new root child I1 with count 1. From it we cannot see I3, so create I3 with count 1.
T6 = I2, I3. I2 count goes to 5. From I2 we can see I3, so go there and increase its count to 2.
T7 = I1, I3. From null we can see I1 (the second root child), so increase its count to 2, and then increase its child I3 to 2.
T8 = I2, I1, I3, I5. I2 count goes to 6. I1 count goes to 3. From I1 we cannot see I3 on this branch, so create I3 with count 1, and from it create I5 with count 1.
T9 = I2, I1, I3. I2 count goes to 7. I1 count goes to 4. From I1 we can see I3, so increase its count to 2.

Worked example — the final tree. The complete FP-tree, read as root-to-leaf paths with the count on each node:

Path from null	Count
null → I2:7 → I1:4 → I5	1
null → I2:7 → I1:4 → I4	1
null → I2:7 → I1:4 → I3:2 → I5	1
null → I2:7 → I4	1
null → I2:7 → I3	2
null → I2:7 → I1:4 → I3:2	2
null → I1:2 → I3:2	2

The I3 node under I1 (on the I2 branch) ends at count 2 — created by T8, incremented by T9; the I3 node directly under I2 ends at 2 (T3, T6); the I3 under the root-level I1 ends at 2 (T5, T7). This matches the reference book's tree exactly.

The student who flagged the wrong node count caught it while the tree was still being drawn; the professor accepted the fix and the class moved on with the corrected tree (the counts in the table above are the corrected ones).

Q: The final count written for that node — "three here" — looks wrong. A: Oh yes, this is three here... my bad. The correction is accepted — thank you for correcting me. The tree counts are fixed now.

Sense-check — every support is encoded in the tree. Sum each item's node counts: $I_{2} = 7$ ✓ (the root child), $I_{1} = 4 + 2 = 6$ ✓, $I_{3} = 2 + 2 + 2 = 6$ ✓, $I_{4} = 1 + 1 = 2$ ✓, $I_{5} = 1 + 1 = 2$ ✓. Every single-item support from step 1 reappears in the tree — the tree is a lossless compression of the log for this mining task.

12.11.5 Checking the Tree Against the Data

After building the tree, check that it encodes the same frequencies as the original table. Look at the I5 nodes: the tree has I5 with count 1 on the path null → I2 → I1 → I5 and count 1 on the path null → I2 → I1 → I3 → I5 — together that reads as support 2, which matches the stated table value of 2. Look at the I4 nodes: count 1 under I2 and count 1 under I1 — together 2, again matching the table. So the tree is consistent with the transaction data.

Why the earlier confusion happened. The in-class reading of T9 as {I1, I2, I5} would have put I5 on three paths, giving support 3 — contradicting the table's 2. That is precisely the discrepancy the professor's in-class correction ("this is three here... my bad") was fixing on the spot, and it is the same reason the reference version of T9 (Section 12.11.3) is used here. With the corrected transaction, the tree check passes cleanly: every item's summed node counts equal its support count from step 1, which is exactly what "the tree encodes the same frequencies as the log" means.

12.11.6 Student Questions and Answers

The question that unlocked the whole construction for the class was about the traversal language.

Q: What do you mean by "can you see I2 from null"? What are we looking for? A: It means: is there a node whose item is I2 — or I1, or whichever item we are processing — hanging directly below the current node? Starting from null, we check whether a child node with that item already exists. If yes, we simply go to that node and increase its count. If no such node exists, we create a new node for that item and put its count as one. "Can I see X from this node?" is shorthand for "does a child of this node already contain X?"

Pitfalls.

Counting a node when the item is not a direct child. "Can I see X from this node?" means direct child, not "anywhere in this subtree". If X sits several levels down, you must walk down through the intermediate nodes — creating or incrementing every node on the way — not jump straight to X.
Forgetting to increment shared prefixes. When a new transaction shares a prefix with an existing path, every node on the common prefix gains +1; only the tail (the items after the shared prefix) gets new nodes. Inflating only the last node corrupts the counts for all longer patterns.
Using an inconsistent item order. If T1 is rearranged as I2, I1, I5 but T4 as I1, I2, I4, the shared prefix I2 is broken, the tree forks unnecessarily, and the counts no longer sum to the step-1 supports.

Recap + bridge. The FP-tree is built in two passes over the log: count and order the single items, then insert each rearranged transaction into the tree, sharing prefixes and counting nodes. The finished tree passes a full consistency check against the log — every support reappears as the sum of that item's node counts. The mining question is next: how do we walk this tree to extract all frequent itemsets without ever re-reading the log?

12.12 Mining the FP-Tree

12.12.1 The Bottom-Up Strategy

With the tree built, we mine frequent itemsets from it. The class started the process and left the full step-by-step walkthrough as a worked slide. The strategy: start from the bottom of the ordering — the item with the least support count, which is explored first because it has the fewest paths in the tree — and work upward.

Formalize — the mining procedure. For the suffix item currently being processed (starting with the last item in the ordering, then moving up):

Find its conditional pattern base. Follow the item's node-links from the header table to every node labelled with the item. For each such node, walk back to the root and collect the items on the path (excluding the item itself), each carrying that node's count.
Build the conditional FP-tree. Treat the pattern base as a mini-transaction log: sum counts per item, drop items whose total falls below min sup, and build a tree from the survivors.
Emit patterns. Any item surviving in the conditional tree, combined with the suffix, is a frequent itemset with the summed count; longer combinations come from sharing paths inside the conditional tree.
Repeat recursively for each item in the conditional tree's header.

Working bottom-up is deliberate: the least frequent item appears on the fewest paths, so its conditional pattern base is tiny, and the subproblems stay small. This divide-and-conquer is why FP-growth never generates and tests candidate itemsets at all — it grows patterns directly from the tree.

12.12.2 The First Item: I5

Start with I5. We want the potential candidates that contain I5. For each node labelled I5, walk from that node back to the root and note every item along the path, together with the node's support. There are two I5 nodes:

Path null → I2 → I1 → I5: the items reached are I2, I1; support 1.
Path null → I2 → I1 → I3 → I5: the items reached are I2, I1, I3; support 1.

These two prefix groups are called the conditional pattern base for I5: ${I_{2}, I_{1}} : 1$ and ${I_{2}, I_{1}, I_{3}} : 1$ . Now count how often each item appears in these prefix groups: I2 appears once in the first group and once in the second, so I2's support is 2; I1 also appears once in each group, so I1's support is 2.

Worked example — finishing I5, then the remaining items. Both I2 and I1 clear the minimum support of 2, so they survive into the conditional FP-tree for I5; I3 appears only once (support 1), so it is dropped. The conditional tree is the single path $⟨ I 2 : 2 \to I 1 : 2 ⟩$ , and from that path we read every combination that, joined with the suffix I5, forms a frequent itemset:

Frequent patterns ending in I5	Support
${I_{2}, I_{5}}$	2
${I_{1}, I_{5}}$	2
${I_{2}, I_{1}, I_{5}}$	2

Sense-check. Each pattern's count is the minimum node count along its path in the conditional tree (here 2 throughout), and each genuinely appears twice in the log: ${I_{2}, I_{5}}$ in T1 and T8 ✓, ${I_{1}, I_{5}}$ in T1 and T8 ✓, ${I_{2}, I_{1}, I_{5}}$ in T1 and T8 ✓.

The class ended the walkthrough here; completing the bottom-up sweep on the same tree gives:

I4. Its two nodes sit on paths null → I2 → I1 → I4 (count 1) and null → I2 → I4 (count 1), so its conditional pattern base is ${I_{2}, I_{1}} : 1$ and ${I_{2}} : 1$ . Counting: I2 appears twice, I1 once. I1 is dropped; the conditional tree is the single node $⟨ I 2 : 2 ⟩$ , giving the pattern ${I_{2}, I_{4}} : 2$ (transactions T2 and T4 ✓).

I3. Its three nodes give the conditional pattern base ${I_{2}, I_{1}} : 2$ (the I3 under I1), ${I_{2}} : 2$ (the I3 under I2), and ${I_{1}} : 2$ (the I3 under the root I1). I2 totals 4, I1 totals 2+2 = 4, both clear min sup. The conditional tree has two paths, $⟨ I 2 : 4 \to I 1 : 2 ⟩$ and $⟨ I 1 : 2 ⟩$ , yielding:

Frequent patterns ending in I3	Support
${I_{2}, I_{3}}$	4
${I_{1}, I_{3}}$	4
${I_{2}, I_{1}, I_{3}}$	2

I1. Its root-level node (count 2) and its node under I2 (count 4) share one prefix path: ${I_{2}} : 4$ . The conditional tree is the single node $⟨ I 2 : 4 ⟩$ , giving ${I_{2}, I_{1}} : 4$ .

I2. Nothing lies above it — no prefix items — so the mining stops. Collecting everything, the complete set of frequent itemsets from the nine-transaction log is:

${I_{2}, I_{5}}, {I_{1}, I_{5}}, {I_{2}, I_{1}, I_{5}}, {I_{2}, I_{4}}, {I_{2}, I_{3}}, {I_{1}, I_{3}}, {I_{2}, I_{1}, I_{3}}, {I_{2}, I_{1}}$ , plus the single items ${I_{1}}, {I_{2}}, {I_{3}}, {I_{4}}, {I_{5}}$ . These are exactly the frequent itemsets Apriori would report on the same data — same answer, but found from a tree rather than through repeated scans of the log.

Pitfalls.

Carrying the node's count, not the whole path's. In a conditional pattern base, the count attached to a prefix group is the count of the suffix node that path came from — not the count of some other node on the path. For I5, both prefix groups carry count 1 because each I5 node has count 1.
Forgetting to filter the conditional base. Items that do not clear min sup inside the pattern base (I3 with support 1 in I5's base) must be dropped before patterns are emitted — keeping them would emit itemsets that never met the threshold.
Skipping the bottom-up order. Starting from a frequent, many-path item first inflates every conditional base. The least frequent item is explored first precisely because it has the fewest paths — the ordering is the algorithm's efficiency engine, not a cosmetic choice.
Emitting combinations from a non-single-path conditional tree. Only when the conditional FP-tree is a single path can you read all combinations directly; bushy conditional trees need recursive mining of each branch.

Recap + bridge. Mining is bottom-up: for each suffix item, collect its conditional pattern base from the tree, build the conditional FP-tree, drop below-threshold items, and emit the patterns that survive. Applied to I5 first, then I4, I3, I1, the sweep produces every frequent itemset — identical to Apriori's answer, but with the log read only twice. This closes the lecture: support and confidence gave us the measures (12.2–12.3), the Apriori principle gave the first pruning lever (12.5), the Apriori algorithm organized it into a loop (12.6–12.9), and FP-growth replaced repeated scanning with one tree and bottom-up pattern growth (12.10–12.12).

Exam Guidance Summary

No exam-specific guidance was given in this session. The session was a recap of association rule mining (definitions, support, confidence, the Apriori principle) followed by new material: the Apriori algorithm's four-step loop and FP-growth's tree construction and bottom-up mining. Expect the definitions (itemset, k-itemset, support count, frequent itemset, minimum support) and the two quality measures (support and confidence of a rule) to be central, along with the Apriori principle's subset/superset logic and the Apriori four-step procedure with a numerical walkthrough.

Exam note (distilled from this session). Three things are almost certain to be tested, based on how the lecture balanced its time:

Vocabulary and formulas. Itemset, $k$ -itemset, support count $σ (X)$ , frequent itemset, min sup, and the two rule measures — $support (X \to Y) = σ (X \cup Y) / N$ and $confidence (X \to Y) = σ (X \cup Y) / σ (X)$ . Be ready to state them precisely, including the difference between support count (raw) and support (fraction).
The Apriori principle, both directions. If $X \subseteq Y$ then $support (X) \geq support (Y)$ ; frequency travels down to subsets, infrequency travels up to supersets. Exam questions love the "if AB is infrequent, what can you say about ABC / CD / ABCDE?" pattern — answer only what the principle guarantees, never what intuition suggests.
Numerical walkthroughs. The four-transaction Apriori example (min sup 2, items 1–5, final frequent itemsets ${1, 3}, {2, 3}, {2, 5}, {3, 5}, {2, 3, 5}$ ) and the nine-transaction FP-tree example (order $I_{2} ≻ I_{1} ≻ I_{3} ≻ I_{4} ≻ I_{5}$ , conditional pattern base of I5 = ${I_{2}, I_{1}} : 1$ , ${I_{2}, I_{1}, I_{3}} : 1$ , patterns ${I_{2}, I_{5}}, {I_{1}, I_{5}}, {I_{2}, I_{1}, I_{5}}$ at support 2) are the two worked examples most worth practising end to end. For Apriori, practise the four steps (generate, prune, count, eliminate) at every level; for FP-growth, practise the tree walk (create vs increment) and the bottom-up conditional-base mining.

Key Industry Applications

Real-world: supermarket self-management, sales promotion, and inventory management are the named applications of association rule mining.
Real-world: wherever an association between two items must be found, the same style of algorithm applies — the class example was the Thanda–Coke co-purchase pattern behind an advertisement.
Real-world: real stores like Lance mall and D-Mart sell thousands of items with transaction logs in the millions, which is exactly the scale that makes the brute-force approach impossible and tree-based mining (FP-growth) attractive.

Where this lands in the broader field. Association rule mining is the core of market basket analysis, the retail analytics loop that decides what sits next to what on a shelf, what goes on sale together, and how inventories are planned: if customers who buy computers also buy antivirus software, the store can place the displays near each other or run a printer sale to pull computer sales. The classic industry story is the diapers-and-beer discovery — a chain store found that diaper shoppers were unusually likely to buy beer, and used the pattern for promotions. The same machinery, with the same support–confidence machinery, is used beyond retail: web mining (pages visited in one session), medical diagnosis (co-occurring symptoms), bioinformatics (co-expressed genes), and scientific analysis of linked earth-system processes. The Thanda–Coke case from class is the retail story in miniature — a co-purchase pattern was strong enough that an entire advertisement was built on it.

One honest caveat that shapes every deployment: rules express co-occurrence, not causality. Retailers use them to place and price, not to claim that buying one item causes the other; causal claims would need experiments or time-ordered data, which a transaction log alone does not provide.

DM Lecture 12 notes · Association Rule Mining: Apriori and FP-Growth

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

1Association Rule Mining — Recap

Association rule mining extracts conditional dependencies (if X is bought, Y is likely bought) from a transaction log, in two stages: find frequent itemsets, then mine association rules inside them.

2Core Definitions: Itemset, Support Count, Frequent Itemset

An itemset is a collection of one or more items (a k-itemset has k items); its support count sigma(X) is the number of transactions containing the whole set; a frequent itemset is one whose support count clears the analyst-chosen minimum support threshold.

3Association Rules: Support and Confidence

A rule X->Y is scored by support = sigma(X U Y)/N (how often the pattern occurs) and confidence = sigma(X U Y)/sigma(X) (how reliably Y follows X, i.e. the conditional probability P(Y|X)); rules from the same itemset share support but differ in confidence.

4Why the Brute-Force Approach Is Too Expensive

Brute force generates every candidate itemset (2^D of them) and every rule (R = 3^D - 2^(D+1) + 1), then counts each against the whole transaction log — infeasible at real-store scale (thousands of items, millions of transactions).

5The Apriori Principle

The Apriori principle (anti-monotone property): if X is a subset of Y then support(X) >= support(Y). Frequency travels down to subsets; by contraposition, infrequency travels up to supersets — one infrequent itemset prunes its entire family of supersets without counting.

6The Apriori Algorithm

Apriori iterates level by level: generate candidate k-itemsets Lk only from frequent (k-1)-itemsets, prune by the Apriori principle, count support in one log scan, eliminate below-min-sup candidates into Fk, repeat until Fk is empty.

7The Apriori Algorithm in Pictures: Five Transactions, Minimum Support 3

The same four-step loop visualized on an itemset lattice with five transactions and min sup 3: egg and coke are infrequent at level 1, so every superset containing them is pruned; two pairs at support 2 are eliminated at level 2, and the loop continues until a null level.

8Candidate Generation by Merging: F_{k-1} x F_{k-1}

Candidates of size k are built by merging pairs of frequent (k-1)-itemsets whose first k-2 elements (the prefix) are identical and whose last elements differ; the rule guarantees each candidate is generated exactly once.

9From Frequent Itemsets to Rules

The final stage generates rules from each frequent itemset: enumerate all nonempty proper subsets s of l, form s -> (l-s), keep those with confidence sigma(l)/sigma(s) >= min conf. Support is already satisfied, so only confidence filters.

10The Cost of Repeated Scanning

Apriori scans the whole transaction log once per itemset level, and candidate sets can still explode (10^4 frequent singles -> >10^7 candidate pairs); the proposed fix is to traverse the log once, compress it into a tree (FP-tree), and mine the tree instead of re-scanning the log.

11FP-Growth: Building the Frequent Pattern Tree

FP-growth compresses the log into an FP-tree in two passes: (1) count single-item supports, drop items below min sup, order by descending support with a tie-breaker; (2) insert each rearranged transaction into a null-rooted tree, sharing prefixes and incrementing node counts. The tree's summed node counts reproduce every stated support.

12Mining the FP-Tree

FP-tree mining works bottom-up from the least frequent item: for each suffix item, gather its conditional pattern base (prefix paths with node counts), build the conditional FP-tree dropping below-min-sup items, and emit combinations as frequent patterns. For I5 the base {I2,I1}:1, {I2,I1,I3}:1 yields {I2,I5}, {I1,I5}, {I2,I1,I5} at support 2.

13Exam Guidance Summary

No session-specific guidance was given, but the definitions (itemset, k-itemset, support count, frequent itemset, min sup), the two rule measures, the Apriori principle in both directions, and the two numerical walkthroughs are the expected exam focus.

14Key Industry Applications

Association rule mining powers supermarket self-management, sales promotion, and inventory management; the class example was the Thanda–Coke co-purchase advertisement; real stores with thousands of items and millions of transactions make tree-based mining (FP-growth) the practical choice.

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Association Rule Mining — Recap

Must-know: Association rule mining is a two-step process: (1) find frequent itemsets, (2) generate association rules inside them. Rules are conditional dependencies, not causality.

⚠️ Top pitfall: Confusing a co-occurrence rule with a causal statement — diapers→beer does not mean diapers cause beer purchases.

Self-check: What are the two stages of association rule mining, and why is the split useful?

Connects to: 12.2, 12.3

Core Definitions: Itemset, Support Count, Frequent Itemset

Must-know: support count sigma(X) = number of transactions containing all items of X. A k-itemset has exactly k items. An itemset is frequent if sigma(X) >= min sup, where min sup is a user-set threshold.

$σ (X) = ∣ {t_{i} : X \subseteq t_{i}, t_{i} \in T} ∣$

⚠️ Top pitfall: Counting transactions that contain only some of the items — every item of X must be present for the transaction to count.

Self-check: In the five-transaction log, why is sigma({milk, bread}) = 3 while sigma({milk, bread, diaper}) = 2?

Connects to: 12.1, 12.3, 12.5

Association Rules: Support and Confidence

Must-know: Confidence(X->Y) = sigma(X U Y)/sigma(X) = P(Y|X). Support(X->Y) = sigma(X U Y)/N. The numerator is shared by all rules from one itemset; only the denominator sigma(X) changes with the left side.

$confidence (X \to Y) = \frac{σ ( X \cup Y )}{σ ( X )}$

⚠️ Top pitfall: Using the wrong denominator: confidence divides by support of X (the left side), not by N — dividing by N gives support.

Self-check: Why do rules drawn from the same itemset always share support but can have different confidence?

Connects to: 12.2, 12.4, 12.9

Why the Brute-Force Approach Is Too Expensive

Must-know: Candidates = 2^D (every subset). Rules = 3^D - 2^(D+1) + 1 (each item goes to left, right, or neither; subtract empty-side cases). For D=5: 32 itemsets, 180 rules. Counting each candidate against N transactions costs O(NMw).

$R = 3^{D} - 2^{D + 1} + 1$

⚠️ Top pitfall: Mixing up the two counts: 2^D is for itemsets, 3^D - 2^(D+1) + 1 is for rules. Also: forgetting that each candidate must be counted against every transaction.

Self-check: A store sells 5 items. How many candidate itemsets and how many possible rules exist?

Connects to: 12.5, 12.6, 12.10

The Apriori Principle

Must-know: If X subset of Y then support(X) >= support(Y). Frequent => all subsets frequent; infrequent => all supersets infrequent. Memory aid: infrequency talks about supersets, frequency talks about subsets.

$X \subseteq Y ⟹ support (X) \geq support (Y)$

⚠️ Top pitfall: Claiming AB is frequent because A and B are frequent, or claiming CD is infrequent because AB is infrequent — the principle is one-directional.

Self-check: If {A,B} is infrequent, which of {A,B,C}, {C,D}, {A,B,C,D,E} can be declared infrequent without counting, and why?

Connects to: 12.6, 12.8

The Apriori Algorithm

Must-know: Four-step loop: (1) generate L(k+1) from Fk, (2) prune by Apriori principle, (3) count support in one scan, (4) eliminate below min sup. Stop when Fk is empty. Notation: Lk = candidates, Fk = frequent (standard books use Ck, Lk).

$F_{k} = {X \in L_{k} : σ (X) \geq min sup}$

⚠️ Top pitfall: Confusing pruning (before counting, uses the principle) with elimination (after counting, uses support values); or generating candidates from infrequent sets.

Self-check: In the four-transaction example, why is {1,5} dropped at level 2 while {1,3} survives, given min sup = 2?

Connects to: 12.5, 12.7, 12.8

The Apriori Algorithm in Pictures: Five Transactions, Minimum Support 3

Must-know: Candidate generation and pruning happen together: pairs containing an infrequent single item are never generated. Any transaction row containing an infrequent item is itself infrequent (it is a superset of that item).

⚠️ Top pitfall: Assuming a TID row's status is about the row's own count rather than about the infrequent item it contains.

Self-check: Why is the TID-5 row infrequent even though the item 5 has support 4?

Connects to: 12.5, 12.6, 12.8

Candidate Generation by Merging: F_{k-1} x F_{k-1}

Must-know: Merge pairs of frequent (k-1)-itemsets iff their first k-2 elements match and last elements differ. At k=4, ABC+ABD -> ABCD; BD+DE cannot merge (prefixes B vs D). Merge pool is F_{k-1}, not L_{k-1}.

$A = {a_{1}, \dots, a_{k - 1}}, B = {b_{1}, \dots, b_{k - 1}} : merge iff a_{i} = b_{i} (i \leq k - 2) \land a_{k - 1} \neq = b_{k - 1}$

⚠️ Top pitfall: Merging sets that share a middle element but not the prefix — the first k-2 elements must be identical.

Self-check: Can {B,D} and {D,E} be merged into a 4-itemset? Why not?

Connects to: 12.5, 12.6

From Frequent Itemsets to Rules

Must-know: Rules come from frequent itemsets only: for each frequent l and each nonempty proper subset s, rule s -> (l-s) has confidence sigma(l)/sigma(s); keep it if confidence >= min conf.

$confidence (s \to (l - s)) = \frac{σ ( l )}{σ ( s )} \geq min conf$

⚠️ Top pitfall: Checking minimum support again at the rule stage — support is guaranteed because l is frequent; only confidence is tested here.

Self-check: From frequent itemset {beer, diaper, milk} with sigma = 2 and min conf = 75%, which rules survive?

Connects to: 12.3, 12.6

The Cost of Repeated Scanning

Must-know: Apriori's cost: one full log scan per level plus candidate generation at each level. FP-growth answers with a single scan that builds an FP-tree storing all frequency information.

⚠️ Top pitfall: Thinking FP-tree mining is prediction — it is pattern finding, same task as Apriori, just cheaper.

Self-check: Why does the number of database scans grow with the longest frequent itemset in Apriori?

Connects to: 12.11, 12.12

FP-Growth: Building the Frequent Pattern Tree

Must-know: FP-tree: 2 passes. Pass 1: count supports, order descending (tie-break: lower index first). Pass 2: insert rearranged transactions, increment shared prefixes, create new nodes with count 1. T9 = {I1,I2,I3}; summed node counts must equal step-1 supports.

$I_{2} ≻ I_{1} ≻ I_{3} ≻ I_{4} ≻ I_{5}$

⚠️ Top pitfall: Counting a node that is not a direct child, or failing to increment every node on a shared prefix.

Self-check: Why does the tree show I5 with total count 2 (1 + 1) even though the in-class reading had T9 containing I5?

Connects to: 12.10, 12.12

Mining the FP-Tree

Must-know: Bottom-up mining: conditional pattern base = prefix paths with suffix-node counts; build conditional FP-tree, drop items below min sup; emit patterns. I5: base {I2,I1}:1, {I2,I1,I3}:1 -> {I2,I5}:2, {I1,I5}:2, {I2,I1,I5}:2.

⚠️ Top pitfall: Attaching the wrong count to a prefix group (use the suffix node's count), or keeping below-threshold items in the conditional tree.

Self-check: Why is I3 dropped from I5's conditional pattern base even though I3 is frequent in the full log?

Connects to: 12.11, 12.10

Exam Guidance Summary

Must-know: Know the vocabulary, support/confidence formulas, the two directions of the Apriori principle, and practise the 4-transaction Apriori trace and the 9-transaction FP-tree trace end to end.

$support (X \to Y) = \frac{σ ( X \cup Y )}{N}, confidence (X \to Y) = \frac{σ ( X \cup Y )}{σ ( X )}$

⚠️ Top pitfall: Answering Apriori-principle questions with intuition (e.g., 'A and B frequent so AB is frequent') instead of only what the principle guarantees.

Self-check: If AB is infrequent, what can be said about ABC, CD, and ABCDE?

Connects to: 12.2, 12.3, 12.5, 12.6, 12.11, 12.12

Key Industry Applications

Must-know: Named applications: supermarket self-management, sales promotion, inventory management. Rules express co-occurrence, not causality.

⚠️ Top pitfall: Treating association rules as causal statements.

Self-check: Why is FP-growth attractive at real-store scale (thousands of items, millions of transactions)?

Connects to: 12.1, 12.10

Previous LectureLecture 11 · Association Rule Mining

Next LectureLecture 13 · Clustering and K-Means

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

12.1 Association Rule Mining — Recap

12.1.1 The Task

12.1.2 Where It Is Used

12.2 Core Definitions: Itemset, Support Count, Frequent Itemset

12.2.1 Itemsets

12.2.2 Support Count

12.2.3 Frequent Itemsets and Minimum Support

12.3 Association Rules: Support and Confidence

12.3.1 Writing a Rule

12.3.2 Support of a Rule

12.3.3 Confidence of a Rule

12.3.4 Rules from the Same Itemset

12.3.5 Student Questions and Answers

12.4 Why the Brute-Force Approach Is Too Expensive

12.4.1 The Brute-Force Recipe

12.4.2 Counting the Candidates and Rules

12.4.3 The Scale Problem in Real Stores

12.5 The Apriori Principle

12.5.1 The Principle

12.5.2 The Inverted Use: Pruning Supersets

12.5.3 Student Questions and Answers

12.6 The Apriori Algorithm

12.6.1 The Notation

12.6.2 The Four Steps in a Loop

12.6.3 Worked Example: Four Transactions, Minimum Support 2

12.6.4 Student Questions and Answers

12.7 The Apriori Algorithm in Pictures: Five Transactions, Minimum Support 3

12.7.1 The Setup

12.7.2 Level 1: Egg and Coke Are Infrequent

12.7.3 Level 2 and Beyond

12.7.4 Student Questions and Answers

12.8 Candidate Generation by Merging: Fk−1​×Fk−1​

12.8.1 The Merging Rule

12.8.2 Student Questions and Answers

12.9 From Frequent Itemsets to Rules

12.9.1 The Last Step

12.10 The Cost of Repeated Scanning

12.10.1 The Pain

12.10.2 Student Questions and Answers

12.11 FP-Growth: Building the Frequent Pattern Tree

12.11.1 The Idea

12.11.2 Step 1: One-Item Supports and Ordering

12.11.3 Step 2: Rearranging Every Transaction

12.11.4 Step 3: Building the Tree Node by Node

12.11.5 Checking the Tree Against the Data

12.11.6 Student Questions and Answers

12.12 Mining the FP-Tree

12.12.1 The Bottom-Up Strategy

12.12.2 The First Item: I5

Exam Guidance Summary

Key Industry Applications

DM Lecture 12 notes · Association Rule Mining: Apriori and FP-Growth

Sections Breakdown

Exam Revision Notes

Association Rule Mining — Recap

Core Definitions: Itemset, Support Count, Frequent Itemset

Association Rules: Support and Confidence

Why the Brute-Force Approach Is Too Expensive

The Apriori Principle

The Apriori Algorithm

The Apriori Algorithm in Pictures: Five Transactions, Minimum Support 3

Candidate Generation by Merging: F_{k-1} x F_{k-1}

From Frequent Itemsets to Rules

The Cost of Repeated Scanning

FP-Growth: Building the Frequent Pattern Tree

Mining the FP-Tree

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

12.8 Candidate Generation by Merging: $F_{k - 1} \times F_{k - 1}$