This forum is about

Difference between "Forward/Backward extension checking" and "Closure jumping"

Posted by:
**
solmaz
**

Date: February 07, 2020 08:32PM

Hello, Prof. Philippe Fournier-Viger.

Thank you for taking the trouble to help me for previous questions. I do appreciate it.

In paper Efim-Closed, for find closed high utility itemsets mining, used of two methods

Forward/Backward extension checking:

To determine if an itemset X is closed, check if there exists an item not in X that appears in all transactions where X appears. If yes, then X is not closed

Closure jumping:

For an itemset X, if all items not in X that can be appended to X have the same support as X, they can be directly appended to X to obtain a closed itemset.

I understand method "Forward/Backward", but I don't understand method "Closure jumping". Can you give an example? what's the difference?

Thank you for taking the trouble to help me for previous questions. I do appreciate it.

In paper Efim-Closed, for find closed high utility itemsets mining, used of two methods

Forward/Backward extension checking:

To determine if an itemset X is closed, check if there exists an item not in X that appears in all transactions where X appears. If yes, then X is not closed

Closure jumping:

For an itemset X, if all items not in X that can be appended to X have the same support as X, they can be directly appended to X to obtain a closed itemset.

I understand method "Forward/Backward", but I don't understand method "Closure jumping". Can you give an example? what's the difference?

Posted by:
**
webmasterphilfv
**

Date: February 07, 2020 08:51PM

Hi,

You have understand the main idea about forward/backward checking.

For closure jumping, the idea is not complicated. It is as follows. Let say that you have this database:

A B C D F

A C D F

A C D E F

A E

You can count the support of the items:

A = 4

B = 1

C = 3

D = 3

E = 2

F = 3

Since C, D and F have the same support, it means that they always appears together, and thus we can directly say that {C,D,F} is a closed itemset. It is unecessary to check the itemset {CD} {DF} and {CF} because they will not be closed. So using this technique we "jump" directly to {C,D,F} and output it as a closed itemset which will save some time.

You can apply this technique on the input database or in any projected database.

Best regards,

Philippe

Edited 2 time(s). Last edit at 02/07/2020 08:52PM by webmasterphilfv.

You have understand the main idea about forward/backward checking.

For closure jumping, the idea is not complicated. It is as follows. Let say that you have this database:

A B C D F

A C D F

A C D E F

A E

You can count the support of the items:

A = 4

B = 1

C = 3

D = 3

E = 2

F = 3

Since C, D and F have the same support, it means that they always appears together, and thus we can directly say that {C,D,F} is a closed itemset. It is unecessary to check the itemset {CD} {DF} and {CF} because they will not be closed. So using this technique we "jump" directly to {C,D,F} and output it as a closed itemset which will save some time.

You can apply this technique on the input database or in any projected database.

Best regards,

Philippe

Edited 2 time(s). Last edit at 02/07/2020 08:52PM by webmasterphilfv.

Posted by:
**
solmaz
**

Date: February 07, 2020 10:16PM

Thanks for your complete and accurate description