[Frequent Data Mining] Reduce DB Scan and Candidates

Apriori의 문제점과 해결

Apriori의 문제점

• Transaction DB scan 횟수가 너무 많다. → partition, sampling 이용
• 생성되는 candidate의 수가 너무 많다. → DHP 이용
• support counting에 대한 cost가 높다. → DIC 이용

 

Reduce DB Scan and Candidates 

• Partition : DB scan 횟수 줄이기 $\rightarrow$ 2번만 scan
• DHP : Candidate 수 줄이기 $\rightarrow$ hash table 이용
• Sampling : DB Scan 횟수 줄이기 $\rightarrow$ 1 + 2번 scan
• DIC : support를 구하는 cost 줄이기 $\rightarrow$ 병렬 scan

 

---

Partition

Scan Database only Twice

 

Apriori alogirothm은 가장 긴 frequent pattern의 길이만큼 DB scan이 발생한다.

Disk access는 cost가 매우 높기 때문에 이를 줄여야 하는데, 이를 위해서는 DB를 메모리에 올려야 한다.

그러나 빅데이터 시대가 다가와 데이터의 크기가 매우 커진 요즘은 이것이 힘들다.

 

Partition은 전체 DB를 k개의 piece로 나누어서 단 두번만 scan하도록 만든 것이다.

나누어진 piece (local database)를 partition이라 한다.

각 parition이 메모리에 올라올 수 있도록 k를 조절해야 한다.

 

2 DB Scan

• Scan 1 : local frequent pattern 찾기
  • 나누어진 partition 내에서 frequent pattern을 찾는다.
  • local minimum support = $\frac{min\_sup}{k}$
    • 나누어진 partition에 대해서 기존의 minimum support를 그대로 적용할 수 없다. 
    • 따라서 $\frac{min\_sup}{k}$을 local minimum support로 삼는다.
  • No false-negative, Yes false-positive
    • frequent pattern이 아닌데 frequent하다고 나오는 경우는 없지만, frequent pattern 하다고 나왔는데 frequent 하지 않은 경우가 발생할 수 있다.
    • 따라서 전체 길이에 대한 candidate에 대해 DB scan을 다시 하면서 테스트를 해야 한다.
• Scan2 : global frequent pattern 통합
  • scan1에서 찾은 local freuqnet pattern들에 대해서 체크하는 과정이다.
  • scan1에서 false-positive가 있기 때문에 다시 체크해야 한다.

 

Never Miss

놓치는 frequent pattern이 존재하지 않는다.

Frequent pattern이라면 하나 이상의 partition에서 $\frac{min\_sup}{k}$ 이상의 support를 가지기 때문이다.

 

다만, global하게 frequent 하지는 않은데 local하게 frequent 하다고 나올 수는 있다.

이를 해결하기 위해 다시 한번 DB를 scan하면서 체크한다.(Scan2 과정)

 

---

DHP (Direct Hashing and Pruning)

Hash table을 이용해서 생성되는 candidate의 수를 줄인다.

 

Hash 값이 같은 itemset들의 count를 합하고 이것이 minimum support보다 작을 경우 버린다.

이를 통해 생성되는 candidate의 수를 줄일 수 있다.

 

과정

1. 1-itemset의 candidate 생성
2. (k+1)-itemset에 대한 hash table 생성
3. hash table의 count 값이 minimum support보다 작으면 해당 열의 itemset을 모두 제외시킨다.

 

---

Sampling for Frequent Patterns

원래의 DB에서 메인 메모리에 올라올 수 있는 크기로 sampling을 하고 apriori를 이용해서 frequent pattern을 mining한다.

 

각 sample에 대한 minimum support는 $min\_sup \; \times \; sample\_rate$으로 한다.

* $sample\_rate$ : sampling 되는 비율

 

vs. Partition

Partition은 전체 DB를 일정 크기로 자르고 잘린 모든 조각에 대해 mining을 실시한다.

Sampling은 전체 DB에서 랜덤하게 몇개의 샘플을 고르고 그것에 대한 mining만을 실시한다.

 

결국 partition은 모든 data에 대해 mining이 이루어지지만, sampling은 일부 data에 대한 mining만 이루어진다.

 

문제점

• SDB(Sampled DB)에서 찾아진 frequent pattern이 실제로 frequent 하지 않을 수 있다.(false-positive)
• 진짜 frequent pattern이 SDB에서 찾아지지 않을 수 있다.(false-negative)

 

해결

false-positive와 false-negative 문제를 추가적인 2번의 scan을 통해서 해결한다.

한 번은 false-positive를 제거하기 위함이고, 한번은 false-negative를 제거하기 위함이다.

 

• Scan 1 : false-positive 제거
  • sampling을 통해 mining 한 frequent pattern과 그의 negative borders을 candidate으로 삼고 테스트한다.
  • negative borders : 집합 S에 속해있지는 않지만 그 원소들의 조합을 통해 생성 가능한 것
    • 예) $\{a, b, c, ab\} \rightarrow \{ ac ,bc, abc \}$
    • 이 과정을 거치면 진짜 frequent pattern들만 살아남게 된다.
• Scan 2 : false-negative 제거
  • 위에서 찾아진 frequent pattern들에 대한 negative border를 다시 형성해서 한번 더 테스트한다.
  • 이를 통해 진짜 frequent pattern이 놓쳐지는 것을 방지할 수 있다.

 

 

---

DIC (Dynamic Itemset Counting)

DB Scan을 줄이는 방법이다.

 

한번의 scan이 끝난 후 scan을 하는 것이 아니라 병렬적으로 scan을 수행해서 scan time을 줄이는 방법이다.

Iteration의 중간에서 frequent하다고 판단되면 그 조합에 대해 동시에 scan을 실시하는 것이다.

 

예를 들어, 1-itemset에 대해 scan하는 도중에 A와 D가 frequent하다고 판단되면 현재 scan과 동시에 AD에 대해 scan을 실시한다.

만약 BC, BD, CD에 대해 모두 frequent 하다고 판단되면 BCD에 대해 frequent한지 scan을 실시한다.