연관규칙분석 (Apriori Algorithm)

Apriori에 대하여

FP-Growth* Algorithm은 먼저, Apriori Algorithm을 이해해야 좋다.
그런 이유로 FP-Growth*를 설명하기 앞서 Apriori부터 설명토록 하겠다.
Apriori Algorithm은 연관규칙분석이다. 임의 데이터 집합간 빈번한 발생패턴을 찾는 알고리즘이다.

그러니까, '핸드폰'을 구매한 사람은 '핸드폰 케이스'를 함께 구매할 확률이 높다, 뭐 이런거?

암튼, 수학적인 그리고 이론적인 설명을 주구장창 해 봤자, 짜증(?)만 나고 이해가 안갈 것이기에, 예를들어 되도록 쉽게 설명토록 하겠다. ㅎㅎ

(전공자의 경우, 수학적 설명이나 기호가 빠져 이상하게 생각할 수 있을텐데, 비전공자를 위한 간단한 알고리즘 설명이라 생각바람.)

다음과 같은 구매 목록이 있다고 가정하자.

구매번호	구매물품
1	키보드, 노트북, 외장하드
2	노트북, 파우치
3	노트북, 거치대
4	키보드, 노트북, 파우치
5	키보드, 거치대
6	노트북, 거치대
7	디카
8	키보드, 노트북, 거치대, 외장하드
9	키보드, 노트북, 거치대
10	노트북, 파우치

먼저, 7번항목의 "디카"를 보면, 전체 구매목록에서 단 1회 구매되었다. 즉, 빈번히 발생하는 사건이 아니기에 다른 제품과의 연관성은 없다고 봐도 좋을 것이다.

이런식으로 특정 상품의 구매횟수(노출횟수)를 지지도(support)라 칭하고, 전체 items 중에 얼마나 노출되었는가에 대한 스코어를 채점한다.

지지도가 낮다면(위 구매목록의 예로보면 '디카'의 경우), 전체 데이터 분석 입장에서는 그저 노이즈가 될 뿐이다.


상품 기준으로 표를 다시 정리해보겠다.

구매번호	노트북	키보드	거치대	파우치	외장하드	디카
1	O	O	X	X	O	X
2	O	X	X	O	X	X
3	O	X	O	X	X	X
4	O	O	X	O	X	X
5	X	O	O	X	X	X
6	O	X	O	X	X	X
7	O	X	X	O	X	X
8	O	O	O	X	O	X
9	O	O	O	X	X	X
10	X	X	X	X	X	O
(support)	8	5	5	3	2	1

디카는 전체 10건 중 1회 노출(1/10=0.1)이라는 지지도로서 분석표본에서 배제되어야 할 노이즈로 간주하도록 한다.

(지지도는 전체 중 얼마나 사건(판매)이 발생되었는가 라는 개념이라, '디카'는 전체10회 중 1회이므로 1/10=0.1 이고, '키보드'는 전체 10회 중 5회이므로 5/10=0.5 이다.)

지지도를 0.2로 제한을 둔다면, 각각의 지지도를 기준으로 노트북(0.8), 키보드(0.5), 거치대(0.5), 파우치(0.3), 외장하드(0.2)만 분석대상이 되고 디카(0.1)은 배제된다.


"키보드"을 구매한 사람들은 각각 "노트북, 외장하드", "노트북, 파우치", "노트북, 거치대, 외장하드", "노트북, 거치대"를 구매했다.

