Maximal & closed frequent -- Answer Included

Question

$$My \ \ dataset:$$ $$1: A,B,C,E$$ $$2:A,C,D,E$$ $$3:\ \ \ \ \ B,C,E$$ $$4:A,C,D,E$$ $$5:\ \ \ \ C, D, E$$ $$6: \ \ \ \ A, D,E$$

I want to find out the maximal frequent item sets and the closed frequent item sets.

Frequent item set $X ∈ F$ is maximal if it does not have any frequent supersets.
Frequent item set X ∈ F is closed if it has no superset with the same frequency

So I counted the occurrence of each item set.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

{A,B} = 1; {A,C} = 3; {A,D} = 3; {A,E} = 4; {B,C} = 2; 
{B,D} = 0; {B,E} = 2; {C,D} = 3; {C,E} = 5; {D,E} = 3

{A,B,C} = 1; {A,B,D} = 0; {A,B,E} = 1; {A,C,D} = 2; {A,C,E} = 3; 
{A,D,E} = 3; {B,C,D} = 0; {B,C,E} = 2; {C,D,E} = 3

{A,B,C,D} = 0; {A,B,C,E} = 1; {B,C,D,E} = 0

Min_Support set to $50%$ // Very important. Thanks steffen for reminding of that.

Does maximal = $\{{A,B,C,E\}}$ ?

Does closed = $\{{A,B,C,D\}} \ and \ \{{B,C,D,E\}}$?

score 5 · Accepted Answer · edited Jan 14 '19 at 07:58

I found a slightly extended definition in this source (which includes a good explanation). Here is a more reliable (published) source: CHARM: An efficient algorithm for closed itemset mining by Mohammed J. Zaki and Ching-jui Hsiao.

According to this source:

An itemset  is  closed  if  none  of  its  immediate  supersets  has   the  same  support  as  the  itemset
An  itemset  is  maximal  frequent  if  none  of  its  immediate  supersets  is  frequent

Some remarks:

It is necessary to set a min_support (support = the number of item sets containing the subset of interest divided by the number of all itemsets) which defines which itemset is frequent. An itemset is frequent if its support >= min_support.
In regards to the algorithm, only itemsets with min_support are considered when one tries to find the maximal frequent and closed itemsets.
The important aspect in the definition of closed is, that it does not matter if an immediate superset exists with more support, only immediate supersets with exactly the same support do matter.
maximal frequent => closed => frequent, but not vice versa.

Application to the example of the OP

Note:

Did not check the support counts
Let's say min_support=0.5. This is fulfilled if min_support_count >= 3

{A} = 4  ; not closed due to {A,E}
{B} = 2  ; not frequent => ignore
{C} = 5  ; not closed due to {C,E}
{D} = 4  ; not closed due to {D,E}, but not maximal due to e.g. {A,D}
{E} = 6  ; closed, but not maximal due to e.g. {D,E}

{A,B} = 1; not frequent => ignore
{A,C} = 3; not closed due to {A,C,E}
{A,D} = 3; not closed due to {A,D,E}
{A,E} = 4; closed, but not maximal due to {A,D,E}
{B,C} = 2; not frequent => ignore
{B,D} = 0; not frequent => ignore
{B,E} = 2; not frequent => ignore
{C,D} = 3; not closed due to {C,D,E}
{C,E} = 5; closed, but not maximal due to {C,D,E}
{D,E} = 4; closed, but not maximal due to {A,D,E}

{A,B,C} = 1; not frequent => ignore
{A,B,D} = 0; not frequent => ignore
{A,B,E} = 1; not frequent => ignore
{A,C,D} = 2; not frequent => ignore
{A,C,E} = 3; maximal frequent
{A,D,E} = 3; maximal frequent
{B,C,D} = 0; not frequent => ignore
{B,C,E} = 2; not frequent => ignore
{C,D,E} = 3; maximal frequent

{A,B,C,D} = 0; not frequent => ignore
{A,B,C,E} = 1; not frequent => ignore
{B,C,D,E} = 0; not frequent => ignore

The source link is broken, just letting you know. And yes min_support is very important, I am using .50 — Mike John, Nov 24 '13 at 11:20
changed min_support=0.5 <=> min_support_count=3 and changed application to example accordingly. — mlwida, Nov 24 '13 at 11:35
Use APRIORI, and you can save a lot of counting and constructing itemsets... — Has QUIT--Anony-Mousse, Nov 28 '13 at 19:30
@Anony-Mousse I know APRIORI ... I stepped over the itemsets manually to explain the concept of closed and maximal frequent itemsets as detailed as possible, since this was the source of confusion of the OP (IMHO). — mlwida, Nov 29 '13 at 06:14
But yeah, I should have skipped the sets where subsets are already not frequent. — mlwida, Nov 29 '13 at 06:21
@steffen Hi, I'm a bit confused, why {C,D} = 3 is not closed due to {C,D,E} , but {C,E} = 5 is closed? — Daniel Chepenko, Oct 06 '17 at 03:38

score 1 · Answer 2 · answered Nov 28 '13 at 19:33

You may want to read up on the APRIORI algorithm. It avoids unneccessary itemsets by clever pruning.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

B is not frequent, remove.

Construct and count two-itemsets (no magic yet, except that B is already out)

{A,C} = 3; {A,D} = 3; {A,E} = 4; 
{C,D} = 3; {C,E} = 5; {D,E} = 3

All of these are frequent (notice that all that had B cannot be frequent!)

Now use the prefix rule. ONLY combine itemsets starting with the same n-1 items. Remove all, where any subset is not frequent. Count the remaining itemsets.

{A,C,D} = 2; {A,C,E} = 3; {A,D,E} = 3; 
{C,D,E} = 3

Note that {A,C,D} is not frequent. As there is no shared prefix, there cannot be a larger frequent itemset!

Notice how much less work I did!

For maximal / closed itemsets, check subsets / supersets.

Note that e.g. {E}=6, and {A,E}=4. {E} is a subset, but has higher support, i.e. it is closed but not maximal. {A} is neither, as it does not have higher support than {A,E}, i.e. it is redundant.

Maximal & closed frequent -- Answer Included

2 Answers2