4. Improving Apriori

Apriori 알고리즘에는 여러 한계가 존재한다고 했다

• Multiple scans of DB (k times)
  • 대략 k번의 DB 스캔이 발생한다는 것
  • 여기서 k는 Max Pattern의 길이이다
  • DB 접근은 너무 느리기 때문에 개선이 필요하다
• Huge number of candidates
  • 후보군의 수가 너무 많다
  • Max Pattern {i1, i2, ..., i100}을 찾기 위해서는
  • # of scans(k): 100
  • # of candidates: 2^100 - 1 만큼의 후보군
• Tedious workload of Candidate generation and Test
  • Candidate들의 Support를 Count하는 것의 Cost가 꽤 크다

 

Improving Apriori

---

Apriori를 개선하기 위한 일반적인 아이디어

• Reduce the number of DB scans
• Reduce the number of candidates
• Improve the candidate counting approaches
  • Support를 더 효율적으로 측정하기 위한 접근

 

DIC

---

Dynamic Itemsets Counting

• DB 스캔의 횟수를 줄이기 위한 방법

• A와 D가 모두 Frequent하다고 판단된 시점에 AD를 Scan해야 할 후보군에 넣는다
• 같은 원리로 AB, AD, BD가 모두 Frequent하다고 판단된 시점에 ABD를 Scan해야 할 후보군에 넣는다

 

DB 스캔횟수 비교

• 기존의 Apriori의 경우 매 Iteration마다 DB 전체를 스캔

 

• DIC의 경우 동시에 여러 길이의 Pattern들에 대해 Scan을 하기 때문에 횟수가 줄어든다
• 위의 경우에는 길이가 3인 Item set들에 대해 Count를 하는데, 2번도 채 안되는 Scan이 발생했다

 

Partition

---

Scan Database Only Twice

• 단 2번의 DB Scan 으로 Frequent Pattern을 찾을 수 있도록 하는 방법

접근법

• DB를 K개의 조각으로 나눈다
  • 이 나눠진 각각의 조각들을 Partition(Local DB) 이라 부른다
  • 이때 파티션의 크기는 메인 메모리의 크기에 맞춰서 정해야 한다
    • 하나의 파티션은 메인 메모리에 계속 올려두고 접근하면, DB에 계속 가지 않아도 된다
  • 각 파티션에서 Local Frequent Pattern 을 찾는다 (Scan 1)
    • local_min_sup = min_sup / k
    • local_min_sup보다 크거나 같은 Support를 가지는 Pattern들을 Local Frequent Pattern이라 한다
  • Local Frequent Pattern들을 대상으로 DB 스캔을 해서 실제 Frequent Pattern을 찾는다 (Scan 2)
    • Local Frequent Pattern이라고 해서 반드시 Frequent Pattern임을 확신할 수는 없다
• 이렇게 해도 Frequent Pattern을 놓치지 않고 찾을 수 있다
  • 어떻게 보장?
  • Global에서 Frequent한 Pattern은 반드시 Local에서 한 번은 Frequent해야 한다
    • 그래야 Frequency가 min_sup보다 크거나 같을 가능성이 있다
    • 모든 Local에서 Frequent하지 않은데, Local에서의 Frequency의 합이 min_sup보다 클 수가 없다
  • 그렇기 때문에 Local Frequent Pattern은 Frequent Pattern의 후보군이 된다
    • 2번째 DB Scan을 통해서 Global Frequent Pattern인지 확인을 해야 한다

 

Samping

---

전체 DB에서 일부를 추출한 Sample을 사용

• Original DB에서 랜덤하게 일부 데이터를 추출 하여 Sample Database (SDB)를 생성한다
• SDB를 대상으로 Apriori 알고리즘을 적용 한다
  • SDB_min_sup = min_sup * (size of SDB) / (size of DB)

 

Samping 방식의 문제점

