Frequent Pattern Mining 3

다시한번 Apriori 알고리즘의 Challenge들을 말해보자면

• 많은 수의 DB scan이 있다. 최대 k번 접근
• 그리고 i1i2i3—-i100이라는 FP가 있다고 하자.
  • 그랬다면 지금까지 DB scan은 100번이 일어났을 것이고
  • 이 FP를 만들기 위해서 최대 2^100 -1 개의 itemset들이 만들어졌을 것이고 검사되었을 것이다.
• 그리고 candidates들에 대한 tedious counting workload.

위 3가지의 문제점을 극복하기 위한 여러가지 알고리즘을 공부해보자.

DIC : Dynamic ItemSet Count

Dynamic ItemSet Count의 줄임말로 기존의 Apriori는 size-1 itemset이 다 끝나면 size-2 itemset을 count했다. 그러지말고 DIC에서는 k번째 Itemset에 대해서 count를 하다가, FP들을 발견해서 그걸로 K+1짜리 itemset을 만들 수 있다면 해당 iteration에 K+1짜리 itemset을 같이 넣어서 검사를 하자는 형식이다.

예전 Apriori에서는 count할 때 매우 static했는데 지금은 iteration 도중에 minsup을 넘어서 FP가 된 애들에 한해서는 그다음 size의 후보를 만든 다음 바로 지금 iteration에 넣어서 같이 count하자는 것이 골자이다.

기억해야하는 포인트는 size k+1짜리 itemset들은 iteration 중간에 끼어진 것이기 때문에 앞쪽의 row들에 대해서는 count를 하지 못했다. 그래서 지금 진행하던 iteration이 끝나더라도 다시 와서 앞쪽의 것들에 대해서 count 검사를 해봐야한다.

위 그림이다.

DIC의 장점은 DB scan을 줄여준다는데에 있다. DB access야 거의 동일하게 하겠지만 Apriori랑 비교했을 때 .

DB scan을 entire DB를 전체 다 돈다는거로 치면 원래 Apriori는 entire DB scan을 k번했겠지만, 이건 확실히 k번 하지 않아도 된다. 전체를 다 돌지 않아도 된다는 뜻 그렇게 되면 disk i/o를 하는 시간이 줄게 되므로 속도가 향상된다. 

자세하게 말하자면 1st scan에서는 size1짜리 itemset만 DB scan을 했지만, DIC에서는 1st scan에서 size2와 size3까지 진행할 수 있으므로 전체적인 DB scan 수가 줄어든다. (위의 그림만 보더라도 원래는 3번 scan했어야 했는데 2번도 꽉 안채우게 돌았는데도 끝났다)

 

그다음 DB scan을 줄일 수 있는 두번쨰 방법이 있는데 Partition이라고 한다.

Partition: 

먼저 DB를 k 개의 조각으로 나눈다. (물론 이 조각들은 메인메모리 위에 올라갈 수 있는 사이즈여야한다.)

그리고 각 메모리에 올린 Piece들에 대해서 메모리에서 Apriori를 돌린다. 그러면 k pieces들에 대해서 다 돌리면 전체적인 DB scan은 한번만 할 수 있다. 그리고 각 partition을 Apriori를 돌릴 때 minSup을 k로 나눈 local minsupport를 구한다. 그리고 partition에서 구한 support가 localminsup을 넘는다면 이것은 FP가 될 가능성이 있다. 그리고 FP에 넘는 FP 후보들을 전체 DB에 대해서 global minSup을 넘는지 다시 테스트해야하기 때문에 여기서 scan2가 일어난다. 그래서 총 db scan이 2번밖에 안든다.

 

그리고 알아야 할 것은 어떤 FP가 partition으로 짤렸다하더라도 무조건 최소 하나의 파티션에서는 localminsup을 넘는 파티션이 나온다는것이다. 하지만 local minsup을 넘는다고 해서 global minsup을 넘지는 못할 가능성이 있기 때문에 scan2때 검사해봐야한다.

 

Sampling

