(R) 연관규칙(Apriori) 이해하기

 

 

Apriori 알고리즘이란?

Apriori 알고리즘이란 연관규칙(association rule)으로, 특정 사건이 발생하였을 때 함께 (빈번하게) 발생하는 또 다른 사건의 규칙을 말한다.

 

 

Apriori 알고리즘을 사용하는 대표적인 예

1. 암 분석 시 빈번히 발생하는 DNA 패턴과 단백질 서열 검사

2. 신용카드 사기를 당했을 때 주로 결제되는 내역 패턴

3. B2C에서 구매자의 구매 상품과 비슷한 상품 추천

 

 

연관규칙에 사용하는 3가지 통계 척도

종류	설명	표기식
지지도(support)	특정 아이템이 데이터에서 발생하는 빈도	s(X) = n(X) / N n(X) : 아이템 X의 거래건수 N : 전체거래건수
		s(X,Y) = n(X∩Y) / N n(X∩Y) : 아이템 X와 Y를 포함하는 거래건수 N : 전체거래건수
신뢰도(confidence)	두 아이템의 연관규칙이 유용한 규칙일 가능성의 척도	c(X→Y) = n(X∩Y)/n(X) n(X∩Y) : 아이템 X와 Y를 포함하는 거래건수 n(X) : 아이템 X의 거래건수
아이템 X를 포함하는 거래 중에서 아이템 Y도 포함하는 거래비율을 말한다. 신뢰도가 높을수록 유용한 규칙일 가능성이 높다.
향상도(lift)	두 아이템의 연관규칙이 우연인지 아닌지를 나타내는 척도	lift(X→Y) = c(X→Y) / s(Y)
아이템 X가 주어지지 않았을 때의 아이템 Y 확률 대비 아이템 X가 주어졌을 때의 아이템 Y 확률 비율을 나타낸다. 향상도가 1보다 크거나(+관계) 작으면(-관계) 우연적 기회보다 우수함을 의미한다.

연산식이 교집합(∩)인지, 합집합(∪)인지에 대해서 헷갈릴 수 있겠는데

그냥 조건부 확률을 구한다고 생각하자.

 

아래의 문제를 통해 연관규칙 알고리즘을 이해해보자.

 

거래번호	거래 아이템
1	우유, 버터, 시리얼
2	우유, 시리얼
3	우유, 빵
4	버터, 맥주, 오징어

 

문제 1. s(우유,시리얼) = n(X∩Y) / N = 2/4

 

          우유와 시리얼이 같이 있는 경우를 교집합(∩)으로 써야할까, 합집합(∪)으로 써야할까?

          나같은 경우는 수학적으로 생각했을 때, 교집합이 맞다고 생각해서 교집합을 썼지만 언어적으로는 합집합이

          맞는것 같다. 따라서 이것은 맥락적으로 이해하는 것이 매우 중요하다.

 

문제 2. c(우유→시리얼) = n(X∩Y) / n(X) = 2/3

 

문제 3. lift(우유→시리얼) = c(우유→시리얼) / s(우유,시리얼) = (2/3) / (2/4) = 1.333

 

 

 

 

 

 

 

---

 

 

 

 

 

PRUNING (가지치기)

모든 아이템들간의 관계성을 알아봐야하기 때문에, 데이터가 많아지면 지수적으로 경우의 수가 많아져 계산량이 많아진다.

따라서 우리는 이것을 효율적으로 수행해야한다.

 

거래번호	아이템 목록
1	A,B,D
2	B,C,
3	A,B,C,E
4	B,C,E

 

1. 각각의 아이템에 대한 지지도를 구한다.

(원래 지지도(s)는 구매건수 / 전체구매건수 이지만 가지치기에서는 단순히 아이템의 갯수로 처리한다.)

 

아이템	지지도
A	2
B	4
C	3
D	1
E	2

 

2. 위의 결과에서 지지도가 1보다 큰 것을 추출한다.

 

아이템	지지도
A	2
B	4
C	3
E	2

 

1-2. 아이템을 2개 조합으로 만들어 지지도를 구한다.

 

아이템	지지도
A B	2
A C	1
A E	1
B C	2
B E	1
C E	2

 

2. 위의 결과에서 지지도가 1보다 큰 것을 추출한다.

 

아이템	지지도
A B	2
B C	2
C E	2

 

1-3. 아이템을 3개 조합으로 만들어 지지도를 구한다.

 

아이템	지지도
A B C	1
A B E	1
A C E	1
B C E	2

 

2. 위의 결과에서 지지도가 1보다 큰 것을 추출한다.

 

아이템	지지도
B C E	2

 

가지치기(Pruning)를 당한 것들에 대해서는 지지도를 계산하지 않는다.

 

 

 

 

 

이외에도 효율적으로 연관성 분석을 하는 방법이 있으니, 블로그를 참고하길 바란다.