[RecSys] 연관분석(Association Analysis)

mincheol2·2022년 3월 11일

RecSys

목록 보기

4/23

이 글은 부스트캠프 AI Tech 3기 강의를 듣고 정리한 글입니다.

개요

연관 규칙 분석(Association Rule Analysis)은 장바구니 분석 or 서열 분석이라고도 불린다.

주어진 Transaction(거래;영수증) 데이터에 대해서 상품A 구매시 상품B가 같이 등장하는 규칙을 찾는 것이다.
상품의 구매나 조회에서 하나의 연속된 거래들 사이의 규칙을 발견하기 위해 적용하고,
유명한 예시로는 기저귀 옆에 맥주를 놨더니 잘 팔리더라(함께구매)가 있다.

이 그림에서 각 Transaction은 한번의 거래를 의미한다.

연관 규칙

연관규칙에서는 규칙과 연관 규칙을 정의해야한다.

규칙 : IF (condition) THEN (result)

{condition} -> {result} 형태로 표시

연관 규칙 : IF (antecedent) THEN (consequent)

antecedent와 consequent 라는 아이템 집합이 빈번하게 발생하는 규칙 가운데 기준을 만족하는 일부

Itemset

antecedent와 consequent를 각각 구성하는 상품들의 집합을 Itemset이라고 한다.
Itemset에서 antecedent와 consequent는 서로소(disjoint) 를 만족한다 -> $antecedent\ \cap\ consequent = \phi$

빈발 집합(Frequent Itemset)

item 품목이 많은 경우 모든 규칙을 살펴보기 현실적으로 어렵기 때문에 많이 등장하는 규칙을 위주로 살펴보아야 한다.

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

Itemset
1개 이상의 Item의 집합(set)
k-itemset : k개의 item으로 이루어진 itemset
Support count( $\sigma$ )
전체 transaction dat에서 item이 등장하는 횟수
Support
itemset이 전체 transaction data에서 등장하는 비율

연관규칙의 척도

Item 수가 많아질 수록 가능한 Itemset에 대한 Rule의 수가 기하급수적으로 많아지기 떄문에
유의미한 Rule만 뽑기 위해 frequent itemset들 사이의 연관 규칙을 만들기 위한 척도가 필요하다.

support

두 Itemset X,Y를 모두 포함하는 transaction의 비율
즉 전체 transacion에 대한 Item의 확률값
좋은(빈도가 높은) 규칙을 찾거난 불필요한 연산을 줄일 때 사용

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

s(X)는 한개도 가능하다는 것을 뜻한다.
$X \rightarrow Y$ 는 연관 규칙을 나타낸다.

이때 $s(X)$ 는 $s(X \rightarrow Y)$ 보다 항상 크거나 같다.

confidence

X가 포함된 transaction 가운데 Y도 포함하는 transaction의 비율
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)

lift

Confidence/Support 로 구한다.
Lift는 1을 기준으로 상관관계를 정의한다.

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 \rightarrow X, Y \text { 는 독립 }$

$\text { lift }>1 \rightarrow X, Y \text { 가 양의 상관관켸를 가짐 }$
-> ancedent와 consequent가 연관성이 높고 유의미하다는 뜻

$\text { lift }<1 \rightarrow X, Y \text { 가음의 상관관계를 가짐 }$

척도의 사용방법

minimum support, confidence를 이용해 의미없는 rule을 제거
lift값으로 내림차순 정렬을 하여 의미있는 rule을 평가함

와인, 와인 오프너, 생수 라는 아이템에 대한 예시를 보자

연관 규칙의 탐색

주어진 트랙잭션 가운데 의미없는 Rule을 제거할 때 가능한 모든 연관 규칙을 나열해서 구한다면 엄청난 계산량을 요구하게 된다.

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

-> 거의 불가능

$N$ : transaction 수
$W$ : transaction의 아이템 수
$M$ : Itemset 수 ( $d$ : item의 unique 갯수)

특히 $M$ 은 item의 개수에 따라 기하급수적으로 증가하기 때문에 사실상 계산 불가

따라서 효율적인 연관규칙을 찾는 것이 중요하다.

연관규칙을 위해서 2가지 일을 수행하는데
1. Frequent Itemset Generation
2. Rule Generation : 1번에서 줄여진 itemset으로 규칙 생성

1번의 cost가 위에서 말한 엄청난 양의 계산량이 요구되는 파트이다.

이를 줄이기 위한 3가지

Apriori 알고리즘 $(M \downarrow)$ : 가지치기(prunning)을 이용하여 가능한 Itemset의 개수를 줄인다
DHP 알고리즘 $(N \downarrow)$ : itemset의 크기가 커짐에 따라 전체 N개 transaction 보다 적은 개수 탐색
FP-Growth 알고리즘 $(N M \downarrow)$ : 모든 itemset과 transaction의 조합을 탐색하지 않고 효율적인 후보 itemset과 transaction을 저장