각 상품별 동시 구매횟수를 보자. ('키보드'을 구매한 사람이 '노트북'을 구매한 건수는 4건이다')

	노트북	거치대	파우치	외장하드
키보드	상품노출: 5 동시노출: 4 지지도: 4/10=0.4 신뢰도: 4/5=0.8	상품노출: 5 동시노출: 3 지지도: 3/10=0.3 신뢰도: 3/5=0.6	상품노출: 5 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/5=0.2	상품노출: 5 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/5=0.4

여기서부터 신뢰도(Confidence)라는 개념이 등장한다.

지지도는 어떤 아이템이나 아이템들의 출현확률(즉 여기서는 상품이 판매된 수)을 의미한다. 신뢰도는 어떤 사건으로부터 다른 어떤 사건이 일어날 확률을 의미한다.

(실제 구매목록이 아니라 꾸며낸 것이기에 좀 이상하지만, 데이터상으로 볼땐 '키보드' 구매자가 '노트북'을 구매한 사건이 80%(0.8)의 신뢰도를 가졌으므로, '키보드'만을 구매한 사람에게 '노트북'을 추천하면 좋아할 가능성이 높다는 의미가 될 것이다.)

좀더 풀어서 설명하겠다. 여기서 알아낼 수 있는 확률관계는 다음과 같을 것이다.

• '키보드'와 파우치가 동시에 판매될 경우는 총 10회 중 5회(50%)이다.
• '키보드'를 구매한 사람이 '파우치'를 구매할 경우는 총 5회 중 1회(20%)이다.
• '파우치'를 구매한 사람이 '키보드'를 구매할 경우는 총 3회 중 1회(33%)이다.

이를 지지도나 신뢰도 입장에서 풀어보면, 다음과 같은 의미가 된다.

• '키보드'와 '파우치'에 대한 지지도는 50%이다.
• '키보드'에서 '파우치'로의 신뢰도는 20%이다. (키보드 → 파우치)
• '파우치'에서 '키보드'로의 신뢰도는 33%이다. (파우치 → 키보드)

"파우치"를 구매한 사람이 "키보드"를 구매하는 경우가 그 반대 상황보다 많다는 것을 알 수 있다.

이제 더 나아가 아이템 수를 단계별로 늘려 같은 방식으로 생각해 본다.

	노트북, 거치대	거치대, 파우치	파우치, 외장하드	외장하드, 노트북	노트북, 파우치	거치대, 외장하드
키보드	상품노출: 5 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/5=0.4	상품노출: 5 동시노출: 0 지지도: 0 신뢰도: 0	상품노출: 5 동시노출: 0 지지도: 0 신뢰도: 0	상품노출: 5 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/5=0.4	상품노출: 5 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/5=0.2	상품노출: 5 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/5=0.2

(기껏 썼는데 좋은 예제가 만들어지지 않는다. ㅠㅠ 쓴게아까워서 지우지는 않겠;;)

'키보드' 말고 '외장하드' 기준으로 다시. (아몰랑ㅎ)

	노트북, 키보드	키보드, 거치대	거치대, 파우치	파우치, 노트북	노트북, 거치대	키보드, 파우치
외장하드	상품노출: 2 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/2=1 ☞ 100%	상품노출: 2 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/2=0.5 ☞ 50%	상품노출: 2 동시노출: 0 지지도: 0 신뢰도: 0 ☞ 0%	상품노출: 2 동시노출: 0 지지도: 0 신뢰도: 0 ☞ 0%	상품노출: 2 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/2=0.5 ☞ 50%	상품노출: 2 동시노출: 0 지지도: 0 신뢰도: 0 ☞ 0%

여기서는 '외장하드' 구매자가 '노트북'과 '키보드'를 함께 구매한 사건이 100%의 신뢰도를 가졌으므로, '외장하드'를 구매한 사람은 대부분(?) '노트북'과 '키보드'를 구매할 것이라는 예측이 가능하다.

이런 방식으로, 아이템세트의 요소 수를 늘려가며 지지도가 정해진 수치 이상인 조건들을 취해 신뢰도가 높은 세트를 솎아내면 연관규칙 테이블이 완성되게 된다.

(보통 최소 지지도(Minimum Support)를 맘대로 정해, 그 이하는 모두 버리고 신뢰도가 어느정도 높은 결과 세트만을 취하는 방법을 사용한다. 최소 지지도는 그야말로 '내맘'이다.)

하지만 이러한 Apriori 알고리즘은 속도가 매우 느리다는 취약점을 가지기에, 이 문제를 보완한 Partitioning, DHP, ECLAT, 등의 방법을 사용한다.

마치며.

사실, 처음 Apriori를 접할때 느낌은.. '그지같은것들, 별것도 아닌데 참 어렵게도 써 놨다~' 였습니다.ㅋㅋㅋㅋㅋㅋㅋㅋ

정말 아주 간단한 내용입니다. 그저 서로 함께 등장할 수 있는 확률(?)을 구하는게 전부입니다.

그래서 다른걸 찾다가 FP-Growth를 찾게 되었는데, 이게 정말 놀라웠답니다. ^^;;

응용할 수 있는 여지도 엄청났구요.

(저에게만 그런 느낌일 수 있으니 너무 기대는 마시고요;)