Association Rule(연관성 분석)

하나의 거래 또는 사건에 포함된 둘 이상의 품목 간의 상호 연관성을 발견하는 분석 과정이다. 고객이 동시에 구매하는 상품 간의 관계를 분석한다는 측면에서 Market Basket Analysis(장바구니 분석)이라고도 한다. 즉 핸드폰을 구매하는 고객이 동시에 이어폰, 케이스, 그립톡 등을 구매할 때의 연관성을 분석하는 것이다.

연관규칙(Association Rule)

항목들 간의 if them A -> the item B 형태로 표현되는 패턴이다. 즉 A를 사는 사람이 B도 산다는 것을 의미한다.
예컨대 {Coke, Potato, Onion} => {Chicken}라면, 즉 콜라와 감자 그리고 양파를 사는 사람은 닭고기를 산다는 규칙이 있다고 가정하자. 이 때 원래 닭고기를 사는 사람이 많아서 우연히 나온 결과인지, 또는 저 규칙이 적용되는 비율이 낮은지 등을 고려해야 하여 판단해야 한다.

연관규칙을 파악하기 위한 측도

1. 지지도(Support)
   P[A•B], 전체 구매 건 중 상품 A와 상품 B를 동시에 구매한 비율
   P[A], 전체 구매 건 중 상품 A를 구매한 비율

2. 신뢰도(Confidence)
   P[B|A], 상품 A를 구매한 건 중 상품 B도 같이 구매한 비율
   Confidence(A -> B) = Support(A -> B) / Support(A)
   
   $\Rightarrow P[B|A] = \frac{P[A \cdot B]}{P[A]}$
   
   조건부 확률 = $\frac{P(A \cap B)}{P(A)}$

3. 향상도(Lift)
   $\frac{P[B|A]}{P[B]}$, 전체 구매 건 중 상품 B를 구매한 비율에 비해 상품 A를 구매한 고객이 상품 B를 구매한 비율은 몇 배인지를 나타낸다.
   Lift(A -> B) = Confidence(A -> B) / Support(B)
   
   $\Rightarrow \frac{P[B|A]}{P[B]} = \frac{P[A \cdot B]}{P[A] \cdot P[B]}$
   
   

• Lift(A -> B) = 1: 상품 A와 상품 B의 구매는 연관성이 없다.
  즉 독립이다. $P(B) = \frac{P(A \cap B)}{P(A)} = P(B|A)$
  
  
• Lift(A -> B) > 1: 상품 A와 상품 B의 구매는 양의 영향력이 있다.
  
  
• Lift(A -> B) < 1: 상품 A와 상품 B의 구매는 음의 영향력이 있다.

---

연역적(Apriori) Algorithm

품목들의 집합에 따라 지지도, 신뢰도, 향상도 지표를 구할 때 품목의 수가 많을 때는 연관규칙의 탐색 비용이 커진다. 이 때 연역적 알고리즘은 더 이상 탐색하지 않아도 될 품목의 조합을 찾고, 그 조합을 부분집합으로 가지는 품목의 집합들을 가지치기(Pruning)하여 효율적인 탐색을 가능하게 한다.

최소 지지도 가지치기(Minimum Support Pruning, MSP)
특정 품목 집합에 대한 지지도가 일정 수준(Threshold Criterion)에 도달하지 못하면 그 품목 집합이 포함된 조합은 더 이상 탐색하지 않는다.

예컨대 품목 (a, b, c, d)가 있을 때 품목의 조합은 다음과 같다.

(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)
(a, b, c), (a, b, d), (a, c, d), (b, c, d)
(a, b, c, d)

이 때 만약 품목 집합 (a, b)가 Threshold Criterion을 넘지 못했을 경우 (a, b)가 포함된 모든 품목 조합을 삭제한다.

(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)
(a, b, c), (a, b, d), (a, c, d), (b, c, d)
(a, b, c, d)

전체 과정을 살펴보자. 주어진 자료는 다음과 같으며, 최소 지지도는 3/7을 기준으로 한다.

구매자	구매 상품
1	a, b
2	b, c
3	a, b, c, d
4	a, b, d
5	b, d
6	b, c, d
7	c, d

1) 개별 품목의 지지도 계산

각 품목의 횟수를 도출한다.

품목	지지도
a	3/7
b	6/7
c	4/7
d	5/7

2) 2개의 품목 조합에 대한 지지도 계산

(a, c)와 (a, d)가 최소 지지도 기준을 넘지 못했다.(비빈발품목)

품목	지지도
a, b	3/7
a, c	1/7
a, d	2/7
b, c	3/7
b, d	4/7
c, d	3/7

3) 3개의 품목 조합에 대한 지지도 계산

(a, c)와 (a, d)가 포함된 (a, b, c)와 (a, c, d)는 고려하지 않는다. (b, c, d)의 지지도 계산 결과 최소 지지도 기준을 넘지 못했기 때문에 3개 품목 조합 이상에 대한 지지도는 계산하지 않고 알고리즘을 중단한다.

품목	지지도
b, c, d	2/7

4) 연관규칙 판단

제거되지 않은 품목 조합 (a, b), (b, c), (b, d), (c, d)에 대한 신뢰도와 향상도를 구한 후 연관규칙을 판단한다.

• 연관규칙(c -> d)
  • 신뢰도(c -> d) = (3/7) / (4/7) = 3/4 = 0.75
  • 향상도(c -> d) = (3/4) / (5/7) = 21/20 = 1.05
  • 연관규칙(c -> d)는 향상도가 1을 넘으므로 품목 c와 품목 d는 양의 상관이다.