Sampling이란? 샘플링이란 DB를 아까 전 Partition기법처럼 나누고 그 한 조각을 샘플처럼 보고 거기서 FP를 뽑아내는것이다. minimumsupport도 그 나눈 비율만큼 줄어든다.

sampling의 문제는? sampling방법은 두가지 문제가 있는데

1. 먼저 sample에서만 FP를 뽑아냈기 때문에 전체적인 FP는 다 찾을 수 없다는 것이고,

2. sample에서 찾은 FP가 사실은 진짜 FP가 아닐 수 있다는점이다. 해당 sample에서만 local minsup을 넘은것이고 global로는 넘지 않았을 수 있다.

그것을 해결하기 위한 방법을 알아보자.

 

먼저 SDB에서 찾은 FP를 전체 DB를 훑으면서 진짜 min_sup을 넘는지 확인한다(2번 문제 해결). 그리고 SDB에서 찾은 FP가 사실 모든 FP가 아닐 수 있기 때문에 S의 negative border를 찾아서 negative border또한 whole database에서 min_sup을 넘는지 확인한다.(1번 문제 해결)

이게 partition과의 차이점이다.

여기서 negative border란

1. S안에는 없고
2. 그 NB의 부분집합이 S여야 하고
3. +single item

이 negative border이다.

bc,bf가 1,2번에 해당하고 d,e가 3에 해당한다.

 

왜 negative border를 찾냐면 NB의 부분집합이 S에 해당하는데 S는 FP일 가능성이 있기 때문에 그것의 상위집합인 NB또한 FP일 가능성이 있기 때문이다. 예를 들어, S의 b,f가 각각 FP일 가능성이 있는데 그렇기 때문에 {b,f}를 확인해봐야한다.

이게 1차적으로 SDB에서 파생될 수 있는 아이템들을 확인하는 방법이고

만약 NB에서 진짜 FP를 찾는다면 S와 NB의 결합도 global db에서 한번 검사해야한다.

NB에서 b,c가 성공했으므로 {a,b}, {a,c}, {b,c}의 조합인 {a,b,c}도 검사해본다.

하지만 이렇게 했다고 모든 FP들을 완벽하게 찾을 수 있는 것은 아니다.

하지만 이 방법으로 많은 FP들을 찾고, candidate 수도 획기적으로 줄여준다(sample로 짤랐고 거기서 확장하는 것이기 때문에)

 

DHP

이 방법은 Direct Hash and Pruning이라는 방법이다.

Lk을 만들 때 즉시 각 transaction마다 size k+1짜리 itemset을 만들고 hashing해서 hash bucket count(얼마나 그 인덱스에 해시값이 있는가) table을 유지한다.

그림의 우상단에서 C1에서 L1을 만들면서 size 2짜리 item에 대한 hashtable을 만든다. 각 transaction마다.

그래서 hash를 해봐서 해당 인덱스에 카운트를 ++시킨다. 어떤 hash function을 쓸 것인지는 마음대로.

 

그리고 가장 중요한 아이디어는 지금 나온다.

이제 Lk에서 Ck+1을 만들고 나서 원래같았으면 Ck+1에 대해 DB scan을 하면서 pruning을 했어야했지만 지금은 해당 아이템에 대한 해시 값을 보고 해시값이 min_sup보다 작으면 가차없이 지워내도 상관없는 것이다. 왜냐하면 해시카운트가 다른 아이템들과도 섞여진 값인데 그 값이 min_sup보다 작으면 개별 아이템의 카운트는 min_sup보다 작은 것이 보장되기 때문이다.

 

여기서 짚고 넘어가야할 것은 해시를 확인해서 지우는 과정을 하고 남은 Ck+1이 모두 FP라고 말할 수는 없는 것이다. 하지만 어차피 안되는 것들을 빨리 지우는 점(상수 시간만에 지운다)에서 효과가 있다는 것. 그래서 Ck+1을 다시 DB를 돌면서 Apriori를 해봐야한다.

다시 정리를 하자면 C2에서 원래라면 Apriori를 통해 {A,B}, {A,E}도 카운트해봤겠지만 DHP는 바로 지울 수 있기 때문에 검사를 해봐야하는 후보를 줄인다는 점이 의의가 있다.