[RecSys] 추천 시스템 - 연관 분석 (Association Analysis)

사실

 

사실 추천 시스템 분야는 현업에서 딥러닝보다 클래식한 ML을 더 많이 사용한다고 함

딥러닝을 통해서 엄청난 성능 향상이 없었고, 분야 특성상 많은 트래픽을 요하는 등의 이유

따라서, 다양한 엔지니어링 등의 능력이 더 중요시 되고 있음

 

사실 요즘에는 지금 포스팅하는 연관 분석과 TF-IDF보다는 협업 필터링을 더 많이 사용하는데,

그래도 이론을 탄탄히 하기 위해 학습해보자

---

연관 분석

개요

추천 시스템의 가장 고전적인 방법론임

 

연관 규칙 분석 (= 장바구니 분석, 서열 분석)

 

• 상품의 구매나 조회 등 하나의 연속된 거래들 사이의 규칙을 발견하기 위해 적용함
• 주어진 transaction(거래) 데이터에 대해, 하나의 상품이 등장했을 때 다른 상품이 같이 등장하는 규칙을 찾는 것

 

예시1) 맥주와 기저귀를 같이 구매하는 빈도가 얼마나 될까?

예시2) 컴퓨터를 산 고객이 다음에 가장 많이 사는 상품이 무엇일까?

 

{기저귀} → {맥주}

의미: 기저귀를 샀을 때 맥주를 산다.

 

{우유, 빵} → {계란, 콜라}

의미: 우유와 빵을 샀을 때 계란과 콜라를 산다.

 

화살표가 인과관계를 의미하는 건 아님!

---

연관 규칙

용어 정리

1. 규칙?

{condition} → {result}

 

2. 연관 규칙?

특정 사건이 발생했을 때 함께 빈번하게 발생하는 또 다른 사건의 규칙

 

3. Itemset

• antecedent와 consequent 각각을 구성하는 상품들의 집합
• {기저귀} → {맥주}에서 antecedent: {기저귀}, consequent: {우유}
• antecedent와 consequent은 서로소를 만족해야 함 (서로 겹치는 게 없어야 함)

4. k-itemset: k개의 item으로 이루어진 itemset

 

5. support count ($ \sigma $)

• 전체 transaction data에서 itemset이 등장하는 횟수
• 예시

Transaction	Items
1	{맥주, 우유}
2	{빵, 기저귀, 맥주, 계란, 우유}
3	{우유, 기저귀, 맥주, 콜라}
4	{빵, 우유, 기저귀, 맥주}
5	{빵, 우유, 기저귀, 콜라, 계란}

$ \sigma \text{({빵, 우유})} = 3 $

 

6. support

• itemset이 전체 transaction data에서 등장하는 비율
• 예시 (위 표 적용)

$ \text{support({빵, 우유})} = \cfrac{3}{5} = 0.5 $

 

7. frequent itemset

• 유저가 지정한 minimum support 값 이상의 itemset을 의미
• infrequent itemset은 반대로 유저가 지정한 minimum support 보다 작은 itemset을 의미

---

연관 규칙의 척도

척도 (measurement)

연관 규칙 척도: support, confidence, lift

 

위에서 설명한 frequent itemset 들 사이의 연관 규칙을 만들기 위해서는 척도가 필요함

 

1. support

 

$$
s(X)=\frac{n(X)}{N}=P(X), \quad s(X \rightarrow Y)=\frac{n(X \cup Y)}{N}=P(X \cap Y)
$$

 

• 두 itemset $ X, Y $를 모두 포함하는 transaction의 비율
• 전체 transaction에 대한 itemset의 확률값
• 좋은 규칙을 찾거나, 불필요한 연산을 줄일 때 사용

 

2. confidence

 

$$
c(X \rightarrow Y)=\frac{n(X \cup Y)}{n(X)}=\frac{s(X \rightarrow Y)}{s(X)}=\frac{P(X \cap Y)}{P(X)}=P(Y \mid X)
$$

 

$ X $가 포함된 transaction 가운데 $ Y $ 도 포함하는 transaction 비율 ($ X $에 대한 $ Y $의 조건부 확률)

 

 

