Frequent Pattern Mining 5

그다음에는 P-conditional Pattern Base를 만들어야 한다.

F-list의 역순으로 읽으면서 P-conditional Pattern Base를 만드는데 트리를 타고 올라가면서 생성되는 패턴이 cond.pattern base에 적히게 되고 그 수를 적어준다. 그리고 링크드리스트의 next가 있으면 next를 타고 가서도 생기는 노드들을 적어주면 된다. 이렇게 되면 각 cond.pattern base는 target DB에 정확하게 매칭된다.

 

T1은 p를 가지고 있는 FP들을 가지고 있는 DB였고 T2는 p는 없고 m을 가지고 있는 그리고 T3는 m,p는 없이 b를 가지고 있는 DB였는데 cond.pattern base를 생성할 때 F-list의 역순으로 읽다보니 이것들은 자동으로 보장된다. 이게 장점이다.

 

정확히 이 말을 가리킨다.

 

아직까지 FP를 찾는 방법은 나오지 않았다.

이제 cond.pattern-base에서 cond.fp-tree를 찾아보자.

cond.pattern base에서 하나를 골라서 예를들어 m을 골랐을 때 m-cond.pattern base는 fca: 2, fcab:1이다. 위에서 나온 대로 accumulate the count for each item in the base를 하면 f : 3번, c: 3 a: 3, b:1이 나오는데 Min_sup이 3이기 때문에 f:3, c:3, a:3이 나오고 이걸 통해서 FP-tree를 생성한다. 그게 그림 가운데에 있는 m-conditional FP-tree이다. 원래 종료조건은 single path가 나오거나 FP-tree가 empty이면 종료하기 때문에 single path이므로 종료한다. 그리고 여기서 FP를 생성해주면 된다. 해당 conditional FP-tree는 DB | m이기 때문에 m을 붙여주면 된다.

size0, size1, size2, size3에 m을 하나씩 붙여주면 맨 오른쪽 FP가 나오게 된다.

만약 single path가 아니거나, empty가 아니라면 계속 recursion을 해야하는데 이건 바로 이 다음에 나온다.

 

recursion은 위에서 했던 conditional pattern base를 f-list기반으로 만들고 그 conditional pattern base가 single path이거나 empty node일때까지 이 과정은 계속 반복하는 것이다.

 

이런 예시가 있다. m-conditional pattern base인데 FP-tree를 그리니까 single-path, empty가 아니다. 그리고 f랑 a로 루트에서 나뉘어져있다. 이럴때는 다시 f-list를 보고 ( f c a ) cond.pattern-base를 생성한다. a는 {} , f는 {}, c는 f:3이다(Min_sup 넘음) 그러므로 am conditional pattern base에서는 am을 붙여주고

cm conditional pattern base에서는 cm을 붙여주고 fm pattern base에서는 fm을 붙여준다.

그리고 모두가 empty이거나 single-path이므로 종료한다.

 

이건 FP growth tree의 수도코드이다.

Tree는 만약 초기라면 global FP-tree이고 재귀적으로 불러진 콜에서는 m-conditional fp-tree인 셈이다.

 

그리고 a(알파)는 m-conditional pattern base에서 m의 역할이다. 어떤 걸 중심으로 conditional pattern이나 conditional fp tree를 그릴 것인지 정하는 역할.

 

먼저 if를 보자면 single path인 경우에 베타는 P에서 만들수있는 조합 가지이다. {}, f, c, a, fc, fa, ca, fca 이렇게 각각에 대해서 pattern은 알파와 합치라는 소리이다 그게 옆에 만들어진 m, fm, cm, 이런식.

그리고 support는 각 베타의 노드의 서포트 중 최소를 고르라는 소리인데 만약 저 m-cond. pattern base에서 f:5, c:4였다면 a가 들어간 fp는 5나 4가 아닌 3이 될것이라는 소리이다.

 

그다음 else를 보자면 Tree의 각 header에 대해서 (즉, f-list의 각 header (f / c / a)에 대해서) pattern B는 fm, cm, am이고 support는 f-list의 support가 된다. 그리고 각 베타에 대한 conditional pattern base를 세우고 treeB를 만든다. 만약 그 트리가 공집합이 아니라면 FP-growth를 재귀호출한다. 만약 싱글패스였다면 들어가서 if문에 걸렸을것이다.

 

 

그래서 FP-growth tree와 standard apriori를 비교하자면 FP-tree에서 엄청난 성능개선이 이루어진다.

만약 min_sup이 높아지면 통과되는 구멍이 작아지는거라 candidate가 많이 생성되지 않는다. 그래서 apriori도 테스트할 게 많이 줄어들기 때문에 apriori와 fp-tree가 얼마 차이 나지 않는다.

하지만 min_sup이 낮아져서 filter가 느슨해진다면 무수하게 많은 candidate가 생성되기 떄문에 apriori와 fp-tree의 성능차이가 엄청 나게 된다.

 

다시 한번 정리를 해보자

FP-growth tree가 왜 뛰어나냐면

1. divide and conquer를 쓰기 때문에 빨라질수밖에 없다. 나눠서 빠르게 계산하고 다시 합치는거라서

그리고 나눌때 disjoint set으로 나누기 때문에 나중에 확인할 필요가 없다. 무조건 분리집합끼리 나누고 합치는거라 나누고 합치기만하면 다시 global로 복구가능.

1. fp들로만 db를 생성해서 확인하기 때문에 만들어진 작은 fp-tree는 메모리에 올라간다. 그래서 빠르게 계산할 수 있다.
2. candidate를 만들지 않고 candidate를 test하지 않기 때문에 빠를 수 밖에 없다.
3. 그리고 db스캔을 적게 한다. 딱 두번한다.
   1. 처음 size 1 itemset을 가져올때와
   2. global fp-tree를 만들기 위해서 f-list를 가지고 db를 접근해서 global fp-tree를 만들때

이렇게 딱 두번만 접근하기 떄문에 빠르다.