Association Rule 연관 규칙

Association Rule

추천 시스템에서 Baseline이 되는 것으로  어떤 사건이 얼마나 자주 함께 발생하는 지를 수치화 하는 방법이다.

• items 사이의 관계를 수치화 하는 방법으로 items끼리의 상호 연관관계를 나타냄
• \( X \Rightarrow Y \): X를 선택하였을 때 Y가 선택될 확률
• "X를 사면 Y를 산다"는 규칙을 찾는 것으로 추천 시스템의 Baseline으로 사용됨

---

용어

조건절 Antecedent, 결과절 Consequent

• \( X \Rightarrow Y \): X를 선택하였을 때 Y가 선택될 확률
• Antecedent(IF): X
• Consequent(THEN): Y

Item Set

• 조건절(Antecedent), 결과절(Consequent)을 구성하는 상품의 집합

---

Association Rule의 3가지 성능 지표

• 지지도 Support
• 신뢰도 confidence
• 향상도 Lift

---

지지도 Support

전체 경우의 수에서 두 아이템이 같이 나오는 비율을 의미한다.

 

$$ Support(X \Rightarrow Y) = P(X,Y)=\frac{N_{X \wedge Y}}{N}= \frac{N_{X \cup  Y}}{N} = P(X) $$

 

\( P(X) \)은 지지도로 X가 등장한 확률을 의미하지만 아래와 같이 많이 쓰인다.

 

\( N_{X \cup  Y} \), \( N_{X \wedge Y} \) X와 Y가 동시에 일어난 경우의 수를 의미한다.

 

예를 들어, tea와 latte를 시킨 고객이 muffin을시킬 Support의 값은 아래와 같다. 

$$ Support( \left\{ tea, latte \right\} \Rightarrow \left\{ muffin \right\}) = P(\left\{ tea, latte \right\},\left\{ muffin \right\})=\frac{N_{\left\{ tea, latte \right\} \wedge \left\{ muffin \right\}}}{N}= \frac{N_{\left\{ tea, latte \right\} \cup \left\{ muffin \right\}}}{N} = \frac{N_{\left\{ tea, latte, muffin \right\}}}{N} $$

 

Support는 X와 Y 순서로 바꾸어도 결과가 똑같으며 Y와 X 반대의 같은 결과가 나온다.

 

Support는 값이 높을수록 연관성이 높다는 것을 의미한다.

---

신뢰도 Confidence

X가 나온 경우 중 X와 Y가 함꼐 나올 비율을 의미한다.

 

$$ confidence(X \Rightarrow Y)= \frac{N_{X \wedge Y}}{N_{X}}= \frac{N_{X \cup  Y}}{N_{X}} $$

 

X를 산 사람중에서도 Y를 같이 사는 사람의 비율을 말한다.

 

예를 들어, tea와 latte를 주문한 고객이 muffin을 구매할 confidence값은 아래와 같다.

$$ confidence( \left\{ tea,latte \right\} \Rightarrow \left\{ muffin \right\})= \frac{N_{\left\{ tea, latte, muffin \right\}}}{\left\{ tea, latte \right\}} $$

---

향상도 Lift

생성된 규칙이 얼마나 유용한지는 나타내기 위해 사용한다. 1을 기준으로 더 높으면 긍정적인 관계(연관성이 높음), 더 낮으면 부정적인 관계(연관성이 낮음)를 의미한다.

 

$$ Lift(X\Rightarrow Y)= \frac{confidence(X\Rightarrow Y)}{support(Y)}=\frac{P(B|A)}{P(B)}=\frac{P(A\cap B)}{P(A)P(B)} $$

 

• 두 상품이 서로 독립일 경우, Lift = 1
• 두 상품이 서로 양의 관계일 경우, Lift > 1
• 두 상품이 서로 음의 관계일 경우, Lift < 1

 

---

Reference

• https://myeonghak.github.io/recommender%20systems/RecSys-%EC%97%B0%EA%B4%80-%EA%B7%9C%EC%B9%99-%EC%B6%94%EC%B2%9C-(Association-Rule)/
• https://ddongwon.tistory.com/110
• https://process-mining.tistory.com/34