A collection of transactions can contain recurring combinations even when no individual row has been labeled as a pattern. The first task is to decide precisely what “recurring” means. The second is to search for every qualifying combination without counting every possible itemset unnecessarily. Apriori connects these tasks through a simple containment argument.
The key distinction is between proving that an itemset cannot be frequent and measuring its exact support. A pruned proposal may need no transaction scan at all. Conversely, a proposal that survives pruning still has to be counted: necessary evidence is not a certificate of frequency.
Count transactions, not repeated appearances within a row
Definition 2.1.1
(Support count and support fraction)
Let be a finite item universe, and let the database be an indexed list of transactions , where and each . For an itemset , define
The count records how many transactions contain every item in . At minimum support count , an itemset is frequent when . Here we mine nonempty itemsets and use a positive integer threshold.
Each row contributes at most one to an item's support count, even if a purchase record originally contained multiple copies of that item. Two separate rows with identical item contents still count twice. Transaction identity and item multiplicity answer different questions.
Use four abstract items and six synthetic teaching transactions. Shorthand such as will mean the itemset , not an ordered string.
| Transaction | Items |
|---|---|
For example, occurs in , so and . Neither nor contains both items, even though each contains one of them.
Prove which extensions can be discarded
Proposition 2.1.2
(Support is antimonotone)
If , then and . Consequently, if , no superset of is frequent; equivalently, every subset of a frequent itemset is frequent.
Proof
(Nested transaction-index sets)
If , every transaction containing also contains . Thus the transaction-index set counted by is contained in the one counted by , giving
If , then for every superset . The contrapositive says that every subset of a frequent itemset is frequent.
This is the downward-closure property used by Apriori. The claim concerns one fixed database and threshold. It does not say that a frequent subset makes a larger itemset frequent: the larger set imposes extra requirements that fewer transactions may satisfy.
For a proposed -itemset, it is enough to check all its immediate -item subsets against the previous frequent level. Every smaller subset is contained in an immediate one, so downward closure then accounts for the smaller subsets too. One missing immediate subset is sufficient evidence to prune.
Separate joined proposals, countable candidates and frequent results
Write for the frequent itemsets of size . To avoid hiding the pruning step, write for joined proposals before pruning and for those retained for counting. Some descriptions use “candidate” for the pre-pruning family too; the operations matter more than the naming convention.
Fix an item order . Join two sorted members of when their first items agree and their last items differ. Then prune any resulting proposal whose immediate subset is absent from . Count each survivor and keep it in only if it reaches .
Worked example 2.1.3
(Complete the singleton and pair levels at m = 2)
The singleton and pair counts are:
| Itemset | ||||
|---|---|---|---|---|
| Support count |
| Itemset | ||||||
|---|---|---|---|---|---|---|
| Support count |
All singletons qualify, so . Joining them produces all six pair proposals. Their singleton subsets are frequent, so all six pairs are counted. Only meet the count threshold, giving
Notice that is counted below threshold, whereas is counted as zero. Neither status is the same as “not counted.”
Worked example 2.1.4
(Level three: counting one proposal and pruning two)
At size three, the shared-prefix joins are , and . There is no proposal from this join: is absent from , so there is no matching pair to join with .
| Joined proposal | Subset decision | Own transaction count performed? | Result |
|---|---|---|---|
| are all frequent | Yes: only matches, so the count is 1 | Counted, but not frequent | |
| is absent from | No | Pruned using | |
| is absent from | No | Pruned using |
Thus , and . No larger frequent itemset exists, because it would have a frequent three-item subset. The final nonempty frequent itemsets are the four singletons and the four members of .
The table records the execution history as well as mathematical facts. A pruned record has no measured support count from its own scan. That does not make its true support undefined: here the bound from even implies . Keep that inference distinct from claiming that the algorithm scanned . Likewise, displaying every possible itemset in a lattice does not mean that every one was generated or counted.
Counterexample mode
Frequent immediate subsets are necessary, not sufficient
At , all three pairs are frequent, but has count only 1. Different transactions can witness the different pairs without any second transaction containing all three items together. Passing the subset test therefore justifies counting ; it does not justify labeling it frequent.
The error is reversing the implication. Frequency of would force frequency of its pairs, but frequency of the pairs does not force frequency of .
The trace below replays these six transactions at any threshold m and keeps the three decisions apart: a joined proposal, a subset-pruning proof and an actual support count.
Why joining and pruning cannot miss a frequent itemset
Theorem 2.1.5
(Level-wise Apriori finds exactly the frequent itemsets)
For every , the family produced by shared-prefix joining, immediate-subset pruning and counting is exactly the set of frequent -itemsets.
Proof
(Soundness by counting, completeness by induction on size)
Soundness: an itemset enters only after its measured support count reaches , so no non-frequent itemset is reported.
Completeness: the singleton level is obtained by direct counting, which is the induction base. Assume contains every frequent -itemset, and take any frequent . Its subsets and are frequent by downward closure, so both occur in . They share the required prefix, and their join produces . Every other immediate subset of is frequent too, so pruning cannot remove . Counting then confirms its support and places it in . Hence the level-by-level procedure finds every frequent nonempty itemset.
Proof X-ray
What each ingredient certifies
Pruning and counting do different jobs. Downward closure is used twice in the completeness half: once to put two particular -subsets of into , so that the shared-prefix join creates , and once to show that every other immediate subset is present, so that the pruning test cannot reject . The two subsets chosen, which omit the last item and the second-to-last item, always satisfy the join condition, which is why restricting joins to shared prefixes loses nothing. Pruning proves that exclusions are safe; it never proves that a survivor is frequent. That is the job of the count, which supplies soundness. Completeness and the support check together establish correctness, and neither alone does.
Frequent itemsets and association rules are different outputs
For nonempty disjoint itemsets with , the rule has
Support uses all transactions as its denominator; confidence uses only those containing the antecedent . When , define lift by
Worked example 2.1.6
(Support, confidence and lift for )
For , support is , confidence is , and lift is . Reversing the rule keeps support and lift unchanged but changes confidence to . The denominator explains the asymmetry; a frequent unordered itemset does not by itself specify a direction.
Counterexample mode
A large confidence can still be below the consequent's baseline
The rule has confidence , but occurs in of all transactions. Its lift is . In this dataset, is actually less common among transactions containing than in the overall database. Looking only at the apparently large confidence would miss that comparison.
Here confidence is an empirical conditional fraction, not a statistical confidence level. Neither that fraction nor lift establishes a causal mechanism or guarantees performance on future data. Their first job is to describe the stated transaction sample with the correct denominators.
Common mistake
(Assuming confidence is monotone in the antecedent)
Do not transfer support's subset rule to confidence without a new proof. In these transactions, , adding to the antecedent lowers it to , while adding raises it to 1. Conditional ratios can move in either direction.
Reproduce the frequent-itemset stage
This small Python implementation uses sorted tuples as canonical itemsets and sets for transactions. It follows shared-prefix joining and immediate-subset pruning; an item's order within a transaction is irrelevant.
from itertools import combinations
transactions = list(map(frozenset, ["ABC", "AB", "AC", "BC", "ABD", "AD"]))
items = tuple("ABCD")
minimum = 2
def support_count(itemset):
return sum(set(itemset).issubset(row) for row in transactions)
def join(previous):
proposals = set()
for left, right in combinations(sorted(previous), 2):
if left[:-1] == right[:-1]:
proposals.add(left + (right[-1],))
return sorted(proposals)
previous = set()
proposals = [(item,) for item in items]
level = 1
counted_candidates = 0
while proposals:
candidates = [
candidate for candidate in proposals
if level == 1 or all(
subset in previous for subset in combinations(candidate, level - 1)
)
]
measured = {candidate: support_count(candidate) for candidate in candidates}
counted_candidates += len(candidates)
frequent = {candidate: count for candidate, count in measured.items() if count >= minimum}
print(level, [("".join(candidate), frequent[candidate]) for candidate in sorted(frequent)])
previous = set(frequent)
proposals = join(previous)
level += 1
print("containment checks", counted_candidates * len(transactions))
The reported frequent levels are , then , then an empty third level. It counts four singletons, six pairs and one triple: eleven candidates against six rows give 66 candidate–transaction containment checks.
That counter is not 66 database passes or a running-time formula. A level can count all its candidates during one database scan; the small program instead makes its candidate-by-candidate work explicit. No support scan for or is hidden in the displayed input table.
Exercises
Quick check
(Use the same six transactions but set . Give and . Can a three-item proposal be formed from the second frequent level, and can a larger frequent itemset have been missed?)
Compute the singleton and pair counts first.
Solution · Answer
and . The only frequent pair cannot join with another frequent pair, so no three-item proposal is formed. A frequent triple would require all its pairs to be frequent, which is impossible here. No larger frequent itemset is missed.
Quick check
(At , why is pruned, and what upper bound follows? Is its exact count mathematically undefined? By directly inspecting the transactions afterwards, find that count and explain why this does not change the earlier execution history.)
Look at which immediate subset of is missing from .
Solution · Answer
has count 1 and is absent from , so . The true count is defined whether or not the mining trace measured it. A separate inspection finds only , hence count 1. That independent count does not mean that the earlier Apriori trace scanned a proposal it had already pruned.
Quick check
(For , compute support, confidence and lift. How many transactions support its perfect observed confidence, and what does this say about treating the rule as a universal statement?)
Use , and .
Solution · Answer
, and , so support is , confidence is 1, and lift is . Only contain the antecedent. Both contain , which establishes the sample fraction; it does not establish that every future transaction containing must contain .
Quick check
(Duplicate every transaction once, giving twelve rows. What happens to support counts, support fractions, confidence and lift? If the absolute threshold remains , which itemsets become newly frequent compared with the original database? Would retaining the old minimum support fraction have the same effect?)
Compare how counts and denominators change.
Solution · Answer
Every support count doubles, but fractions, confidence and lift remain unchanged because their corresponding denominators double too. Keeping absolute now admits original count-one itemsets: become newly frequent. Retaining support fraction instead requires at least four of the twelve rows, so it preserves the original frequent family. The threshold's units must be stated.