[RecSys] 연관 규칙(Association Rule)

RecSys 공부를 하며 가장 먼저 선행되어야 할 공부는 개인적으로 알고리즘 공부라고 생각된다. 몇억개의 로그 데이터를 다루고 분석함에 있어서 빈틈 없는 알고리즘 구조를 익혀야 한다고 생각한다..

 

그 중 가장 기본이 되는 Apriori 알고리즘을 공부하고자 하는데, 그 전에 선행되어야 하는 Association Rule에 대해 간략히 정리해보고자 한다.

 

Association Rule

 

대학교 데이터 분석 수업시간에 마트에서 기저귀를 사는 사람들은 맥주도 함께 사간다는 예시를 들은 경험이 있다. 

연관 규칙(Association Rule)은 이 예시와 같다. 즉, 이렇게 어떤 사건이 얼마나 자주 발생하고 서로 얼마나 연관되어 있는지를 나타내는 것이 Association Rule이라고 보면 된다.

 

연관 규칙(Association Rule)에는 Support, Confidence, Lift의 3가지 척도가 존재한다.

 

Support(지지도)

 

Support는 어떤 아이템이 전체 중에서 출현한 비율, 또는 전체 경우의 수에서 두 아이템이 같이 나오는 비율을 의미한다. 

X랑 Y라는 아이템이 있다고 가정할 때, Support 요소는 X와 Y가 로그에서 얼마나 많이 발생하는 가를 측정하는 척도라고 생각하면 된다. Support를 통해 특정 로그가 우연히 발생했는지, 일반적으로 발생했는지를 알 수 있다.

$$support(x=>y) = \frac{N_{x\cap y}}{N}$$

 

이 때 x와 y의 교집합은 x와 y가 동시에 일어날 경우의 수를 의미하며 support 값이 높을수록 관계가 더욱 의미있다고 볼 수 있다.

 

Confidence(신뢰도)

 

Confidence는 직관적으로 X와 Y의 아이템이 있다고 가정할 때 X가 나온 경우 중 X와 Y가 함께 나올 비율을 의미한다.

이 때 X를 조건부라고 하면 Y를 귀결부라고 한다.

 

Confidence의 요소는 조건부 확률로 Y가 선택이 되었을 때, X가 선택되었을 확률을 의미하며, 두 아이템간의 순차적인 연관성을 설명해준다. 즉, 아이템 간의 발생 순서를 고려하기 때문에, predictability(예측 가능성)을 결정할 수 있다.

$$confidence(x => y) = \frac{N_{x\cap y}}{N_x}$$

 

N_x의 경우 x가 나온 경우의 수를 의미하며, x와 y의 교집합의 경우, x와 y가 동시에 일어날 경우의 수를 의미한다. confidence의 값은 1에 가까울 수록 관계가 더 의미있다고 볼 수 있다.

 

Lift(향상도)

 

개인적으로 가장 RecSys에서 의미있는 Association 지표라고 생각한다. 리프트 값이 높을수록 아이템 X의 출현과 아이템 Y의 출현의 상관관계가 높으므로 아이템 A를 구입한 사용자에게 아이템 B를 추천하면 구입 확률이 높아질 가능성이 존재한다고 생각할 수 있기 때문이다. (이 말은 아래 글을 좀 더 읽으면 이해가 될 것이다..)

 

Lift의 경우 X와 Y의 출현이 어느 정도 상관관계를 갖는지를 나타내는 지표이다. 이는 X와 Y라는 아이템이 있다고 가정할 때 X와 Y가 같이 나오는 비율을 X가 나올 비율과 Y가 나올 비율의 곱으로 나눈값이다.

$$lift(x=>y) = \frac{support(x\cap y)}{support(x) * support(y)}$$

$$lift(x=>y)=\frac{N_{x\cap y}/N}{(N_x/N)(N_y/N)}$$

 

Lift 값은 1보다 클 때 positively correlation, 1일 때 independent, 1 미만일 때 negatively correlation이라고 본다. 때문에, 1보다 큰 값을 가질 때 의미가 있는 수치라고 볼 수 있다.

(Lift값에 로그를 취하게 되면 점별 상호정보량(PMI)가 되는데 word2vec 알고리즘은 점별 상호정보량을 요소로 하는 행렬을 행렬 분해한 것이다.)

 

정리한 위 3가지 척도를 이용해서 데이터셋으로부터 의미있는 Association Rule을 만들어 사용하기 위해 brute force, apriori algorithm, FP-growth algorithm 등 여러가지 알고리즘이 사용된다.

다음 시간에는 대표적인 RecSys 알고리즘인 Apriori 알고리즘을 살펴보자.🤔