RecSys : 추천 시스템 종류와 연관 분석

연관 분석 (association analysis)

\[X \rightarrow Y \text{가 존재할 때, (X, Y: itemset, N: 전체 transaction 수)}\]

연관 규칙
- 주어진 transaction에서 하나의 상품이 등장시 다른 상품의 등장 규칙을 찾는 것
- 규칙 (rule)의 구조
  IF (condition) THEN (result) : {condition} $\rightarrow$ {result}
- 연관 규칙 (association rule)의 구조
  IF (antecendent) THEN (consequent)
  특정 사건이 발생했을 때 함께 빈번하게 발생하는 또 다른 사건 규칙을 의미
Itemset
- antecedent와 consequent 각각을 구성하는 상품들의 집합
- antecedent와 consequent는 서로소를 만족함
  ex) antecedent: {빵, 버터}, consequent: {우유}
support count($\sigma$)
- 전체 transaction data에서 itemset이 등장하는 횟수
support
- itemset이 전체 transaction data에서 등장하는 비율
- 공식은 일반적으로 $\text{support count}/\text{# of transaction}$
빈발 집합 (Frequent Itemset)
- 유저가 지정한 minimum support (threshold) 이상의 itemset을 의미
- 반대 성향은 infrequent itemset이라 함

\[\begin{aligned} s(X) = \frac{n(X)}{N}=P(X) \geq s(X \rightarrow Y) = \frac{n(X \cup Y)}{N} = P(X \cap Y) \end{aligned}\]

연관 규칙에서 자주 사용되는 척도 중 하나
두 itemset X, Y를 모두 포함하는 transaction의 비율
= 전체 transaction에 대한 itemset의 확률값
좋은 규칙을 찾거나, 불필요한 연산을 줄일 때 사용
Support에 나타나는 $n(X \cup Y)/N$은 확률의 교집합과 동일한 개념
- 집합의 관점으로 바라보면 이 의미는 X가 있는 동시에 Y가 있는 집합이라는 의미

\[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|X)\]

\[l(X \rightarrow 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 \rightarrow Y)}{s(Y)}\]

minimum support, minimum confidence로 의미 없는 rule filtering
lift 값의 내림차순으로 의미있는 rule 평가
- 이는 lift가 antencedent와 consequent의 연관분석 값을 의미하므로 큰 값일수록 둘의 상관관계가 높음
- lift는 user의 질적 만족도와 관련성이 높음

transaction이 주어진 경우에 가능한 연관 규칙을 찾는 방법
Brute-force approach
- 가능한 모든 연관 규칙에 대해 support와 confidence를 계산
- 모든 case를 탐색하므로 계산량이 상당함
- $Complexity \sim O(NW M), M = 2^d \text{(d: # of unique items)}$
brute-force 방식의 문제점을 해결하고자 다양한 방법이 도입
rule mining 과정에서 많은 cost가 들어가는 부분은 minimum support 이상의 모든 itemset을 생성하는 것이므로 이 부분의 cost를 줄일 필요가 있음
- Apriori 알고리즘 : 가지치기를 활용하여 탐색하는 M을 줄임
- Direct Hashing & Pruning (DHP) 알고리즘 : itemset 크기가 커지면 전체 N개 transaction보다 적은 개수 탐색
- FP-Growth 알고리즘 : 호율적 자료구조를 활용하여 후보 Itemset과 transaction 저장