1. SDB에서의 Frequent Pattern이 실제 Frequent Pattern임을 보장할 수 없다
   • 이건 Partition에서도 발생하는 문제
2. Sample이 어떻게 생성되느냐에 따라 잃어버리는 Frequent Pattern이 발생 할 수 있다
   • Partition에서는 그래도 전체 DB를 한번은 스캔하는 셈이므로 잃어버리는 Pattern은 없었다

 

해결책 ?

2번의 추가적인 DB 스캔을 한다

 

1. 전체 DB를 한번 스캔해서, Original Minimun Support를 적용한다 

• SDB에서 찾은 Local Frequent Pattern들이 실제 Frequent Pattern인지 확인 한다
• 이때 SDB에서 찾은 Frequent Pattern을 S라고 하면, S뿐만 아니라 Negative Borders(NB) 도 함께 후보군으로 고려하여 스캔한다
  • Negative Borders(NB): not in S, but all its subsets are in S + single items
• S에는 없지만, 모든 Subset이 S에 존재하는 Itemset(Pattern)은 Frequent Pattern일 가능성이 높기 때문에 함께 고려

 

2. 전체 DB를 다시 한번 Scan한다

• 새롭게 고려하게 된 NB를 통해서 잃어버린 Frequent Pattern들을 찾을 수 있었다
• 이렇게 해서 {a,b}, {a,c}, {a,b}가 모두 Frequent Pattern임이 확인되었다면, {a,b,c}도 Frequent Pattern일 가능성이 있기 때문에, 한번 더 Scan을 하는 것이다
  • 그런데 여기서 {a, b, c}가 Frequent Pattern임이 확인되었다면, 또 추가로 {a, b, c, d} 등이 후보군으로 생길 수도 있지만, 그 이상은 찾지 못한다
  • 여전히 100% 정확성은 보장하지 못한다

 

DHP

---

Direct Hashing and Pruning

• Lk(크기가 k인 Frequent Pattern)를 찾을 때, 각 Transaction에서 크기가 k+1인 Itemset들도 함께 찾는다
• 그리고 해당 Itemset을 Hash해서 해시 테이블을 통해 Count값을 유지 한다

• C1으로부터 크기가 1인 Frequent Pattern(L1)을 찾을 때, 각 Transaction에서 크기가 2인 Itemset들을 찾아서 이 Itemset들에 대해 해시 테이블을 생성한다

 

• 크기가 1인 Freqeunt Pattern으로부터 크기가 2인 Candidate들을 찾을 때, Hash bucket count 값을 통해 1차적으로 필터링을 한다
• 이때 Hash Collision의 발생 가능성이 있기 때문에 Hash bucket count가 정확한 Fequency라고는 할 수 없다
• 그러나 Hash bucket count < min_sup이라면 명백히 Infrequent Pattern이므로 Candidate에서 제거한다
  • 효율적으로 Candidate의 수를 줄일 수 있다

 

Original Apriori vs DHP

---

기존의 Apriori와 DHP 방식 비교

• DHP는 Hash bucket count 값을 통해서 Frequent Pattern이 될 가능성이 없는 Pattern은 Candidate로 넣지 않는다
• 따라서 Candidate의 수를 줄여준다
• 기존의 Apriori에서는 C2의 크기가 6이지만, DHP에서는 C2의 크기가 4로 줄어든다

 

정리

---

지금까지의 내용 정리

• 위에서 DIC, Partition, Sampling, DHP 4가지 방법에 대해 알아보았다
  • DB Scanning 횟수를 줄여주는 방법: DIC, Partition, Sampling
  • Candidate의 수를 줄이는 방법: DHP, Sampling
• 그러나 이 방법들도 여전히 느리다는 문제가 있다
  • Candidate를 줄였다고 하더라도, 각 Candidate의 Support를 구하는 과정은 여전히 무겁다,,
• 그냥 Candidate 생성을 안 하는 방법 은 없을까?
  • FP-growth 라는 방법이 있다!