Association Rules - Advanced Artificial Intelligence - page 443

2. for (k=flen-1; k>=0; k--) { // flen is the length of frequent itemset
3. pat[0]=fitem[k];
4. output { pat[0]} with support count[k];
5. generate ST(k).EndArray[];
6. mine(ST(k));
7. }
Procedure mine(ST(

i k ,..., i

2 ,

i

)) {

1

i k ,..., i

2 ,

i i k ,..., i

2 ,

i

1. generate ST( ).fitem[] and ST( ).count[], let the length be listlen;

1 1

2. if (listlen==0 ) then return;
3. if (listlen==1) then {pat[patlen]= ST(

i k ,..., i

2 ,

i

).fitem[0];

1

i k ,..., i

2 ,

i

output pat with support ST( ).count[0]; return}

1

i k ,..., i

2 ,

i

4. if ST( ) has only single path then

{ output pat ∪ all the combination of ST(

1

i k ,..., i

2 ,

i

).fitem[];

1

return; }
5. patlen++;
6. for (k=listlen-1; k>=0; k--) {
7. generate array;
8. generate ST(

i k ,..., i , i , k

).EndArray[];

2 1

i k ,..., i , i , k

9. if ST( ).EndArray[] is not NULL then

2 1

i k ,..., i , i , k

10. mine(ST( ));

2 1

11. }
12. patlen--;
13. }
In mine procedure, line 1 generate frequent itemset in the constrained subtree
ST(

i ,...,i ,i

). Line 2~3 process the condition while listlen is 0 or 1. Line 4
process the condition while constrained subtree has only single path. Line 6~11
generate new array and constrained subtree, then mine the new subtree.
Because the CFP-tree could have millions of nodes, thus, it takes plenty of
time for allocating and deallocating the nodes. Just like (Grahne, 2003), we also
implement unified memory management for CFPmine algorithm. In the
recursively mining process, the memory used in it is not frequently allocated and
freed. It allocating a large chunk before the first recursion, and when a recursion
ends, it doesn't really free the memory, only changes the available size of chunk.
If the chunk is used up, it allocates more memory. And it frees the memory only
when all the recursions have been finished.

2 1