3. Apriori

Scalable Mining Method 중 하나

• Scale down을 하면서 Frequent Pattern을 찾는 Method 중 하나

 

Apriori

---

Candidate Generation and Test Approach

• Apriori에서 Scaledown을 하는 원리는 Infrequent한 Pattern이 있다면, 해당 패턴의 Superset은 절대 Frequent할 수가 없다는 것을 이용
  • Downward property 이용
• 그렇기 때문에 굳이 Generation하고 Test할 필요가 없다
  • 체크해야 할 패턴의 수를 줄여준다

 

방법을 간략하게 보면

1. DB를 스캔해서 크기가 1인 Frequent Pattern들을 찾는다
2. 아래의 과정을 계속해서 반복한다
    2-1. 길이가 K인 Frequent Pattern들로부터 길이가 K+1인 Candidate Pattern들을 생성한다
    2-2. DB를 다시 스캔하면서 Candidate Pattern들 중에 실제 Frequent Pattern을 찾는다 (Test)
    2-3. 해당 단계에서 크기가 K+1인 Frequent Pattern 또는 Candidate Pattern을 생성할 수 없다면 종료한다 (Terminate)

 

예시

---

예시를 보면서 이해해보자

• 먼저 DB를 Scan해서 길이가 1인 Frequent Pattern을 뽑아낸다.
  • 이때 {D}의 경우엔 min_sup보다 작은 Support 값을 갖기 때문에 Frequent Pattern이 될 수 없다
• 길이가 1인 Frequent Pattern을 이용해서 길이가 2인 Candidate Pattern들을 뽑아낸다
  • DB를 Scan하면서 Candidate Pattern 중에 Frequent Pattern을 찾아낸다
• 길이가 2인 Frequent Pattern을 이용해서 길이가 3인 Candidate Pattern들을 뽑아낸다
  • 이때, {A,B}, {A,E}는 Infrequent Pattern이기 때문에, {A,B}, {A,E}의 Superset은 Candidate로 생성하지 않는다
  • DB를 Scan하면서 Candidate Pattern 중에 Frequent Pattern을 찾아낸다
• 길이가 3인 Frequent Pattern을 이용해서 길이가 4인 Candidate Pattern을 생성할 수 없으므로 종료한다
• Infrequent Pattern의 Superset은 Candidate로 생성하지 않는 것 이 Apriori의 핵심!

 

이 과정을 코드로 동작시키게 될텐데, 수도 코드를 보자

Pseudo Code:

Ck: Candidate itemset of size k
Lk: Frequent itemset of size k
L1 = 길이가 1인 Frequent Patterns

for(k = 1, Lk != {}, k++) do begin
    Ck+1 = candidates generated from Lk
    for each transaction t in database do
        increment the count of all candidates in Ck+1 that are contained in t
    Lk+1 = candidates in Ck+1 with min_support
    end
return Lk

 

Important Details of Apriori

---

• Lk로부터 Ck+1을 생성하는 방법
  • Step 1: Self-Joining Lk
    • Self Join을 통해서 모든 경우의 후보군 생성
  • Step 2: Pruning
    • Step 1에서 생성한 Candidate 중에서 이전 단계에서 Infrequent하다고 판단된 Pattern의 Superset이 있다면 제거
• Self Join과 Pruning을 통해 Candidate를 생성하는 예시
  • L3 = {abc, abd, acd, ace, bcd}
  • Self Join L3 * L3
    • {abcd, abce, abde, acde}
  • Pruning
    • bce가 L3에 없기 때문에 abce는 pruned
    • bde가 L3에 없기 때문에 abde는 pruned
    • cde가 L3에 없기 때문에 acde는 pruned
  • C4 = {abcd}

 

Challenges of Frequent Pattern Mining

---

Apriori 알고리즘이 갖는 한계점

• 대략 K번 정도의 DB 스캔이 발생한다 (DB 접근은 매우 느린 작업)
• 여전히 Candidate의 수가 너무 많다
• Candidate들의 Support를 측정하기 위한 작업량이 너무 많다

 

결국 개선해야 할 점은 ?

• DB를 스캔하는 횟수를 줄인다
• 생성하는 Candidate의 수를 줄여야 한다
• Candidate들의 Support를 측정하는 효율적인 방법을 찾아야 한다