Association Rules - 1
이 Association Rules란 무엇인가... 하면
데이터 상호간의 연관 규칙을 찾아내는 기술이라고 한다.
예를 들어
구매 번호 | 구매 상품들 |
1 | {라면, 우유, 오렌지, 쥬스, 커피} |
2 | {라면, 우유, 소시지} |
3 | {라면, 우유, 커피} |
4 | {오렌지 쥬스, 비누, 샴푸} |
사용자 1, 2, 3, 4에 의해 물품들이 위와 같이 판매 되었다면
{라면, 우유} {커피}
즉, 라면과 우유를 산 사람은 커피도 산다라는 간단한 규칙을 얻을 수 있다.
이러한 규칙을 설명하는데 두 가지의 파라메터를 이용하는데
1. 지지도(support) 전체 트랜젝션 중에서 그 규칙을 가지고 있는 트랜젝션의 % * 위의 예제에서는 50%라고 할 수 있다.
2. 신뢰도(confidence) 규칙의 왼쪽에 있는 것들을 산 사람들 중에서 오른쪽에 있는 물건들을 모두 산사람의 % * 위 예제에서는 66.67%, 2/3이라고 할 수 있다. |
Association Rule을 찾기 위해서는 정의되어야 할 수치가 있다.
minimum support와 minimum confidence(최소 지지도, 최소 신뢰도)가 그것이다.
왜냐! 개나 소나인 Association Rule은 찾아보이 쓸데가 없기 때문이라고 할 수 있다.
(개나 소나가 아닌 Association Rule을 Frequent Association Rule이라 한다. 바꿔 말하면
쓸모 있는 것은 Frequent Association Rule이란 소리…)
자, 이제 그렇다면 Association Rule을 찾아 보도록 하자.
Transaction ID | Items |
10 | a, c, d, f |
20 | b, c, e |
30 | a, b, c, e |
40 | b, e |
50 | a, f |
Minimum support = 40%
Minimum confidence = 80%
위와 같은 데이터가 있다고 하자.
Step 1. minimum support를 만족하는 모든 아이템 셋들을 찾는다.
minimum support를 만족하는, item set의 크기가 1인 frequent item set
(말이 어렵지, 그저 a가 몇 번, b가 몇 번 나왔는지 센 것에 불과하다.)
Item set | Support |
| Item set | Support |
| Item set | Support |
a | 3 | a, c | 2 | b, c, e | 2 | ||
b | 3 | a, f | 2 |
|
| ||
c | 3 | b, c | 2 |
|
| ||
e | 3 | b, e | 3 |
|
| ||
f | 2 | c, e | 2 |
|
|
(* 여기서 acdf, abce가 나오지 않은 이유는 minimum support를 만족하지 않기 때문이다.)
자, 이제 Naïve한 Frequent item set을 찾는 알고리즘을 소개한다.
다음과 같은 데이터에서
TID | Items |
10 | A, C, D |
20 | B, C, E |
30 | A, B, C, E |
40 | B, E |
10번 ID의 Item의 subset들을 카운트 한다.
Item set | Count |
A | 1 |
C | 1 |
D | 1 |
A, C | 1 |
A, C | 1 |
C, D | 1 |
A, C, D | 1 |
20번 ID의 Item의 subset들을 카운트 하여 추가한다. (표로 하자니 좀 힘드네..)
Item set | Count |
A | 1 |
C | 2 |
D | 1 |
A, C | 1 |
A, C | 1 |
C, D | 1 |
A, C, D | 1 |
B | 1 |
E | 1 |
B, C | 1 |
B, E | 1 |
C, E | 1 |
B, C, E | 1 |
30번 ID, 40번 ID의 item들도 세어서 추가한다.
Item set | Count | Item set | Count |
A | 2 | A, B | 1 |
C | 3 | A, E | 1 |
D | 1 | A, B, C | 1 |
A, C | 2 | A, B, E | 1 |
A, C | 1 | A, B, C, E | 1 |
C, D | 1 |
| |
A, C, D | 1 | ||
B | 3 | ||
E | 3 | ||
B, C | 2 | ||
B, E | 3 | ||
C, E | 2 | ||
B, C, E | 2 | ||
이제 minimum support를 만족하는 item set들을 추려내면 된다.
이와 같은 방법을 사용하면 각 Item에 해당되는 subset들을 찾느라고 2의 n승만큼의 연산이 필요하다.
이는 매우 효과적이지 못한 방법인데, 이를 해결하기 위한 알고리즘은 다음에 소개하기로 한다.
이제 Frequent Association Rules를 찾으면 되는데, 간단한 알고리즘은 다음과 같다.
풀어서 적자면, 모든 large item set(후에 frequent itemset으로 terminology 변경)의 집합에 대하여 genrules를 수행하는데
여기서 k는 large item set의 원소의 수이다.
for each frequent itemset f do |