추천시스템의 연관 규칙 분석

추천시스템 연관 규칙 분석 (Association Rule Analysis, Assuciation Rule Mining)은 흔히 사용되는 머신러닝 기법 중 하나이다.

상품 구매, 조회 등 하나의 연속된 거래들 사이에서 규칙을 발견하기 위해 사용한다.

예를 들어, 맥주를 사는 사람과 소주를 같이 구매하는 빈도가 어떻게 될까? 와 같은 규칙을 수치적으로 나타내는 것이다.

이런 식으로 규칙을 찾는 것이고, 연관 규칙 분석은 "이걸 사서 저걸 사게 됐다"와 같은 인과관계를 의미하지 않는다.

연관 규칙 알고리즘 전에 몇가지 정의하고 가야 한다.

1. 연관 규칙 : If (antecedent) Then (consequent)
   특정 사건이 발생했을 때 함께 빈번하게 발생하는 또 다른 사건의 규칙을 의미한다.

• Itemset : antecedent와 consequent 각각 구성하는 상품들의 집합
  antecedent와 consequent는 disjoint를 만족한다.
  antecedent : {빵, 버터}, consequent: {우유} 이런 식으로 서로 겹치는 것이 없도록 만든다.
• Support count($\sigma$) : 전체 transaction data에서 해당 itemset이 등장하는 횟수
• Support : itemset이 전체 transaction data에서 등장하는 비율
• Frequent itemset : minimum support 값 이상의 itemset

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

• Support : 두 itemset X, Y를 포함하는 transaction 비율
  $s(X)=\frac{n(X)}{N}=P(X), s(X \rightarrow Y)=\frac{n(X\cup Y)}{N}=P(X \cap Y)$
• Confidence : X가 포함된 transaction 중 Y도 포함하는 transaction 비율 (Y의 X에 대한 조건부 확률)
  $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)$
• lift : (X가 포함된 transaction 가운데 Y가 등장될 확률) / (Y가 등장할 확률)
  lift = 1 → X, Y는 독립
  lift > 1 → X, Y가 양의 상관관계를 가짐
  lift < 1 → X, Y가 음의 상관관계를 가짐
  $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)}$

연관 규칙 분석을 하기 위해선 모든 아이템에 대해서 support, confidence, lift를 계산해야한다.

즉, item수가 많아질수록, rule 수가 기하급수적으로 증가한다.

따라서, 효율적인 Association Rule Mining이 필요한데, 2가지 step을 밟는다.

1. Frequent Itemset Generation : minimum support 이상 모든 itemset 생성 → 요기서 computation cost가 가장 크다

• 가능한 후보 itemset 개수를 줄인다
  Apriori 알고리즘 : 가지치기를 활용해서 탐색해야하는 M을 줄인다
• 탐색하는 transaction 숫자를 줄인다
  DHP (Direct Hashing&Pruning) 알고리즘
• 탐색 횟수를 줄인다
  FP-Growth 알고리즘

2. Rule Generation : minimum confidence 이상 association rule 생성