[데이터 마이닝] Pattern Mining: Methods (Apriori)

1. 효율적인 Pattern Mining 방법

• Frequent Patterns의 Downward Closure Property (하향 폐쇄.. 방법)
  • The Apriori Algoritm
  • 확장(extensions) or 향상(Improvements) of Apriori  
• 수직 데이터 포맷 탐색에 의한 frequent patterns mining
• FPGrowth: A Frequent Pattern-Growth Approach
• Mining Closed Patterns

 

...

 

2. The Apriori Algorithm (의사 코드)

C_k: Candidate itemset of size k (item 갯수 k개인 후보 itemset)

F_k: Frequent item set of size k (item 갯수 k개인 frequent itemset)

 

K := 1; # item 갯수 1인 것 먼저 계산
F_k := {frequent items};  # frequent한 1-itemset

While (F_k != (공집합) do {  # frequen한 것의 리스트가 공집합이 아니면 루프 반복
  C_k+1 := candidates generated from F_k;  # F_k 리스트에서 나온 그다음 길이 후보 집합
  Derive F_k+1 by counting candidates in C_k+1 with respect to TDB at minsup; 
  # minsup 참고해서 C_k+1에서 frequent한 것만 골라내서 F_k+1에 추가
  k := k+1  k+1 단계로 바뀜
  }
return 합집합_k Fk  # 위 단계에서 발생한 F_k 집합 return

 

3. The Apriori Algorithm - 예시

1. C_1 생성: TDB에서 k=1인 1-itemsets 골라내기.

2. F_1 생성: minsup = 2 따져서 2 미만인 sup 골라내고 F_1 만들어내기 (s{D}=1 이므로 D는 F_1에서 빠짐)

3. C_2 생성: F_1에서 조합해서 k=2인 2-itemsets 생성. 4C3=6개 생성 

* k=1->2는 특이 케이스이다.

4. F_2 생성: minsup = 2 따져서 C_2에서 2 미만인 sup 집합 골라내고 F_2 만들어내기 ({A,C}, {A,E} 탈락)

5. C_3 생성: k-1 같은 것끼리 묶고 다른 2가지 생각해서 조합 --> k-1+2 = k+1 개인 조합 만들어짐.

({B,C}, {B,E} 조합해서 길이 2+1인 {B,C,E} 생성

6. F_3 생성: minsup = 2 따져서 2 이상인 것은 살려두고 F_3에 넣기 (frequent한 집합)

 

 

fails negative: negative라고 잘못 판정 -> 타격이 크다.

fails positive: positive라고 잘못 판단

fails positive를 줄이고 싶은데, 줄이는 과정에서 positive를 negative로 판단해 버림. -> fails negative 발생.

fails positive 줄이면서 fails negative 발생하지 않도록 하는 것이 목표

 

 

4. Apriori: Implementation Tricks (구현 트릭)

• candidate(후보) 생성하는 방법: 1. self-joining F_k   2. pruning(가지치기)
• 요약: 조합한 다음, 골라내기
  
  • 예시) F_3 = {abc, abd, acd, ace, bcd}
  • 1. self-joining: F_3 * F_3
    • abcd from abc, abd
    • acde from acd, ace
  • 2. Pruning(가지치기)
    
    • 각 집합의 같은 k-1길이 조합을 포함하는 것이 F_3에 존재하는지 확인.
    • ex) abcd = abc, abd, acd, ace / acde = acd, ace, ade(없음), cde(없음)
    • acde는 삭제한다. 왜냐하면 ade, cde가 F_3에 없기 때문이다.
  • 결론: C_4 = {abcd}

 

5. candidate 생성 (의사 코드)

• F_k-1의 items들이 순서대로 나열되어있다고 가정
• 1. joining

