[DB] Data Mining & Apriori Algorithm

0. 개요

Data Mining이란?
"Knowledge(Rule) Discovering"
= 방대한 양의 Database로 부터 유용한 지식, 패턴을 찾아내는 것(일반적으로 예측하지 못한 것)

• decision tree도 data mining의 일종

1. A priori Algorithm

: Data Mining에 사용되는 알고리즘

1) priori Algorithm

e.g. rule (if A then B)
if contains apple & cheese(if) => contains beer (then)

< Examines for algorithm >

• Confidency : if일때 then을 만족하는 비율 (rule의 정확성
• Coverage and support : if를 만족하는 부분(record)이 전체에서 얼마나 차지하는가?

2) Interesting(useful) Rules

: 우연히 발견(<> 당연히 예상되는 것)하게 되는 유의미한 패턴 혹은 규칙

e.g. rule
빵이 존재할 확률 : 0.1
파우더가~ : 0.04
=> 빵과 파우더가 존재할 확률 : 0.004 (둘은 독립사건이므로)

• 그렇다면 여기서 Interesting Rule이란? = Surprising Rule

  위 예제를 실제 시험한 결과 1000개 중 20개에 빵과 파우더가 존재한다면?
  => 예상 외 결과 (통계에 따르면 1000개중 4개꼴로 나와야하므로)
  => "빵과 세제"의 구매가 연관이 있을 수 있다! 라는 Knowledge

• Data Mining의 핵심은 Interesing Rule을 찾아내는 것
  (이 외의 패턴은 'Rule'이라기보다 'Fact'에 가까움. 즉 당연한 것)

• 즉, Data Mining은 '사실 찾기'가 아니라 '지식 찾기' (당연한 상식을 찾는 것은 의미 없음)

※ if A then B 와 같은 rule은 수억개가 가능할 수 있음. 각 rule에 대해 accuracy와 coverage를 계산하는 것 또한 무수히 많은 연산을 포함
=> 이를 보다 효과적으로 찾고자 사용하는 것이 "Apriori Algorithm"

2. Finding Surprising Rules

1) Measuring rules

20records of supermarket transaction, 9 things to be sold

If a basket contains beer and cheese, then it also contains honey

① confidence (accuracy)
= if를 만족할 때, then을 얼마나 만족하는가 (1/2) = 50%
beer & cheese : 2개
beer & cheese & honey : 1개

② coverage (support)
= 전체 database 중 if를 만족하는 것이 얼마나 되는가 (2/20) = 10%
beer & cheese : 2개
전체 : 20개

2) Terminology

ⓐ K itemset = 장바구니에 k개의 item이 존재한다

e.g. {beer, cheese, eggs} : 3-itemset
{cheese} : 1-itemset

ⓑ large itemsets = item이 많다는 얘기가 아니라 "larger than minimum support"★보다 크다는 컨셉

ⓒ Support = support(%)이상의 itemset이 존재

ⓓ Lk = all large K-itemsets in DB

• L1 : 1개의 item을 가지고, minsup 이상인 모든 itemset

ⓔ Ck = candidate large k-itemsets

• C2 : L2의 후보 itemset

3. Apriori Algorithm

1) How to find rules?

① minimum support를 갖는 모든 itemsets를 찾을 것
② itemsets을 가지고 interesting rules를 생성

Assumption : minimum support is 30%

1. Find all large 1-itemsets
   20개 중 30% 이상이므로, 6개 이상인 1-itemset을 찾을 것

   L1 = { {a}, {b}, {c}, {d}, {f} }

2. finding large itemsets

C2 = { {a,b}, {a,c}, {a,d},,, {f,g} }
L2 = {C2중에 minimum support 이상인 것들}
C3 = {L2로부터 3-itemset 생성}

이런식으로 Lk가 공집합이 될 때까지 진행하며, 이 과정에서 생성된 모든 L1,L2,,, 가 minimum support 이상을 만족하는 itemset

 For(k=2;while Lk-1 is non empty;k++)
 {
  Ck = apriori-gen(Lk-1)
  For each c in CK, initilize c.count to zero
  For all records r in DB
   { 
   	Cr = subset(Ck,r);
    for each c in Cr, c.count++
    }
   Set LK:= all C in Ck whose count >= minsup
  }