연관 규칙 분석(Association Rule Analysis)

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

장바구니 분석, 서열 분석이라고도 불린다.

상품의 구매, 조회 등 하나의 연속된 거래들 사이의 규칙을 발견하기 위해 적용하는 방법

즉, 사용자의 장바구니 내에 포함된 상품들의 규칙을 발견하기 위해 적용하는 방법

유저 정보(유저 행동 정보)를 활용하는 분석 방법

규칙

IF {condition} THEN {result}

{condition} → {result}

연관 규칙

규칙 가운데 일부 기준(빈번함의 기준)을 만족하는 것

IF {antecedent} THEN {consequent}

빈번하게 발생하는 규칙을 의미한다.

ex) {기저귀} → {맥주}

{우유} → {빵}

이 때, 화살표는 연관 관계를 나타낼 뿐, 인과관계를 의미하지 않는다.

Itemset

연관규칙을 구성하는 상품의 집합(antecedent, consequent)

하나 이상의 집합으로 구성

antecedent와 consequent는 disjoint(서로소)를 만족해야 한다.

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

support count($\sigma$)

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

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

support

itemset에서 전체 transaction data에서 등장하는 비율

• support count로 계산된 값.

  support({빵, 우유}) = 3 / 5 = 0.6

• 연관 규칙에서 가장 중요한 값.

frequent itemset

유저가 지정한 minimum support 값 이상의 itemset

minimum support 값을 넘지 못한 itemset은 infrequent itemset이라고 부른다.

연관 규칙의 척도

frequent itemset들 사이의 연관 규칙을 만들기 위해서 measurement가 필요하다.

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

• support

  두 itemset $X,Y$를 모두 포함하는 transaction의 비율

  즉, 전체 transaction에 대한 itemset의 확률값

  좋은 규칙을 찾거나, 불필요한 연산을 줄일 때 사용된다.

• confidence

  $Y$의 $X$에 대한 조건부 확률

  confidence가 높을수록 유용한 규칙이다.

• lift

  [$X$가 포함된 transaction가운데 $Y$가 등장할 확률] / [$Y$가 등장할 확률]

  1을 기준으로 나타난다.

  0~1 사이의 값이 아니다.

  • $\tt lift = 1 ⇒ X,Y\ 독립$
  • $\tt lift > 1 ⇒ X,Y\ 양의\ 상관관계$
  • $\tt lift < 1 ⇒ X,Y\ 음의\ 상관관계$

• 예시

연관 규칙의 사용

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

이 중 유의미한 rule만 사용해야 한다.