HI
i have a question about forward and backward checking which is used in EFIMclose algorithm .would you please explain the difference between forward and backward checking?
Thank you

Hi,

Just saw your message.

I will try to explain in a simple way.

In the algorithm EFIM-Closed we use some processing order to process items.

To make my example simple, let's say that this order is A < B < C < D < E < F.

And let's say that we have a transaction database with three transactions:

T1: A B C D
T2: A B D
T3: A C D E F

Now, all the itemsets and transactions are sorted according to this order.

So now, let's say that the algorithm wants to check if the itemset X={B,D} is closed.

We know that {B,D} has a support of 2.

To check if {B,D} is closed, we need to know if we could add an item to {B,D} such that the resulting itemset will still have the same support of 2. If we can find such item, then we know that {B,D} is not closed. Otherwise {B,D} is closed.

There are two cases:
- We could add an item after the last item of {B,D} to create some itemset like {B,D, E} or {B,D,F}. If we add an item after the last item, we call this a forward extension.
- Or we could add an item before the last item of {B,D} to create some itemset like {A, B,D} and {B, C, D}. This is called a backward extension.

So in other words, if an itemset like {B,D} has a forward-extension or a backward-extension that has the same support as {B,D}, then {B,D} is not closed.

Let's check.

In my example, we can find that the itemset {B,D} has a backward extension {A,B,D} that has also a support of 2! Thus, {B,D} is not closed!

Let's take another example.

Consider the itemset {A, C}, which has a support of 2.

Is it closed?

We can look at the backward and forward extensions to know the answer. We find that there is a foward extension {A,C,D} that has the same support as {A,C}. Thus, {A,C} is not closed.

So that is the main idea about the concepts of foward and backward extensions.

When EFIM-Closed considers an itemset, it will check the forward and backward extensions to determine if it is closed or not.

Best regards,
Philippe

Hi
Thank you for your response.i learned forward/backward extensions with your good explanation.

Happy it is clear;-)

Best regards,

Philippe