Re: Forward /backward extentions in EFIMclose
Date: August 06, 2020 10:25PM
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