[연관 규칙 - 1] Apriori란?

어떤 현상들끼리 연관 규칙이 있는가를 알아내는 알고리즘이 Apriori이다.

 

 

밤 8시만 되면 기저귀와 맥주가 동시에 팔리는 현상이 있다고 하자.

기저귀와 맥주? 아무 연관관계도 없을 것 같은 이 두 물건이 무슨 관계가 있을까?

아마 유부남이 기저귀가 다 떨어져서 기저귀를 사러왔는데 퇴근도 했겠다 맥주도 같이 사러 간다는 분석이 있다면 어느 정도 일리가 있다고 느낄 수 있다.

그냥 흔한 경우를 생각해본다면, 편의점에서 햄버거를 사는 사람은 콜라도 구매할 확률이 높다.

데이터 세트에서 이런 연관 규칙을 찾는 것이 Apriori 알고리즘이라고 할 수 있다.

 

---

Apriori 알고리즘

아래와 같은 데이터 세트가 있다.

ID	itemset
1	A, B, C
2	B, C
3	A, C
4	A
5	A, D

지지도를 2/5 로 설정하겠다.

 

개수마다 부분 집합의 수를 세어본다. 이 과정을 pruning이라고 한다.

C_1

itemset	count
A	4
B	2
C	3
D	1

여기서 D는 우리가 설정한 지지도보다 낮으므로 삭제한다.

 

C_1을 만족하는 C_2

itemset	count
A, B	1
A, C	2
B, C	2

A, B는 우리가 설정한 지지도보다 낮으므로 삭제한다.

 

C_2를 만족하는 C_3

itemset

count

는 없다.

A, B, C밖에 경우의 수가 남지 않았는데 A, B, C는 이전에 제거했던 A, B를 포함하므로 카운트 하지 않는다.

 

 

 

---

신뢰도(Confidence)와 향상도(Lift)

 

신뢰도는 햄버거를 구매한 사람이 40명이라고 했을 때, 콜라를 구매한 사람이 10명이라고 하면 신뢰도는 10 / 40 = 1 / 4이다.

향상도는 신뢰도를 지지도로 나눈 것이다. 지지도를 2/5라고 했을 때, 향상도는 (1 / 4) / (1 / 10) = 2.5이다.