Hi
I read EFIM Close algorithm but i did not understand the concept of prune withe closure jumping would you please explain this prune strategy with example?
Thanks

Hi,

I will try to explain this optimization with a simple example.

Let's say that we have a database containing only three transactions:

Transaction 1: A B C D E F

Transaction 2: A B C D E F

Transaction 3: A B C

Then, the algorithm will star to search for the closed itemsets. At some point the algorithm will find {A,B,C} and will then want to extend that itemset further to find larger itemsets starting with {A,B,C}.

The algorithm will count what items could extend {A,B,C}. The answer is:

"D" and it appears two times after {A,B,C}

"E" and it appears two times after {A,B,C}

"F" and it appears two times after {A,B,C}

Because all the items D, E, and F that could extend {A,B,C} have the same support (two times), then we can directly jump to the itemset {A,B,C,D,E,F} and we know that this itemset will be closed.

The other itemsets starting with ABC like ABCD, ABCE, ABCF, ABCDE, ABCDF etc cannot be closed because they will all have a support of 2, and {ABCDEF} has a support of 2.

This is the reason why we can jump directly to ABCDEF... This will save time because we dont need to explicitly check ABCD, ABCE etc...

So this is an optimization for closed itemset mining.

Hope that this is more clear.

Best regards,

Philippe

Hi
Thank you for your good explanations i understand it.
Best regards

Great :-)

Hi
in your previous example the support of ABC is not equal to the support of D,E,F and in the EFIM close algorithm in page 10 mention that the the support of itemset BETA should be equal to the support of BETA with item z.is it true?

Thanks

Hi,

Yes, it is indeed written as you said in the paper. And I am checking the code and it seems that the paper and the code are the same. So it is my example above that contains error, and BETA should have the same support as Z

Good that you found it.

Hi again
thank you