6. Miner Improvements

지금까지 Frequent Pattern Mining을 하기 위한 다양한 방법들을 살펴보았다

• Apriori는 Candidate의 수를 줄여주긴 하지만 여전히 그 수가 너무 많고, DB 접근도 너무 많다
• 그래서 이걸 개선하기 위한 Improving Apriori 알고리즘들을 보았다
• 그럼에도 여전히 Candidate를 생성하고, Test하는 것이 무거운 작업이라 이것을 하지 않아도 되는 FP-growth라는 방법도 봤다
• 이것 외에 다른 마이닝을 Improve할 수 있는 방법들을 살펴볼 것이다

 

MaxMiner

---

Mining Max Patterns

Recall Max Pattern :
Max Pattern은 X의 Superset(X ⊂ Y) 중에 Frequent Pattern이 존재하지 않으면, Itemset X를 Max Pattern이라고 한다

• MaxMiner도 Apriori Algorithm을 기반으로 한다
  • MaxMiner는 오직 Max Pattern을 찾는 것에 집중한다
  • 모든 Frequent Pattern을 찾지는 못 할 수도 있다
  • 이걸 Naive하게 하려고 하면 Cost가 너무 크기 때문에 나온 방법
    • Naive하게 한다는 것은 모든 Frequent Pattern을 찾고, 거기서 Max Pattern을 찾는 것

 

1. 첫번째 Scan에서는 Frequent Items를 찾고 Frequency를 기준으로 오름차순 정렬한다
2. 두번째 Scan에서는 길이가 2인 Itemset들에 대해 Support를 측정하는데, 잠재적 Max Pattern을 포함하여 측정 한다

 

예시

• A,B,C,D,E가 Frequent Pattern이라고 하자.
  • 오름차순으로 정렬한다고 했으므로, E가 가장 큰 Support를 가진 Item이다
• 길이가 2인 Item들의 Frequency를 측정하는 동시에, Potential Max Pattern에 대해서도 탐색한다

 

이 방법은 Later Stage에서의 Candidates를 줄여준다

• Potential Max Pattern을 함께 탐색하는 이유는 나중 Stage에서의 Candidate 수를 줄여줄 수 있기 때문이다
• 만약 BCDE가 Max Pattern이라고 하면, BCD, BDE, CDE에 대해서는 굳이 탐색할 필요가 없다

 

Construct Set-enumeration Tree

---

예시를 통해 Set-enumeration Tree를 생성하는 과정을 살펴보자

• 정렬된 Frequent Items는 A,B,C,D라고 하자
• Set-enumeration Tree는 Potential Max Pattern을 찾는 것을 도와준다
• FP-Growth에서 Conditional Database를 찾을 때처럼,
  • 해당 Item이 포함된 Conditional Candidates를 찾는다
  • 이렇게 해서 Max Pattern이 될 수 있는 후보군들을 찾는다

 

Mining Closed Patterns

---

CLOSET

Recall Closed Pattern :
Itemset X에 대해서, X가 Frequent하고 같은 Frequent를 가진 Superset이 없으면, X를 Closed Pattern이라고 한다
=> 같은 Support를 가진 Frequent Pattern 중에 Superset

• CLOSET은 FP-growth를 하면서 Closed Pattern을 찾는 방법이다
  • FP-growth 알고리즘은 자연스럽게 Closed Pattern을 찾는 것을 도와준다

 

CLOSET

---

CLOSET은 어떤 식으로 동작을 할까

• Naive하게 그냥 찾는 것은 다시 말하지만 너무 Cost가 많이 든다
• Recursive하게 FP-growth를 하는 동안 Closed Pattern을 찾는 것에만 집중한다
  • 모든 Transcation이 m을 가지고 있고, 또한 fca도 가지고 있다면 => fcam이 Frequent Closed Pattern이 된다는 것을 이용
  • 정확히는 Potential Closed Pattern
  • p-Conditional Pattern Base에서 fcamp가 Frequent Pattern이고 Frequency가 같았다면, fcam은 Closed Pattern이 될 수 없기 때문에 "Potential"

 

• m의 Conditional Pattern Base에서 모든 Pattern이 fca를 가지고 있다면, fcam이 Potential Closed Pattern이 된다

 

CHARM

---

Vertical Data Format을 통해서 마이닝을 하는 방법

왼쪽이 Horizontal, 오른쪽이 Vertical

• 지금까지 우리가 봤던 테이블은 Transcation 별로 어떤 Item들이 등장했는지를 나타내는 Horizontal Format의 테이블이었다
• CHARM 방식에서 사용하는 테이블은 Item을 기준으로 어떤 Transaction에서 등장했는지를 나타내는 Vertical Format을 사용 한다

 

방식

1. Database를 한번 Scan해서 Horizontal로 표현된 테이블을 Vertical Format으로 변경한다.
   • 이때 오직 크기가 1인 Frequent Item들만 기준이 된다
   • 일반적으로 크기가 1인 Frequent Item의 수가 Transcation의 수보다 적을 것이기 때문에, 테이블의 Row의 수가 줄어들 것이다
2.  k=1부터 시작해서 k+1 길이의 Frequent Item들을 찾아 나간다
   • 이때 DB를 Scan할 필요없이 교집합(Intersection) 연산을 통해서 k+1 길이의 Frequent Pattern을 찾을 수 있다
3.  k+1 길이의 Frequent Pattern이 발견되지 않을 때까지 이 과정을 반복한다

 

예시

•  Effectiveness
  • DB를 스캔할 필요없이 교집합 연산만으로 Frequency를 바로 구할 수 있다
  • TID list의 길이가 Frequency가 된다