[Day31] 추천 시스템 Basic 2-1 연관 분석

추천 시스템 분야는 다른 분야에 비해 ML기법을 DL기법 보다 많이 사용한다. DL이 더 좋은 성능을 내긴 하지만 향상 폭이 dramatic하지 않고, 많은 유저가 이용하는 서비스에서 큰 트래픽을 감당하기에 DL은 연산량이 많아서 무겁다.

연관 규칙 분석=장바구니 분석=서열 분석 Association Rule Analysis=Association Rule Mining

소비자가 한 장바구니 안에 어떤 물건을 같이 담는지 유저가 상품을 구매하는 연속된 거래 사이에서 규칙을 발견하기 위해서 적용

ex) 컴퓨터를 산 고객이 같이 구매하는 상품

 

연관 규칙 Association Rule

하나의 상품이 등장했을 때 다른 상품이 같이 등장하는 규칙을 찾는 것

ex) 기저귀를 샀을 때 맥주도 같이 산다 : {기저귀}$\rightarrow${맥주}

• 규칙
  IF (condition) THEN (result)
  {condition} $\rightarrow$ {result}
  어떤 condition에 해당하는 아이템이 있을 때 result에 해당하는 아이템이 등장한다.
• 연관 규칙
  IF (antecedent) THEN (consequent)
  antecedent와 consequent라는 아이템 집합이 빈번하게 나타나 기준을 만족시키는 규칙
• Itemset
  antecedent와 consequent를 구성하는 상품의 집합
  antecedent와 consequent는 서로 겹치는 아이템을 가지고 있지 않다.
  1개 이상의 item으로 이루어져 있다.
• k-itemset
  k개의 item으로 이루어진 itemset
• support count($sigma$)
  전체 transaction data에서 itemset이 등장하는 비율
  ex) itemset : {빵, 우유}
  

  Transaction	Items
  1	{빵}
  2	{빵,우유}

  $\sigma$({빵, 우유})=1
• support
  연관 규칙에서 가장 중요한 개념 중 하나
  support({빵,우유})=1/2=0.5
• 빈발 집합 Frequent Itemset
  transaction data에 자주 등장한다.
  모든 itemset 가운데 유저가 지정한 minimum support값 이상을 만족시키는 itemset을 의미한다.
• Infrequent Itemset
  Frequent Itemset과 반대로 유저가 지정한 minimum support보다 작은 itemset을 의미한다.

연관 규칙의 척도

Support

$X\rightarrow Y$가 존재할 때, 전체 transaction에서 itemset이 등장하는 비율 [0,1]

※$X,Y$는 itemset, N은 transaction 수

 

$X$에 대해서만도 정의할 수 있고

$$s(X)=\frac{n(X)}{N}=P(X)$$

 

$X\rightarrow Y$에 대해서도 정의할 수 있다.

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

$P(X\cap Y)$ : $X$와 $Y$가 모두 등장할 확률

 

항상 s(X) $\geq s(X\rightarrow Y)$가 된다

Confidence

$Y$의 $X$에 대한 조건부 확률[0,1]

:X가 포함된 transaction 가운데 Y도 포함하는 transaction 비율

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

$n(X)$ : X에 대한 support count

 

그래서 confidence가 높으면 추천하기에 유용한 규칙임을 알 수 있다.

 

Lift

lift = 1 이면 X, Y는 서로 독립이고,

lift > 1 이면 X, Y가 양의 상관관계,

lift < 1 이면 X, Y가 음의 상관관계를 가진다.

 

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

=(X가 주어졌을 때 Y가 등장할 확률)/(Y가 등장할 확률)

 

유의미한 rule filtering

item수가 많아짐 -> 가능한 itemset 수가 많아짐 ->rule수가 기하급수적으로 많아짐

그렇기 때문에  유의미한  rule 을 찾아서 사용해야 한다.

1. 사용자가 지정한 minimum support, minimum confidence값을 가지고 의미없는 rule을 screen out한다.
   support $\geq$ minimum support
   confidence $\geq$ minimum confidence
   :전체 transaction 중에서 너무 적게 등장하는 itemset이나 조건부 확률이 아주 낮은 rule을 필터링 한다.
2. 최종 추천을 제공하기 위한 척도로 lift값을 이용한다.
   
   예를 들어 x=와인, y=오프너, z=생수일 때,와인을 샀는데 오프너도 살 확률은 P(Y|X)=0.1와인을 샀는데 생수도 살 확률 P(Z|X)=0.2이고평소에 오프너를 살 확률 P(Y)=0.01평소에 생수를 살 확률 P(Z)=0.2 라고하자와인을 사지 않아도 평소 사람들이 많이 생수를 소비하기 때문이다.이 경우 lift값을 구하면 오프너는 10, 생수는 1이라는 결과가 나온다.그래서 와인을 샀을 때 오프너를 추천받으면 더 만족스러운 결과를 얻을 것이고,소비자 입장에서 lift를 사용하는 것이 만족스러운 추천 결과가 나온다.

연관 규칙의 탐색

Mining Association Rules

: 연관 규칙을 추천에 사용하기 위해서 주어진 데이터 셋에서 모든 연관 규칙을 추출하는 것

연관 규칙을 탐색하는 과정이 연관 분석에서 가장 중요하고 어렵다.

 

위의 1번에서 본 규칙

support $\geq$ minimum support
confidence $\geq$ minimum confidence

을 만족하는 모든 연관 규칙을 어떻게 찾아야 할까?

 

Brute-force approach

가장 간단하고 무식한 방법
가능한 규칙을 나열하고 그 규칙들에 대한 각각의 support와 confidence를 계산해서 rule에 따라 pruning해서 frequent item을 찾는 것이다.
하지만 그렇기 때문에 Brute-force approach는 엄청난 계산량을 요구한다.

개별 transaction별로 모든 item을 full scan하고 가능한 itemset별로 모든 support를 또 계산 해야한다.

• N : 전체 transaction 수
• W : 각 transaction의 itemset의 갯수
• M : itemset의 모든 가능한 갯수 $=2^{d}$ ※d=unique한 item의 갯수

그래서 계산량이 N*W*M이 된다.

M이 exponential scale로 증가하기 때문에 M이 가장 큰 문제이다.

만약 itemset의 support를 계산했다고 하더라고 주어진 d개의 item으로 구성한 모든 연관 규칙의 갯수는 $3^{d}$이 되어 계산이 매우 복잡하다.

결국 제한시간 내에 의미있는 연관 규칙을 탐색할 수 없게 된다.

 

효율적인 Association Rule Mining

1. Frequent Itemset Generation
   minimum support 이상의 모든 itemset을 생성한다.
   이렇게 확 수가 줄어든 frequent itemset을 만들 수 있다.
   하지만 가능한 모든 itemset의  support를 계산하는 과정이 또 계산량이 크다. 그래서 또 이를 해결할 전략이 필요하다. 밑의 전략들은 원래 exponential 시간이 걸리는 itemset계산을 단축시킨다.
   
   Frequent Itemset Generation Strategies
   
   1. 가능한 후보 itemset의 개수를 줄인다.
      M의 수 줄이기 -> Apriori 알고리즘
   2. 탐색하는 transaction의 숫자를 줄인다
      N의 수 줄이기 -> DHP(Direct Hashing & Pruning) 알고리즘
   3. 탐색 횟수를 줄인다
      N*M 줄이기 -> FP-Growth 알고리즘
2. Rule Generation
   minumum confidence 이상의 association rule을 생성한다.

1번의 계산량 문제를 해결하기 위한 전략