Re: EFIM
Date: November 13, 2020 08:34AM
frank Wrote:
-------------------------------------------------------
> Hi
> thank you for help.in line 4 of algorithm 2 in
> efim close when we want to check backward
> extention of item beta we scan database alfa-D or
> beta-D?
> Regards
Hi Frank,
I will explain a bit. We have an itemset BETA and we want to check if it is closed. Thus we will check if it has a backward extension or if it has a forward extension.
To check if BETA has a backward extension, we need to check all transactions that contain BETA. So this means that we need to check all transactions that are in BETA-D. However, it is important to note that we dont really use the transations as they are in BETA-D. We instead use the ORIGINAL transactions that correspond to those in BETA-D.
Why? The reason is that the transactions in BETA-D have been cut (some items have been removed) when doing the projection. But when we check for backward extensions, we need to be able to check the items that have been removed. So we check all original transactions that correspond to those in BETA-D.
For example if BETA = C
And the original database is:
Transaction 1 : A B C D E
Transaction 2 : A B C E F
Transaction 3 : A B G
and the total order is A < B < C < D < E < F,
the projected database of BETA is:
Transaction 1 : D E
Transaction 2 : E F
If we want to check if BETA has a backward extension, we need to check all the transactions in the BETA-projected-database, that is transactions 1 and 2.
Transaction 1 : D E
Transaction 2 : E F
However, we will check for backward extensions of BETA using the corresponding original transactions:
Transaction 1 : A B C D E
Transaction 2 : A B C E F
and we will find that A appears 2 times and B appear two times...
Thus BETA has two backward extensions. The first one is the item A. The second one is the item B.
Hope that this helps
Edited 2 time(s). Last edit at 11/13/2020 08:37AM by webmasterphilfv.