Hi this is my question post at researchgate, so please go easy on me. I tried going through an algorithm Dualize and Advance for generating maximal frequent item sets. I considered an example as follows
Transactions
1.abcde
2.ace
3.bd
4.abc
and minimum frequency threshold as 2.
Now, I have a problem understanding how to generate 'minimal transversals' part of the algorithm.
I understood that transversal is a subset of vertices of the hypergraph that intersects every hyper edge. So the initial set of minimal transversals should be {a,b,c,d,e} if I am not wrong.
Can you please explain me this part of 'minimal transversal' w.r.t the transactions.
See the following article. It will be helpful to you.
Thomas Eiter and Georg Gottlob. Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM J. Comput., 24(6), 1278–1304., DOI:10.1137/S0097539793250299
Hi, your understanding of a transversal of a hypergraph is correct and yes the initial one could be the vertex set of the hypergraph. If I understand your problem correctly then your transactions are the hyperedges of a hypergraph and you want to find the minimal transversal of that hypergraph. Then you have found a maximal frequent item in the set of transactions of some length between 1 and |V| (V is the vertex set). That is how I would understand the formulation "minimal transversal w.r.t. transactions".
You are absolutely right. At the end of first iteration of the algorithm and for the given transactions, {abc} is emanated as maximal frequent itemset. Here is how I understood,
minimal transversal X = S1' = {a,b,c,d,e}
S2 = {abc} is maximal and S2' = {de}
Find minimal transversal of S2' which is {d,e}
Now, X = {d,e}, consider 'd' ,
S3 = {bd} is maximal and S3' = {ace}
Now, consider 'e'
S4 = {ace} is maximal and meanwhile I get {ad} , {be} ,{cd} and {de} as minimal transversals which are infrequent.
See the following article. It will be helpful to you.
Thomas Eiter and Georg Gottlob. Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM J. Comput., 24(6), 1278–1304., DOI:10.1137/S0097539793250299
Hi Suvdev Naduvath. Thanks a lot sir for the reference paper. But I solved it as shown above.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms