[RecSys] 연관 규칙 (Association Rule)

Intro

추천 시스템은 크게 content-based와 collaborative filtering으로 분류된다. CF는 '이웃 기반'과 '모델 기반'으로 나뉘는데, 연관 규칙은 모델 기반의 협업 필터링에 속하는 방식이다. 데이터 간의 관계를 분석하기 위하여 마케팅 등의 분야에서 고전적으로 사용되고 있던 방법이나, 추천 알고리즘의 일환으로도 사용된다. 오늘은 연관 규칙이 무엇인지 알아보고자 한다.

 

연관 규칙(Association Rule)이란?

연관 규칙이란 데이터에서 흥미로운 관계를 찾는 rule-based machine learning 기법 중 하나이다. 다양한 아이템간의 관계 중 어느 수준 이상의 관련성을 가지는 관계가 연관 규칙이고, 이를 찾아내는 기법을 Association Rule Mining이라 한다. Association Rule Mining에 대해서는 아래와 같이 표현할 수도 있다.

• 최소 지지도(minimum support)와 최소 신뢰도(minimun confidence)를 넘는 rule을 찾는 과정
• 특정 measure를 통해 interestingness를 평가하여 strong rules를 찾는 과정

연관 규칙의 measures

연관 규칙에서는 지지도, 신뢰도 그리고 향상도라는 mesure가 사용된다. 이들은 모두 규칙의 발생 확률 또는 관련성을 수치로 나타내는 개념이다. 각각의 measure를 계산하는 방법뿐 아니라, 의미하는 바를 이해하는 것이 중요하다.

지지도(support)

지지도는 아이템이 동시에 발생할 확률이다. 즉 전체 데이터 중 규칙(A, B)를 포함하는 데이터의 비율을 의미한다. 확률이므로 값은 [0, 1] 사이의 값을 가지며, 0에 가까울수록 자주 발생하지 않음을, 1에 가까울수록 자주 발생하므로 A와 B사이의 관계가 중요하다는 것을 의미한다. support(A-> B)와 support(B -> A)는 차이점 파악이 불가능하다. 

연관 규칙 마이닝에서는 minimum support threshold를 설정한 뒤, 아이템간의 규칙 중 threshold를 넘는 규칙을 선택한다. 다시 말하면 연관 규칙을 찾을 때에는 특정 확률 이상 발생하는 사건(규칙)을 채택한다는 의미이다.

지지도 수식

신뢰도(confidence)

신뢰도는 특정 아이템 A를 선택했을 때, 다른 아이템 B를 선택할 확률이다. (A, B)의 관계를 가정하고, A를 선택한 사람이 B를 선택한 비율이다. 신뢰도도 확률이므로 [0, 1] 사이의 값을 가진다. A에 대한 B의 조건부 확률이기도 하다. 그러므로 1에 가까울수록 A는 B에 많은 영향을 받는다고 할 수 있다. 또 지지도와는 다르게 confidence(A -> B)와 confidence(B -> A)는 다른 값을 가진다.

 

연관 규칙 마이닝에서는 minimum support를 넘어 채택된 규칙 중 confidence가 가장 큰 규칙을 선택한다. 이는 자주 발생하는 규칙 중 A와 B 사이의 관계가 더 명확한 규칙을 선택하는 것으로 해석할 수 있다.

신뢰도 수식

향상도(Lift)

(A, B)의 관계를 직접적으로 나타내는 measurement. 지지도, 신뢰도와는 다르게 [0, 1] 사이의 확률 값이 아니라, A와 B 사이의 관계를 파악하는 용도로 사용된다. 향상도의 값은 아래와 같이 해석 가능하다. 향상도는 A -> B에 대한 신뢰도를 B에 대한 지지도로 나눈 값이다. 

• lift(A -> B) < 1: 상호 대체, A와 B는 반비례 (A, B 각각의 발생 확률을 곱한 값보다 A&B 발생 확률이 더 작음)
• lift(A -> B) = 1: 독립, 관계 없음 (A, B 각각의 발생 확률을 곱한 값과 A&B 발생 확률이 같음. 독립 사건)
• lift(A -> B) > 1: 상호 보완, A와 B는 정비례 (A, B 각각의 발생 확률을 곱한 값보다 A&B 발생 확률이 더 큼)

향상도 수식

예제

지지도, 신뢰도, 향상도를 계산해보자. 유저들이 본 영화 정보가 담긴 테이블이 있다. 아래 질문에 답해보자.

 

User-id	Movies Watched
1	A, B, C
2	A, C
3	A, D
4	B, E, F
5	B, C, D

1. Confidence(A -> C)를 구해라

=> Confidence(A -> C) = P(C|A) = 2/3

A -> C의 신뢰도는 비교적 1에 가까우므로, 두 아이템의 관계는 중요하다고 할 수 있음

 

2. Lift(A -> C)를 구해라

 

=> Lift(A -> C) = Confidence(A -> C) / Support(C)

=> Confidence(A -> C) = 2/3 = 0.67

 

=> Support(C) = 3/5 = 0.6

 

=> Lift(A -> C) = 0.67/0.6 = 1.1111...

A -> C 향상도는 1보다 크므로, 둘은 상호 보완 관계임. 

 

Association rule mining methods

위의 measurements는 연관 규칙을 판단하는 기준이라면, 아이템간의 규칙을 찾아 연관 규칙을 찾아내는 방법은 아래와 같은 방법들이 있다.

Brute Force

• 모든 연관관계에 대해 minimum support threshold, minimum confidence threshold를 전부 평가하는 방법.
• 연산량이 많고 비효율적임.

Frequent Itemset Generation

• 빈도수가 높은 관계 위주로 후보군을 축소하여 rule mining을 진행하는 방법
• Apriori principle: 데이터 발생 빈도를 바탕으로 데이터 간의 연관관계 파악에 사용됨

추천 알고리즘과 연관 규칙

인트로에서 언급했지만, 연관 규칙은 규칙 기반의 머신 러닝 기법으로, 추천 알고리즘에서는 모델 기반의 협업 필터링으로 분류된다. 연관 규칙은 데이터에서 유저들의 아이템 선택에 어떤 규칙이 있는지를 찾아내어, 그 규칙을 새로운 유저에게 적용하는 방법이다. 이렇게 다른 유저와 아이템 간의 관계를 활용하므로 협업 필터링에 속한다고 할 수 있다.

어떤 방식으로 추천 알고리즘의 역할을 할 수 있는지 예제를 통해 이해해보자. 이커머스에서 아이템을 구매하는 상황이다. 유저들은 다양한 아이템을 구매하는데, 그 중에서 특히 우유와 시리얼의 구매 빈도가 높았다. 확인해보니 우유를 구매한 사람은 시리얼을 구매하는 규칙의 향상도가 1 이상으로 높았다. 우유를 구매한 사람에게 시리얼을 추천하도록 rule을 코딩하여 우유를 구매한 사람에게 시리얼을 제안할 수 있다. 

 

참고 자료

- 패스트 캠퍼스 추천 시스템 강의