Review support counts and Apriori first.
Setting and conventions
Definition 2.2.1
(Transactions, support and frequency)
- A nonempty finite item universe .
- The domain of itemsets is the set of all subsets of , which is the power set . This includes and .
- A finite nonempty transaction multiset , where each transaction is a set. Two transactions may be equal as sets and still count separately.
- The support count of an itemset is
counted over indices, so duplicate transactions each contribute one.
- A positive integer minimum support . The itemset is frequent when .
Proposition 2.2.2
(Support is anti-monotone)
If , then .
Proof
(A larger itemset is contained in fewer transactions)
Every transaction that contains also contains , so the set of indices counted for is a subset of the set counted for .
This is the property Apriori relies on.
Three definitions
Definition 2.2.3
(Closed, closed frequent and maximal frequent itemsets)
- An itemset is closed when every proper superset satisfies .
- An itemset is closed frequent when it is both closed and frequent.
- An itemset is maximal frequent when it is frequent and no proper superset of it is frequent.
Common mistake
(Confusing closed with maximal)
Closed asks whether a larger itemset keeps exactly the same count; maximal frequent asks whether a larger itemset reaches the threshold at all. A closed set can therefore have a larger frequent extension, provided that extension has smaller support. In the worked example below, has support and is closed, yet the frequent set (support ) contains it, so is not maximal.
Closure by intersection
Let have positive support. Its closure is defined as
We use this construction only when . In that case the family being intersected is nonempty, so the intersection is well defined.
When , the family is empty, and the formula needs an extra convention. A common convention takes the empty intersection to be ; we leave the closure undefined in this case. Closedness itself is still defined above: a zero-support itemset is closed exactly when it equals . Indeed, if , its proper superset also has support , so is not closed. If , it has no proper superset and is closed vacuously, even when its support is . This conclusion does not require a value for . In this chapter, "closed frequent" always involves positive support, since .
Lemma 2.2.4
(Closure preserves support)
If , then and .
Proof
(Both sets are contained in the same transactions)
Every transaction in the family contains , so their intersection does too. This gives .
Now compare the two supports.
- If , then is one of the intersected sets, so .
- Conversely, if , then .
The same indices are therefore counted for both sets.
Lemma 2.2.5
(Closed itemsets are fixed points of closure)
If , then is closed if and only if .
Proof
(The closure is the largest superset with the same support)
Suppose and . The indices of transactions containing form a subset of the indices of transactions containing . Both index sets have the same size, so they are equal. Every transaction containing therefore contains , which gives .
This shows that is the largest superset of with the same support.
- If , then is a proper superset with equal support, so is not closed.
- If , then every proper superset has support different from , since equal support would force . By anti-monotonicity, that support is strictly smaller, so is closed.
Concept lensStructural
Closed itemsets as intersections of transactions
The supersets of form the large family . The closure is one particular member of that family, but it is computed from transactions, not by searching through supersets. The closed itemsets of positive support are exactly the intersections of nonempty subfamilies of transactions. One direction is the definition of . For the other, if for a nonempty family of transactions, then every member of contains , so , and therefore . Such an intersection need not be a superset of any particular you started from.
Maximal implies closed
Theorem 2.2.6
(Maximal frequent itemsets are closed)
Every maximal frequent itemset is closed.
Proof
(A support-preserving superset would be frequent)
Let be maximal frequent. Then , so has positive support.
Suppose were not closed. Then some proper superset would have . That makes a frequent proper superset of , which contradicts maximality.
Counterexample mode
Closed frequent itemsets need not be maximal
Claim: every closed frequent itemset is maximal frequent. Take , and the transactions , , , , , . The itemset lies in the first three transactions, so . Its supersets are (support ), (support ) and (support ), all strictly below , so is closed and frequent. But is a frequent proper superset of , so is not maximal. The corrected statement is the implication proved above: maximal frequent implies closed, and not conversely.
Reconstructing supports
Proposition 2.2.7
(Supports are recovered from closed frequent itemsets)
For any , the itemset is frequent if and only if has a frequent closed superset. In that case
Proof
(The closure attains the maximum)
Suppose is frequent. By the closure lemmas, is closed, contains , and has support . Any other superset has by anti-monotonicity. So the maximum is attained at and equals .
Conversely, if has a frequent superset, then is at least that superset's support, so is frequent.
Proof X-ray
Why the closure is the right witness
The proof has one non-routine move: to name the superset that attains the maximum, namely . Anti-monotonicity gives only the inequality for every superset , so the maximum can never exceed . Equality needs a superset that is both closed and equal in support, and this is exactly what the two closure lemmas provide. The hypothesis that is frequent is used so that the witness is frequent, which is why the maximum ranges over closed frequent sets. For an infrequent the statement is about membership only: there is then no closed frequent superset, because its support would force to be frequent.
The closed frequent sets, together with their supports, are therefore a lossless summary: you can recover every frequent itemset and its exact support.
Maximal frequent sets only tell you which itemsets are frequent: exactly the subsets of some maximal set. They give a lower bound on each support, but not the exact counts. The last worked example below shows two databases with identical maximal families and different supports.
Worked examples
Worked example 2.2.8
(Supports and closures of all sixteen itemsets)
Take and . The transaction multiset is:
| Index | Transaction |
|---|---|
Note that and are duplicates and are counted twice. The closure is computed only where the support is positive. The final column uses the definition of closedness for every itemset, including those of zero support.
| Containing transactions | supp | Frequent? | Closed? | ||
|---|---|---|---|---|---|
| all six | 6 | yes | yes | ||
| 1,2,3,4,6 | 5 | yes | yes | ||
| 1,2,3,5 | 4 | yes | yes | ||
| 1,2,4 | 3 | yes | no | ||
| 4,5 | 2 | yes | yes | ||
| 1,2,3 | 3 | yes | yes | ||
| 1,2,4 | 3 | yes | yes | ||
| 4 | 1 | no | no | ||
| 1,2 | 2 | yes | no | ||
| 5 | 1 | no | yes | ||
| 4 | 1 | no | no | ||
| 1,2 | 2 | yes | yes | ||
| none | 0 | no | (undefined) | no | |
| 4 | 1 | no | yes | ||
| none | 0 | no | (undefined) | no | |
| none | 0 | no | (undefined) | yes |
The intersection of all six transactions is , so is closed, with support , and it is frequent.
The frequent itemsets (9) are . The closed frequent itemsets (7) are , , , , , , . The maximal frequent itemsets (2) are , because , and , because , and each have support . Both are closed, as the theorem on maximal itemsets predicts.
Worked example 2.2.9
(Reconstructing supports from closed frequent sets)
In the same database, recover supports from the closed frequent itemsets , , , , , , .
- For : the frequent closed supersets are and . The maximum is , which matches .
- For : the only frequent closed superset is , giving .
- For : there is no frequent closed superset, so is infrequent, which agrees with .
Worked example 2.2.10
(Maximal sets lose counts)
Delete from the database above to obtain a second multiset of five transactions. The supports change as follows: becomes , becomes , and every other support is unchanged. The frequent family is identical, so the maximal sets are still . However, the support of is in one database and in the other. The maximal sets alone cannot tell these two databases apart, whereas the closed frequent sets can: becomes and becomes .
Common mistake
(Counting duplicate transactions once)
In the database above, and are equal as sets but are separate transactions. Merging them would make , and would wrongly become infrequent. The support count is taken over indices, so duplicates each contribute one.
Exercises
Quick check
(Take , and the transactions , , . Compute , and . Which of , , are closed?)
Intersect the transactions that contain each itemset.
Solution · Answer
All three transactions contain , and , so . The transactions containing are the first two, so . The transactions containing are the last two, so . Each of the three differs from its closure, so none is closed. In particular is not closed here, because the intersection of all transactions is not empty.
Quick check
(For the same database, list the closed frequent itemsets with their supports and the maximal frequent itemsets.)
Compute all supports first: , and , have support .
Solution · Answer
The supports are , , , , , , , . The frequent itemsets are . The closed ones among them are , and , since were shown not to be closed. The maximal frequent itemsets are and . Each is closed, as expected, while is closed and frequent but not maximal.
Quick check
(Using only the closed frequent itemsets , , of the same database, find and , and decide whether is frequent.)
Apply the reconstruction formula.
Solution · Answer
The closed frequent supersets of are alone, so . The closed frequent supersets of are alone, so . No closed frequent itemset contains , so is not frequent; indeed .
Roadmap and checklist
- Fix , the multiset , and an integer . Count duplicates separately.
- List all supports, or mine the frequent sets with Apriori.
- For each frequent , compute by intersecting the transactions that contain it. Mark closed if .
- Remember the empty set: it is closed whenever the intersection of all transactions is empty.
- Mark a frequent maximal when no frequent set properly contains it. Verify that each maximal set appears among the closed ones.
- Exhibit a closed nonmaximal frequent set, if one exists.
- Reconstruct supports from the closed frequent sets. Use maximal sets only to decide membership in the frequent family.
- Keep the zero-support convention separate from the positive-support intersection construction.