whisler@naver.com

잘 정리된 문서입니다.

출처 : http://inobae.blog.me/90004955169

아이템에 있는 것들로 만들 수 있는 모든 리스트들을 이용해 Association Rule을 테스트하는 알고리즘에 대한 얘기가 바로 Apriori Algorithm이다.

이 아이템에 있는 것들로 만들 수 있는 모든 리스트들을 이용한다는 것에서 각 후보들간에 Dependency가 존재하게 된다. 하지만 최초 시드로 부터 한 단계씩 리스트의 길이를 늘려간다면 이 Dependency 문제는 큰 문제가 아닐 거라고 생각한다.(실제 구현해 보지 않은 시점이기에 검증된 생각은 아니다.)

앞서 Association Rule에 대해서 살펴 보았는데,
이 척도를 이용해 서로 관계가 깊은 것들을 알아낼 수 있다면 뭔가 지식을 구축하는데 있어 큰 도움이 되지 않을까.
모든 Association Rule을 검사하는데는 2가지 기준이 되는 문턱값이 존재한다.
 하나는 통계적으로 일어날 법한 일이여야 하기 때문에 후보가 되는 item set들이 임의의 빈도수 이상 출현해야 한다는 것이다.(support라는 개념을 앞에서 설명했지만, 논문에는 빈도수가 아닌 support라 표현되어 있다.)
이 임의의 빈도수는 작업 목적에 따라 다를 수 밖에 없는데, 스팸 키워드를 추출할때의 이 빈도수 기준은 정상문서에서 유용한 키워드를 추출하는 작업에서의 빈도수보다 낮아 질 수 밖에 없다. 정상문서가 스팸 문서보다 더 많기 때문이다.(물론 경우에 따라서는 아닐수도 있지만, 워낙 스팸이 많아서...) 그리고 임의의 빈도수 기준에 딱 걸쳐있는 가장 아슬아슬한 item set을 large item set이라고 부른다. 그 외의 것들은 모두 small item set이라고 부른다.
 둘째는 Association Rule은 large item set들을 이용해 만든다. 그것은 곧 경계에 있는 것들을 테스트해서 경계를 확장하는 것이라고 설명할 수 있다. 예를 들면, ABCD와 AB가 large itemset 이라면 AB=>CD 라는 rule을 conf(AB, CD) = support(ABCD)/support(AB) 가 정해진 값 이상인지 확인 해서 rule을 테스트한다. 이때 ABCD와 AB가 mininum support하기 때문에 support 조건을 통과한다.

알고리즘은 크게 다음의 순서로 진행된다.
1. 각각의 item의 support(빈도수)를 구한다. 그리고 그 중 정해진 값을 넘는 것을 seed item set으로 한다.
2. seed item set을 이용해 새로이 large item set이 될 수 있는 후보군을 만들고 이 후보군의 support가 임계치르르 넘는 값들을 다음 단계의 seed item set으로 확정한다.
3. 2 과정이 새로운 item set이 생기지 않을 때까지 반복된다.

앞으로 설명할 알고리즘에서 사용되는 용어들은 다음과 같다.(논문 그림 캡쳐)

Apriori 알고리즘은 다음과 같다.


이 알고리즘은 다음과 같은 게임을 하는 것이라고 생각할 수 있다.
나는 나랑 절친한 친구들의 그룹을 만들고 싶다. 이때 내 친구의 절친도 내게 절친이 될 수 있다고 생각했다. 다음 조건을 만족한다면... '절친하다'의 기준은 내가 친구들이라고 생각하는 후보들이 주고 받은 전체 메일 중 참조를 포함해 적어도 5번 이상 편지를 주고 받은 기록이 있어야 한다고 정했다.(각각의 메일이 하나의 Transaction이 될 것이다.) 음.. 5번 이상 출현한 친구들을 보니 다음과 같았다.
{기남}. {승보}, {재춘}, {현호}, {경부}, {신환}
L1 = { {경부}, {기남}, {승보}, {신환}, {재춘}, {현호} } (가나다 순으로 정렬되었다.)
그 다음은 이 바운더리를 확장하는 것이다. 
다음 후보가 생기지 않을때까지 같은 작업을 반복하는데, 현재 후보군은 size가 1이니까 2부터 반복된다.
C2 = apiori-gen(L1); // 이것이 사이즈가 2인 새로운 후보 집합을 만드는 작업인데...
apriori-gen 은 다음과 같다. 


위 알고리즘에 따라서 사이즈가 2인 C2를 구하면,
k가 2인 단계에서, p.item1 != q.item1이며, p.item1 < q.item1 인 것들만 남게 된다.
 C2 = { {경부, 기남}, {경부, 승보}, ..., {재춘, 현호} 가 될 것이다.
그리고 이 새로운 후보 set이 유효한지 검사를 하는데, 검사 내용은 기존 set과 단 하나의 item만 달라야 한다는 것이다. 즉, 기존 모든 set이 이 새로운 후보에 포함되어야 한다.

이렇게 새로운 후보셋을 구한뒤에 서로 주고 받은 모든 메일에 대해서 하나씩 검토하게 되며(transaction), 한 메일에 새로운 후보가 포함된 메일들을 통해서 사이즈가 2인 모든 Subset을 만들고, 카운팅한다. 이 카운팅 값이 minsup이상인 얘들을 L2로 확정한다.

이것이 직관적이고 쉬운 Apriori Algorithm이다.

출처 : http://oopsoopskeke.tistory.com/entry/Apriori-Algorithm