[데이터 마이닝] 연관 분석 (Association Analysis) - Apriori Algorithm

강의 출처) 2023-1 숙명여자대학교 소프트웨어학부 강의 "데이터마이닝및분석", 이기용 교수님

1. Principle

• 어떤 아이템셋이 frequent하면, 그 아이템셋의 모든 subset은 frequent하다.
  • Ex. {a, b, c} is frequent → {a, b}, {b, c}, {a, c}, {a}, {b}, {c} must also be frequent
• 어떤 아이템셋이 infrequent하면, 그 아이템을 포함하는 모든 아이템셋은 infrequent하다.
  • Ex. {a, b} is infrequent → {a, b, c} is also infrequent

2. Process 

• Frequent itemset generation (using minsup, support)
• Rule generation (using minconf, confidence)

3. Process - 1 : Frequent Itemset Generation

1) Basic Steps

• 용어 설명
  • Cn (Candidate itemset) : Fn-1을 사용하여 만든 n개로 이루어진 모든 아이템셋
  • Fn (Frequent itemset) : Cn에서 Frequent한 아이템셋만 뽑아낸 것 = minsup 이상인 아이템셋들만 추출 
• 요약
  • C1 → F1 → C2 → F2 → ... → Cn → Fn
  • 더이상 frequent itemset이 발견되지 않을 때까지 위의 과정을 반복
• 과정
  
  • 가장 처음으로 각 아이템이 몇번씩 등장했는지 count → 한개로 이루어진 아이템셋의 빈도를 계산하여 C1 생성
  • C1 중 minsup 이상인 아이템셋만 추출해 F1 생성
  • k = 2, 3 ... (아이템셋의 아이템 개수) 일때 더이상 frequent itemset이 발견되지 않을 때까지 아래의 과정을 반복
    • Ck를 Fk-1을 사용하여 생성
    • Ck를 pruning
    • pruning된 Ck를 사용해 Fk를 생성

2) Methods of Candidate Generation

• 원칙 
  • Complete : 모든 frequent itemset이 포함되어야 한다
  • Non-rebundant : 중복되는 itemset이 없어야 한다 (Ex. {a, b, c, d} = {b, c, d, a} = {d, a, b, c})
  • Effective : 필요없는 후보를 너무 많이 만들지 않아야 한다
• 방법 1 : Fk-1 X F1 Method
  • (k - 1) - itemset과 1 - itemset을 조합하여 candidate 생성
  • 특징
    1. Complete 만족 O
    2. Non-rebundant 만족 X  → 해결 방안 : 알파벳 순으로 나열 → (k-1)-itemset의 가장 끝 알파벳보다 더 뒤의 알파벳 순서를 가지는 1-itemset만을 결합
    3. Effective 만족 X → 필요없는 아이템셋 많음 → infrequent한 subset을 가진 아이템셋이 candidate에 포함되어 있기 때문

• 방법 2 : Fk-1 X Fk-1 Method
  • (k-2)번째까지 문자는 고정 → (k-2)번째까지 문자가 동일한 (k-1)-itemset에 대해 알파벳순으로 결합
  • 특징
    1. Complete 만족 O
    2. Non-rebundant 만족 O
    3. Effective 개선 → 일단 최소 두개의 frequent한 (k-1)-itemset은 있다고 보장되어 있기 때문
       

3) Candidate Pruning

• 과정
  • 각 아이템셋에서 아이템을 하나씩 제거해보면서 제거했을 때의 아이템셋이 frequent한지 판단
  • infrequent하면 → pruning
• 특징
  • Ck를 pruning한다고 할 때, (k-1)-itemset의 frequent 유무만 파악하면 됨
  • Ex. X = {i1 , i2 , …, i k }라는 k-itemset이 있다고 가정할 때, << X – {i1 }, X – {i2 }, …, X – {i k } >> 만 확인
  • (k-1)-itemset이 만약에 frequent하다고 가정하면, 그 itemset의 모든 subset 또한 frequent한 것이기 때문

4. Process - 2 : Rule Generation

• 별도의 계산 필요없음 → Frequent itemset을 만들면서 이미 support가 다 계산되어 있기 때문에 그대로 사용 가능

1) Basic Steps

• 과정
  • 앞서 선정된 모든 Frequent itemset을 사용해 rule을 생성
  • 한 itemset에 대해서도 여러개의 rule이 생성됨
  • 각 rule에 대해 minconf 이상이 되는지 판단 후 minconf 이상이 되는 rule을 association rule이라고 처리
• rule 생성 방식
  • X라는 itemset이 있다고 할 때, X1, X2로 분리
  • X1, X2는 교집합이 없고, 둘을 합집합했을 때 X가 되어야 함
  • Ex, X = {a, b, c} → X1 = {a}, X2 = {b, c}

2) Confidence - Based  Pruning

• Theorem
  
  • X1 → Y1 & X2 → Y2 의 룰에 대해
  • << X1이 X2를 포함한다는 >> 가정이 성립할때
  • X1 → Y1이 minconf를 만족하지 못하면 X2 → Y2도 min conf를 만족하지 못함
• Proof