CAFE

Apriori 알고리즘은 연관성 분석 기법 중에 하나로 가장 먼저 개발되었고 또한 가장 많이 쓰이는 알고리즘이다.

연관성 분석은 보통 매우 많은 항목들간의 관계를 파악해야 하므로 알고리즘의 성능이 매우 중요한 요소가 된다.

n개의 항목이 있을때 이 항목을 이용하여 만들 수 있는 모든 항목집합은 2^n 제공이 된다. 실제로 지지도와 신뢰도 처리 로직은 간단하나 항목수가 많아질수록 알고리즘은 실제로 활용하기 어려워진다.

Apriori알고리즘의 경우는, 우선 1단계에서는 최소 지지도로 설정된 값에 따라 빈도수가 높은 항목의 집합을 찾아내고 2단계에서는 이들 빈도수가 높은 항목 집합에서 신뢰도 설정값을 만족하는 연관 규칙을 모두 찾아내는 방식이다.

이 알고리즘의 특징은 빈도수가 높은 항목 집합의 모든 부분 집합은 모두 빈도수가 높고, 어떤 집합이 주어졌을 때 새로운 항목을 더해주면 지지도는 절대로 전보다 증가할 수 없다는 점을 바탕으로 우선 크기가 1인 항목 집합에서 빈도수가 높은 항목만을 찾고, 그 다음에는 그 항목들을 바탕으로 크기가 2인 항목 집합을 구하는 방식으로 수행한다.

Apriori 알고리즘은 항목 집합 크기가 1인 경우부터 크기를 차례로 늘려가는 방식으로 수행한다. 가장 크기가 큰 항목집합의 크기가 k라면 대략 데이터를 k번 스캔하게 된다. 크기가 k개인 빈도 높은 항목들을 구했다면 이들 항목을 이용해 크기가 k+1인 항목들 집합을 구한다. 예를 들어 <주스, 콜라> 와 <주스, 맥주>의 빈도 높은 크기가 2인 항목집합이 구해졌다면 다음에는 <주스,콜라,맥주>의 항목 집합을 만들어 빈도를 계산한다. 빈도 높은 크기 2인 항목 집합의 항목들을 포함하여 크기 3인 후보 항목집합을 만든 후, 실제 데이터를 스캔하여 빈도를 계산하여 주어진 지지도를 만족하는 집합을 찾는다. 그리고, 이들을 다시 이용하여 크기가 4인 항목 집합을 만들고 지지도를 검사하는 식을 더 이상 항목 집합을 만들 수 없을 때까지 반복한다.

예를 들어 다음의 트랜잭션에 대해서 항목을 구매했다고 가정해자.

TID	Items
100	A C D
200	B C E
300	A B C E
400	B E

이제 각각의 item에 대해서 지지도를 산정해보자. 물론 원래 지지도는 "구매건수/전체구매건수"로 계산할 수 있지만 여기에서는 단순하게 그 개수로 정하고 처리했다.

ItemSet	Support
A	2
B	3
C	3
D	1
E	3

이것에 대해서 지지도가 1이상인 것만 추출하여 다시 정리하면 다음과 같다.

ItemSet	Support
A	2
B	3
C	3
E	3

이제 두 ItemSet의 곱으로 ItemSet을 다시 구성한다.

ItemSet
A B
A C
A E
B C
B E
C E

그리고 앞에서 한 절차에 따라서 다시 지지도를 구한다. 물론 지지도는 최초 TID에 대한 ItemSet을 기준으로 계산해야 한다.

ItemSet	Support
A B	1
A C	2
A E	1
B C	2
B E	3
C E	2

그리고 지지도가 1인 것을 제외시킨다.

ItemSet	Support
A C	2
B C	2
B E	3
C E	2

이제 각각의 ItemSet에서 첫번째 Item을 기준으로 동일한 것을 찾는다. 위 경우에는 B가 발생하며 이 B에 대해서 각각의 두번째 키를 조합한다. 그러면 B에 대해서 C, E가 조합된다. 이제 C와 E가 있는지 확인하여 존재하면 조합하여 "B, C, E"를 구성한다.

ItemSet	Support
B C E	2

그리고 다시 이것에 대해서 지지도를 구하면 2가 나타난다. 이제 더 이상 조합을 찾을 수 없으므로 이것이 빈발하는 항목집합이 된다.

Apriori Algorithm은 집합의 크기가 1인 경우 부터 차례로 늘려가면서 처리한다. K개인 빈도 높은 항목을 구했다면 그 다음에는 K+1인 항목의 잡합을 계산한다. 그래서 총 최대 개수를 가진 빈도항목까지 반복한다. 그러므로 항목이 많아지는 경우 시간이 오래걸릴 수 밖에 없다.

CAFE

4. R 수업

8장. Apriori 알고리즘 설명

댓글

카페 검색