for each p in F_k-1: # 조합할 첫번째 k-1 
  for each q in F_k-1: # 조합할 두번째 k-1
     if p.item1=q.item1, ..., p.itemk-2=q.itemk-2, p.itemk-1 < q.itemk-1{
     # 2번 비교하는 것 막기 위해서. k-2까지 같고 k-1번째가 달라야 조합 가능 
          c=join(p,q)

• 2. pruning

if has_infrequent_subset(c, F_k-1)
    continue  # prune (여기서 조합 끝내고 새로운 조합 만들러 가기)
else add c to C_k  # frequent하지 않은 서브셋에 없다면 frequent한 것. C_k(후보 리스트)에 추가

 

 

6. Apriori: 개선과 대안

• 트랜잭션 DB를 스캔하는 횟수 감소
  • partitioning
  • Dynamic itemset counting 
• candidate(후보) 수 줄이기
  • Hashing, 낮은 결합 support에 의한 Pruning(가지 치기), Sampling
• 특별한 데이터 structure 탐색
  • Tree 그리기, H-miner, Hypecube 분해

 

7. Partitioning: Database를 단 2번만 스캔

• TDB에서 잠재적으로 frequent한 itemset은 적어도 TDB partition 하나 이상에서는 frequent해야 함
• 방법: DB를 2번만 스캔
  • TDB 존재, minsup 존재 
  • Scan 1: 메인 메모리에 딱 맞도록 database를 partition(분할)한다.
    - 이 partition에서 local frequent patterns를 가지고 있다. (partition 내에서만 frequent한 pattern)
    (나누어진 partition에 대해서 기존 minsup 적용 불가. -> minsup / k= minsupk을 local minsup으로 삼는다.)
  •  Scan 2: global frequent patterns를 통합한다.
    - global frequent itemset candidate(전역에서 frequent 한 아이템셋 후보=적어도 한 partition에서 frequent한 것들)를 찾는다.
    (No false-negative, Yes false-positive: frequent pattern이 아닌데 frequent하다고 나오는 경우는 없지만, frequent pattern 하다고 나왔는데 frequent 하지 않은 경우가 발생할 수 있다.)
    - TDB를 한 번 더 스캔하여 위 candidate의 실제 frequency를 찾는다.
• 모든 partition에서 support가 50%이 안 되는 것 --> 전체 TDB에서 supoort가 50%이 안 됨.

 

8. Direct Hashing and Pruning (DHP)

• Hashing: v = hash(itemset) 
  • 메인 메모리에 들어가는 값의 range 줄여줘서 candidate 수를 작게 구하고 빠를 수는 있지만, 충돌이 필연적으로 발생
• Scan 1: 1-itemset을 셀 때, 2-itemset을 hash하여 bucket 수를 계산한다. (k=1, k=2 동시에 count)
  • ex) TDB 1번째 스캔에서 1-itemset를 세고 bucket에 대한 트랜잭션에 2-itemsets을 해시한다. (해쉬 테이블을 만든다.)
    - {ab, ad, ce}
    - {bd, be, de}
    - ...
  • 1번째 스캔 후, minsup = 80 따져서 itemsets를 제거한다. (count{ab, ad, ce} < 80)

- 한계: 만약 해당하는 해쉬 테이블의 count가 minsup threshold보다 낮다면 k-itemset은 frequent 할 수 없다.

 

9. Pattern Growth: 왜 pattern growth에 의해 Mining을 하는 걸까?

• Apriori: 너비우선탐색 (BFS) 마이닝 알고리즘
  • frequent한 k-itemsets의 완전한 집합을 찾음. -> frequent한 (k+1)-itemset candidate 도출해냄
  • true frequent (k+1)-itemsets를 찾기 위해 DB를 다시 스캔함
• 다양한 Mining 방법론을 위한 동기 부여 
  • 왜 BFS 마이닝 알고리즘에서 더 개선할 수 있을까?
  • frequent itemset p라고 하면, 그 다음 탐색을 p를 포함하는 트랜잭션에서만 수행할 수 있는가? (그다음 탐색에 frequent한 itemset이 없을 수도  .. 아닐 수도)
• 이런 생각이 frequent growth approach로 이끌었다: FPGrowth