Frequent Pattern Mining #1

데이터마이닝에 대한 대학 강의를 수강하면서 기본 개념 정리를 블로그에 기록하려 한다.

 

■ Market Basket Problem

- 쿠팡이나 쇼핑몰 웹사이트에서 흔히 볼 수 있는 "구매자가 함께 구매한 상품"과 같은 기법을 구현할 때 사용된다.

ex) Customer who bought beer also bought diapers

 

- Motivation : cross-selling

- 고객의 구매 패턴, 고객이 자주 함께 구매한 아이템들에 대한 Big data가 요구된다.

 

★ Basic Terms

• Transaction : 한 사람이 한 번 샀을 때의 item 집합
• Frequent Itemset : minimum support 보다 support가 크거나 같은 Itemset
• Support(지지도) : transaction 속에서 몇 개를 가진지에 대한 퍼센트(빈도) -> 일종의 교집합 개념
• Confience(신뢰도) : A transaction 집합 일 때 B 집합 또한 포함하는 퍼센트 -> 조건부 확률과 유사
• Association Rule(연관성 규칙) : 두 아이템 집합들 사이의 관계, minimum confidence 보다 크거나 같은 confidence를 가진 Rule -> 최종 목적

 

★ Solving Market Basket Problem

 

- Step 1 : minimum support를 근거로 frequent itemset 찾기

- Step 2 : minumum confidence를 근거로 frequent itemset 속에서 Association Rule 찾기

 

 

★ Generalized Formulas

 

- Computation of Support 

   Support(A -> B) = P(A∪B)

- Computation of Confidence

   Confidence(A -> B) = P(A∪B) / P(A)

 

이 공식에서 P(X)의 개념이 명확하지 않으면 왜 합집합을 쓰는 것인지 이해를 할 수가 없다. 우리는 여기서 엄밀하게 P(X)의 개념을 정리하고 넘어가 보자.

 

P(X) = X set이 포함된 집합 / 전체 집합

 

예를 들어 X = {1,2}, Y = {1,2,3} 이라 하자. 여기서 P(X)와 P(Y)를 비교해 보면 P(X) = 전체 집합 중 {1,2}가 포함된 모든 set을 의미한다. 전체집합이 자연수 집합이라면 P(X) = {1,2}, {1,2,3}, {1,2,4}, ... ,{1,2,3,4}, .......  이런식으로 {1,2}가 포함된 모든 집합의 개수를 의미한다. 그렇다면 당연히 {1,2,3}을 포함해야 하는 P(Y)보다 P(X)는 더 큰 값을 가지게 된다.

 

여기서 우리는 X⊆Y 이면 P(X) ≥ P(Y)임을 알 수 있다.

 

이처럼 P(X)의 개념 자체를 비율 집합으로 생각하게 되면 왜 위의 공식에서 교집합이 아닌 합집합을 사용하는 것인지를 파악할 수 있게 된다.

 

 

★ Problem of Support & Confidence

 

- Data Unbalance가 일어나게 되면 정확한 Association Rule을 찾을 수 없다. 어떤 조건부 확률 값을 선택하게 되었더라도 다른 data와의 차이가 너무 크게 되면 단순히 그 확률 값만을 보고 Association Rule로 단정지어 말할 수는 없기 때문이다.

 

- 이러한 문제에 대한 대안으로 Lift(향상도) 개념을 가져올 수 있다.

 

lift(A -> B) = confidence(A -> B) / P(B) =  P(A∪B) / P(A)×P(B) = correlation(A,B)

 

lift(A, B) = 1 : no relationship(독립)

lift(A, B) > 1 : Positive correlation

lift(A, B) < 1 : Negative correlation(less frequently)

 

 

★ Chi-Square Test(카이제곱 검정)

 

- 여기서 다루는 카이제곱 검정은 통계적 유의미성 보다 데이터 마이닝 적인 relationship 여부에 조금 더 초점을 맞춘다.

 

Chi-Square X^2 = ∑ { (관찰빈도 - 기대빈도)^2 / 기대빈도 }

 

- Chi-Square = 0 : 귀무가설을 기각하지 못할 확률 ↑ - 비교 대상이 no relationship

- Chi-Square > 0 : 귀무가설을 기각할 확률 ↑ - 비교 대상이 relationship

 

ex)

	Tea	Not Tea	Sum
Coffee	20(21)	50(49)	70
Not Coffee	10(9)	20(21)	30
Sum	30	70	100

 

Tea 일때 Coffee의 기대빈도 = 30 × (0.7) = 21

Tea 일때 Not Coffee의 기대빈도 = 30 × (0.3) = 9

Not Tea 일 때 Coffee의 기대빈도 = 70 × (0.7) = 49

Not Tea 일 때 Not Coffee의 기대빈도 = 70 × (0.3) = 21

 

X^2 > 0 이므로 Coffee와 Tea는 relationship 하다.