Apriori 알고리즘

Support = 전체집합에서 Item들이 있을 확률. (A,B 모두 있는 경우.)
Confidence = 조건부확률.( A가 일어났을 때, B도 일어날 확률)

minimum support(최소지지도) 를 넘는 경우 빈발항목에 넣음.

minimum confidence를 넘는 경우 연관규칙에 넣음. 

Apriori 알고리즘 소개

연관규칙(Association Rule)의 대표적인 형태의 하나로 데이터 마이닝에서 아직도 사용되는 알고리즘이다.예로 마켓에서 소비자의 구매 패턴을 파악하는데 사용된다. 가령 "우유를 구매한 사람은 어떤 제품을 같이 구매하는가?" 라는 질문에 대한 답을 좀 더 분석적으로 답변을 낼 수 있는 알고리즘이다.

주요 용어

Apriori 알고리즘 설명 때 등장하는 주요 용어에 대한 정리이다.

• 트랜젝션(transaction) : 물건들을 살 때의 물건에 대한 묶음을 1번의 트랜잭션이 발생했다고 할 수 있다. 마트에 가서 구매한 묶음이라고 볼 수도 있다. 여러 명의 누적된 트랜잭션으로 Apriori 알고리즘을 사용하면 물건(아이템)간 연관 관계를 분석해 낼 수 있는 것이다.
• 신뢰도 s (Support) - 상관성(correlation)을 측정하기 위한 지수로 주어진 트랜잭션에서 동시에 구매된 아이템간의 상관관계 빈도 (가령 2%의 지지도는 분석에 사용된 모든 트랜잭션의 2% 중, 우유와 시리얼이 함께 구매한다는 의미)
• 신뢰도 c (Confidence) - 아이템간의 인과 (causality) 관계를 나타내는 것 (가령, 우유를 구매하면, 시리얼를 구매할 지수, 60%의 신뢰도는 우유를 구매한 60% 고객이 시리얼을 함께 구매한다는 것을 의미)

Apriori 연관 규칙 산출 예제

트랜젝션 (transaction) 목록 

Transaction ID	Items
2000	A, B, C
1000	A, C
4000	A, D
5000	B, E, F

위 트랜잭션 ID는 구매한 경우(사건)를 구별하기 위한 ID에 불과하며 가령, 트랜젝션 2000 일 경우, 아이템 A, B, C를 함께 구매한 것을 표현한 것이다.

신뢰도 s (Support)를 산출

위 아이템 셋의 경우에 있어 Min. Support = 50 % 이상, Min Confidence = 50% 이상의 아이템들을 찾아보자. 우선 아이템들에 대한 신뢰도 s(상관도?)를 구해보자.

Item set	Support (신뢰도 s)	발생 횟수/전체 횟수
{A}	75%	= 3/4
{B}	50%	= 2/4
{C}	50%	= 2/4
{A,C}	50%	= 2/4

신뢰도 c (Confidence)를 산출

A=>C (A를 구매하면 C를 구매할 지수) 에 대한 신뢰도 c(Confidence) 는

Item Causality	Confidence (신뢰도 c)	산출
A=>C	66.6%	= support({A,C})/support({A})

그러므로 Min. Support = 50 % 이상, Min Confidence = 50% 이상의 아이템은 A=>C ({A,C} 신뢰도 s 50%, A=>C 신뢰도 c는 66.6%) 라는 결과가 도출된다.