3. lift

$$
l(X \rightarrow Y)=\frac{P(Y \mid X)}{P(Y)}=\frac{P(X \cap Y)}{P(X) P(Y)}=\frac{s(X \rightarrow Y)}{s(X) s(Y)}=\frac{c(X \rightarrow Y)}{s(Y)}
$$

 

$ \text{lift} = 1 \leftarrow X, Y \text{는 독립} $

$ \text{lift} > 1 \leftarrow X, Y \text{가 서로 양의 상관 관계} $

$ \text{lift} < 1 \leftarrow X, Y \text{가 서로 음의 상관 관계} $

 

 

통합 예시

Transaction	Items
1	{맥주, 우유}
2	{빵, 기저귀, 맥주, 계란, 우유}
3	{우유, 기저귀, 맥주, 콜라}
4	{빵, 우유, 기저귀, 맥주}
5	{빵, 우유, 기저귀, 콜라, 계란}

 

$$
\begin{aligned}
s(X \rightarrow Y) & =\frac{n(X \cup Y)}{N}=P(X \cap Y) \\
& =\frac{n(2,5)}{5}=0.4 \\
c(X \rightarrow Y) & =\frac{n(X \cup Y)}{n(X)}=\frac{n(2,5)}{n(2,4,5)}=0.66 \\
& =P(Y \mid X)=\frac{P(X \cap Y)}{P(X)}=\frac{0.4}{0.6}=0.66 \\
l(X \rightarrow Y) & =\frac{c(X \rightarrow Y)}{s(Y)}=\frac{0.66}{0.4}=1.66 \\
& =\frac{P(X \cap Y)}{P(X) P(Y)}=\frac{s(X \rightarrow Y)}{s(X) s(Y)}=\frac{0.4}{0.6 \cdot 0.4}=1.66
\end{aligned}
$$

 

사용 방법

Item의 수가 많아질수록, 가능한 itemset에 대한 rule의 수가 기하급수적으로 많아짐!

→ 그러니까 이 중에 유의미한 rule만 사용하자

 

1. minimum support, minimum confidence로 의미 없는 rule을 먼저 쳐내기

→ 전체 transaction 중에서 너무 적게 등장하거나, 조건부 확률이 아주 낮은 rule을 필터링

 

2. lift 값으로 내림차순 정렬을 하여 의미 있는 rule 평가

→ lift가 크면 rule을 구성하는 antecedent와 consequent가 연관성이 높고 유의미하기 때문

 

---

연관 규칙의 탐색

 

아래 조건을 만족하는 모든 연관 규칙을 찾자

 

1. (support) $\geq$ (minimum support)
2. (confidence) $\geq$ (minimum confidence)

 

이 조건을 만족하는 모든 연관 규칙 경우의 수를 어떻게 찾을까?

 

Brute-force approach

말 그대로 모든 가능한 연관 규칙을 나열하고,

모든 연관 규칙에 대해 각 support와 confidence를 계산하고,

위 조건에 만족하는 rule만 남기면 됨

 

→ 계산량 매우 많음!

 

$$ \text{Complexity} \sim O(NWM), M = 2^d \text{(d: # of unique items)} $$

 

unique item의 수인 d에 의해 M이 너무 커지게 된다.

 

연관 규칙 탐색 스텝을 두 개로 쪼개보면 다음과 같다.

 

1. Frequent Itemset Generation

minimum support 이상의 모든 itemset 생성

 

2. Rule Generation

minimum confidence 이상의 association rule을 생성

이때, rule을 이루는 antecedent와 consequent는 서로소를 만족

 

1번에서 연산량이 큼

→ 1번의 연산량을 줄여보자

 

방법1) 가능한 후보 itemset의 개수 줄이기 (M 줄이기)

- Apriori 알고리즘

 

방법2) 탐색하는 transaction의 숫자 줄이기 (N 줄이기)

- DHP 알고리즘

 

방법3) 탐색 횟수를 줄인다. (N, M 줄이기)

- FP Growth 알고리즘