유동하 (mozala@hufs.ac.kr) Apriori 알고리즘
연관 규칙을 찾아주는 알고리즘 중에서 가장 먼저 개발됐고 또 가장 많이 쓰이는 알고리즘은 Apriori 알고리즘입니다. 이 알고리즘은 두 가지 단계로 구성됩니다. 우선 첫 번째 단계에서는 최소 지지도 설정 값에 따라 빈도수가 높은 항목의 집합들을 찾아내고 그 다음 단계에서는 이들 집합들로부터 신뢰도 설정 값을 모두 뽑아냅니다.
Apriori 알고리즘에서 사용하는 중요한 법칙은 빈도수가 높은 항목 집합의 모든 부분 집합도 다 빈도수가 높다는 사실입니다. 예를 들어 데이터에 {빵, 버터, 우유}가 최소 지지도에 의해 빈도수가 높다면 당연히 {빵, 버터}만을 봐도 빈도수가 높고, {버터, 우유}을 봐도 빈도수가 높습니다. 다시 말해 어떤 집합이 주어졌을 때 새로운 항목을 더해주면 지지도는 절대로 전보다 증가할 수 없습니다.
Apriori 알고리즘은 우선 사이즈 한 개의 빈도수가 높은 항목들을 먼저 구하고 그 다음에 이것들을 이용해 사이즈가 두 개인 빈도수가 높은 항목들의 집합을 구하는 방식으로 한 사이즈씩 차례로 수행합니다. 그렇기 때문에 데이터에 있는 사이즈가 가장 큰 빈도 높은 항목 집합의 크기가 k라면 대략적으로 데이터를 k번 스캔하게 됩니다(여기서 집합의 사이즈란 그 집합에 들어 있는 원소 개수를 말합니다). 사이즈가 k인 빈도 높은 항목들을 지금 막 구한 단계라고 합시다. 이 때 이들을 이용해 사이즈가 k+1인 후보 항목들의 집합들을 먼저 구합니다.
예를 들어 <그림 1>에서 사이즈가 2인 빈번 아이템 항목 L2에서 {B, C}와 {B, E}를 이용해 {B, C, E}라는 사이즈가 3인 후보 항목들의 집합이 만들어집니다. 이 때 이 집합의 원소로 구성된 사이즈가 2인 모든 부분 집합이 사이즈 2인 빈도 높은 항목 집합들에 다 들어있는지 체크하고 만일 하나라도 없다면 후보에서 탈락시킵니다. 여기서 {B, C, E}는 그것의 부분집합 {B, C}, {B, E}, {C, E}가 모두 빈도 높은 항목 집합들에 들어 있으므로 후보 집합에 해당됩니다. 즉 {A, B, C}나 {A, C, E}가 후보 항목에 들어갈 수 없는 이유로 {A, C}나 {A, E}가 빈도 높은 항목 집합에 들어 있지 않기 때문입니다. 이런 식으로 후보들을 만든 후에는 실제 데이터를 스캔해 후보들을 카운트하고 그런 후에 지지도를 만족하는 것들만 뽑아내 사이즈가 3인 후보 항목 집합을 만들어냅니다. 그 다음에는 다시 이들을 이용해 사이즈가 4인 후보들을 만들어 내고 더 이상 후보 집합을 만들지 못할 때까지 같은 과정을 반복합니다.


<그림 1> Apriori 알고리즘의 수행 과정


[ 연관 규칙 알고리즘의 성능 비교 ]   
연관 규칙 알고리즘의 성능 비교
연관 규칙은 항목 집합으로 표현된 트랜잭션에서 각 항목간의 연관성을 반영하는 규칙으로 Apriori 알고리즘이 처음 소개된 후, 데이터베이스 검색 횟수를 줄이거나 주기억 장치의 한계를 없애는 등의 발전된 알고리즘들이 발표되어 왔습니다. Apriori를 개선한 알고리즘으로는 AprioriTID, AprioriHybrid, DHP 등이 있으며 대부분 Apriori 알고리즘과의 비교를 통해서 진화된 알고리즘의 성능을 밝히고 있습니다. 그러나 연관 규칙 알고리즘의 성능 비교 측면에서 보면, 알고리즘마다 서로 다른 실험 환경에서 수행되었기 때문에 그들을 하나의 기준으로 비교한다는 것은 불가능합니다.
참조:
http://www.gurugail.com/pmwiki.php?n=Apriori.Lifegear
http://adeuxist.egloos.com/971440